Get all the updates for this publication

Conferences

Circumventing Connectivity for KernelizationPublished in Springer Science and Business Media Deutschland GmbH

2021

Volume: 12701 LNCS

Pages: 300 - 313

Classical vertex subset problems demanding connectivity are of the following form: given an input graph G on n vertices and an integer k, find a set S of at most k vertices that satisfies a property and G[S] is connected. In this paper, we initiate a systematic study of such problems under a specific connectivity constraint, from the viewpoint of Kernelization (Parameterized) Complexity. The specific form that we study does not demand that G[S] is connected but rather G[S] has a closed walk containing all the vertices in S. In particular, we study Closed Walk-Subgraph Vertex Cover (CW-SVC, in short), where given a graph G, a set X⊆ E(G), and an integer k; the goal is to find a set of vertices S that hits all the edges in X and can be traversed by a closed walk of length at most k in G. When X is E(G), this corresponds to Closed Walk-Vertex Cover (CW-VC, in short). One can similarly define these variants for Feedback Vertex Set, namely Closed Walk-Subgraph Feedback Vertex Set (CW-SFVS, in short) and Closed Walk-Feedback Vertex Set (CW-FVS, in short). Our results are as follows: CW-VC and CW-SVC both admit a polynomial kernel, in contrast to Connected Vertex Cover that does not admit a polynomial kernel unless NP⊆ coNP/ poly.CW-FVS admits a polynomial kernel. On the other hand CW-SFVS does not admit even a polynomial Turing kernel unless the polynomial-time hierarchy collapses. We complement our kernelization algorithms by designing single-exponential FPT algorithms – 2 O ( k )nO ( 1 ) – for all the problems mentioned above. © 2021, Springer Nature Switzerland AG.

Topics: Feedback vertex set (65)%65% related to the paper, Kernelization (63)%63% related to the paper, Vertex cover (60)%60% related to the paper, Vertex (geometry) (60)%60% related to the paper and Cover (topology) (58)%58% related to the paper

View more info for "Circumventing Connectivity for Kernelization"

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Data powered by TypesetSpringer Science and Business Media Deutschland GmbH |

ISSN | 03029743 |