Pith. sign in

REVIEW 4 major objections 5 minor 31 references

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that Independent Set Reconfiguration under Token Jumping has a kernel of size linear in k on K_{3,r}-minor-free graphs, with size at most 42k for planar graphs.

desk verdict First linear kernel for a reconfiguration problem, but the main equivalence lemma has an unproved reordering step that both theorems depend on. read the letter →

arxiv 2506.03319 v1 pith:VM4AEIEJ submitted 2025-06-03 math.CO cs.CC

Nicolas Bousquet , Daniel W. Cranston This is my paper
classification math.COcs.CC MSC 05C6905C1005C8305C85
keywords independentsetreconfigurationtokenjumpingkernelizationlinearkernelplanargraphsK_{3r}-minor-freefixed-parametertractabilityneighbourhoodcomplexity
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 proves that the Token Jumping version of Independent Set Reconfiguration (ISR-TJ) has a kernel of size linear in the number of tokens k on every $K_{3,r}$-minor-free graph: any instance given by a source and a target independent set of size $k$ can be reduced in polynomial time to an equivalent instance on a subgraph with $O(k)$ vertices. For planar graphs the bound is explicit: at most $42k$ vertices. A kernel of this size means the parameter $k$ alone determines the size of the equivalent instance, so the reconfigurability question can be decided in time exponential only in $k$. This answers a question posed in the reconfiguration survey literature and improves the previously known quadratic kernel; it is the first linear kernel for a reconfiguration problem.

What carries the argument

The argument rests on the $X$-projection decomposition, where $X=I_s\cup I_t$ and each vertex $v$ is assigned to the class $C_Y$ of vertices for which $N(v)\cap X=Y$. Classes with $|Y|\le 1$ or $|Y|\ge 3$ are bounded using degeneracy, Euler's formula, or a neighbourhood-complexity bound; the obstacle is the 2-classes. For those, the key mechanism is 'unlocking': a big 2-class is reached when at most one of its two key vertices still holds a token, and then the class's large independent set can absorb tokens. The reduction deletes vertices from big 2-classes while preserving a global set $I$ of independent vertices spread over many classes, so that unlocking one class starts a cascade that unlocks the next and eventually moves all tokens to $I$. For planar graphs the cascade is sharpened by weakly greedy and clean independent sets, which lower the size threshold for a class to be safely reduced.

What would settle it

Compute, on a family of $K_{3,r}$-minor-free graphs with $k$ fixed, the value $N_2(G)+N_3(G)$ of nonempty projection classes with two or more key neighbours; if any family makes this exceed $O(k)$, then Corollary 9, and with it the general linear kernel as proved, is false. A stronger check is to run Construction 12 on small instances and exhaustively compare token-jumping reachability between $I_s$ and $I_t$ in $G$ and in $G'$; any difference refutes the claimed equivalence of Lemma 3.

Watch

Extended reading notes

Core claim

The central claim is that, for every fixed positive integer $r$, ISR-TJ on $K_{3,r}$-minor-free graphs reduces in polynomial time to an equivalent instance on a subgraph with $O(k)$ vertices, and that on planar graphs the reduced graph has at most $42k$ vertices. The reduction keeps the same source and target sets and never adds vertices. The proof decomposes the graph by the set $X=I_s\cup I_t$: each vertex is classified by its neighbourhood $N(v)\cap X$, and the hard part is the classes whose neighbourhood meets exactly two vertices of $X$. The paper shows that classes with many such vertices can be either discarded entirely, when no token can ever reach them, or compressed through a collective argument: once one 'big' class is unlocked, a carefully chosen independent set spread over many classes lets tokens cascade through them one after another. In the planar case a refined notion of greedy independent sets reduces the per-class threshold to a constant, yielding the $42k$ bound.

Load-bearing premise

The general (non-planar) theorem depends on an external, not-yet-refereed bound on neighbourhood complexity in $K_t$-minor-free graphs; if that bound fails, the $O(k)$ control over classes with many neighbours in $X$ collapses, although the planar $42k$ result would survive because it uses Euler's formula instead.

Editorial extensions

If this is right

  • Any instance on $K_{3,r}$-minor-free graphs can be solved in time $2^{O(k)}$ times a polynomial in $n$, giving a single-exponential algorithm for a reconfiguration problem.
  • On planar graphs the reduced instance has at most $42k$ vertices, so the search space is bounded by a function of $k$ alone.
  • The reduction is closed within the graph class: the kernel of a $K_{3,r}$-minor-free graph is again $K_{3,r}$-minor-free, and the kernel of a planar graph is planar.
  • The result improves the previous quadratic kernel for token jumping on surfaces by making the dependence on $k$ linear for $K_{3,r}$-minor-free and planar inputs.

Reading between the lines

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

  • An extension the authors do not pursue: if the borrowed neighbourhood-complexity bound can be proved by elementary means or extended to wider minor-free classes, the same global cascade would likely yield linear kernels for $K_r$-minor-free or $K_{r,r}$-free graphs, which the authors leave open.
  • A testable consequence of the planar argument is that the constant $42$ is unlikely to be tight; sharper counting over key vertices could push the planar kernel size toward $4k$, a value suggested by four-colorability.
  • The unlocking-cascade pattern is a candidate template for Token Sliding reconfiguration, where no linear kernel is currently known; the planar class used here is the natural first test case.
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.

Referee Report

4 major / 5 minor

Summary. This paper studies the Token Jumping variant of Independent Set Reconfiguration (ISR-TJ), parameterized by the common size k of the source and target independent sets Is and It. The main claims are: (Main General Theorem) for every fixed positive integer r, ISR-TJ admits a kernel of size linear in k on K3,r-minor-free graphs, answering a question posed by Bousquet, Mouawad, Nishimura, and Siebertz (2024) and improving the quadratic kernel of Cranston, Muehlenthaler, and Peyrille (2024+); and (Main Planar Theorem) on planar graphs the kernel has size at most 42k. The reduction is polynomial time and outputs a subgraph of the input graph. The proof partitions the vertices outside X = Is union It into X-projection classes C1, C2, C3 according to the size of their neighborhood in X; bounds |C1| via the chromatic number and |C3| via a neighborhood-complexity result (or Euler's formula in the planar case); and then devotes the core of the paper to C2, the 2-classes. A global argument shows that one may delete vertices from 'big' 2-classes without changing the yes/no status: in the general case via helpful independent sets and Lemma 17, and in the planar case via weakly clean greedy independent sets and Lemmas 27-30. The paper is clearly organized at the macro level, and the high-level strategy differs substantially from the neighborhood-decomposition approach of previous kernels.

Significance. If the two theorems are correct, this is a substantial contribution: it yields the first linear kernel for a reconfiguration problem, resolves an open question from the survey literature, and improves the recent quadratic kernel for surfaces. The K3,r-minor-free statement is broad, and the planar bound is explicit (42k) with a polynomial-time subgraph kernel; these are precise, falsifiable claims. The paper's global treatment of the 2-classes, rather than reducing each class individually, is an original idea that may be useful beyond this problem. The paper does not ship code or machine-checked proofs, and its arguments are self-contained only up to the cited external results. The main structural lemmas, especially Lemma 17 and the planar counting argument, are presented too tersely and contain at least one unjustified step, so the results cannot yet be considered fully certified; in my assessment the issues are repairable within the scope of a revision.

major comments (4)
  1. [§2.3, Lemma 17] The minimality argument that supports claims (i) and (ii) is not valid as written. R is chosen as a shortest transformation from Is to the fixed independent set J'_0, but in claim (ii) the proposed exchange — replacing a non-adjacent jump v->w by a jump of the token on the key vertex x to w — changes the configuration in two positions (v remains occupied, x becomes empty), so the original suffix of R need not remain executable, and the resulting sequence need not reach J'_0. Thus the stated 'shorter transformation' does not contradict the stated minimality. The claim can be repaired by redefining R to be a shortest transformation that unlocks some big class, truncating at the first unlocking step, and observing that for a non-adjacent jump v->w the vertex w is adjacent to no token of the current configuration, so x->w is a valid jump and the truncated configuration is independent; but this exchange argument is absent from the text. Since the identical minimality observation is reused verbatim in Lemma 29 and Lemma 30, both the Main General Theorem and the Main Planar Theorem rest on this step. The authors should rewrite the proof of Lemma 17 with an explicit exchange and truncation argument.
  2. [§2.3, Lemma 17 (neighbor-count claim)] The claim that every big class C' has at most 2(r-1) vertices with neighbors in J'_0 \ Is is stated without the qualification that is actually needed, and its proof misapplies Lemma 15 to the final target z. If z is a key vertex of some other big class C', then z is deleted in G'', Lemma 15 does not apply to z, and every vertex of C' is adjacent to z, so the claimed bound is false for such C'. The subsequent argument only needs the bound for the class C that contains the pair {a,b}; in that case z is not a key vertex of C, and the bound |N(z) intersect C| ≤ r-1 follows from a direct K3,r-subgraph argument using the two key vertices of C and z as the side of size three. The proof should be restated with this distinction made explicit.
  3. [§3.4, Main Planar Theorem proof; §3.3, Lemma 25] The counting that produces the constant 42k is asserted too tersely at two points. In Lemma 25, the candidate set I is declared weakly Is-greedy with the justification 'we start the ordering with the vertices of C union C'' (resp. 'we begin with the vertices in a class of size at least 3'), but the required ordering conditions for weak greediness are not verified, and the final step that adds tokens from small bad classes does not specify the order in which vertices are replaced. In the final counting paragraph of the Main Planar Theorem, the step 'the total number of vertices outside I in these (big, uncolored) classes is at most 6n1' does not follow from the reduction rules as stated: an uncolored 2-class with an unimportant key vertex is not touched by Reduction Rules 1-3, so nothing in the rules bounds the number of its vertices outside I by six (a former blue class of size at least 7 that lost its color is a possible such class). The authors should either justify this charging argument or replace it with a correct one.
  4. [§3.3, Lemma 21] The proof of Lemma 21 is a compact topological argument that is not fully specified: the claim that every pair of 2-classes is either nested or incomparable, and the claim that deleting the two boundary vertices of each Gi makes the remaining classes pairwise anticomplete, require a precise argument about which pairs of vertices of two distinct classes can be adjacent in a planar drawing of the union of the classes and their key vertices. Lemma 21 (and the similar Lemma 22) underpins the construction in Lemma 25 and the transformations in Lemmas 29 and 30; a complete proof should be provided.
minor comments (5)
  1. [§3.5, Lemma 29] In the paragraph after Phase 1, the text says we 'cancel all the moves of R (except the last one which moved the token initially on x)', but earlier in the same proof the last step of R is identified, by symmetry, as moving the token initially on y (to y'). The two passages should be made consistent.
  2. [§3.4, Main Planar Theorem proof] The symbol r is reused as a counter in the final counting paragraph ('where 3k - r is the number of 2-classes with both key vertices in Is'), conflicting with the fixed parameter r from the Main General Theorem; this counter should be renamed.
  3. [§2.2, Corollary 9] The Main General Theorem depends on Theorem 18 of the arXiv preprint [7] for the bound N2(G)+N3(G) = O(k); the authors should state explicitly that this is an external result and, ideally, include a self-contained proof of the K3,r-minor-free case or verify that the constants in [7] apply to the stated parameter range.
  4. [Throughout] There are numerous typos, including 'neigbhbors' (Lemma 15), 'at leaset' (Lemma 17), 'polynmial' and 'kenel' (Section 1), 'retricted' (Section 1), and 'tranformation' (Lemma 30); a careful proofreading pass is needed.
  5. [§2.1, Lemma 5] In the proof of Lemma 5 the implicit fact used is that a vertex of C1 has at most one neighbor in Is union It, which is why tokens can be moved onto Im in arbitrary order; stating this explicitly would help the reader.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: kernel built from external minor-free bounds plus an internal unlocking argument; self-citations are contextual.

full rationale

Verdict: no significant circularity (score 1). The derivation chain is self-contained in the sense that matters here. Main General Theorem = Lemma 10 (|C1|+|C3| = O(k)) + Lemma 11/Proposition 13 and Lemma 3 (C'2 = O(k) after deleting vertices of big 2-classes, with equivalence proved in Lemma 17 by an explicit unlock-and-reach-helpful-set construction). The heavy external inputs are Kostochka-Prince degeneracy (Lemma 4, [23]) for the coloring bound and the neighborhood-complexity theorem of Beaudou et al. (Lemma 8, [7, Thm 18]) applied with A := X and s := 1, giving Corollary 9 (N2+N3 = O(k)); the planar 42k bound uses Euler's formula (Lemma 7) instead and is independent of [7]. Neither external input is by the present authors, and neither statement includes the target linear-kernel result, so these citations are independent evidence even though [7] is an unrefereed arXiv preprint; fragility of the general theorem to [7] is a correctness risk, not circularity. No fitting-then-prediction occurs: the thresholds defining 'big' (size at least chi(G)(2r-1)+1), 'helpful', 'important', and 7/5 in the planar reduction are fixed constants, not parameters fitted to instances. Self-citations ([11], [12], [13], [10], [5]) are contextual only; the paper explicitly separates its method from [13] ('we instead use a more subtle global approach, which is different from previous methods') and [12] is cited only as the source of the open question. Passages flagged as missing support or omitted details - Lemma 17's minimality assertion that 'each jump of the transformation except the last one consists of moving a token... to an adjacent vertex' (Section 2.3) and Lemma 30's 'We omit the final few moves of the transition' (Section 3.5) - are internal proof-completeness and correctness concerns about exchange arguments, not reductions of the conclusion to the hypothesis, so they do not raise the circularity score.

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

No free parameters are fitted to data; r and k are fixed inputs. The paper relies on standard graph theory theorems plus one recent external lemma [7] on neighborhood complexity. The newly defined objects (helpful independent sets, clean sets, weakly greedy sets) are internal proof devices, not new postulated entities with independent evidence.

assumptions (5)
  • standard math Kostochka-Prince bound: for r >= 6300, a K_{3,r}-minor-free graph on n >= r+3 vertices satisfies 2|E(G)| <= (r+3)(n-2)+2; hence chi(G) <= r+3.
    Used in Lemma 4 and to bound |C1| via Lemma 5 for the general theorem; the paper cites [23].
  • domain assumption Neighborhood complexity bound for K_t-minor-free graphs (Beaudou et al., arXiv:2501.08895, Theorem 18): |{N^s[v] cap A}| <= 4t(t-3)t^{2(t-1)}(s+1)^{3(t-1)}|A|.
    Used in Corollary 9 to bound N2(G)+N3(G)=O(k) for K_{3,r}-minor-free graphs. This is the main external load-bearing lemma for the general theorem.
  • standard math Euler's formula and planarity invariants: a plane graph on n vertices has at most 3n-6 edges and 2n-4 faces.
    Used in Lemmas 7 and 21 to count 2-classes and to prove the planar kernel bounds.
  • standard math Planar graphs have chromatic number at most 4 (four color theorem).
    Used in Lemma 5 to get |C1| <= 4k for the planar case.
  • domain assumption In a planar graph, the vertices of a 2-class induce a cycle or a disjoint union of paths (Remark 19).
    Derived from the K_{3,3}-free property of planar graphs; used to extract large independent sets in 2-classes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Linear Kernel for Independent Set Reconfiguration in Planar Graphs." pith.science (2026). https://pith.science/paper/VM4AEIEJ

@misc{pith2026250603319,
  author       = {Pith},
  title        = {Pith review of: A Linear Kernel for Independent Set Reconfiguration in Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VM4AEIEJ}},
  note         = {Machine review of arXiv:2506.03319}
}
abstract

Fix a positive integer $r$, and a graph $G$ that is $K_{3,r}$-minor-free. Let $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a ``token'' on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated ``token jumping'', removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ into $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kami\'nski, and Ono (2014) to be fixed-parameter tractable. That is, when $k$ is fixed, the problem can be solved in time polynomial in the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a $K_{3,r}$-minor-free graph into an equivalent problem on a ($K_{3,r}$-minor-free) graph with order $O(k)$. This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz (2024) and improves the recent quadratic kernel of Cranston, M\"{u}hlenthaler, and Peyrille (2024+). For planar graphs, we further strengthen this upper bound to get a kernel of size at most $42k$.

Figures

Figures reproduced from arXiv: 2506.03319 by the authors.

Figure 1
Figure 1. An Is-greedy indepen￾dent set, together with the trans￾formation Is I 1 2 3 4 i1 i2 j1 j2 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 3
Figure 3. The independent set I is 3-clean for Is. are the activation pairs. Is I | {z } other 2-classes x C C′ [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 5
Figure 5. — phase 1 — phase 2 — phase 3 We denote by Z the set of vertices that were involved in a move during the sequence R, excluding vertex Z y. (A vertex v is involved in a move if there exist two steps of the sequence such that one has a token on v and one has no token on v.) By (i) and (ii) above, all the vertices of Z belong to the same component of G \ (D ∪ {x, y}). So, by Lemma 15, the set N(Z) ∩ D has size at most … view at source ↗
Figures from the paper (3 more)
Figure 6
Figure 6. Figure 6: — phase 1 — phase 2 — phase 3 16 [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]
Figure 7
Figure 7. Figure 7: — phase 1 — phase 2 — phase 3 As in the proof of Lemma 29, we can argue using Lemma 17 that all the vertices Z involved in the transformation between Is and I ′ (except for the last vertex x replaced in the sequence, which is a key vertex of A) induce a connected subgr…
Figure 8
Figure 8. Figure 8: — phase 1 — phase 2 — phase 3 We omit the final few moves of the transition, since they depend on the cases described below. To complete the transformation we distinguish 3 cases. If y, y′ ∈ { / j1, j2, j3}, then we complete the tranformation with a ′′ 2 → y, b ′′ 1 → …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

31 extracted references · 19 canonical work pages

  1. [7]

    Beaudou, J

    L. Beaudou, J. Bok, F. Foucaud, D. A. Quiroz, and J.-F. Raymond. Profile and neighbourhood complexity of graphs with excluded minors and tree-structured graphs. 2025, arXiv:2501.08895

    work page arXiv 2025

  2. [1]

    F. N. Abu-Khzam, M. R. Fellows, M. A. Langston, and W. H. Suters. Crown structures for vertex cover kernelization. Theory Comput. Syst., 41(3):411–430, 2007. https://doi.org/10.1007/s00224-007-1328-0

    work page doi:10.1007/s00224-007-1328-0 2007

  3. [2]

    Alber, M

    J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363–384, 2004

    work page 2004

  4. [3]

    Bartier, N

    V. Bartier, N. Bousquet, C. Dallard, K. Lomer, and A. E. Mouawad. On girth and the parameterized complexity of token sliding and token jumping. Algorithmica, 83(9):2914–2951, 2021. doi:10.1007/S00453-021-00848-1

    work page doi:10.1007/s00453-021-00848-1 2021

  5. [4]

    Bartier, N

    V. Bartier, N. Bousquet, J. Hanna, A. E. Mouawad, and S. Siebertz. Token sliding on graphs of girth five. Algorithmica, 86(2):638–655, 2024

    work page 2024

  6. [5]

    Bartier, N

    V. Bartier, N. Bousquet, and A. E. Mouawad. Galactic token sliding. J. Comput. Syst. Sci., 136:220–248, 2023. doi:10.1016/J.JCSS.2023.03.008

    doi:10.1016/j.jcss.2023.03.008 2023

  7. [6]

    Bartier, N

    V. Bartier, N. Bousquet, and M. M¨ uhlenthaler. Independent set reconfiguration in h-free graphs. In D. Kr´ al and M. Milanic, editors, Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Gozd Martuljek, Slovenia, June 19-21, 2024, Revised Selected Papers, volume 14760 of Lecture Notes in Computer Science, pages 35–49. Spr...

    work page doi:10.1007/978-3-031-75409-8 2024

  8. [8]

    Belmonte, E

    R. Belmonte, E. J. Kim, M. Lampis, V. Mitsou, Y. Otachi, and F. Sikora. Token sliding on split graphs. Theory Comput. Syst., 65(4):662–686, 2021

    work page 2021

Show all 31 references
  1. [9]

    P. S. Bonsma, M. Kaminski, and M. Wrochna. Reconfiguring independent sets in claw-free graphs. In R. Ravi and I. L. Gørtz, editors, Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings, volume 8503 of Lectur...

    2014 doi

  2. [10]

    Bousquet, Q

    N. Bousquet, Q. Deschamps, A. Mary, A. E. Mouawad, and T. Pierron. The tape reconfiguration problem and its consequences for dominating set reconfiguration. arXiv preprint arXiv:2505.00988, 2025

    2025 arXiv

  3. [11]

    Bousquet, A

    N. Bousquet, A. Mary, and A. Parreau. Token jumping in minor-closed classes. In Fundamentals of computation theory, volume 10472 of Lecture Notes in Comput. Sci., pages 136–149. Springer, Berlin, 2017. doi:10.1007/978- 3-662-55751-8 12

    2017 doi

  4. [12]

    Bousquet, A

    N. Bousquet, A. E. Mouawad, N. Nishimura, and S. Siebertz. A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems. Apr 2022, arXiv:2204.10526

    2022 arXiv

  5. [13]

    D. W. Cranston, M. M¨ uhlenthaler, and B. Peyrille. A simple quadratic kernel for token jumping on surfaces. 2024, arXiv:2408.04743

    2024

  6. [14]

    R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput., 24(4):873–921, 1995. doi:10.1137/S0097539792228228

    1995 doi

  7. [15]

    Fabianski, M

    G. Fabianski, M. Pilipczuk, S. Siebertz, and S. Torunczyk. Progressive algorithms for domination and inde- pendence. In R. Niedermeier and C. Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany,...

    2019 doi

  8. [16]

    Guo and R

    J. Guo and R. Niedermeier. Linear problem kernels for np-hard problems on planar graphs. In L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceeding...

    2007

  9. [17]

    R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoret. Comput. Sci., 343(1-2):72–96, 2005. doi:10.1016/j.tcs.2005.05.008

    2005 doi

  10. [18]

    Hopcroft, J

    J. Hopcroft, J. Schwartz, and M. Sharir. On the complexity of motion planning for multiple independent objects; pspace- hardness of the ”warehouseman’s problem”. The International Journal of Robotics Research, 3(4):76–88,

  11. [19]

    T. Ito, M. Kami´ nski, and H. Ono. Fixed-parameter tractability of token jumping on planar graphs. In Algo- rithms and computation, volume 8889 of Lecture Notes in Comput. Sci., pages 208–219. Springer, Cham, 2014. doi:10.1007/978-3-319-13075-0 17

    2014 doi

  12. [20]

    T. Ito, M. Kami´ nski, H. Ono, A. Suzuki, R. Uehara, and K. Yamanaka. On the parameterized complexity for token jumping on graphs. In T. V. Gopal, M. Agrawal, A. Li, and S. B. Cooper, editors, Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014...

    2014 doi

  13. [21]

    Joret and C

    G. Joret and C. Rambaud. Neighborhood complexity of planar graphs. 2023. doi:10.1007/s00493-024-00110-6

    2023 doi

  14. [22]

    Kaminski, P

    M. Kaminski, P. Medvedev, and M. Milanic. Complexity of independent set reconfigurability problems. Theor. Comput. Sci., 439:9–15, 2012. doi:10.1016/J.TCS.2012.03.004

    2012 doi

  15. [23]

    A. V. Kostochka and N. Prince. Dense graphs have K3,t minors. Discrete Math., 310(20):2637–2654, 2010. doi:10.1016/j.disc.2010.03.026

    2010 doi

  16. [24]

    Lokshtanov and A

    D. Lokshtanov and A. E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Trans. Algorithms, 15(1):7:1–7:19, 2019. doi:10.1145/3280825

    2019 doi

  17. [25]

    Lokshtanov, A

    D. Lokshtanov, A. E. Mouawad, F. Panolan, M. S. Ramanujan, and S. Saurabh. Reconfiguration on sparse graphs. J. Comput. Syst. Sci., 95:122–131, 2018. doi:10.1016/J.JCSS.2018.02.004

    2018 doi

  18. [26]

    A. E. Mouawad, N. Nishimura, V. Raman, N. Simjour, and A. Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmica, 78(1):274–297, 2017. https://doi.org/10.1007/s00453-016-0159-2

    2017 doi

  19. [27]

    Nishimura

    N. Nishimura. Introduction to reconfiguration. Algorithms (Basel), 11(4):Paper No. 52, 25, 2018

    2018

  20. [28]

    van den Heuvel

    J. van den Heuvel. The complexity of change. In Surveys in combinatorics 2013, volume 409 of London Math. Soc. Lecture Note Ser., pages 127–160. Cambridge Univ. Press, Cambridge, 2013, arXiv:1312.2816

    2013 arXiv

  21. [29]

    M. Wrochna. Reconfiguration in bounded bandwidth and tree-depth. J. Comput. Syst. Sci., 93:1–10, 2018. doi:10.1016/J.JCSS.2017.11.003

    2018 doi

  22. [30]

    Zuckerman

    D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3(6):103–128, 2007. doi:10.4086/toc.2007.v003a006. 20

    2007 doi

  23. [1984]

    https://doi.org/10.1177/027836498400300405

    doi

Pith tools

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