Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
\((k,n-k)\)-Max-Cut: An \({\mathcal O}^*(2^p)\)-Time Algorithm and a Polynomial Kernel
verfasst von : Saket Saurabh, Meirav Zehavi
Erschienen in: LATIN 2016: Theoretical Informatics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Max-Cut is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph \(G=(V,E)\) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if \(p\le |E|/2\), the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called \((k,n-k)\)-Max-Cut, restricts the size of the subset A to be exactly k. For the \((k,n-k)\)-Max-Cut problem, we obtain an \({\mathcal O}^*(2^p)\)-time algorithm, improving upon the previous best \({\mathcal O}^*(4^{p+o(p)})\)-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G.