Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On Cutwidth Parameterized by Vertex Cover
verfasst von : Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized and Exact Computation
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
We study the
Cutwidth
problem, where input is a graph
G
, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for
Cutwidth
with running time
O
(2
k
n
O
(1)
). Here
k
is the size of a minimum vertex cover of the input graph
G
, and
n
is the number of vertices in
G
. Our algorithm gives an
O
(2
n
/2
n
O
(1)
) time algorithm for
Cutwidth
on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for
Cutwidth
on a graph class where the problem remains NP-complete. Additionally, we show that
Cutwidth
parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless
$\ensuremath{\textrm{NP} \subseteq \textrm{coNP}/\textrm{poly}}$
. Our kernelization lower bound contrasts the recent result of Bodlaender et al.[ICALP 2011] that
Treewidth
parameterized by vertex cover does admit a polynomial kernel.