Revisiting connected vertex cover: FPT algorithms and lossy kernels

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

Authors: R. Krithika, Diptapriyo Majumdar, Venkatesh Raman 

Publication date: 5 September 2019

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

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.

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

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

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)

Cites Work

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

Cited In (8)

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