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

DOI10.20429/TAG.2023.10108MaRDI QIDQ6174607zbMATH OpenOpenAlexFDO

Authors Duc A. Hoang

Publication date 14 July 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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).

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

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)