Lower bounds for dominating set reconfiguration on sparse (directed) graphs

Alexandre Vigny; Jona Dirks

REVIEW 3 major objections 5 minor 12 references

Lower bounds for dominating set reconfiguration on sparse (directed) graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that the token-sliding version of dominating set reconfiguration is W[2]-hard on graphs of bounded pathwidth and treewidth, and that the directed variant is already intractable on very shallow DAGs.

desk verdict The central reductions fail because the start set does not dominate the red vertex s; the paper needs a fix but the target question is worth referee time. read the letter →

arxiv 2507.11446 v1 pith:FESYI7IU submitted 2025-07-15 cs.DM

Jona Dirks , Alexandre Vigny This is my paper · ORCID

classification cs.DM MSC 05C6905C8568Q2768R10

keywords dominatingsetreconfigurationtokenslidingW[2]-hardnesspathwidthtreewidthdirectedacyclicgraphsfixed-parametertractability

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper attacks an open question about reconfiguration: when you must transform one dominating set into another of the same size by sliding a single token along an edge at a time, keeping the set dominating at every step, is the problem fixed-parameter tractable in the set size k? The answer given here is no, even for very sparse graphs: DSR-TS is W[2]-hard for parameter k on undirected graphs with pathwidth 13 and treewidth 10, and W[2]-hard for k together with pathwidth and the newly introduced iteration parameter. For directed token sliding, the paper shows NP-hardness already on DAGs of depth 3, and W[2]-hardness on DAGs parameterized by k and pathwidth. These results matter because the parallel independent-set and token-jumping problems are FPT in the same regimes, so they map a sharp boundary where the dominating-set sliding problem escapes tractability.

What carries the argument

The validator gadget: given a graph G and integer k, it creates k blue paths, one per token, each path having a segment for every vertex of G; red vertices $p^\ell_1$, $p^\ell_2$, $p^\ell_3$ and $s$ are connected so that a token on path position $(i,j)$ can only move in synchronization with a clock, and the red vertex $s$ is dominated exactly when the chosen indices $\{i_1,\dots,i_k\}$ form a dominating set of G (Lemma 4.2). A blue path or 3-cycle acts as the clock that forces all gadget tokens to advance exactly one position per tick, and the parity connections to $p^\ell_1,\dots,p^\ell_3$ are what lock the tokens to their chosen index path. The mechanism transfers the reconfiguration question to the existence of a dominating set by extracting the indices of the tokens when the clock completes its traversal.

What would settle it

Run a brute-force state search on the validator construction with k=2 and a small graph G (say three vertices) to enumerate all token configurations reachable while dominating all red vertices; if any reachable configuration has a gadget token on a different index path than the one it started on when the clock has not yet finished, the synchronization invariant that the reduction depends on fails.

Watch

Extended reading notes

Core claim

The central claim is that the reconfiguration problem DSR-TS remains W[2]-hard when parameterized by the dominating set size k even when the input graph has constant pathwidth 13 and treewidth 10, and even when the reconfiguration sequence is constrained to have iteration 1 and pathwidth is added to the parameter. The directed variant DSR-DTS is NP-hard on DAGs of depth 3 and W[2]-hard on DAGs parameterized by k plus pathwidth, and remains NP-hard on DAGs of pathwidth 9 and treewidth 5. The authors build reductions from dominating set through a red-blue validator gadget and a clock gadget, and transfer the hardness from the red-blue variant to the uncolored problem via gadgets that trap tokens in their components. In the undirected case the same construction, without the iteration bound, gives hardness on graphs whose pathwidth and treewidth are fixed small constants.

Load-bearing premise

The whole reduction rests on the synchronization invariant that, at every clock step, each gadget token sits exactly one column ahead of the clock token and never switches between the k index paths; if a token could drift or switch paths in some reachable configuration, the extracted indices need not form a dominating set.

Editorial extensions

If this is right

No fixed-parameter algorithm for DSR-TS parameterized by k exists on graphs of bounded pathwidth or treewidth unless FPT = W[2].
In the same sparse settings where independent set reconfiguration under token sliding is known to be fixed-parameter tractable, the dominating set version is provably hard, separating the two problems.
The iteration parameter, which bounds how often a token may visit a vertex, does not buy tractability: hardness holds even with iteration 1 when k and pathwidth are parameters.
For DAGs, depth is a sharp boundary: DSR-DTS is solvable in linear time on depth 2 but NP-hard on depth 3, and remains W[2]-hard on DAGs when k and pathwidth are parameters.
The explicit width bounds (pathwidth 13, treewidth 10 undirected; pathwidth 9, treewidth 5 directed) mean the hardness holds on graphs that are genuinely narrow, not just asymptotically sparse.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural next step is to test whether the same validator gadget can express other domination-like reconfiguration problems, such as connected dominating set or total dominating set, under token sliding, which would likely inherit the same sparse hardness.
Because the reduction's width bounds come from the clock gadget, replacing the 3-cycle clock with a different bounded-width synchronizer might lower the treewidth bound further, a question the paper leaves open.
The depth-2 tractability result suggests a broader program: for each fixed depth d, determine the complexity of DSR-DTS on DAGs of depth d, with the likely threshold at d=3.
The W[2]-hardness for DSR-TS on bounded pathwidth does not rule out XP algorithms; an empirical or theoretical check of whether a dynamic program with complexity n^{O(k)} exists on such graphs would delineate the boundary more sharply.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know before reading closely: the core reductions in Section 4 do not produce valid ReBuDSR-TS instances. In Construction 4.1, the red vertex s is adjacent only to internal blue path vertices u^ell_{i,j} with 1 <= j <= n. The start vertices s_ell (u^ell_{i,0}) and the clock vertex h_0 are not adjacent to s, so the proposed start set S = {s_1,...,s_k, h_0} fails to dominate s. Since ReBuDSR requires every configuration to be a red-blue dominating set, the instances are illegal from step zero. This affects Theorems 4.3, 4.7, 4.11, and 4.12, and likely the directed adaptations in Section 5. The synchronization concerns you flagged are real, but this initial non-domination is a more basic failure that must be repaired first.

The paper is not without merit. The question is a good one: it targets the open case [7, Question 10], and the lower constants (treewidth 9/10, pathwidth 13) would improve on the independent simultaneous work [6]. The DAG depth-3 NP-hardness and the directed variants add coverage. The red-blue gadget is a reasonable strategy, and the authors are transparent about the overlap with [6].

That said, there are multiple soft spots beyond the fatal one. The treewidth numbers are inconsistent: the abstract says 9, Theorem 4.12 says 10, and Claim 4.8 says 6 with a bag count that suggests 7. Section 2 defines treewidth as largest bag size plus one, off by one from the standard convention. The synchronization Claims 4.6 and 4.9 are sketched and need real expansion, especially Claim 4.9 with the unbounded clock. The claimed first separation between ISR-TS and DSR-TS relies on the FPT result from the authors' own preprint [9]; that dependency should be verified or clearly flagged.

On balance, the core idea is salvageable, for instance by adding s to the start set or making the clock vertex dominate s. But the current manuscript does not establish its main theorems. A referee could work through a fix, so it merits peer review in that sense, but the paper needs major revision and re-verification before acceptance. If you are assigning referees, this is a legitimate target, though expect a heavy revision cycle.

Referee Report

3 major / 5 minor

Summary. The paper studies the token-sliding reconfiguration of dominating sets, both undirected (DSR-TS) and directed (DSR-DTS). It introduces a red-blue ``validator'' gadget and reduces from Dominating Set. The claimed results are: DSR-TS is W[2]-hard parameterized by k+pw+ι (Theorem 4.11), and W[2]-hard parameterized by k even on graphs of bounded pathwidth and treewidth (Theorem 4.12); in the directed setting, DSR-DTS is NP-hard on DAGs of depth 3, NP-hard on DAGs with fixed pathwidth 9 and treewidth 5, and W[2]-hard for DAGs parameterized by k+pw. The authors frame these as the first setting where independent-set reconfiguration is FPT but dominating-set reconfiguration is not, and they discuss simultaneous independent work on the same question.

Significance. If the reductions are correct, the paper gives a substantial answer to an open question: dominating set reconfiguration under token sliding is not FPT on bounded-treewidth graphs, in contrast to the token jumping variant and to independent set reconfiguration, and the directed variant is hard even on DAGs where the independent set version is FPT. The reductions are from the external W[2]-hard Dominating Set problem, so the hardness claims are grounded independently of the authors' prior work. The gadget constructions are natural and the stated bounds are small, which is valuable. However, the validity of the main reductions is currently blocked by a concrete flaw in the construction of the initial configuration, and a second, more subtle synchronization argument is not fully established. The paper's contribution will be solid once these issues are repaired.

major comments (3)

[Section 4.1, Construction 4.1 and Theorem 4.3] The initial configuration S is not a red-blue dominating set, so the produced instances are not valid ReBuDSR-TS instances as defined. In Construction 4.1, the red vertex s is adjacent only to the vertices u^ℓ_i,j with 1≤j≤n, and it is not adjacent to sℓ = u^ℓ_i,0, dℓ, or any h vertex; the h vertices are adjacent only to the p^ℓ vertices. In Theorem 4.3 the start set is S = {s_1,...,s_k,h_0}, so no vertex of S dominates s. Since DSR-TS and ReBuDSR-TS require the initial configuration to be a dominating set, the reconfiguration sequence described in the proof cannot legally begin. The same flaw affects Theorem 4.7 and the directed adaptations in Section 5, and therefore the consequences Theorem 4.11, Theorem 4.12, Theorem 5.4, and Theorem 5.5. The construction must be modified, for example by adding edges from s to each sℓ and then rechecking every domination argument in the sequence.
[Section 4.2, Claim 4.9] The synchronization proof does not rule out a gadget token switching between the internal paths P_i and P_i' at the shared endpoints sℓ and dℓ. For a fixed ℓ, all paths sℓ-u^ℓ_i,1-...-u^ℓ_i,n-dℓ share only sℓ and dℓ; a token that returns to sℓ could in principle depart along a different path. Claim 4.9 asserts that after a forward or backward move the ℓ-th token lies on some u^ℓ_i,j with the correct column j, but it does not prove that the index i is fixed for the whole sequence. The later extraction of the set I = {i_1,...,i_k} after the last time a=b is well-defined only under this additional invariance, and the application of Lemma 4.2 to that fixed index set is otherwise unjustified. The parity constraints may indeed prevent such switches, but the proof as written does not formalize this, and the invariant is load-bearing for Theorems 4.7 and 4.12.
[Section 4.3, Theorem 4.12 versus Claim 4.8 and the abstract] The stated treewidth values are inconsistent. Claim 4.8 constructs a tree decomposition whose largest bag contains 7 vertices and concludes treewidth 6; Lemma 4.10 increases the treewidth by 3, which yields treewidth 9. The abstract says treewidth 9, but Theorem 4.12 states treewidth 10. The pathwidth bound 13 is consistent with Claim 4.8's pathwidth 10 plus the additive 3 from Lemma 4.10. The treewidth statement should be corrected and the decomposition checked so that the exact numerical claims in the theorem, abstract, and proof agree.

minor comments (5)

[Section 2, Parameterized Complexity] The sentence ``Dominating Set is known to be W[1]-hard'' is misleading; Dominating Set is W[2]-complete, and the paper's reductions should be described as FPT reductions from Dominating Set.
[Section 3, Theorem 3.1 proof] The text describing the vertex construction is corrupted: the word ``Vertices:'' is repeated many times, and the membership lists ``a1,a2,a3,a5∈S and a1,a2,a4,a7∈S'' are incoherent because both lists contain a1 and a2. Please rewrite this passage and align it with Figure 1.
[Section 2, Definition 2.1] The displayed formula for the iteration parameter is hard to parse; in particular, the set whose cardinality is taken mixes the starting position with entries and the condition ``α_{i-1}(t)≠α_i(t)=v'' is ambiguous. A precise verbal definition would improve readability.
[Section 5, Theorem 5.2 and Lemma 5.3] The parameter dfvs is used without being defined in the preliminaries; the directed feedback vertex set should be defined explicitly.
[Section 6, opening and proof of Claim 6.5] There are several editorial errors in this section: the sentence ``Not the validator gadget to yields even better bounds but blows up k'' is incomplete, and ``We now proof that ReBuDSR-DTS is hard...'' should read ``We now prove...''.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: hardness results reduce from the external Dominating Set problem, and the sole self-citation to [9] is contextual rather than load-bearing.

full rationale

The paper's hardness theorems (Theorems 4.3, 4.7, 4.11, 4.12, 5.1, 5.4, 6.4 and 6.9) are established by explicit FPT reductions from the externally W[2]-hard Dominating Set problem. The validator gadget in Construction 4.1 and Lemma 4.2 translate domination in the source graph G into adjacency to a red vertex s; this is a standard equivalence between a dominating set of G and a token configuration in the gadget, not a definitional identity that presupposes the target reconfiguration instance. The only self-citation is reference [9], used in Definition 2.1 to define the iteration parameter and in the introduction to cite an FPT result for ISR-TS on DAGs; that FPT result supports the advertised contrast between ISR-TS and DSR-TS, but it is not part of the reduction chain that proves the new DSR-TS hardness, so the self-citation is not load-bearing. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work, and no known result is merely recast in new coordinates. The skeptic-flagged issue that the start set S may fail to dominate the red vertex s in Theorem 4.3 concerns whether the constructed instance satisfies the input condition of ReBuDSR-TS; if real, it is a soundness bug in the reduction, not a circularity, because the proof does not assume the truth of the reconfiguration instance it is trying to establish. Similarly, the footnote on page 1:8 concedes a subtlety in the synchronization argument for bounded iteration, but a proof gap is a rigor concern rather than a circular step. Accordingly, no circular step can be exhibited from the paper's own equations or definitions.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper relies on standard parameterized complexity facts and on the authors' own prior preprint for the ISR-TS FPT result that underlies the claimed separation. No fitted parameters or invented entities are introduced; the gadgets are proof constructions, not empirical entities.

assumptions (5)

standard math W[2]-hardness of Dominating Set parameterized by solution size k, used as the source problem in every reduction (Sections 3.1, 4.2, 4.3, 5, 6).
The reductions construct equivalent reconfiguration instances from any Dominating Set instance, transferring W[2]-hardness or NP-hardness.
standard math The conjecture W[2] is not equal to FPT, the standard interpretation of W[2]-hardness as fixed-parameter intractability.
Used throughout to express the consequence of the hardness results.
domain assumption Correctness of the FPT result in the authors' prior preprint [9] (Dirks and Vigny, arXiv:2504.10671) that ISR-TS and directed variants are FPT on DAGs parameterized by k and treewidth, and that the iteration parameter has the stated properties.
The paper's claimed first separation of ISR-TS (FPT) and DSR-TS (hard) depends on this unreviewed self-cited result; the hardness results themselves do not depend on it.
domain assumption In red-blue reconfiguration, tokens may only occupy blue vertices and red vertices need only be dominated; this is assumed without loss of generality in Sections 4 and 5.
The reductions build red-blue instances and transfer hardness to the uncolored problem via Lemmas 4.10, 5.3 and 6.1.
standard math Standard treewidth and pathwidth definitions (max bag size minus one), applied in Claims 4.4, 4.8, 6.5 and 6.6.
The stated width bounds are computed from bag sizes; Section 2's definition 'largest bag plus one' is a typo contradicted by the usage.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Lower bounds for dominating set reconfiguration on sparse (directed) graphs." pith.science (2026). https://pith.science/paper/FESYI7IU

@misc{pith2026250711446,
  author       = {Pith},
  title        = {Pith review of: Lower bounds for dominating set reconfiguration on sparse (directed) graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FESYI7IU}},
  note         = {Machine review of arXiv:2507.11446}
}

abstract

In a graph, a vertex dominates itself and its neighbors, and a dominating set is a set of vertices that together dominate the entire graph. Given a graph and two dominating sets of equal size $k$, the {\em Dominating Set Reconfiguration with Token sliding} (DSR-TS) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while ensuring that every set during the reconfiguration process is a dominating set. The token jumping variant, where a vertex can be replaced by a non-adjacent one, is known to be efficiently solvable on many graph classes such as planar, bounded treewidth, and the very broad notion of nowhere-dense classes of graphs. Alternatively, some algorithms also exist for the reconfiguration of independent sets in the token sliding paradigm for graph classes with bounded degree or large girth. We show that DSR-TS is W[2]-hard when parameterized $k$, the pathwidth of the instance, and the iteration of the reconfiguration sequence (a recently introduced parameter). This is a setting where both the token jumping and the independent set variants are fixed parameter tractable. Not restricting the iteration yields W[2] hardness already on graphs with treewidth 9 and pathwidth 13. In the directed variant (DSR-DTS), we are only allowed to replace a vertex with an out-neighbor. We show that DSR-DTS is NP-hard on DAGs of treewidth 5 and W[2]-hard for both the case of DAGs of depth 3 parameterized by $k$, and the case of DAGs when parameterized by $k$ and the pathwidth of the instance (independent set reconfiguration is again FPT in both settings).

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 7 canonical work pages

[6]

Token Sliding Reconfiguration on DAGs

URL: https://doi.org/10.48550/arXiv.2504.10671, arXiv:2504.10671, doi:10. 48550/ARXIV.2504.10671. 10 Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive algorithms for domination and independence. In Symp. on Theoretical Aspects in Com- puter Science (STACS), volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl -...

work page Pith review arXiv doi:10.48550/arxiv.2504.10671
[9]

14 Daniel Lokshtanov, Amer E

doi:10.1145/3280825. 14 Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. On the parameterized complexity of reconfiguration of connected dominating sets.Algorithmica, 84(2):482–509,

doi:10.1145/3280825
[3]

The tape reconfiguration problem and its consequences for dominating set reconfiguration

URL: https://doi.org/10.48550/arXiv.2505.00988, arXiv:2505.00988, doi:10.48550/ARXIV.2505.00988. 7 Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, and Sebastian Siebertz. A sur- vey on the parameterized complexity of reconfiguration problems. Comput. Sci. Rev., 53:100663,

work page Pith review arXiv doi:10.48550/arxiv.2505.00988
[8]

12 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa

URL: https://doi.org/10.1007/s00453-024-01261-0, doi:10.1007/S00453-024-01261-0. 12 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa. Independent set reconfiguration on directed graphs. InIntl. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 241 ofLIPIcs, pages 58:1–58:15. ...

work page doi:10.1007/s00453-024-01261-0
[12]

URL:https: //doi.org/10.1016/j.jcss.2017.11.003, doi:10.1016/J.JCSS.2017.11.003

doi:10.1016/j.jcss.2017.11.003 2017
[2014]

Token sliding reconfiguration on dags.CoRR, abs/2504.10671,

9 Jona Dirks and Alexandre Vigny. Token sliding reconfiguration on dags.CoRR, abs/2504.10671,

arXiv
[2018]

17 Marcin Wrochna

doi:10.37236/7458. 17 Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth,

work page doi:10.37236/7458
[2019]

11 Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi

URL: https://doi.org/10.4230/LIPIcs.STACS.2019.27, doi:10.4230/LIPICS.STACS.2019.27. 11 Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi. Algorithmic meta-theorems for combinatorial reconfiguration revisited. Algorithmica, 86(11):3395–3424,

doi:10.4230/lipics.stacs.2019.27 2019

Show all 12 references

[2022]

15 Amer E

URL: https://doi.org/10.1007/s00453-021-00909-5, doi:10.1007/ S00453-021-00909-5. 15 Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems.Algorithmica, 78(1):274–297,

doi
[2023]

4 Hans L

URL: https://doi.org/10.1016/j.jcss.2023.03.008, doi: 10.1016/J.JCSS.2023.03.008. 4 Hans L. Bodlaender, Carla Groenland, and Céline M. F. Swennenhuis. Parameterized com- plexities of dominating and independent set reconfiguration. InIntl. Symp. on Parameterized and Exact Compu...

2023 doi
[2024]

8 Erik D

URL: https://doi.org/10.1016/j.cosrev.2024.100663, doi:10.1016/ J.COSREV.2024.100663. 8 Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Polynomial-time algorithm for sliding tokens o...

2024
[2025]

2 Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E

URL:https: //doi.org/10.1016/j.jcss.2024.103578, doi:10.1016/J.JCSS.2024.103578. 2 Valentin Bartier, Nicolas Bousquet, Jihad Hanna, Amer E. Mouawad, and Sebastian Siebertz. Token sliding on graphs of girth five.Algorithmica, 86(2):638–655,

2024

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [6]

Token Sliding Reconfiguration on DAGs

URL: https://doi.org/10.48550/arXiv.2504.10671, arXiv:2504.10671, doi:10. 48550/ARXIV.2504.10671. 10 Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive algorithms for domination and independence. In Symp. on Theoretical Aspects in Com- puter Science (STACS), volume 126 ofLIPIcs, pages 27:1–27:16. Schloss Dagstuhl -...

work page Pith review arXiv doi:10.48550/arxiv.2504.10671

[2] [9]

14 Daniel Lokshtanov, Amer E

doi:10.1145/3280825. 14 Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz. On the parameterized complexity of reconfiguration of connected dominating sets.Algorithmica, 84(2):482–509,

doi:10.1145/3280825

[3] [3]

The tape reconfiguration problem and its consequences for dominating set reconfiguration

URL: https://doi.org/10.48550/arXiv.2505.00988, arXiv:2505.00988, doi:10.48550/ARXIV.2505.00988. 7 Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, and Sebastian Siebertz. A sur- vey on the parameterized complexity of reconfiguration problems. Comput. Sci. Rev., 53:100663,

work page Pith review arXiv doi:10.48550/arxiv.2505.00988

[4] [8]

12 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa

URL: https://doi.org/10.1007/s00453-024-01261-0, doi:10.1007/S00453-024-01261-0. 12 Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, and Kunihiro Wasa. Independent set reconfiguration on directed graphs. InIntl. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 241 ofLIPIcs, pages 58:1–58:15. ...

work page doi:10.1007/s00453-024-01261-0

[5] [12]

URL:https: //doi.org/10.1016/j.jcss.2017.11.003, doi:10.1016/J.JCSS.2017.11.003

doi:10.1016/j.jcss.2017.11.003 2017

[6] [2014]

Token sliding reconfiguration on dags.CoRR, abs/2504.10671,

9 Jona Dirks and Alexandre Vigny. Token sliding reconfiguration on dags.CoRR, abs/2504.10671,

arXiv

[7] [2018]

17 Marcin Wrochna

doi:10.37236/7458. 17 Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth,

work page doi:10.37236/7458

[8] [2019]

11 Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi

URL: https://doi.org/10.4230/LIPIcs.STACS.2019.27, doi:10.4230/LIPICS.STACS.2019.27. 11 Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, and Yota Otachi. Algorithmic meta-theorems for combinatorial reconfiguration revisited. Algorithmica, 86(11):3395–3424,

doi:10.4230/lipics.stacs.2019.27 2019