Back to Search
Start Over
Reconfiguring k-Path Vertex Covers
- Source :
- IEICE Transactions on Information and Systems. (7):1258-1272
- Publication Year :
- 2022
- Publisher :
- Institute of Electronics, Information and Communications Engineers (IEICE), 2022.
-
Abstract
- 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.<br />Comment: 29 pages, 6 figures, to be published in IEICE Trans. Information and Systems
- Subjects :
- FOS: Computer and information sciences
Computer Science - Computational Complexity
computational complexity
Discrete Mathematics (cs.DM)
Computer Science - Data Structures and Algorithms
Data Structures and Algorithms (cs.DS)
combinatorial reconfiguration
Computational Complexity (cs.CC)
k-path vertex cover
polynomial-time algorithms
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
PSPACE-completeness
Subjects
Details
- Language :
- English
- ISSN :
- 09168532
- Issue :
- 7
- Database :
- OpenAIRE
- Journal :
- IEICE Transactions on Information and Systems
- Accession number :
- edsair.doi.dedup.....17786a7d6ba2cc53226b3f6539434b98