PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Duc A. Hoang

arXiv:2610.31261v1cs.DScs.DM

TL;DR

Whether two k-PVCs of a tree can be connected by Token Sliding remained open for k≥3. This paper characterizes reachability using rigid tokens and component token counts, then gives a decision algorithm and a construction of slide sequences. The decision algorithm runs in O(kn^2) time, and the paper identifies polynomial-length sequence construction for fixed k≥3 as an open question.

  • Problem

    For every k≥3, the complexity of Token Sliding for k-PVCs on trees remained open.

    Source: §1 · p. 2

  • Method

    The paper characterizes reachability by matching rigid-token sets and component token counts, with sufficiency established by a lemma for covers whose tokens are all movable.

    Source: §1.1 · p. 2

  • Results

    O(kn^2) time decides reachability for every k≥2, and a direct construction returns at most 8n^2 3^ceil(n/2) slides in O(n^10 3^(n/2)) time.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    Reachability on trees has an exact characterization through rigid tokens and token counts in the components remaining after their deletion.

    Source: §1.1 · p. 2

    Finding polynomial-length TS-sequences between reachable k-PVCs of trees remains open for every fixed k≥3.

    Source: §6 · p. 34

Abstract

from arXiv · show

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.

1 Introduction

Earlier work left Token Sliding for k-PVCs on trees open for every k ≥3. This paper gives a polynomial-time decision algorithm and a construction of a slide sequence for every reachable pair.

1.1 Our Results

  • O(kn^2) time decides whether two k-PVCs of a tree are reachable, with k part of the input.Source: §1.1 · p. 2
  • For k=3, the decision algorithm yields an O(n^2)-time algorithm for sliding between dissociation sets of a tree.Source: §1.1 · p. 2
  • Two k-PVCs are reachable exactly when their rigid-token sets match and each component after deleting those vertices has the same token count.Source: §1.1 · p. 2
  • The Key Lemma uses a canonical cover built on properly rooted subtrees, each attached at a root whose removal eliminates its k-vertex path.When the root is occupied, tokens in the rest of that subtree do not interact with the rest of the tree.Source: §1.1 · p. 2
  • A rooted-subtree recurrence computes values used to test candidate-token mobility, enabling the algorithm to identify the rigid tokens.The test uses the minimum token count and the shortest possible longest unoccupied path from a component's boundary vertex.Source: §1.1 · p. 2
  • At most 8n^2 3^ceil(n/2) slides are returned in O(n^10 3^(n/2)) time for every reachable pair.These are upper bounds; the construction need not return exponentially many slides.Source: §1.1 · p. 3

2 Preliminaries

The preliminaries establish notation and foundational properties for later reachability characterization and algorithms, defining properly rooted subtrees and basic token-sliding sequence properties. They also study token-sliding on tree subgraphs, relating boundary projections and token additions or removals to reachability, never-occupied vertices, and rigidity.

2.1 Graph Notation

  • The graph notation defines connected vertex sets and rooted-tree terms, including branches, rooted height, depth, and descendant subtrees.The paper works with finite trees and k ≥ 2.Source: §2.1 · p. 3

2.2 Token Sliding on k-PVCs

  • A k-PVC meets every path on k vertices, and token sliding moves one token along an edge to an unoccupied vertex while preserving the cover.A TS-sequence is a sequence of such covers; reachable covers have the same number of tokens.Source: §2.2 · pp. 3–4
  • Rigid tokens occupy every cover in a reachability class, while H marks vertices never occupied; ε records the longest unoccupied path starting at a vertex.For an unoccupied vertex, ε is at most k − 1.Source: §2.2 · p. 4
  • A slide is legal exactly when the two largest unoccupied-path heights at the token’s other neighbors sum to at most k − 2.The heights are measured along paths starting at those neighbors and avoiding the token’s vertex.Source: §2.2 · p. 5

2.3 Properly Rooted Subtrees

  • A properly rooted subtree contains a k-vertex path, but deleting its root leaves none, so every such path passes through the root.Consequently, every subset containing the root is a k-PVC of that subtree.Source: §2.3 · p. 5

2.4 Basic Properties of TS-Sequences

  • With rigid vertices fixed, configurations reconfigure independently within each component remaining after their deletion.More generally, fixing occupied vertices lets reconfigurations on a union of those components extend to the whole tree and lets whole-tree sequences restrict back to them.Source: §2.4 · p. 6
  • If a connected subtree has no k-vertex path, or has fewer than k unoccupied vertices, every t-element subset is a k-PVC and all such subsets are mutually reachable.Adding a token at a fixed vertex preserves reachability when that vertex is unoccupied at both endpoints.Source: §2.4 · p. 7
  • A projected sequence with slides and boundary additions or removals, whose token count never exceeds its initial count, can be replaced by slides and removals at the boundary.This permits such projected sequences to be handled using only slides and removals.Source: §2.4 · p. 8
  • Slides and removals from a reachable cover preserve a containing reachable cover, and vertices never occupied initially remain never occupied.In particular, if Y is reached from Z by slides and removals at r, then Y is contained in a member of [Z]W and HW(Z) ⊆ HW(Y).Source: §2.4 · p. 8
  • The minimum possible ε at r is zero when r is not never occupied; otherwise it equals the longest path length from r within its component of never-occupied vertices.A reachable cover attains the minimum, with the component containing r contained in HW(S) when r is unoccupied.Source: §2.4 · p. 8
  • A rigid token adjacent to a vertex without a rigid token lies on a k-vertex path whose other vertices are all never occupied.Such a path exists whenever the cover is not the whole subtree and has at least one rigid token.Source: §2.4 · pp. 8–9
  • If a cover has no rigid tokens, any reachable restriction attaining the maximum token count on a non-full side of an edge also has no rigid tokens there.The maximum is taken over restrictions of covers reachable in the whole subtree.Source: §2.4 · p. 9
  • For a cover with no rigid tokens, the reachable-cover class after adding a token at a vertex is independent of the chosen reachable cover omitting that vertex; the enlarged cover has no rigid tokens if it is not full.The size condition is |S| + 1 < |W|.Source: §2.4 · p. 9
  • Restricting a cover with no rigid tokens to one side of an edge leaves that side’s boundary endpoint non-rigid unless the side is full.The other tokens on that side need not be movable.Source: §2.4 · p. 9

3 Characterization of Reachability

This section characterizes reachability among tree k-PVCs using rigid-token sets and token counts in the components left after those tokens are fixed. It develops the characterization through properly rooted subtree normalization and the Key Lemma’s movable-token case, and gives a corollary on changes as tokens are added or removed.

3.1 Unoccupied Vertices in a Properly Rooted Subtree

  • For a properly rooted subtree, γ(U) is the maximum number of unoccupied vertices in a k-PVC omitting its root; prescribed sets C_h attain every h from 0 to γ(U).For h < γ(U), removing the root token from C_h still leaves a k-PVC.Source: §3.1 · p. 10
  • With the rest of the tree fixed, a first slide of the root token into the subtree is possible exactly when Equation (3) holds.The same condition applies to the properly rooted subtree alone, with exterior value x = 0.Source: §3.1 · p. 10
  • The possible sizes of k-PVCs of T[U] with all tokens movable are exactly d, d + 1, …, |U| − 1.For each 1 ≤ h ≤ γ(U), C_h has no rigid tokens.Source: §3.1 · p. 13
  • Every reachable configuration with no rigid tokens can be normalized to restriction C_h* on U, where h* = min(γ(U), q − 1), while the remaining tokens are movable.Here q is the number of unoccupied vertices in W; every such normalized configuration permits sequences in W′ to extend with C_h* fixed.Source: §3.1 · p. 13

3.2 The Key Lemma

  • The proof deletes properly rooted subtrees; the safe degree-1 vertex deletion used by Demaine et al. does not suffice for this argument already when k = 3.Source: §3.2 · p. 14
  • In the k = 3 path example, deleting either safe degree-1 vertex with its neighbor fails to leave a movable-token remainder, whereas the properly rooted subtree {a0, a1, a2} with root a2 works.On the remaining path a3a4a5a6, the one-token covers {a4} and {a5} are reachable from one another.Source: §3.2 · p. 14
  • For equal-size k-PVCs with all tokens movable, the Key Lemma guarantees reachability by normalizing both on the same properly rooted subtree and recursively joining their complements.The preceding theorem replaces part of each cover with the same prescribed set, leaving a smaller tree on which all tokens are movable.Source: §3.2 · pp. 14–15

3.3 The Characterization

  • Two k-PVCs of a tree are reachable exactly when their rigid-token sets agree and their token counts agree in every component remaining after the rigid vertices are deleted.For example, Figure 4 shows counts (2, 0, 0, 1) for two reachable covers and (3, 0, 0, 0) for an unreachable cover with the same rigid set.Source: §3.3 · p. 15, Figure 4 · p. 15
  • For k = 2, Theorem 3.10 gives the same reachability relation as Demaine et al., although the two characterizations delete different vertex sets.The rigid set consists of the neighbors of the independent-set rigid vertices and certain components containing no independent-set vertex.Source: §3.3 · p. 16
  • For every nonempty connected P, the feasible counts F(P) form a nonempty integer interval ending at |P| − 1, with one common reachable set Ω(P, t) for each feasible count.Adding a token at any fixed vertex successively yields the sets at higher counts and then P; between counts t and t′, exactly t′ − t removals at that vertex suffice, with slides.Source: §3.3 · p. 16

4 Algorithm for Trees

Section 4 develops rooted-subtree parameters to identify rigid-token vertices, then uses them to compute rigid tokens and decide reachability by comparing the endpoints’ rigid sets and component token counts in O(kn²) time.

4 Algorithm for Trees

  • Reachability reduces to computing rigid-token vertices, and Algorithm 1 removes vertices from a candidate set for rigid tokens.Source: §4 · p. 16

4.1 A Recurrence for Rooted Subtrees

  • A rooted-subtree recurrence defines c(P, r) and τ(P, r), selecting the largest feasible collection of positive child values whose two largest sum to at most k − 2.For k = 2, c(P, r) equals the independence number of T[P] − r, and τ(P, r) indicates whether r belongs to every maximum independent set; on subtrees with no k-vertex path, τ is the rooted height and c is zero.Source: §4.1 · pp. 16–18

4.2 Removing Tokens at the Root

  • From the full vertex set, every k-PVC reached by slides and removals at r has at least c(P, r) tokens; at that minimum, ε is at least τ(P, r), and both bounds are attainable.Source: §4.2 · p. 18

4.3 The Minimum of ε

  • For every integer k ≥ 2, nonempty connected P ⊆ V(T), and k-PVC S of T[P] with R_P(S) = ∅, H_P(S) = {r ∈ P : |S| = c(P, r) and τ(P, r) > 0}.Source: §4.3 · p. 21

4.4 Computing the Rigid Tokens

  • Algorithm 1 repeatedly removes a candidate whose token can slide while other candidates stay occupied, returning the exact rigid and never-occupied sets within |S| + 1 rounds.The input cover S remains fixed as the candidate set shrinks.Source: §4.4 · pp. 21–23
  • Every valid removal order returns the same rigid and never-occupied sets.The invariant is preserved for each pair satisfying the slide condition, and termination depends only on the absence of another such pair.Source: §4.4 · p. 23

4.5 Running Time and Proof of the Decision Theorem

  • Two-pass subtree computations take O(k|P|), and linear-time slide-condition scans make each round O(kn), yielding O(kn^2) overall.There are at most n + 1 rounds for each input k-PVC.Source: §4.5 · p. 24
  • The reachability test accepts exactly when the endpoint covers have identical rigid sets and equal token counts in every component after rigid-set deletion.If the rigid sets differ, the algorithm rejects.Source: §4.5 · p. 24

5 Finding a TS-Sequence

The section develops a recursive construction of token-sliding sequences using elementary routing, prescribed targets on properly rooted subtrees, and recursion on smaller subtrees, fixing common rigid tokens or aligning endpoint restrictions before recursing. It returns sequences with explicit length and running-time bounds for reachable pairs, and, with cover checks and a decision test, rejects invalid or unreachable pairs.

5.1 Elementary Procedures and Prescribed Targets

  • Exchange legally swaps an occupied and unoccupied vertex in a branch using exactly their distance in slides, while every prefix fixes the configuration outside that branch.The lemma assumes the properly rooted subtree’s root is occupied and the exchanged vertices lie in one branch.Source: §5.1 · p. 25
  • Normalize routes a configuration to the prescribed set Ch in at most 2a^2 slides, preserving the exterior throughout.It prepares occupied branch roots, transfers tokens between branches until prescribed counts are met, then routes each branch to its target restriction.Source: §5.1 · pp. 25–26
  • Lemma 5.3 constructs in polynomial time a k-PVC with t movable tokens that either leaves r unoccupied or minimizes ε_P(Z, r).The input condition is that some k-PVC on the connected set P already has t tokens, all movable.Source: §5.1 · p. 27

5.2 The Recursive Construction

  • ConnectPair fixes the common rigid set; with no rigid tokens, it assigns both endpoints the same prescribed set on a properly rooted subtree and recurses on the remaining restrictions.Its one-token base case moves the token along the path between endpoint positions.Source: §5.2 · p. 28
  • Each recursive preparation makes at most one smaller call to reach a target that leaves r unoccupied or minimizes ε_Q at r.The call is omitted when the current restriction already equals the chosen target.Source: §5.2 · p. 28
  • Under the recursive-call hypothesis, Settle returns a reachable endpoint whose restriction to U is C_min(γ(U), |P − S| − 1), with every token in W movable.This is the stated guarantee for a k-PVC with no rigid token on the properly rooted side U.Source: §5.2 · p. 29
  • For every integer k ≥2, the algorithm returns a TS-sequence for each reachable pair, and its wrapper rejects precisely invalid or unreachable pairs.The recursion combines smaller component sequences for rigid-token splits; otherwise it settles both endpoints to the same prescribed restriction and connects their remaining restrictions with a smaller pair call.Source: §5.2 · pp. 30–31

5.3 The Length of the Output

  • The returned sequence has length at most 8n^2 3^⌈n/2⌉ for every reachable pair on an n-vertex tree.For a properly rooted side of order a, each settling stage uses at most γ(U) smaller pair calls and at most ℓ(a) local slides; the full-list bound follows by induction.Source: §5.3 · p. 32

5.4 Running Time

  • The algorithm runs in O(n^10 3^(n/2)) time, after returning a sequence of length at most 8n^2 3^⌈n/2⌉.The stated analysis counts arithmetic operations, not bit complexity, and does not claim a matching lower bound on the output length or on shortest TS-sequences.Source: §5.4 · pp. 33–34

6 Concluding Remarks

The paper gives an O(kn^2)-time decision algorithm for k-PVC Token Sliding on trees and a direct recursive construction of TS-sequences for reachable pairs. Whether polynomial-length sequences can be found in polynomial time for every fixed k ≥3 remains open.

6 Concluding Remarks

  • O(kn^2) time decides reachability, and the direct construction returns a TS-sequence of at most 8n^2 3^⌈n/2⌉ slides in O(n^10 3^{n/2}) time.The decision algorithm uses rigid-token vertices and token counts in the components remaining after their deletion.Source: §6 · p. 34
  • Polynomial-time construction of polynomial-length TS-sequences remains open for reachable k-PVCs of trees for every fixed k ≥3.Source: §6 · p. 34
  • For k = 2, sequences of length O(n^2) can be found in O(n^2) time, but the direct construction here does not recover that quadratic guarantee.Whether O(n^2) slides suffice for every fixed k ≥3 and whether the decision bound can be improved to linear time for each fixed k ≥3 are also open.Source: §6 · p. 34

AI Declaration

The authors used ChatGPT 6 Pro and Claude Fable 5.1 to assist with mathematical arguments and drafting, while taking full responsibility for the paper.

AI Declaration

  • ChatGPT 6 Pro and Claude Fable 5.1 assisted with developing and reviewing mathematical arguments and drafting and revising the paper; the author takes full responsibility for its correctness and content.Source: AI Declaration · p. 34
Loading 2610.31261v1…