论文标题
$ k $ - path顶点的ts-reconfiguration在卡特彼勒（Caterpillars）覆盖$ k \ geq 4 $
TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$
论文作者
论文摘要
图$ g $的$ k $ - path顶点封面（$ k $ -pvc）是顶点子集$ i $，因此$ g $ in $ g $的每条路径至少包含$ i $的一个成员。想象一下，将一个令牌放在$ K $ -PVC的每个顶点上。给定了两个$ k $ -pvcs $ i，图$ g $的j $，$ k $ -path顶点封面重新配置（$ k $ -pvcr）在令牌滑动下（$ \ m athsf {ts} $）问题问是否有一个$ k $ $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i $ i的顺序询问$ i $ i $ i $ i $ i $顶点到其无人居住的邻居之一。已知这个问题是$ \ mathtt {pspace} $ - 即使对于最高度$ 3 $的平面图和有界的树宽的平面图，也可以在多项式时间内解决路径和周期。树木的复杂性仍然未知。在本文中，作为回答这个问题的第一步，对于$ k \ geq 4 $，我们提出了一种多项式时间算法，该算法在$ \ mathsf {ts} $下求解$ k $ -pvcr for caterpillars（即，通过将叶子连接到路径上形成的树木）。
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, as a first step toward answering this question, 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).
