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

DOI10.20429/TAG.2023.10108zbMATH Open1518.05155arXiv2203.11667OpenAlexW4367164110MaRDI QIDQ6174607FDOQ6174607

Authors: Duc A. Hoang 

Publication date: 14 July 2023

Published in: Theory and Applications of Graphs (Search for Journal in Brave)

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 ($mathsfTS$) 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 $mathttPSPACE$-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 $kgeq4$, we present a polynomial-time algorithm that solves $k$-PVCR under $mathsfTS$ for caterpillars (i.e., trees formed by attaching leaves to a path).

Full work available at URL: https://arxiv.org/abs/2203.11667

Recommendations

• On the weighted \(k\)-path vertex cover problem
• Reconfiguration of vertex covers in a graph
• Minimum \(k\)-path vertex cover
• Vertex Cover Reconfiguration and Beyond
• Complexity of the maximum \(k\)-path vertex cover problem

zbMATH Keywords

\(k\)-path vertex cover reconfigurationtoken sliding problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (1)

• Reconfiguration of vertex covers in a graph

This page was built for publication: TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174607)