Deterministic parameterized connected vertex cover

DOI10.1007/978-3-642-31155-0_9zbMATH Open1357.05143arXiv1202.6642OpenAlexW89448923MaRDI QIDQ2904546FDOQ2904546

Authors: Marek Cygan 

Publication date: 14 August 2012

Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Abstract: In the Connected Vertex Cover problem we are given an undirected graph G together with an integer k and we are to find a subset of vertices X of size at most k, such that X contains at least one end-point of each edge and moreover X induces a connected subgraph. For this problem we present a deterministic algorithm running in O(2^k n^O(1)) time and polynomial space, improving over previously best O(2.4882^k n^O(1)) deterministic algorithm and O(2^k n^O(1)) randomized algorithm. Furthermore, when usage of exponential space is allowed, we present an O(2^k k(n+m)) time algorithm that solves a more general variant with arbitrary real weights. Finally, we show that in O(2k k(n + m)) time and O(2^k k) space one can count the number of connected vertex covers of size at most k, which can not be improved to O((2 - eps)^k nO(1)) for any eps > 0 under the Strong Exponential Time Hypothesis, as shown by Cygan et al. [CCC'12].

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

Recommendations

• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
• An improved fixed-parameter algorithm for vertex cover
• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (28)

• Connected vertex cover for \((sP_1+P_5)\)-free graphs
• \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
• Graph Layout Problems Parameterized by Vertex Cover
• Connected Vertex Covers in Dense Graphs
• Matroid-constrained vertex cover
• Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Computing connected-\(k\)-subgraph cover with connectivity requirement
• Extension and its price for the connected vertex cover problem
• Enumerate and measure: improving parameter budget management
• On the lossy kernelization for connected treedepth deletion set
• Enumeration and maximum number of minimal connected vertex covers in graphs
• Revisiting connected vertex cover: FPT algorithms and lossy kernels
• On the parameterized complexity of contraction to generalization of trees
• Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
• Parameterized algorithm for eternal vertex cover
• Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Parameterized approximation via fidelity preserving transformations
• Circumventing connectivity for kernelization
• A multivariate approach for weighted FPT algorithms
• Complexity of independency and cliquy trees
• Reoptimization of parameterized problems
• Parameterized complexity of multi-node hubs
• Parameterized measure \& conquer for problems with no small kernels
• On the parameterized complexity of contraction to generalization of trees
• A multivariate framework for weighted FPT algorithms
• Twin-width and polynomial kernels

This page was built for publication: Deterministic parameterized connected vertex cover

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