Revisiting connected vertex cover: FPT algorithms and lossy kernels

DOI10.1007/s00224-017-9837-yzbMath1430.68225arXiv1711.07872OpenAlexW2949267003MaRDI QIDQ2322693

Diptapriyo Majumdar, R. Krithika, 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 complexityW-hardnessconnected vertex coverstructural parameterizationlossy kernelization

Mathematics Subject Classification ID

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

Related Items (6)

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

Cites Work

• Unnamed Item
• A fast branching algorithm for cluster vertex deletion
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Data reduction for graph coloring problems
• Exact exponential algorithms.
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Some APX-completeness results for cubic graphs
• Algorithmic graph theory and perfect graphs
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Vertex Cover: Further Observations and Further Improvements
• Deterministic Parameterized Connected Vertex Cover
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• Kernelization Lower Bounds Through Colors and IDs
• Faster Parameterized Algorithms Using Linear Programming
• On Problems as Hard as CNF-SAT
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• Parameterized Algorithms

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