A vertex subset $I$ of a graph $G$ is called a $k$-path vertex cover if every path on $k$ vertices in $G$ contains at least one vertex from $I$. The textsc{$k$-Path Vertex Cover Reconfiguration ($k$-PVCR)} problem asks if one can transform one $k$-path vertex cover into another via a sequence of $k$-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of textsc{$k$-PVCR} from the viewpoint of graph classes under the well-known reconfiguration rules: $mathsf{TS}$, $mathsf{TJ}$, and $mathsf{TAR}$. The problem for $k=2$, known as the textsc{Vertex Cover Reconfiguration (VCR)} problem, has been well-studied in the literature. We show that certain known hardness results for textsc{VCR} on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for textsc{$k$-PVCR}. In particular, we prove a complexity dichotomy for textsc{$k$-PVCR} on general graphs: on those whose maximum degree is $3$ (and even planar), the problem is $mathtt{PSPACE}$-complete, while on those whose maximum degree is $2$ (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for textsc{$k$-PVCR} on trees under each of $mathsf{TJ}$ and $mathsf{TAR}$. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given $k$-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.
Download