TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k\ge 4$

Abstract

A $k$-path vertex cover ($k$-PVC) of a graph $G$ is a vertex subset $I$ such that each path on $k$ vertices in $G$ contains at least one member of $I$. Imagine that a token is placed on each vertex of a $k$-PVC. Given two $k$-PVCs $I,J$ of a graph $G$, the $k$-Path Vertex Cover Reconfiguration ($k$-PVCR) under Token Sliding ($\mathsf{TS}$) problem asks if there is a sequence of $k$-PVCs between $I$ and $J$ where each intermediate member is obtained from its predecessor by sliding a token from some vertex to one of its unoccupied neighbors. This problem is known to be $\mathtt{PSPACE}$-complete even for planar graphs of maximum degree $3$ and bounded treewidth and can be solved in polynomial time for paths and cycles. Its complexity for trees remains unknown. In this paper, as a first step toward answering this question, for $k\ge 4$, we present a polynomial-time algorithm that solves $k$-PVCR under $\mathsf{TS}$ for caterpillars (i.e., trees formed by attaching leaves to a path).

arXiv comment12 pages, 3 figures, minor revision, update title and abstract

References in corpus (2)

• Minimum k-path vertex cover
• TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k\ge 4$

Cited by in corpus (1)

• TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k\ge 4$