Downloads: 65
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
arXiv.2203.11667.pdf | 439.68 kB | Adobe PDF | View/Open |
Title: | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k geq 4$ |
Authors: | HOANG, Duc Anh |
Keywords: | Reconfiguration problems Polynomial-time algorithms $k$-Path vertex covers Caterpillars Token sliding |
Issue Date: | 22-Mar-2022 |
Start page: | 1 |
End page: | 12 |
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, for $k geq 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). |
Rights: | This paper is made available under the CC BY-SA 4.0 license. |
URI: | http://hdl.handle.net/2433/277667 |
DOI(Published Version): | 10.48550/arXiv.2203.11667 |
Appears in Collections: | Preprint |

This item is licensed under a Creative Commons License