Polynomial time algorithm solves path cover reconfiguration on trees

A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding

Data Structures and AlgorithmsDiscrete Mathematics

Summary

The paper studies a puzzle where you want to rearrange tokens placed on a tree’s vertices so that certain conditions are always met. Specifically, these tokens must always cover every path of a certain length (k) in the tree, and tokens can only slide to adjacent empty vertices. The authors found a way to decide efficiently if one arrangement of tokens can be turned into another using these slides, even when the path length k is part of the input. Their method breaks the problem down into simpler parts of the tree and identifies tokens that must stay fixed, allowing them to solve the problem in polynomial time.

What this means in practice

  • For network schedulers: Decide efficiently if configurations covering critical communication paths in tree-based networks can be reconfigured without loss of coverage during updates.
  • For robotic path planners: Ensure guaranteed coverage of critical paths in hierarchical environments while moving agents without losing coverage, by planning token-like transitions.

A theory result. No direct application yet.

Authors

Duc A. Hoang

Abstract

A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.
View PDFOpen arXiv