Group for Research in Decision Analysis

Algorithms and computational complexity on the $$P_k$$-hitting set problem

Eglantine Camby

The $$P_k$$-hitting set problem consists in removing a minimum number $$\psi_k(G)$$ of vertices of a given graph $$G$$ so that the resulting graph does not contain path $$P_k$$ on $$k$$ vertices as a subgraph. For instance, the corresponding vertex set for $$k=2$$ is a vertex cover. Cubic graphs received more attention for this problem in the last decade, especially for approximation algorithms.

In the present paper, we prove that the $$P_k$$-hitting set problem is NP-complete in the class of cubic graphs, for any fixed constant $$k \geqslant 4$$. Then, we design for cubic graphs a polynomial-time algorithm which is a $$1.25$$-approximation for the $$P_3$$-hitting set problem, better than the best-known ($$1.57$$-approximation algorithm), and a $$2$$-approximation for the $$P_4$$-hitting set problem. Compared to other approximation algorithms, one of its force is its simplicity. We conjecture that for any cubic graph $$G$$ and any constant $$k \geqslant 5$$, $$\frac{|V(G)|}{k} \leqslant \psi_k(G)$$. Moreover, if true, this lower bound is achieved by a family of graphs with arbitrary large value of~$$\psi_k$$. As a consequence of Bollobas, Robinson and Wormald's result~\cite{Bollobas,RW92,RW94}, the conjecture is true for almost all cubic graphs. So our algorithm becomes a $$\frac{k}{2}$$-approximation for the $$P_k$$-hitting set problem for almost all cubic graphs, which is better than other constant approximation ratios. Finally, we design, for subcubic graphs, a polynomial-time algorithm which transforms any minimum $$P_k$$-hitting set into another one with the following property: itself and its complement are $$P_k$$-hitting sets. Besides, there does not exist such algorithm if the graph has at least one vertex with degree $$d \geqslant 4$$.

, 15 pages