arxiv: 2604.27802 · v1 · submitted 2026-04-30 · 💻 cs.DM · cs.DS· math.CO

Recognition: unknown

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery

Amer E. Mouawad, Daniel Schmand, Enna Gerhard, Hanno von Bergen, Larissa Fastenau, Mai Trinh, Nicola Lorenz, Nicole Schirrmacher, Roman Rabinovich, Sebastian Siebertz, Stephanie Maaz

Authors on Pith no claims yet

Pith reviewed 2026-05-07 07:11 UTC · model grok-4.3

classification 💻 cs.DM cs.DSmath.CO

keywords solution discoverypath discoverytwo-graph modeltoken slidingtoken jumpingNP-hardnesscomplexity analysisshortest paths

0 comments

The pith

A two-graph model separates the graph defining valid solutions from the graph governing movements to handle asymmetry and costs in path discovery.

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

The paper introduces a model for solution discovery that uses one graph to specify which sets of vertices form valid solutions and a second graph to specify how agents or tokens may move between vertices along with the costs of those moves. This separation lets the framework represent directed movements, varying constraints across locations, and weighted transitions that single-graph approaches cannot capture directly. The authors apply the model to the tasks of reaching any s-t path and reaching a shortest s-t path in the feasibility graph. The resulting complexity analysis shows that some instances remain solvable in polynomial time while others become NP-hard, with the split producing a richer set of tractable and intractable cases than earlier models.

Core claim

The central claim is that a directed weighted two-graph framework cleanly separates the problem graph, which defines the combinatorial objects that count as solutions, from the movement graph, which defines admissible relocations and their costs. When applied to Path Discovery and Shortest Path Discovery, the framework subsumes classical single-graph models such as token sliding and token jumping as special cases while accommodating asymmetry and heterogeneous constraints. The complexity results establish both polynomial-time algorithms for certain restricted cases and strong NP-hardness results that hold even when the underlying path-finding problems are easy.

What carries the argument

The directed weighted two-graph model, with one graph specifying feasible vertex sets and the other governing admissible relocations together with costs.

If this is right

Classical token-sliding and token-jumping models become special cases obtained by setting the two graphs equal.
Directed edges and position-dependent movement costs become expressible without changing the feasibility rules.
Some path-discovery instances remain polynomial-time solvable even after the split, while others become NP-hard despite the underlying path problem being easy.
The model yields a detailed complexity map that distinguishes cases based on the interaction between the two graphs.

Where Pith is reading between the lines

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

The same separation could be applied to other discovery problems such as finding matchings or independent sets to see whether similar complexity enrichments appear.
Implementation in logistics or network reconfiguration tools might allow movement rules to be tuned independently of validity rules, potentially improving solution quality.
Experimental testing on graphs drawn from specific domains could identify additional parameter restrictions that restore tractability beyond those already analyzed.

Load-bearing premise

That the separation between a feasibility graph and a movement graph accurately models real applications and that the hardness and tractability classifications transfer directly from the new definitions without unstated reductions or hidden assumptions in the proofs.

What would settle it

A concrete polynomial-time algorithm for an instance family that the paper proves NP-hard under the two-graph definitions, or a real-world application in which the two-graph split fails to represent movement constraints that matter for solution discovery.

read the original abstract

We study solution discovery, where the goal is to obtain a feasible solution to a problem from an initial configuration by a bounded sequence of local moves. In many applications, however, the graph that defines which vertex sets are feasible is not the same as the graph that governs how tokens, agents, or resources may move. Existing models such as token sliding and token jumping typically do not distinguish the problem graph and the movement graph. Motivated by this mismatch, we introduce a directed weighted two-graph model that cleanly separates feasibility from movement. A problem graph specifies the desired combinatorial objects, while a movement graph specifies admissible relocations and their costs. This yields a flexible framework that captures asymmetry, heterogeneous movement constraints, and weighted transitions, while subsuming classical discovery models as special cases. We investigate this model through \textsc{Path Discovery} and \textsc{Shortest Path Discovery}, where the task is to realize a vertex set containing an $s$-$t$-path or a shortest $s$-$t$-path in the problem graph. These problems are particularly natural in applications, since directed and weighted shortest paths are among the most fundamental algorithmic primitives. At the same time, previous work has already shown that discovery can be computationally hard even when the underlying optimization problem is easy. Our results show that this phenomenon persists, and becomes especially rich, in the two-graph setting. We obtain a detailed complexity picture, identifying tractable cases as well as strong hardness results.

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.

Desk Editor's Note private letter to a colleague

The paper cleanly splits feasibility from movement in a two-graph model for solution discovery and maps out the resulting complexity for path problems.

read the letter

The main point is that this two-graph setup lets the problem graph define what counts as a feasible vertex set while the movement graph independently controls token relocations, directions, and costs. Classical token sliding and jumping emerge exactly when the two graphs coincide, so the model is a strict generalization rather than a replacement. They apply it to Path Discovery and Shortest Path Discovery, where the goal is to reach a set containing an s-t path or a shortest s-t path in the problem graph via moves on the movement graph. The results give a fairly complete complexity picture with both polynomial cases and NP-hardness results that survive even when the underlying path problem is easy on a single graph. The reductions are explicit and keep the separation intact, so the claim that the phenomenon becomes richer holds up without circularity or hidden assumptions. The definitions are straightforward and the special cases recover prior work exactly. One minor limitation is that the application motivation stays at the level of sketches; there are no concrete network or planning instances showing how often the extra modeling power actually matters in practice. The tractable cases also tend to require the graphs to share structure such as being undirected or having bounded weights, which is reasonable but narrows the immediate scope. This work is aimed at people already working on reconfiguration, token models, and parameterized graph algorithms. A reader who cares about how modeling choices affect hardness will find the case breakdowns useful. It deserves a serious referee because the framework is well-defined, the results rest on explicit constructions, and the separation addresses a real modeling gap without introducing inconsistencies.

Referee Report

0 major / 3 minor

Summary. The paper introduces a directed weighted two-graph model that separates the problem graph, which defines the feasibility of solutions such as vertex sets containing an s-t path, from the movement graph, which specifies admissible token relocations and their costs. Through the study of Path Discovery and Shortest Path Discovery, the authors provide a detailed complexity classification, identifying both polynomial-time tractable cases and NP-hard instances, and demonstrate that the separation of feasibility and movement leads to a richer set of computational phenomena than in classical single-graph models.

Significance. If the results hold, this work significantly advances the modeling of solution discovery problems by allowing for asymmetry, heterogeneous constraints, and weights in movement, while exactly recovering classical models when the graphs coincide. The explicit reductions and case analyses for hardness and tractability provide a solid foundation for understanding when discovery remains hard even for easy underlying problems like shortest paths. This framework has potential applications in network design and reconfiguration where movement rules differ from feasibility constraints. The clean separation and subsumption of prior models are particular strengths.

minor comments (3)

[Abstract] Abstract: The claim that the phenomenon 'becomes especially rich' in the two-graph setting is plausible but would be strengthened by briefly naming one concrete new tractable case or hardness result (e.g., a specific combination of directed/weighted graphs) rather than leaving it at the high-level statement.
[§2] §2 (Preliminaries): The formal definition of a discovery sequence is precise, yet a small worked example showing how a feasible s-t path is realized via moves on the movement graph (with costs) would improve accessibility, especially for readers new to discovery problems.
[§4–5] §4–5 (Complexity Results): While the skeptic confirms explicit reductions without hidden assumptions, a summary table classifying all combinations of directed/undirected and weighted/unweighted graphs (with references to the relevant theorems) would make the 'detailed complexity picture' easier to navigate.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our work, for highlighting its significance in advancing the modeling of solution discovery via the separation of feasibility and movement graphs, and for recommending minor revision. We appreciate the recognition that our framework subsumes classical models while yielding richer computational phenomena, and we will incorporate any minor polishing points in the revised version.

Circularity Check

0 steps flagged

No significant circularity in model definition or complexity results

full rationale

The paper introduces the two-graph model via explicit definition separating the problem graph (for feasible s-t path vertex sets) from the movement graph (for relocations and costs). Classical discovery models are recovered exactly by equating the two graphs, which is a direct special-case instantiation rather than a derived claim. Complexity results for Path Discovery and Shortest Path Discovery are obtained through explicit reductions and case analyses that respect the graph separation. No load-bearing step reduces by construction to fitted parameters, self-citations, or prior inputs; the framework is self-contained as a new modeling approach with independent hardness/tractability analyses.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The paper introduces two new modeling constructs (problem graph and movement graph) as the core contribution; these are not supported by independent evidence outside the framework but rely on standard assumptions of graph theory.

axioms (2)

standard math Graphs are finite directed structures with vertices and edges
Invoked implicitly in definitions of problem and movement graphs throughout the abstract.
domain assumption Feasibility is defined by vertex sets containing s-t paths in the problem graph
Central to the Path Discovery problem definition.

invented entities (2)

problem graph no independent evidence
purpose: Specifies the combinatorial objects that are feasible solutions
New modeling entity introduced to separate feasibility from movement.
movement graph no independent evidence
purpose: Specifies admissible relocations and their costs between configurations
New modeling entity introduced to capture asymmetric and weighted movement constraints.

pith-pipeline@v0.9.0 · 5608 in / 1430 out tokens · 58877 ms · 2026-05-07T07:11:14.760000+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Color-coding.Journal of the ACM, 42(4):844–856, 1995.doi:10.1145/210332.210337

1 Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.Journal of the ACM, 42(4):844–856, 1995.doi:10.1145/210332.210337. 2 Hans L. Bodlaender and Krisztina Szilágyi. XALP-completeness of parameterized problems on planar graphs.Discrete Applied Mathematics,

work page doi:10.1145/210332.210337 1995
[2]

https://doi.org/10.1016/j

arXiv:2402.03087, doi:10.1016/j. dam.2026.01.021. 3 Nicolas Bousquet, Amer E Mouawad, Stephanie Maaz, Naomi Nishimura, and Sebastian Siebertz. On algorithmic meta-theorems for solution discovery: Tractability and barriers

work page doi:10.1016/j 2026
[3]

and Maaz, Stephanie and Nishimura, Naomi and Siebertz, Sebastian , year = 2025, month = oct, number =

arXiv:2510.17344. 4 Marek Cygan, Fedor V Fomin,Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized algorithms, volume

work page arXiv
[4]

Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

Springer, 2015.doi:10.1007/978-3-319-21275-3. 5 Walter Didimo, Giuseppe Liotta, and Maurizio Patrignani. HV-planarity: Algorithms and complexity.Journal of Computer and System Sciences, 99:72–90,

work page doi:10.1007/978-3-319-21275-3 2015
[5]

2018.08.003

doi:10.1016/j.jcss. 2018.08.003. 6 Michael R Fellows, Mario Grobler, Nicole Megow, Amer E Mouawad, Vijayaragunathan Ramamoorthi, Frances A Rosamond, Daniel Schmand, and Sebastian Siebertz. On solution discovery via reconfiguration.Journal of Computer and System Sciences, 157:103747,

work page doi:10.1016/j.jcss 2018
[6]

7 Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E

doi:10.1016/j.jcss.2025.103747. 7 Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, and Sebastian Siebertz. Solution discovery via reconfiguration for problems in P. InProceedings of ICALP 2024, LIPIcs,

work page doi:10.1016/j.jcss.2025.103747 2025
[7]

doi:10.4230/LIPIcs.ICALP. 2024.76. 8 Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, and Sebastian Siebertz. Kernelization complexity of solution discovery problems. In35th International Symposium on Algorithms and Computation, ISAAC 2024, LIPIcs, pages 36:1–36:17. Schloss Dagstuhl - Leibniz-Zentrum für Infor...

work page doi:10.4230/lipics.icalp 2024
[8]

10 Marcin Kamiński, Paul Medvedev, and Martin Milanič

Springer Nature Switzerland.doi:10.1007/978-3-031-49275-4_14. 10 Marcin Kamiński, Paul Medvedev, and Martin Milanič. Shortest paths between shortest paths and independent sets. InCombinatorial Algorithms, pages 56–67, Berlin, Heidelberg,

work page doi:10.1007/978-3-031-49275-4_14
[9]

11 Nancy G

Springer.doi:10.1007/978-3-642-19222-7_7. 11 Nancy G. Kinnersley. The vertex separation number of a graph equals its path-width. Information Processing Letters, 42(6):345–350, 1992.doi:10.1016/0020-0190(92)90234-M. 12 Naomi Nishimura. Introduction to reconfiguration.Algorithms, 11(4):52, 2018.doi:10.3390/ a11040052. S. Siebertz et al. 25 13 Rin Saito, Ano...

work page doi:10.1007/978-3-642-19222-7_7 1992
[10]

14 Jan van den Heuvel

Springer Nature Switzerland.doi:10.1007/978-3-032-17801-5_32. 14 Jan van den Heuvel. The complexity of change. InSurveys in Combinatorics 2013, volume 409 ofLondon Mathematical Society Lecture Note Series, pages 127–160. Cambridge University Press, 2013.doi:10.1017/CBO9781139506748.005

work page doi:10.1007/978-3-032-17801-5_32 2013