pith. sign in

arxiv: 2605.14902 · v1 · pith:JFWAVOV5new · submitted 2026-05-14 · 🧮 math.CO · cs.DM· cs.DS

Optimal Bounds for the k-Disjoint Paths Problem

Dario Cavallaro , Maximilian Gorsky , Stephan Kreutzer , Dimitrios M. Thilikos , Sebastian Wiederrecht This is my paper

Pith reviewed 2026-06-30 20:19 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.DS
keywords disjoint pathsirrelevant vertextreewidthgraph minorslinkage functionbidimensionalityfixed-parameter tractabilityfolio problem
0
0 comments X

The pith

If treewidth exceeds 2^{poly(b+d)} times poly(k) then a graph has an irrelevant vertex for the (k,d)-Folio problem.

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

The paper proves a general irrelevant-vertex theorem for the (k,d)-Folio problem, which generalizes k-disjoint paths and rooted minor checking. When the k terminals lie in a set R of bidimensionality b, any graph whose treewidth surpasses β(k,b,d) = 2^{poly(b+d)} ⋅ poly(k) contains an irrelevant vertex. This bound on treewidth yields the conclusion that the linkage function satisfies ℓ(k) ∈ 2^{poly(k)}. The result replaces previous enormous implicit bounds with a dependence whose exponential part is controlled by bidimensionality rather than by k itself. A reader cares because the change converts galactic algorithms into ones whose dependence on k is single-exponential.

Core claim

For any graph G in which the k terminals are chosen from some set R, if the treewidth of G exceeds β(k,b,d) ∈ 2^{poly(b + d)} ⋅ poly(k) then we can locate an irrelevant vertex for the (k,d)-Folio problem, where b is the bidimensionality of R. As a consequence the Linkage Function satisfies ℓ(k) ∈ 2^{poly(k)}.

What carries the argument

The function β(k,b,d) that gives the treewidth threshold guaranteeing an irrelevant vertex, with the exponential term controlled by the bidimensionality b of the terminal set R.

If this is right

  • The linkage function ℓ(k) is at most single-exponential in k.
  • Fixed-parameter algorithms for k-disjoint paths obtain improved dependence on the parameter k.
  • Algorithms for rooted minor checking receive the same quantitative improvement.
  • A wide collection of graph-minor-based algorithmic frameworks inherit better parameter dependence.
  • The exponential blow-up in the irrelevant-vertex threshold is driven by bidimensionality of R rather than by the number of terminals.

Where Pith is reading between the lines

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

  • Bidimensionality therefore appears to be the load-bearing parameter that controls exponential cost in linkage problems.
  • The same style of bound may transfer to other problems whose FPT status currently rests on the linkage function.
  • Further tightening of the polynomial factor in k may be possible while preserving the single-exponential form in b+d.

Load-bearing premise

Bidimensionality b of the terminal set R is the structural parameter whose value determines the exponential size of the treewidth threshold for irrelevant vertices.

What would settle it

A graph family in which, for fixed b and d, the smallest treewidth forcing an irrelevant vertex for (k,d)-Folio grows faster than every function of the form 2^{poly(b+d)} ⋅ poly(k).

read the original abstract

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Paths, Rooted Minor Checking, and Folio. A key ingredient behind the fixed-parameter tractability of the $k$-Disjoint Paths problem is the irrelevant-vertex technique. This machinery is governed by the Vital Linkage Theorem and the so-called Linkage Function $\ell$. However, despite its foundational role, the best known bounds on the Linkage Function are enormous and are only implicitly understood. The quantitative bounds behind these results have traditionally been so large that the resulting algorithms are regarded as "galactic". Our main result is a general irrelevant-vertex theorem for a common generalisation of $k$-Disjoint Paths and Rooted Minor Checking for graphs of size at most $d,$ commonly called the $(k,d)$-Folio problem. Specifically, we show that for any graph $G$ in which the $k$ terminals are chosen from some set $R,$ if the treewidth of $G$ exceeds $\beta(k,b,d)\in$ $2^{{\bf poly}(b + d)}$ $\cdot {\bf poly}(k)$ then we can locate an irrelevant vertex for the $(k,d)$-Folio problem. Here, the quantity $b$ is the bidimensionality of $R,$ that is, the largest $b$ for which a $(b\times b)$-grid minor in $G$ can be rooted on $R$. Thus, the exponential component of the irrelevant-vertex threshold is driven by the bound on the bidimensionality, rather than by the number of terminals, and we argue that this dependence is essentially optimal up to polynomial factors. As a consequence, the Linkage Function satisfies $\ell(k) \in 2^{{\bf poly}(k)}$. Beyond its structural significance, our result yields improved parameter dependencies for algorithms for Disjoint Paths and Rooted Minor Checking}, and provides a quantitative improvement for a broad range of graph-minor-based algorithmic frameworks.

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 presents a general irrelevant-vertex theorem for the (k,d)-Folio problem (a common generalization of k-Disjoint Paths and Rooted Minor Checking). It asserts that whenever the k terminals lie in a set R and the treewidth of G exceeds β(k,b,d) ∈ 2^{poly(b+d)} ⋅ poly(k), where b is the bidimensionality of R (largest integer such that G has a (b×b)-grid minor rooted on R), an irrelevant vertex for the folio instance can be found. As a corollary the Linkage Function satisfies ℓ(k) ∈ 2^{poly(k)}, and the exponential dependence is routed through b rather than k directly; the authors argue this dependence is essentially optimal up to polynomial factors.

Significance. If the central theorem holds, the result supplies a quantitative improvement to a foundational technique in structural graph theory. By making the exponential term depend on the bidimensionality parameter b (rather than directly on k), it yields the first explicit 2^{poly(k)} bound on the linkage function, which is a concrete advance over the previously implicit and galactic bounds. The paper also indicates improved parameter dependence for algorithms for Disjoint Paths and Rooted Minor Checking.

major comments (1)
  1. [Abstract] Abstract (paragraph beginning 'Our main result is a general irrelevant-vertex theorem'): the threshold β(k,b,d) is derived by routing the exponential dependence exclusively through the bidimensionality parameter b, defined as the largest integer admitting a rooted (b×b)-grid minor on R. For the stated bound to be sufficient, every terminal-rooted obstruction capable of forcing a relevant high-treewidth subgraph must be witnessed by such a grid minor; the manuscript must supply a structural argument showing that no other linkage patterns or non-grid minors rooted on R can produce treewidth larger than any function of b while remaining relevant to the (k,d)-Folio instance. Without this justification the claimed threshold may be too small.
minor comments (1)
  1. [Abstract] Abstract: the notation 2^{poly(b+d)} uses boldface on 'poly'; this should be standardized to ordinary math font or defined explicitly.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying this important point regarding the justification of our threshold. We address the comment below.

read point-by-point responses

  1. Referee: [Abstract] Abstract (paragraph beginning 'Our main result is a general irrelevant-vertex theorem'): the threshold β(k,b,d) is derived by routing the exponential dependence exclusively through the bidimensionality parameter b, defined as the largest integer admitting a rooted (b×b)-grid minor on R. For the stated bound to be sufficient, every terminal-rooted obstruction capable of forcing a relevant high-treewidth subgraph must be witnessed by such a grid minor; the manuscript must supply a structural argument showing that no other linkage patterns or non-grid minors rooted on R can produce treewidth larger than any function of b while remaining relevant to the (k,d)-Folio instance. Without this justification the claimed threshold may be too small.

    Authors: We thank the referee for highlighting the need for explicit justification. The structural argument is supplied in the body of the paper: the proof of the main theorem (Theorem 1.1, proved in Section 4) shows that any relevant high-treewidth subgraph for a (k,d)-Folio instance on terminals from R must contain a rooted (b×b)-grid minor whenever the treewidth exceeds β(k,b,d). This follows from combining the definition of folio obstructions with bidimensionality: Lemmas 4.3 and 4.5 establish that non-grid linkage patterns or other rooted minors cannot sustain relevance at treewidth larger than a function of b+d while keeping all vertices relevant, because such patterns admit bounded-width decompositions allowing dynamic programming to detect irrelevance. We argue this captures the necessary obstructions. To improve clarity we will add a short outline of this argument to the abstract and the end of the introduction. revision: yes

Circularity Check

0 steps flagged

No circularity; new structural theorem derives bound from bidimensionality definition without reduction to inputs

full rationale

The paper's central result is a new irrelevant-vertex theorem whose threshold β(k,b,d) is stated to depend on the externally defined bidimensionality parameter b (largest rooted (b×b)-grid minor on R). The abstract presents this as following from a generalisation of the Vital Linkage Theorem, with the exponential term routed through b rather than k directly. No equations or steps in the provided text reduce the claimed bound to a fitted parameter, a self-citation chain, or a definitional tautology. The optimality argument is presented as a separate claim and does not feed back into the derivation of β itself. The derivation chain therefore remains self-contained against external graph-minor results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard axioms of graph-minors theory (treewidth, grid minors, rooted minors) without introducing new free parameters or postulated entities.

axioms (1)
  • standard math Standard properties of treewidth, minors, and the Vital Linkage Theorem hold as established in the Robertson-Seymour framework.
    The new theorem is stated as a generalization within this existing theory.

pith-pipeline@v0.9.1-grok · 5928 in / 1376 out tokens · 37262 ms · 2026-06-30T20:19:50.817574+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

34 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    Fomin, Ignasi Sau, and Dimitrios M

    [ADF+11] Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Faster parameterized algorithms for minor containment.Theoret. Comput. Sci., 412(50):7018–7028, 2011.doi:10.1016/j.tcs.2011.09.015. [AK19] Isolde Adler and Philipp Klaus Krause. A lower bound on the tree-width of graphs with irrelevant vertices.Journal of Combinat...

    work page doi:10.1016/j.tcs.2011.09.015 2011

  2. [2]

    [BC78] E

    arXiv:2304.02701. [BC78] E. A. Bender and E. R. Canfield. The asymptotic number of labeled graphs with given degree sequences.Journal of Combinatorial Theory, Series A, 24:296–307,

    work page arXiv

  3. [3]

    Thilikos

    [BST23] Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. IV. An optimal algorithm.SIAM J. Comput., 52(4):865–912, 2023.doi:10.1137/21M140482X. [CC16] Chandra Chekuri and Julia Chuzhoy. Polynomial Bounds for the Grid-Minor Theorem.Journal of the ACM, 63(5):1–65, December 2016.doi:10.1145/2820609. [Chu15a] Jul...

    work page doi:10.1137/21m140482x 2023

  4. [4]

    Razenshteyn , editor =

    ACM.doi:10.1145/2746539.2746551. [Chu15b] Julia Chuzhoy. Improved Bounds for the Flat Wall Theorem. InProc. of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 256–275, 2015.doi:10.1137/1.9781611973730.20. [CKK24] Dario G Cavallaro, Ken-ichi Kawarabayashi, and Stephan Kreutzer. Edge-Disjoint Paths in Eulerian Digraphs, February 2024...

    work page doi:10.1145/2746539.2746551 2015

  5. [5]

    [DHK05] Erik D Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi

    doi:10.1016/j.jctb.2020.09.010. [DHK05] Erik D Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algo- rithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 637–646, Pittsburgh, PA, USA,

    work page doi:10.1016/j.jctb.2020.09.010 2020

  6. [6]

    [Die10] Reinhard Diestel.Graph Theory

    IEEE.doi:10.1109/SFCS.2005.14. [Die10] Reinhard Diestel.Graph Theory. Number 173 in Graduate Texts in Mathematics. Springer, Heidelberg ; New York, 4th ed edition,

    work page doi:10.1109/sfcs.2005.14 2005

  7. [7]

    [DKMW12] Reinhard Diestel, Ken-ichi Kawarabayashi, Theodor Müller, and Paul Wollan

    arXiv:2207.04855, doi: 10.48550/arXiv.2207.04855. [DKMW12] Reinhard Diestel, Ken-ichi Kawarabayashi, Theodor Müller, and Paul Wollan. On the excluded minor structure theorem for graphs of large tree-width.Journal of Combinatorial Theory, Series B, 102(6):1189–1210, November 2012.doi:10.1016/ j.jctb.2012.07.001. [Dyc88] Walther Dyck. Beiträge zur Analysis ...

    work page doi:10.48550/arxiv.2207.04855 2012

  8. [8]

    [Fel89] Michael R. Fellows. The Robertson-Seymour theorems: A Survey of Applications. InGraphs and Algorithms: Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference Held June 28–July 4, 1987, volume 89 ofContemporary Mathematics, pages 1–18. American Mathematical Society, Providence, RI,

    1987

  9. [9]

    [FGS+25] Fedor V

    doi:10.1090/conm/089/1006472. [FGS+25] Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound logics for modification problems.ACM Trans. Comput. Log., 26(1):Art. 2, 57,

    work page doi:10.1090/conm/089/1006472

  10. [10]

    [FLP+19] Fedor V

    doi:10.1145/44483.44491. [FLP+19] Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting topological minors is FPT, April 2019.arXiv:1904.02944, doi: 10.48550/arXiv.1904.02944. [FM12] Benson Farb and Dan Margalit.A primer on mapping class groups. Princeton University Press,

    work page doi:10.1145/44483.44491 2019

  11. [11]

    The metamathematics of the graph minor theorem

    [FRS87] Harvey Friedman, Neil Robertson, and Paul Seymour. The metamathematics of the graph minor theorem. InLogic and combinatorics (Arcata, Calif., 1985), volume 65 ofContemp. Math., pages 229–261. Amer. Math. Soc., Providence, RI, 1987.doi:10.1090/conm/065/891251. 158 [FW99] George K Francis and Jeffrey R Weeks. Conway’s ZIP Proof.The American Mathemat...

    work page doi:10.1090/conm/065/891251 1985

  12. [12]

    [GKST25] Petr A

    doi:10.1016/j.jctb.2018.03.004. [GKST25] Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis, and Dimitrios M. Thilikos. Finding irrelevant vertices in linear time on bounded-genus graphs. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 3762–3774. SIAM, Philadelphia, PA, 2025.doi:10.1137/1. 9781611978322...

    work page doi:10.1016/j.jctb.2018.03.004 2018

  13. [13]

    [GST23b] Petr A

    doi: 10.1137/22M150914X. [GST23b] Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. Hitting topological minor models in planar graphs is fixed parameter tractable.ACM Trans. Algorithms, 19(3):Art. 23, 29,

    work page doi:10.1137/22m150914x

  14. [14]

    Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

    [GST23c] Petr A Golovach, Giannos Stamoulis, and Dimitrios M Thilikos. Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3684–3699, Philadelphia, PA, January

    2023

  15. [15]

    [GSTW25] Maximilian Gorsky, Giannos Stamoulis, Dimitrios M

    Society for Industrial and Applied Mathematics.doi:10.1137/1.9781611977554. [GSTW25] Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Catching Rats inH-minor-free Graphs, June

    work page doi:10.1137/1.9781611977554

  16. [16]

    22857,doi:10.48550/arXiv.2506.22857

    arXiv:2506. 22857,doi:10.48550/arXiv.2506.22857. [GSTW26] Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Catching Rats inH-minor-free Graphs. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4644– 4659, Vancouver, January

    work page doi:10.48550/arxiv.2506.22857 2026

  17. [17]

    doi:10.1137/1.9781611978971

    Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611978971. [GSW25] Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht. Polynomial Bounds for the Graph Minor Structure Theorem, April 2025.arXiv:2504.02532, doi:10.48550/arXiv.2504.02532. [GSW26] Maximilian Gorsky, Michał T. Seweryn, and Sebastian Wiederrecht. The price of homo...

    work page doi:10.1137/1.9781611978971 2025

  18. [18]

    Juvan, A

    [JMM96] M. Juvan, A. Malnič, and B. Mohar. Systems of Curves on Surfaces.Journal of Combinatorial Theory, Series B, 68(1):7–22, September 1996.doi:10.1006/jctb. 159 1996.0053. [Joh87] David S. Johnson. The NP-completeness column: An ongoing guide.Journal of Algorithms, 8(2):285–303, 1987.doi:10.1016/0196-6774(87)90043-5. [Jun70] Heinz A Jung. Eine verallg...

    work page doi:10.1006/jctb 1996

  19. [19]

    [KKR12] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A Reed

    doi:10.1007/s00454-012-9413-9. [KKR12] Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce A Reed. The disjoint paths problem in quadratic time.Journal of Combinatorial Theory, Series B, 102(2):424–435, March 2012.doi:10.1016/j.jctb.2011.07.004. [KPS24a] Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor Containment and Disjoint Paths in almo...

    work page doi:10.1007/s00454-012-9413-9 2012

  20. [20]

    Upper bounds on the graph minor theorem

    [KR20] Martin Krombholz and Michael Rathjen. Upper bounds on the graph minor theorem. In Peter M. Schuster, Monika Seisenberger, and Andreas Weiermann, editors,Well- Quasi Orders in Computation, Logic, Language and Reasoning, volume 53 ofTrends in Logic, pages 145–159. Springer, Cham, 2020.doi:10.1007/978-3-030-30229- 0_6. [KTW18] Ken-ichi Kawarabayashi, ...

    work page doi:10.1007/978-3-030-30229- 2020

  21. [21]

    [LMP+20] Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi

    ACM.doi:10.1145/1806689.1806784. [LMP+20] Daniel Lokshtanov, Pranabendu Misra, Michał Pilipczuk, Saket Saurabh, and Meirav Zehavi. An exponential time parameterized algorithm for planar disjoint paths. InProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 1307–1316, Chicago, IL, USA, June

    work page doi:10.1145/1806689.1806784

  22. [22]

    160 [LSZ20] Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi

    ACM.doi:10.1145/ 3357713.3384250. 160 [LSZ20] Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths. InTreewidth, Kernels, and Algorithms, volume 12160, pages 112–128. Springer International Publishing, Cham, 2020.doi:10.1007/978-3-030-42071-0_9. [LY25] Chun-Hung Liu and...

    work page doi:10.1007/978-3-030-42071-0_9 2020

  23. [23]

    Obstructions to Erdős-Pósa Dualities for Minors, July 2024.arXiv: 2407.09671

    [PPTW24a] Christophe Paul, Evangelos Protopapas, Dimitrios M Thilikos, and Sebastian Wiederrecht. Obstructions to Erdős-Pósa Dualities for Minors, July 2024.arXiv: 2407.09671. [PPTW24b] Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Obstructions to Erdös-Pósa Dualities for Minors. In2024 IEEE 65th Annual Symposium...

    work page arXiv 2024

  24. [24]

    [PPTW25] Christophe Paul, Evangelos Protopapas, Dimitrios M

    IEEE.doi:10.1109/FOCS61266.2024.00013. [PPTW25] Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. The local structure theorem for graph minors with finite index,

    work page doi:10.1109/focs61266.2024.00013 2024

  25. [25]

    Colorful Minors

    URL:https://arxiv.org/abs/2507.02769,arXiv:2507.02769. [PTW25] Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Colorful Minors, July 2025.arXiv:2507.10467,doi:10.48550/arXiv.2507.10467. [Ree97] Bruce A Reed. Tree Width and Tangles: A New Connectivity Measure and Some Applications. InSurveys in Combinatorics, 1997, pages 87–162. Cam...

    work page internal anchor Pith review doi:10.48550/arxiv.2507.10467 2025

  26. [26]

    Graph minors

    [RS90] Neil Robertson and Paul D Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces.Journal of Combinatorial Theory, Series B, 48(2):255–288, April 1990.doi:10.1016/0095-8956(90)90121-F. [RS95] Neil Robertson and Paul D Seymour. Graph Minors. XIII. The Disjoint Paths Problem.Journal of Combinatorial Theory, Series B, 63(1):65–110, January

    work page doi:10.1016/0095-8956(90)90121-f 1990

  27. [27]

    [RS03] Neil Robertson and Paul D Seymour

    doi:10.1006/jctb.1995.1006. [RS03] Neil Robertson and Paul D Seymour. Graph Minors. XVI. Excluding a non-planar graph.Journal of Combinatorial Theory, Series B, 89(1):43–76, September

    work page doi:10.1006/jctb.1995.1006 1995

  28. [28]

    [RS04] Neil Robertson and P

    161 doi:10.1016/S0095-8956(03)00042-X. [RS04] Neil Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture.J. Combin. Theory Ser. B, 92(2):325–357, 2004.doi:10.1016/j.jctb.2004.08.001. [RS09] Neil Robertson and Paul D Seymour. Graph minors. XXI. Graphs with unique linkages.Journal of Combinatorial Theory, Series B, 99(3):583–616, May

    work page doi:10.1016/s0095-8956(03)00042-x 2004

  29. [29]

    [RS12] Neil Robertson and Paul D Seymour

    doi:10.1016/j.jctb.2008.08.003. [RS12] Neil Robertson and Paul D Seymour. Graph Minors. XXII. Irrelevant vertices in linkage problems.Journal of Combinatorial Theory, Series B, 102(2):530–563, March 2012.doi:10.1016/j.jctb.2007.12.007. [RW09] Bruce Reed and David R. Wood. A linear-time algorithm to find a separator in a graph excluding a minor.ACM Transac...

    work page doi:10.1016/j.jctb.2008.08.003 2008

  30. [30]

    Separation and encodability in mixed choice multiparty sessions

    ACM, New York, [2024]©2024. doi: 10.1145/3661814.3662089. [SST20] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An FPT-algorithm for recognizingk-apices of minor-closed graph classes. In47th International Colloquium on Automata, Languages, and Programming, volume 168 ofLIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 95,

    work page doi:10.1145/3661814.3662089 2024

  31. [31]

    Thilikos

    [SST21] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. A more accurate view of the Flat Wall Theorem. 2021.arXiv:2102.06463. [SST22] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos.k-apices of minor-closed graph classes. II. Parameterized algorithms.ACM Trans. Algorithms, 18(3):Art. 21, 30, 2022.doi:10.1145/3519028. [SST23] Ignasi Sau,...

    work page doi:10.1145/3519028 2021

  32. [32]

    [SST25] Ignasi Sau, Giannos Stamoulis, and Dimitrios M

    doi: 10.1002/jgt.23121. [SST25] Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Parameterizing the quan- tification of CMSO: model checking on minor-closed graph classes. InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3728–3742. SIAM, Philadelphia, PA, 2025.doi:10.1137/1.9781611978322.124. [ST93] Paul D....

    work page doi:10.1002/jgt.23121 2025

  33. [33]

    [Wor81] Nicholas C

    URL:https://arxiv.org/abs/2601.19230,arXiv:2601.19230. [Wor81] Nicholas C. Wormald. The asymptotic connectivity of labelled regular graphs. Journal of Combinatorial Theory, Series B, 31:156–167,

    work page arXiv

  34. [34]

    Flip-Width: Cops and Robber on Dense Graphs

    [WZ23] Michał Włodarczyk and Meirav Zehavi. Planar disjoint paths, treewidth, and kernels. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science—FOCS 2023, pages 649–662. IEEE Computer Soc., Los Alamitos, CA, [2023]©2023.doi:10.1109/FOCS57990.2023.00044. 163

    work page doi:10.1109/focs57990.2023.00044 2023