Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
Pith reviewed 2026-05-08 01:57 UTC · model grok-4.3
The pith
Finding shortest sequences to reconfigure independent sets via connected symmetric differences is NP-hard even on planar graphs of bounded degree, even for two steps.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The shortest reconfiguration sequence problem under connected symmetric difference adjacency is NP-hard on planar graphs of bounded degree, even when deciding if the target is reachable in at most two steps, and on split graphs. For split graphs it is W[2]-hard parameterized by the number of steps and inapproximable. This implies that the length of a shortest path between two vertices of a 0/1 polytope in R^n given by O(n) inequalities is hard to approximate within (1-ε)ln n. The problem is solvable in polynomial time for block graphs, cographs, and bipartite chain graphs. On paths and cycles the optimal length exactly matches a trivial upper bound.
What carries the argument
The 1-skeleton of the independent set polytope, whose edges connect independent sets whose symmetric difference induces a connected subgraph.
If this is right
- The problem remains NP-hard even when restricted to deciding reachability in two or fewer steps on planar bounded-degree graphs.
- On split graphs the problem is W[2]-hard when parameterized by the number of steps.
- The optimal length is inapproximable on split graphs, implying (1-ε)ln n inapproximability for shortest paths between vertices of 0/1 polytopes with O(n) inequalities.
- Polynomial-time algorithms exist for block graphs, cographs, and bipartite chain graphs.
- On paths and cycles the shortest sequence length equals the trivial upper bound given by the size of the symmetric difference.
Where Pith is reading between the lines
- Hardness results may transfer to other reconfiguration problems that admit a polytope-skeleton formulation, such as token sliding models.
- Applications involving independent sets in scheduling or network design may require heuristics or approximation schemes outside the identified tractable classes.
- The polyhedral view could enable transferring approximation or fixed-parameter results from combinatorial optimization to reconfiguration.
- Similar skeleton-path problems on other 0/1 polytopes with few inequalities might inherit the same logarithmic inapproximability.
Load-bearing premise
Modeling valid reconfiguration steps as edges on the 1-skeleton via connected symmetric difference correctly captures the intended problem.
What would settle it
A polynomial-time algorithm computing the shortest sequence on planar graphs of maximum degree 4 would falsify the NP-hardness claim unless P equals NP.
read the original abstract
We initiate the study of the shortest reconfiguration problem for independent sets under the adjacency relation derived from the independent set polytope. Given a graph and two independent sets, the problem asks for a shortest sequence transforming one into the other such that the subgraph induced by the symmetric difference of any two consecutive sets is connected. This is equivalent to finding a shortest path on the $1$-skeleton of the independent set polytope. We prove that the problem is NP-hard even on planar graphs of bounded degree, as well as on split graphs. Notably, the hardness for planar graphs of bounded degree still holds even when deciding whether the target can be reached in at most two steps. For split graphs, we further show the W[2]-hardness when parameterized by the number of steps, as well as the inapproximability of the optimal length. As a consequence, we prove that the length of a shortest path between two vertices of a 0/1 polytope in $\mathbb{R}^n$ described by $O(n)$ linear inequalities is hard to approximate within a factor of $(1-\varepsilon)\ln n$ for any constant $\epsilon >0$, unless $P=NP$. On the positive side, we provide polynomial-time algorithms for block graphs, cographs, and bipartite chain graphs. Moreover, for paths and cycles, we show that the optimal length of the shortest reconfiguration sequence exactly matches a trivial upper bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript initiates the study of the shortest independent set reconfiguration problem under the adjacency relation where the symmetric difference of consecutive independent sets induces a connected subgraph. This is shown to be equivalent to finding a shortest path on the 1-skeleton of the independent set polytope. The authors prove NP-hardness on planar bounded-degree graphs (even for distance at most 2) and on split graphs, W[2]-hardness parameterized by the number of steps, and inapproximability on split graphs. They derive a consequence for approximating shortest paths in 0/1 polytopes with O(n) inequalities. Positive results include polynomial-time algorithms for block graphs, cographs, bipartite chain graphs, and exact optimality for paths and cycles.
Significance. If the results hold, this work bridges reconfiguration problems with polyhedral combinatorics by establishing strong hardness results (including for distance-2 decisions and approximation) on natural graph classes while providing efficient algorithms for several restricted classes and an exact characterization on paths/cycles. The derived inapproximability for shortest paths on 0/1 polytopes with O(n) inequalities is a notable general consequence.
major comments (2)
- [Preliminaries / §2] The equivalence between the connected symmetric-difference adjacency and 1-skeleton edges of the independent set polytope is load-bearing for all hardness transfers and the polytope consequence; this modeling assumption should be formally verified with a short proof or reference in the preliminaries section rather than stated only in the abstract.
- [Hardness results for planar graphs] The NP-hardness for planar bounded-degree graphs even at distance at most 2 (abstract) is a strong claim; the reduction must be checked to ensure the target independent set is constructed without increasing the distance artificially, as this is central to the 'notably' highlighted result.
minor comments (2)
- [Consequence for 0/1 polytopes] Clarify the exact number of inequalities in the 0/1 polytope consequence (abstract states 'O(n)'); confirm whether it is strictly linear or allows a small constant factor.
- [Positive results for paths and cycles] The claim that the optimal length on paths and cycles 'exactly matches a trivial upper bound' would benefit from a one-sentence explanation or small example of what that bound is.
Simulated Author's Rebuttal
We thank the referee for their positive assessment and detailed comments. We address each major point below and will revise the manuscript accordingly to strengthen the presentation.
read point-by-point responses
-
Referee: [Preliminaries / §2] The equivalence between the connected symmetric-difference adjacency and 1-skeleton edges of the independent set polytope is load-bearing for all hardness transfers and the polytope consequence; this modeling assumption should be formally verified with a short proof or reference in the preliminaries section rather than stated only in the abstract.
Authors: We agree that a formal verification of this equivalence is warranted given its central role. In the revised manuscript we will insert a short self-contained proof in §2 (Preliminaries) establishing that two independent sets I and J are adjacent under the connected symmetric-difference relation if and only if the line segment between their characteristic vectors is an edge of the 1-skeleton of the independent-set polytope. The argument relies only on the definition of the polytope and the connectedness condition; no external reference is required. revision: yes
-
Referee: [Hardness results for planar graphs] The NP-hardness for planar bounded-degree graphs even at distance at most 2 (abstract) is a strong claim; the reduction must be checked to ensure the target independent set is constructed without increasing the distance artificially, as this is central to the 'notably' highlighted result.
Authors: The reduction for planar bounded-degree graphs is constructed so that the target independent set T' is obtained by a direct, distance-preserving embedding of the original target T. Specifically, any sequence of length at most 2 in the constructed instance projects to a valid sequence of the same length in the source instance, and conversely; the gadgets are attached in a way that does not create shortcuts of length 1 or 2. We will add an explicit paragraph immediately after the reduction statement that verifies this distance preservation by case analysis on the possible one- and two-step moves. revision: yes
Circularity Check
No significant circularity identified
full rationale
The paper establishes NP-hardness and W[2]-hardness results for shortest reconfiguration sequences via explicit polynomial-time reductions from known hard problems, along with polynomial-time algorithms for restricted graph classes. These are standard complexity-theoretic arguments with no fitted parameters, self-definitional equations, or load-bearing self-citations that reduce the central claims to their own inputs. The stated equivalence between the symmetric-difference adjacency and the 1-skeleton of the independent-set polytope is a modeling definition, not a derived result that loops back on itself. Positive results for paths, cycles, and other classes are obtained by direct combinatorial arguments that match a trivial upper bound without circularity.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The 1-skeleton of the independent set polytope has edges precisely when the symmetric difference of the two independent sets induces a connected subgraph.
Reference graph
Works this paper leans on
-
[1]
Finding Short Paths on Simple Polytopes
2 AlexanderE.BlackandRaphaelSteiner. Findingshortpathsonsimplepolytopes.CoRR,abs/2603.05482,
work page internal anchor Pith review Pith/arXiv arXiv
-
[2]
Analytical approach to parallel repetition
13 Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624–633. ACM,
work page 2014
-
[3]
19 Victor Klee and George J. Minty. How good is the simplex algorithm? InInequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), pages 159–175,
work page 1969
-
[4]
Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T
25 Roni Stern, Nathan R. Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne T. Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Satish Kumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. InTwelfth International Symposium on Combinatorial Search (SOCS 2019), pages 151–158. AAAI Press,
work page 2019
-
[5]
27 Jan van den Heuvel. The complexity of change. In Simon R. Blackburn, Stefanie Gerke, and Mark Wildon, editors,Surveys in Combinatorics 2013, London Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press,
work page 2013
-
[6]
Reconfiguration in bounded bandwidth and tree-depth.J
28 Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth.J. Comput. Syst. Sci., 93:1–10, 2018
work page 2018
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.