Improved approximation algorithms for path vertex covers in regular graphs

Given a simple graph $G=(V,E)$ and a constant integer $k\ge 2$, the $k$-path vertex cover problem ({\sc P$k$VC}) asks for a minimum subset $F \subseteq V$ofverticessuchthattheinducedsubgraph$G[V - F]$ does not contain any path of order $k$. When $k=2$, this turns out to be the classic vertex cover ({\sc VC}) problem, which admits a $\left(2 - {\rm \Theta}\left(\frac 1{\log|V|}\right)\right)$-approximation. The general {\sc P$k$VC} admits a trivial $k$-approximation; when $k=3$ and $k=4$, the best known approximation results for {\sc P$3$VC} and {\sc P$4$VC} are a $2$-approximation and a $3$-approximation, respectively. On $d$-regular graphs, the approximation ratios can be reduced to $\min\left{2 - \frac 5{d+3} + \epsilon, 2 - \frac {(2 - o(1))\log\log d}{\log d}\right}$ for {\sc VC} ({\it i.e.}, {\sc P$2$VC}), $2-\frac{1}{d}+\frac{4d-2}{3d\mathrm{\mid }V\mathrm{\mid }}$ for {\sc P$3$VC}, $\frac{\lfloor d\mathrm{/}2\rfloor (2d-2)}{(\lfloor d\mathrm{/}2\rfloor +1)(d-2)}$ for {\sc P$4$VC}, and $\frac{2d-k+2}{d-k+2}$ for {\sc P$k$VC} when $1 \le k-2 < d \le 2(k-2)$. By utilizing an existing algorithm for graph defective coloring, we first present a $\frac {\lfloor d/2\rfloor (2d - k + 2)}{(\lfloor d/2\rfloor + 1) (d - k + 2)}-approximation for {\sc PkVC} ond$-regular graphs when $1\le k-2<d$. This beats all the best known approximation results for {\sc P$k$VC} on $d$-regular graphs for $k\ge 3$, except for {\sc P$4$VC} it ties with the best prior work and in particular they tie at $2$ on cubic graphs and $4$-regular graphs. We then propose a $1.875$-approximation and a $1.852$-approximation for {\sc P$4$VC} on cubic graphs and $4$-regular graphs, respectively. We also present a better approximation algorithm for {\sc P$4$VC} on $d$-regular bipartite graphs.