On Approximability of Connected Path Vertex Cover

摘要

This paper is concerned with the approximation complexity of the CONNECTED PATH VERTEX COVER problem. The problem is a connected variant of the more basic problem of path vertex cover; in k-PATH VERTEX COVER it is required to compute a minimum vertex set C {is contained in} V in a given undirected graph G = (V, E) such that no path on k vertices remains when all the vertices in C are removed from G. CONNECTED k-PATH VERTEX COVER (k-CPVC) additionally requires C to induce a connected subgraph in G. Previously, k-CPVC in the unweighted case was known approximable within k~2, or within k assuming that the girth of G is at least k, and no approximation results have been reported on the weighted case of general graphs. It will be shown that (1) unweighted k-CPVC is approximable within k without any assumption on graphs, and (2) weighted k-CPVC is as hard to approximate as the weighted set cover is, but approximable within 1.35 ln n + 3 for k ≤ 3.