Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs

摘要

Given a simple graph G=(V,E) and a constant integer k = 2, the k-path vertex cover problem (PkVC) asks for a minimum subset F subset of V of vertices such that the induced subgraph G[V-F]does not contain any path of order k. When k=2, this turns out to be the classic vertex cover (VC) problem, which admits a 1log|V|-approximation. The general PkVC admits a trivial k-approximation; when k=3and k=4, the best known approximation results are a 2-approximation and a 3-approximation, respectively. On d-regular graphs, the approximation ratios can be reduced to min2-5d+3+epsilon,2-(2-o(1))loglogdlogd for VC (i.e. , P2VC), 2-1d+4d-23d|V| for P3VC, Ld/2SIC RIGHT FLOOR(2d-2)(Ld/2SIC RIGHT FLOOR+1)(d-2) for P4VC, and 2d-k+2d-k+2 for PkVC when 1 = k-2d = 2(k-2). By utilizing an existing algorithm for graph defective coloring, we first present a Ld/2SIC RIGHT FLOOR(2d-k+2)(Ld/2SIC RIGHT FLOOR+1)(d-k+2)-approximation for PkVC on d-regular graphs when 1 = k-2d. This beats all the best known approximation results for PkVC on d-regular graphs for k = 3, except for P4VC it ties with the best prior work and in particular they tie at 2 on cubic graphs and 4-regular graphs. We then propose a (1.875+epsilon)-approximation and a 1.852-approximation for P4VC on cubic graphs and 4-regular graphs, respectively. We also present a better approximation algorithm for P4VC on d-regular bipartite graphs.