Pith. sign in

REVIEW 1 major objections 25 references

Computing Twin-Width via Treedepth and Vertex Integrity

T0 review · 1 major / 0 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read Approximating twin-width is fixed-parameter tractable parameterized by treedepth, and exact computation of twin-width is fixed-parameter tractable parameterized by vertex integrity.

desk verdict 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 →

arxiv 2606.20331 v1 pith:ME2TSSII submitted 2026-06-18 cs.DS cs.CC

Robert Ganian , Mathis Rocton This is my paper · ORCID
classification cs.DScs.CC
keywords twin-widthtreedepthvertexintegrityparameterizedalgorithmscontractionsequencesfixed-parametertractabilityapproximation
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 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.

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.

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.

Watch

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

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)
  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

  1. 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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing Twin-Width via Treedepth and Vertex Integrity." pith.science (2026). https://pith.science/paper/ME2TSSII

@misc{pith2026260620331,
  author       = {Pith},
  title        = {Pith review of: Computing Twin-Width via Treedepth and Vertex Integrity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ME2TSSII}},
  note         = {Machine review of arXiv:2606.20331}
}
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  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]

    In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D

    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]

    Parameterized algorithms for queue layouts

    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]

    2022 , isbn =

    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,

    work page arXiv

  7. [7]

    9 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant

    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

Show all 25 references
  1. [9]

    19 Thomas Depian, Simon D

    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...

    2025 doi

  2. [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,

  3. [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 comp...

    2013 doi

  4. [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.Art...

    doi

  5. [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 ...

    2021 doi

  6. [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,

  7. [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, a...

    2023 doi

  8. [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,

    doi

  9. [17]

    artint.2017.12.006,doi:10.1016/J.ARTINT.2017.12.006

    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,

    2017 doi

  10. [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,

    2022 doi

  11. [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, ...

    2016 doi

  12. [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,...

    2021 doi

  13. [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,

    2022 doi

  14. [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,

    2005 doi

  15. [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 Kou...

    2005 doi

  16. [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,

    1983 doi

  17. [25]

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

    2017 doi

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.