Deterministic parameterized connected vertex cover

2012/02/29 by Marek Cygan, Cygan, Marek · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1202.6642

openalex publication_date 2012/02/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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].

Cited by

• On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems

Related

• A randomized polynomial kernelization for Vertex Cover with a smaller parameter
• p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
• Exact approaches for the Connected Vertex Cover problem
• Connected Vertex Cover for (sP₁+P₅)-Free Graphs
• A faster algorithm for Vertex Cover parameterized by solution size