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