Downloads: 65

Files in This Item:
File Description SizeFormat 
arXiv.2203.11667.pdf439.68 kBAdobe PDFView/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

Show full item record

Export to RefWorks


Export Format: 


This item is licensed under a Creative Commons License Creative Commons