pith. sign in

arxiv: 2402.12705 · v5 · pith:JDRRYYNGnew · submitted 2024-02-20 · 💻 cs.DS · cs.DM

Distance Recoloring

Niranka Banerjee , Christian Engels , Duc A. Hoang This is my paper

Pith reviewed 2026-05-24 03:51 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords distance coloringreconfigurationPSPACE-completeplanar graphsbipartite graphs2-degenerate graphssliding tokens
0
0 comments X

The pith

For every d at least 3, reconfiguring distance-d colorings is PSPACE-complete even on planar bipartite graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Reconfiguration problems determine whether one feasible solution can be transformed into another through a sequence of local moves that preserve feasibility at every step. The paper studies this for distance-d colorings, where vertices at distance at most d must receive distinct colors. It proves that for d greater than or equal to 3 the reconfiguration problem is PSPACE-complete on planar, bipartite, and 2-degenerate graphs. The proof uses a reduction from the sliding tokens problem and employs a linear number of colors in the size of the instance. This shows that the hardness known for ordinary colorings extends to the distance variant on these restricted classes.

Core claim

For every d >= 3, (d,k)-Coloring Reconfiguration is PSPACE-complete even on planar, bipartite, and 2-degenerate graphs, via reduction from Sliding Tokens, with k = k0 + 2 + n(ceil(d/2)-1) where k0 in {3d+3, 3d+6}.

What carries the argument

A reduction from the Sliding Tokens problem that constructs a graph instance for (d,k)-coloring reconfiguration while preserving the existence of reconfiguration sequences.

If this is right

  • The problem remains PSPACE-complete on planar graphs for all d >= 3.
  • The problem remains PSPACE-complete on bipartite graphs for all d >= 3.
  • The problem remains PSPACE-complete on 2-degenerate graphs for all d >= 3.
  • For d=2 the problem is PSPACE-complete on planar and 2-degenerate graphs.
  • The problem can be solved in quadratic time on paths for any d >=2.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique may imply hardness results for other distance-based reconfiguration problems on similar graph classes.
  • On split graphs the complexity depends on d in a way that larger d makes the problem polynomial while smaller d keeps it hard.
  • Polynomial time algorithms on paths suggest that the problem might be tractable on graphs with bounded treewidth or other restricted structures for fixed d.

Load-bearing premise

The explicit reduction from sliding tokens instances to the coloring reconfiguration instances preserves the existence of valid reconfiguration sequences in both directions.

What would settle it

A polynomial-time algorithm for (d,k)-coloring reconfiguration on planar graphs when d is at least 3 would contradict the PSPACE-completeness result.

read the original abstract

Reconfiguration problems ask whether one feasible solution can be transformed into another by a sequence of local moves while maintaining feasibility throughout. For integers $d \geq 1$ and $k \geq d+1$, the Distance Coloring problem asks if a given graph $G$ has a $(d, k)$-coloring, i.e., a coloring of the vertices of $G$ by $k$ colors such that any two vertices within distance $d$ from each other have different colors. For ordinary proper colorings ($d=1$), the $k$-Coloring Reconfiguration problem is polynomial-time solvable for $k\le 3$ [Cereceda, van den Heuvel, and Johnson, J. Graph Theory 67(1):69--82, 2011] but is $\mathsf{PSPACE}$-complete for every fixed $k\ge 4$, even on bipartite graphs [Bonsma and Cereceda, Theor. Comput. Sci. 410(50):5215--5226, 2009]. In this work, we initiate a study of the distance-$d$ analogue, for $d \geq 2$. We show that even for planar, bipartite, and $2$-degenerate graphs, $(d, k)$-Coloring Reconfiguration remains $\mathsf{PSPACE}$-complete for every $d \geq 3$ via a reduction from the well-known Sliding Tokens problem. Our construction uses $k = k_0 + 2 + n(\lceil d/2\rceil-1)$ colors on instances of size $n$, where $k_0\in\{3d+3,3d+6\}$ (depending on the parity of $d$). For $d = 2$, the same reduction scheme can be adapted to show that the problem is $\mathsf{PSPACE}$-complete on planar and $2$-degenerate graphs with same values of $k$. Additionally, on split graphs, there is an interesting dichotomy: the problem is $\mathsf{PSPACE}$-complete when $d = 2$ and $k$ is large but can be solved efficiently when $d \geq 3$ and $k \geq d+1$. For chordal graphs, we show that the problem is $\mathsf{PSPACE}$-complete for even values of $d \geq 2$. Finally, we design a quadratic-time algorithm to solve the problem on paths for any $d \geq 2$ and $k \geq d+1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper initiates the study of (d,k)-Coloring Reconfiguration for d≥2. It proves PSPACE-completeness for every d≥3 (and for d=2 on some classes) on planar, bipartite, and 2-degenerate graphs via an explicit polynomial reduction from Sliding Tokens, using k=k0+2+n(⌈d/2⌉−1) colors with k0∈{3d+3,3d+6}. It also shows a dichotomy on split graphs (PSPACE-complete for d=2 and large k; polynomial for d≥3), PSPACE-completeness on chordal graphs for even d≥2, and a quadratic-time algorithm on paths for any d≥2 and k≥d+1.

Significance. If the reduction is correct, the results substantially extend the known PSPACE-completeness landscape for coloring reconfiguration (previously limited to d=1) to distance-d variants while preserving sparsity restrictions such as planarity and bipartiteness. The explicit gadget construction with parameter-dependent k and the polynomial algorithm on paths are concrete contributions that could serve as templates for other distance-constrained reconfiguration problems.

major comments (1)
  1. [Reduction construction (abstract and main technical section)] The central PSPACE-completeness claim for d≥3 rests on the reduction from Sliding Tokens (stated in the abstract and presumably detailed in the construction section). The load-bearing step is verifying that every valid sequence of (d,k)-colorings in the augmented graph corresponds exactly to a sequence of token slides and vice versa, with no extraneous color transitions permitted by the distance-d constraints on the added vertices/edges. A full case analysis of the gadgets (including how the extra colors and distance-d separation interact with the original tokens) is required to establish this equivalence; without it the hardness does not follow.
minor comments (1)
  1. [Abstract] The abstract states k0∈{3d+3,3d+6} depending on parity of d, but does not indicate which value applies to even vs. odd d; this should be clarified in the construction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and for highlighting the need for explicit verification of the reduction. We address the major comment below and will incorporate the requested details in the revision.

read point-by-point responses

  1. Referee: [Reduction construction (abstract and main technical section)] The central PSPACE-completeness claim for d≥3 rests on the reduction from Sliding Tokens (stated in the abstract and presumably detailed in the construction section). The load-bearing step is verifying that every valid sequence of (d,k)-colorings in the augmented graph corresponds exactly to a sequence of token slides and vice versa, with no extraneous color transitions permitted by the distance-d constraints on the added vertices/edges. A full case analysis of the gadgets (including how the extra colors and distance-d separation interact with the original tokens) is required to establish this equivalence; without it the hardness does not follow.

    Authors: We agree that a complete case analysis is essential to confirm the bidirectional equivalence between valid (d,k)-coloring sequences and token slides. The current manuscript presents the gadget construction and states the key invariants, but does not include an exhaustive enumeration of all possible color transitions on the auxiliary vertices. In the revised version we will add a dedicated subsection that performs this case analysis, covering (i) all ways the extra colors can be assigned without violating distance-d constraints, (ii) why no spurious recoloring moves are possible on the token vertices, and (iii) how the parameter-dependent choice of k interacts with the distance-d separation to enforce the sliding-token rules. revision: yes

Circularity Check

0 steps flagged

No circularity; hardness via explicit external reduction

full rationale

The central PSPACE-completeness claim for (d,k)-Coloring Reconfiguration rests on a direct polynomial reduction from the independently established PSPACE-complete Sliding Tokens problem (cited as external). The construction explicitly defines the target graph class, the color count k = k0 + 2 + n(⌈d/2⌉-1) with k0 in {3d+3,3d+6}, and the claimed equivalence of reconfiguration sequences; none of these steps reduce to a self-definition, a fitted parameter renamed as prediction, or a load-bearing self-citation chain. The source problem and its PSPACE-completeness are external benchmarks, so the derivation chain is self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Hardness claims rest on the assumption that Sliding Tokens remains PSPACE-complete on the source graphs used in the reduction and that the constructed gadgets correctly encode reconfiguration sequences.

axioms (1)
  • domain assumption Sliding Tokens is PSPACE-complete on the graphs employed in the reduction.
    Invoked as the source problem for all hardness results.

pith-pipeline@v0.9.0 · 6007 in / 1176 out tokens · 25158 ms · 2026-05-24T03:51:59.013498+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Approxima- tions for λ-colorings of graphs

    [Bod+04] Hans L. Bodlaender, Ton Kloks, Richard B. Tan, and Jan van Leeuwen. “Approxima- tions for λ-colorings of graphs”. In: The Computer Journal 47.2 (2004), pp. 193–204. doi: 10.1093/comjnl/47.2.193. [BC09] Paul S. Bonsma and Luis Cereceda. “Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances”. In: Theoretical Com...

    work page doi:10.1093/comjnl/47.2.193 2004

  2. [2]

    Finding Paths Between 3-Colorings

    url: http://etheses.lse.ac.uk/131/. [CvJ11] Luis Cereceda, Jan van den Heuvel, and Matthew Johnson. “Finding Paths Between 3-Colorings”. In: Journal of Graph Theory 67.1 (2011), pp. 69–82. doi: 10.1002/ jgt.20514. [Die17] Reinhard Diestel. Graph Theory. 5th. Vol

    work page 2011

  3. [3]

    Springer, doi: 10.1007/978-3-662-53622-3

    doi: 10.1007/978-3-662-53622-3 . [HIZ15] Tatsuhiko Hatanaka, Takehiro Ito, and Xiao Zhou. “The List Coloring Reconfigu- ration Problem for Bounded Pathwidth Graphs”. In: IEICE Transactions on Fun- damentals of Electronics, Communications and Computer Sciences E98.A.6 (2015), pp. 1168–1178. doi: 10.1587/transfun.E98.A.1168. [HIZ19] Tatsuhiko Hatanaka, Take...

    work page doi:10.1007/978-3-662-53622-3 2015

  4. [4]

    In: Proc

    2010, pp. 238–249. doi: 10.1007/978- 3-642-11409-0_21. [LS95] Yaw-Ling Lin and Steven S Skiena. “Algorithms for Square Roots of Graphs”. In: SIAM Journal on Discrete Mathematics 8.1 (1995), pp. 99–118. doi: 10 . 1137 / S089548019120016X. 30 [Mah24] Reem Mahmoud. “Graph Coloring Reconfiguration”. PhD thesis. Virginia Common- wealth University,

    work page doi:10.1007/978- 2010

  5. [5]

    Optimal Approximation of Sparse Hessians and Its Equiva- lence to a Graph Coloring Problem

    url: https://scholarscompass.vcu.edu/etd/7564/. [McC83] S. Thomas McCormick. “Optimal Approximation of Sparse Hessians and Its Equiva- lence to a Graph Coloring Problem”. In: Mathematical Programming 26.2 (1983), pp. 153–171. doi: 10.1007/BF02592052. [MN19] C.M. Mynhardt and S. Nasserasr. “Reconfiguration of Colourings and Dominating Sets in Graphs”. In: ...

    work page doi:10.1007/bf02592052 1983

  6. [6]

    Introduction to Reconfiguration

    [Nis18] Naomi Nishimura. “Introduction to Reconfiguration”. In: Algorithms 11.4 (2018), p

    work page 2018

  7. [7]

    Distance Coloring

    doi: 10.3390/a11040052. [Sha07] Alexa Sharp. “Distance Coloring”. In: Proceedings of ESA

    work page doi:10.3390/a11040052

  8. [8]

    The Complexity of Change

    LNCS. Springer, 2007, pp. 510–521. doi: 10.1007/978-3-540-75520-3_46 . [van13] Jan van den Heuvel. “The Complexity of Change”. In: Surveys in Combinatorics . Vol

    work page doi:10.1007/978-3-540-75520-3_46 2007

  9. [9]

    Parameterized Complexity of Graph Constraint Logic

    London Mathematical Society Lecture Note Series. Cambridge University Press, 2013, pp. 127–160. doi: 10.1017/cbo9781139506748.005. [van15] Tom C. van der Zanden. “Parameterized Complexity of Graph Constraint Logic”. In: Proceedings of IPEC

    work page doi:10.1017/cbo9781139506748.005 2013

  10. [10]

    Reconfiguration in Bounded Bandwidth and Treedepth

    LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2015, pp. 282–293.doi: 10.4230/LIPIcs.IPEC.2015.282. [Wro18] Marcin Wrochna. “Reconfiguration in Bounded Bandwidth and Treedepth”. In: Journal of Computer and System Sciences 93 (2018), pp. 1–10. doi: 10.1016/j. jcss.2017.11.003. 31

    work page doi:10.4230/lipics.ipec.2015.282 2015