### G-2018-08

# Algorithms and computational complexity on the \(P_k\)-hitting set problem

## BibTeX reference

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

.

Published **February 2018**
,
15 pages

### Document

**G1808.pdf**
(500 KB)