Computing Twin-Width via Treedepth and Vertex Integrity

Mathis Rocton; Robert Ganian

arxiv: 2606.20331 · v1 · pith:ME2TSSIInew · submitted 2026-06-18 · 💻 cs.DS · cs.CC

Computing Twin-Width via Treedepth and Vertex Integrity

Robert Ganian , Mathis Rocton This is my paper

Pith reviewed 2026-06-26 15:19 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords twin-widthtreedepthvertex integrityparameterized algorithmscontraction sequencesfixed-parameter tractabilityapproximation algorithms

0 comments

The pith

Approximating twin-width is fixed-parameter tractable parameterized by treedepth, and exact computation of twin-width is fixed-parameter tractable parameterized by vertex integrity.

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

The paper shows that approximating twin-width becomes fixed-parameter tractable when the parameter is treedepth, via a reduction that uses oriented twin-width as an intermediate. It further proves that exact computation of twin-width, including optimal contraction sequences, is fixed-parameter tractable when parameterized by vertex integrity. These are the first such algorithms that move beyond parameterizations based solely on deletion distance. The results matter because twin-width controls the tractability of first-order model checking on broad graph classes, so computing the parameter itself unlocks new algorithmic applications.

Core claim

Approximating twin-width is fixed-parameter tractable when parameterized by treedepth, and computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.

What carries the argument

Oriented twin-width, used as an intermediate parameter in the reduction that transfers the FPT approximation guarantee from treedepth back to standard twin-width.

If this is right

Approximation algorithms for twin-width now exist under a parameterization that is not deletion distance.
Exact optimal contraction sequences can be computed in FPT time on all graphs whose vertex integrity is bounded by a constant.
First-order model-checking algorithms that rely on small twin-width can now be instantiated on input graphs whose treedepth is small even if their twin-width is unknown in advance.
The set of parameters that admit non-trivial algorithms for twin-width has expanded beyond deletion-distance measures.

Where Pith is reading between the lines

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

The same oriented-twin-width reduction might be reusable for other parameters that are FPT-incomparable with deletion distance.
Practical implementations could first compute vertex integrity or treedepth and then decide whether to invoke the exact or the approximation routine.
If vertex integrity is small on real-world instances, the exact algorithm could become the default method for obtaining contraction sequences.

Load-bearing premise

The reduction via oriented twin-width preserves the approximation guarantee for standard twin-width without introducing non-FPT factors or requiring additional unstated conditions on the input graphs.

What would settle it

An explicit family of graphs with bounded treedepth on which no FPT-time algorithm can produce a constant-factor approximation to twin-width, or on which the oriented-twin-width reduction fails to yield a valid approximation for the original parameter.

read the original abstract

Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.

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

Twin-width approximation is FPT under treedepth via oriented variant and exact computation is FPT under vertex integrity; the reduction step needs explicit FPT bounds to confirm the claims.

read the letter

The paper's core contribution is two new FPT results for twin-width: an approximation algorithm parameterized by treedepth, and an exact algorithm parameterized by vertex integrity. These are the first such results that move past deletion-distance parameters, and the abstract positions them as breaking a prior barrier in the area.

The work is useful in showing how oriented twin-width can serve as an intermediate for the treedepth case, giving some concrete evidence that the oriented version may be more tractable. The claims are stated clearly as algorithmic results rather than fitted or self-referential ones.

The soft spot is the reduction from oriented twin-width back to standard twin-width in the approximation result. For the overall procedure to remain FPT, the reduction must run in f(treedepth) time and convert an alpha-approximation without a ratio blow-up that depends on n or introduces extra exponential dependence on the parameter. The stress-test note flags this correctly; the abstract asserts the reduction works but does not supply the explicit runtime or ratio bounds here. If the full proofs contain parameter-preserving bounds, the result stands; if not, the FPT claim would need qualification.

Citation patterns look ordinary for the field and there are no visible circularities or invented entities. The paper targets researchers in parameterized complexity who work on width parameters and first-order model checking. A reader looking for new parameterizations of twin-width will get value from the specific claims.

It deserves peer review because the results are concrete enough to be checked in detail and could affect algorithm design if the reduction holds.

Referee Report

1 major / 0 minor

Summary. The manuscript claims two algorithmic results on twin-width: (1) approximating twin-width is fixed-parameter tractable when parameterized by treedepth, obtained by first approximating oriented twin-width and reducing back; (2) computing twin-width exactly is fixed-parameter tractable when parameterized by vertex integrity. These are presented as breaking the barrier of deletion-distance parameterizations and as the first non-trivial FPT algorithm for optimal contraction sequences.

Significance. If the claims hold with the required FPT guarantees, the results would be significant: they supply the first FPT approximation and exact algorithms for twin-width under treedepth and vertex integrity, respectively, and give constructive evidence that oriented twin-width may be algorithmically more tractable than the standard variant.

major comments (1)

[Abstract / proof of the treedepth result] The central claim of an FPT approximation for twin-width parameterized by treedepth rests on the reduction from oriented twin-width back to standard twin-width preserving both the approximation ratio (with blow-up g(α) independent of n) and the FPT runtime bound. The abstract asserts that the reduction works, but no explicit statement of the ratio function g or the runtime dependence on treedepth is supplied; if either depends on n or introduces an extra exponential factor in the parameter, the overall algorithm is not FPT. This point is load-bearing for the first result.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the importance of explicitly verifying the FPT properties of the reduction from oriented twin-width back to twin-width. We address this point directly below.

read point-by-point responses

Referee: [Abstract / proof of the treedepth result] The central claim of an FPT approximation for twin-width parameterized by treedepth rests on the reduction from oriented twin-width back to standard twin-width preserving both the approximation ratio (with blow-up g(α) independent of n) and the FPT runtime bound. The abstract asserts that the reduction works, but no explicit statement of the ratio function g or the runtime dependence on treedepth is supplied; if either depends on n or introduces an extra exponential factor in the parameter, the overall algorithm is not FPT. This point is load-bearing for the first result.

Authors: The manuscript provides the full details of the reduction in the body (following the oriented twin-width approximation). The reduction is a polynomial-time procedure that produces a twin-width approximation ratio g(α) depending only on α (independent of n) and preserves the FPT runtime bound in the treedepth parameter with no additional exponential factors in the parameter. While the abstract does not name the explicit g or runtime function, the proof establishes both required properties. We will revise the abstract to include an explicit statement of these dependencies. revision: yes

Circularity Check

0 steps flagged

No circularity; new FPT algorithms presented without self-referential reductions

full rationale

The paper states two main algorithmic results: FPT approximation of twin-width parameterized by treedepth (via oriented twin-width) and exact FPT computation parameterized by vertex integrity. These are presented as constructive algorithmic contributions with no equations, parameters fitted to data, or derivations that reduce to the inputs by construction. The reduction via oriented twin-width is described as a proof technique yielding new evidence, not as a self-citation chain or ansatz smuggled from prior work by the same authors. No load-bearing uniqueness theorems or renamings of known results appear. The derivation chain consists of standard parameterized algorithm design steps that remain independent of the target claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from parameterized complexity and graph theory with no visible free parameters, invented entities, or ad-hoc axioms in the abstract.

axioms (1)

standard math Standard definitions of fixed-parameter tractability, treedepth, vertex integrity, twin-width, and oriented twin-width.
These are established concepts invoked to state the FPT claims.

pith-pipeline@v0.9.1-grok · 5696 in / 1092 out tokens · 30042 ms · 2026-06-26T15:19:53.469604+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 21 canonical work pages

[1]

Computing twin-width parameterized by the feedback edge number

1 Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing twin-width parameterized by the feedback edge number. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volume 289 ofLIPIcs...

2024
[2]

2 Jakub Balabán, Robert Ganian, and Mathis Rocton

URL: https://doi.org/10.4230/LIPIcs.STACS.2024.7,doi:10.4230/LIPICS.STACS.2024.7. 2 Jakub Balabán, Robert Ganian, and Mathis Rocton. Twin-width meets feedback edges and vertex integrity. In Édouard Bonnet and Pawel Rzazewski, editors,19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, Univer...

work page doi:10.4230/lipics.stacs.2024.7 2024
[3]

3 Jakub Balabán and Petr Hlinený

URL: https: //doi.org/10.4230/LIPIcs.IPEC.2024.3,doi:10.4230/LIPICS.IPEC.2024.3. 3 Jakub Balabán and Petr Hlinený. Twin-width is linear in the poset width. In Petr A. Golovach and Meirav Zehavi, editors,16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 6:1–6:...

work page doi:10.4230/lipics.ipec.2024.3 2024
[4]

9 Hans L

URL:https: //doi.org/10.7155/jgaa.00597,doi:10.7155/JGAA.00597. 9 Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Preprocessing for treewidth: A combinatorial analysis through kernelization.SIAM J. Discret. Math., 27(4):2108–2142,

work page doi:10.7155/jgaa.00597
[5]

10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

doi:10.1137/120903518. 10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1977–1996. SIAM, 2021.doi:10.1137/1.9781611976465.118. 11 Édouard Bon...

work page doi:10.1137/120903518 2021
[6]

13 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk

doi:10.1145/ 3519935.3520037. 13 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk. Twin-width IV: ordered graphs and matrices.J. ACM, 71(3):21,

arXiv
[7]

14 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé

doi:10.1145/3651151. 14 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Twin- width V: linear minors, modular counting, and matrix multiplication. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors,40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-...

work page doi:10.1145/3651151 2023
[8]

16 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

doi:10.1137/1.9781611977073.45. 16 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.J. ACM, 69(1):3:1–3:46, 2022.doi:10.1145/3486655. 17 Domagoj Bradač, Jacob Fox, and Benny Sudakov. The growth rate of multicolor ramsey numbers of 3-graphs.Research in the Mathematical Sciences, 11(3):52,

work page doi:10.1137/1.9781611977073.45 2022
[9]

10 Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M.M

doi:10.1007/978-3-319-21275-3. 19 Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan. Linear layouts revisited: Stacks, queues, and exact algorithms. In33rd Annual European Symposium on Algorithms (ESA 2025), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page doi:10.1007/978-3-319-21275-3 2025
[10]

20 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics

URL:https://www.arxiv.org/abs/2508.16319. 20 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer,

arXiv
[11]

Downey and Michael R

21 Rodney G. Downey and Michael R. Fellows.Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.doi:10.1007/978-1-4471-5559-1. 22 Pål Grønås Drange, Markus S. Dregi, and Pim van ’t Hof. On the computational complexity of vertex integrity and component order connectivity.Algorithmica, 76(4):1181–1202,

work page doi:10.1007/978-1-4471-5559-1 2013
[12]

23 Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak

URL:https://doi.org/10.1007/s00453-016-0127-x,doi:10.1007/S00453-016-0127-X. 23 Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints.Artif. Intell., 300:103561,

work page doi:10.1007/s00453-016-0127-x
[13]

24 Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon

URL: https://doi.org/10.1016/ j.artint.2021.103561,doi:10.1016/J.ARTINT.2021.103561. 24 Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A unifying framework for characterizing and computing width measures. In Mark Braverman, editor,13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 202...

work page doi:10.1016/j.artint.2021.103561 2021
[14]

26 Paul Erdos and Richard Rado

arXiv:2308.03967. 26 Paul Erdos and Richard Rado. Combinatorial theorems on classifications of subsets of a given set.Proceedings of the London mathematical Society, 3(1):417–439,

arXiv
[15]

Structure-aware lower bounds and broadening the horizon of tractability for QBF

27 Johannes Klaus Fichte, Robert Ganian, Markus Hecher, Friedrich Slivovsky, and Sebastian Ordyniak. Structure-aware lower bounds and broadening the horizon of tractability for QBF. InLICS, pages 1–14, 2023.doi:10.1109/LICS56636.2023.10175675. 28 Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameterizations of the bounded-degree ver...

work page doi:10.1109/lics56636.2023.10175675 2023
[16]

29 Robert Ganian and Sebastian Ordyniak

URL: https://doi.org/10.1007/s00453-020-00758-8,doi:10.1007/S00453-020-00758-8. 29 Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP.Artif. Intell., 257:61–71,

work page doi:10.1007/s00453-020-00758-8
[17]

Bowman, Mara G

URL: https://doi.org/10.1016/j. artint.2017.12.006,doi:10.1016/J.ARTINT.2017.12.006. 30 Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity.Theor. Comput. Sci., 918:60–76,

work page doi:10.1016/j 2017
[18]

31 Tatsuya Gima and Yota Otachi

URL:https://doi.org/10.1016/j.tcs.2022.03.021, doi: 10.1016/J.TCS.2022.03.021. 31 Tatsuya Gima and Yota Otachi. Extended MSO model checking via small vertex integrity. Algorithmica, 86(1):147–170,

work page doi:10.1016/j.tcs.2022.03.021 2022
[19]

32 Yasuaki Kobayashi and Hisao Tamaki

URL:https://doi.org/10.1007/s00453-023-01161-9, doi:10.1007/S00453-023-01161-9. 32 Yasuaki Kobayashi and Hisao Tamaki. Treedepth parameterized by vertex cover number. In Jiong Guo and Danny Hermelin, editors,11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 18:1–...

work page doi:10.1007/s00453-023-01161-9 2016
[20]

34 WojciechNadara, MichalPilipczuk, andMarcinSmulewicz

URL:https: //doi.org/10.4230/LIPIcs.ISAAC.2021.34,doi:10.4230/LIPICS.ISAAC.2021.34. 34 WojciechNadara, MichalPilipczuk, andMarcinSmulewicz. Computingtreedepthinpolynomial space and linear FPT time. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors,30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Ber...

work page doi:10.4230/lipics.isaac.2021.34 2021
[21]

79,doi:10.4230/LIPICS.ESA.2022.79

URL:https://doi.org/10.4230/LIPIcs.ESA.2022. 79,doi:10.4230/LIPICS.ESA.2022.79. 35 Jaroslav Nesetril and Patrice Ossona de Mendez.Sparsity - Graphs, Structures, and Al- gorithms, volume 28 ofAlgorithms and combinatorics. Springer,

work page doi:10.4230/lipics.esa.2022 2022
[22]

37 Sang-il Oum and Paul D

doi:10.1016/j.jctb.2005.03.003. 37 Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width.J. Comb. Theory B,96(4):514–528,

work page doi:10.1016/j.jctb.2005.03.003 2005
[23]

38 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar

URL:https://doi.org/10.1016/j.jctb.2005.10.006, doi:10.1016/J.JCTB.2005.10.006. 38 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,Automata, Languages, and Programming - 41st International Coll...

work page doi:10.1016/j.jctb.2005.10.006 2005
[24]

39 Neil Robertson and Paul D

doi: 10.1007/978-3-662-43948-7\_77. 39 Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest.J. Comb. Theory B, 35(1):39–61, 1983.doi:10.1016/0095-8956(83)90079-5. 40 Martijn van Ee. Some notes on bounded starwidth graphs.Inf. Process. Lett., 125:9–14,

work page doi:10.1007/978-3-662-43948-7 1983
[25]

URL:https://doi.org/10.1016/j.ipl.2017.04.011,doi:10.1016/J.IPL.2017.04.011

work page doi:10.1016/j.ipl.2017.04.011 2017

[1] [1]

Computing twin-width parameterized by the feedback edge number

1 Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing twin-width parameterized by the feedback edge number. In Olaf Beyersdorff, Mamadou Moustapha Kanté, Orna Kupferman, and Daniel Lokshtanov, editors,41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France, volume 289 ofLIPIcs...

2024

[2] [2]

2 Jakub Balabán, Robert Ganian, and Mathis Rocton

URL: https://doi.org/10.4230/LIPIcs.STACS.2024.7,doi:10.4230/LIPICS.STACS.2024.7. 2 Jakub Balabán, Robert Ganian, and Mathis Rocton. Twin-width meets feedback edges and vertex integrity. In Édouard Bonnet and Pawel Rzazewski, editors,19th International Symposium on Parameterized and Exact Computation, IPEC 2024, September 4-6, 2024, Royal Holloway, Univer...

work page doi:10.4230/lipics.stacs.2024.7 2024

[3] [3]

3 Jakub Balabán and Petr Hlinený

URL: https: //doi.org/10.4230/LIPIcs.IPEC.2024.3,doi:10.4230/LIPICS.IPEC.2024.3. 3 Jakub Balabán and Petr Hlinený. Twin-width is linear in the poset width. In Petr A. Golovach and Meirav Zehavi, editors,16th International Symposium on Parameterized and Exact Computation, IPEC 2021, September 8-10, 2021, Lisbon, Portugal, volume 214 of LIPIcs, pages 6:1–6:...

work page doi:10.4230/lipics.ipec.2024.3 2024

[4] [4]

9 Hans L

URL:https: //doi.org/10.7155/jgaa.00597,doi:10.7155/JGAA.00597. 9 Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Preprocessing for treewidth: A combinatorial analysis through kernelization.SIAM J. Discret. Math., 27(4):2108–2142,

work page doi:10.7155/jgaa.00597

[5] [5]

10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

doi:10.1137/120903518. 10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes. In Dániel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1977–1996. SIAM, 2021.doi:10.1137/1.9781611976465.118. 11 Édouard Bon...

work page doi:10.1137/120903518 2021

[6] [6]

13 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk

doi:10.1145/ 3519935.3520037. 13 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, and Szymon Torunczyk. Twin-width IV: ordered graphs and matrices.J. ACM, 71(3):21,

arXiv

[7] [7]

14 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé

doi:10.1145/3651151. 14 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Twin- width V: linear minors, modular counting, and matrix multiplication. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors,40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, March 7-...

work page doi:10.1145/3651151 2023

[8] [8]

16 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

doi:10.1137/1.9781611977073.45. 16 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.J. ACM, 69(1):3:1–3:46, 2022.doi:10.1145/3486655. 17 Domagoj Bradač, Jacob Fox, and Benny Sudakov. The growth rate of multicolor ramsey numbers of 3-graphs.Research in the Mathematical Sciences, 11(3):52,

work page doi:10.1137/1.9781611977073.45 2022

[9] [9]

10 Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M.M

doi:10.1007/978-3-319-21275-3. 19 Thomas Depian, Simon D. Fink, Robert Ganian, and Vaishali Surianarayanan. Linear layouts revisited: Stacks, queues, and exact algorithms. In33rd Annual European Symposium on Algorithms (ESA 2025), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

work page doi:10.1007/978-3-319-21275-3 2025

[10] [10]

20 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics

URL:https://www.arxiv.org/abs/2508.16319. 20 Reinhard Diestel.Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer,

arXiv

[11] [11]

Downey and Michael R

21 Rodney G. Downey and Michael R. Fellows.Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013.doi:10.1007/978-1-4471-5559-1. 22 Pål Grønås Drange, Markus S. Dregi, and Pim van ’t Hof. On the computational complexity of vertex integrity and component order connectivity.Algorithmica, 76(4):1181–1202,

work page doi:10.1007/978-1-4471-5559-1 2013

[12] [12]

23 Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak

URL:https://doi.org/10.1007/s00453-016-0127-x,doi:10.1007/S00453-016-0127-X. 23 Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints.Artif. Intell., 300:103561,

work page doi:10.1007/s00453-016-0127-x

[13] [13]

24 Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon

URL: https://doi.org/10.1016/ j.artint.2021.103561,doi:10.1016/J.ARTINT.2021.103561. 24 Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, and O-joung Kwon. A unifying framework for characterizing and computing width measures. In Mark Braverman, editor,13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 202...

work page doi:10.1016/j.artint.2021.103561 2021

[14] [14]

26 Paul Erdos and Richard Rado

arXiv:2308.03967. 26 Paul Erdos and Richard Rado. Combinatorial theorems on classifications of subsets of a given set.Proceedings of the London mathematical Society, 3(1):417–439,

arXiv

[15] [15]

Structure-aware lower bounds and broadening the horizon of tractability for QBF

27 Johannes Klaus Fichte, Robert Ganian, Markus Hecher, Friedrich Slivovsky, and Sebastian Ordyniak. Structure-aware lower bounds and broadening the horizon of tractability for QBF. InLICS, pages 1–14, 2023.doi:10.1109/LICS56636.2023.10175675. 28 Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameterizations of the bounded-degree ver...

work page doi:10.1109/lics56636.2023.10175675 2023

[16] [16]

29 Robert Ganian and Sebastian Ordyniak

URL: https://doi.org/10.1007/s00453-020-00758-8,doi:10.1007/S00453-020-00758-8. 29 Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP.Artif. Intell., 257:61–71,

work page doi:10.1007/s00453-020-00758-8

[17] [17]

Bowman, Mara G

URL: https://doi.org/10.1016/j. artint.2017.12.006,doi:10.1016/J.ARTINT.2017.12.006. 30 Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity.Theor. Comput. Sci., 918:60–76,

work page doi:10.1016/j 2017

[18] [18]

31 Tatsuya Gima and Yota Otachi

URL:https://doi.org/10.1016/j.tcs.2022.03.021, doi: 10.1016/J.TCS.2022.03.021. 31 Tatsuya Gima and Yota Otachi. Extended MSO model checking via small vertex integrity. Algorithmica, 86(1):147–170,

work page doi:10.1016/j.tcs.2022.03.021 2022

[19] [19]

32 Yasuaki Kobayashi and Hisao Tamaki

URL:https://doi.org/10.1007/s00453-023-01161-9, doi:10.1007/S00453-023-01161-9. 32 Yasuaki Kobayashi and Hisao Tamaki. Treedepth parameterized by vertex cover number. In Jiong Guo and Danny Hermelin, editors,11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 of LIPIcs, pages 18:1–...

work page doi:10.1007/s00453-023-01161-9 2016

[20] [20]

34 WojciechNadara, MichalPilipczuk, andMarcinSmulewicz

URL:https: //doi.org/10.4230/LIPIcs.ISAAC.2021.34,doi:10.4230/LIPICS.ISAAC.2021.34. 34 WojciechNadara, MichalPilipczuk, andMarcinSmulewicz. Computingtreedepthinpolynomial space and linear FPT time. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors,30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Ber...

work page doi:10.4230/lipics.isaac.2021.34 2021

[21] [21]

79,doi:10.4230/LIPICS.ESA.2022.79

URL:https://doi.org/10.4230/LIPIcs.ESA.2022. 79,doi:10.4230/LIPICS.ESA.2022.79. 35 Jaroslav Nesetril and Patrice Ossona de Mendez.Sparsity - Graphs, Structures, and Al- gorithms, volume 28 ofAlgorithms and combinatorics. Springer,

work page doi:10.4230/lipics.esa.2022 2022

[22] [22]

37 Sang-il Oum and Paul D

doi:10.1016/j.jctb.2005.03.003. 37 Sang-il Oum and Paul D. Seymour. Approximating clique-width and branch-width.J. Comb. Theory B,96(4):514–528,

work page doi:10.1016/j.jctb.2005.03.003 2005

[23] [23]

38 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar

URL:https://doi.org/10.1016/j.jctb.2005.10.006, doi:10.1016/J.JCTB.2005.10.006. 38 Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,Automata, Languages, and Programming - 41st International Coll...

work page doi:10.1016/j.jctb.2005.10.006 2005

[24] [24]

39 Neil Robertson and Paul D

doi: 10.1007/978-3-662-43948-7\_77. 39 Neil Robertson and Paul D. Seymour. Graph minors. i. excluding a forest.J. Comb. Theory B, 35(1):39–61, 1983.doi:10.1016/0095-8956(83)90079-5. 40 Martijn van Ee. Some notes on bounded starwidth graphs.Inf. Process. Lett., 125:9–14,

work page doi:10.1007/978-3-662-43948-7 1983

[25] [25]

URL:https://doi.org/10.1016/j.ipl.2017.04.011,doi:10.1016/J.IPL.2017.04.011

work page doi:10.1016/j.ipl.2017.04.011 2017