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\).