Revisiting connected vertex cover: FPT algorithms and lossy kernels

DOI10.1007/S00224-017-9837-YzbMATH Open1430.68225OpenAlexW2949267003MaRDI QIDQ2322693FDOQ2322693

Authors R. Krithika, Diptapriyo Majumdar, Venkatesh Raman

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.07872

zbMATH Keywords

parameterized complexityconnected vertex coverstructural parameterizationW-hardnesslossy kernelization

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Abstract: The CONNECTED VERTEX COVER problem asks for a vertex cover in a graph that induces a connected subgraph. The problem is known to be fixed-parameter tractable (FPT), and is unlikely to have a polynomial sized kernel (under complexity theoretic assumptions) when parameterized by the solution size. In a recent paper, Lokshtanov et al.[STOC 2017], have shown an $alpha$-approximate kernel for the problem for every $alpha>1$, in the framework of approximate or lossy kernelization. In this work, we exhibit lossy kernels and FPT algorithms for CONNECTED VERTEX COVER for parameters that are more natural and functions of the input, and in some cases, smaller than the solution size. The parameters we consider are the sizes of a split deletion set, clique deletion set, clique cover, cluster deletion set and chordal deletion set.

Recommendations

• On the approximate compressibility of connected vertex cover
• Lossy kernelization
• Towards optimal kernel for connected vertex cover in planar graphs
• Deterministic parameterized connected vertex cover
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A fast branching algorithm for cluster vertex deletion
• A measure and conquer approach for the parameterized bounded degree-one vertex deletion
• Algorithmic graph theory and perfect graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Data reduction for graph coloring problems
• Deterministic parameterized connected vertex cover
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Exact exponential algorithms.
• Faster parameterized algorithms using linear programming
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Lossy kernelization
• On problems as hard as CNF-SAT
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Parameterized algorithms
• Some APX-completeness results for cubic graphs
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Vertex cover: Further observations and further improvements
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms

Cited in

(8)

• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Algorithms and Data Structures
• Parameterized and Exact Computation
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Extension and its price for the connected vertex cover problem
• On the approximate compressibility of connected vertex cover
• Circumventing connectivity for kernelization

This page was built for publication: Revisiting connected vertex cover: FPT algorithms and lossy kernels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322693)