Complexity and algorithms for the connected vertex cover problem in 4-regular graphs

摘要

In the connected vertex cover (CVC) problem, we are given a connected graph G and required to find a vertex cover set C with minimum cardinality such that the induced subgraph G[C] is connected. In this paper, we restrict our attention to the CVC problem in 4-regular graphs. We proved that the CVC problem is still NP-hard for 4-regular graphs and gave a lower bound for the problem. Moreover, we proposed two approximation algorithms for CVC problem with approximation ratio 32 and 43+O(1n), respectively.