REVIEW 2 major objections 3 minor 1 cited by
Twin-width one
T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read The paper proves that every graph of twin-width at most 1 is a permutation graph, gives a linear-time algorithm that recognises such graphs and outputs a 1-contraction sequence, and characterises the twin-width of distance-hereditary…
desk verdict Twin-width 1 graphs are permutation graphs — the structural result is solid and new; the linear-time recognizer's proof has a real but likely fixable gap in a recursive case. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central objects are trigraphs — graphs whose edges are coloured black or red — and a $1$-contraction sequence, in which the graph is reduced to one vertex by repeatedly merging two vertices while keeping each vertex's red degree at most $1$. The load-bearing tool is Lemma 7 (from [9]): in every $1$-contraction sequence of a prime graph of twin-width $1$, every intermediate trigraph has exactly one red edge. Around this, the paper builds realisers $(\sigma,\tau)$ of permutation graphs, whose inversion sets are the edges of the graph, and shows that parts of the graph that are contracted together form intervals of the two orders (Lemma 11). The recognition algorithm uses the modular decomposition to reduce to prime quotient graphs, then guesses the unique extremal vertex that becomes incident to a red edge last and reconstructs the sequence by deleting vertices that are doubly extremal in the diagram.
What would settle it
Run a brute-force enumeration over all prime graphs on up to, say, 10 vertices, generate every 1-contraction sequence, and check that every intermediate trigraph has exactly one red edge; a sequence with an intermediate trigraph having zero or two red edges would disprove Lemma 7 and with it the pruning behind the linear-time recogniser. Equivalently, any graph that the algorithm rejects while still admitting a permutation diagram of the required interval structure would refute Theorem 24.
Extended reading notes
Core claim
Every graph of twin-width at most $1$ is a permutation graph (Theorem 8): it admits a realiser $(\sigma,\tau)$, two linear orders of the vertices such that edges are exactly the inversions of $\sigma^{-1}\circ\tau$, i.e. crossings of line segments in a permutation diagram. Moreover, any $1$-contraction sequence can be chosen so that every contracted pair is consecutive in the realiser and red edges are consecutive too (Lemma 11, Corollary 15). Conversely, every realiser of such a graph yields such a sequence. The induced structure gives a recursive decomposition of prime graphs and a linear-time decision algorithm (Theorem 24) that guesses the last vertex to become incident to a red edge, of which there are only four extremal candidates, and then greedily reconstructs the sequence. For distance-hereditary graphs, the paper proves that twin-width is $0$, $1$, or $2$ according to whether the graph is a cograph, is AT-free (equivalently a permutation graph), or neither, and this can be read from the split decomposition and computed in linear time.
Load-bearing premise
The argument depends on the previously proven fact that, while collapsing a prime graph of twin-width 1, every intermediate state has exactly one pair of vertices whose neighbourhood relation is mixed; if a single counterexample existed, the structure lemmas and the linear-time algorithm would collapse.
Editorial extensions
If this is right
- Every twin-width-1 graph is a permutation graph, so it is perfect, asteroidal-triple-free, and has an intersection model by line segments between two parallel lines.
- There is a $1$-contraction sequence whose contracted pairs are consecutive in the permutation diagram; this gives an inductive way to build realisers from contraction sequences and vice versa.
- Twin-width at most $1$ is recognisable in linear time: the algorithm returns a $1$-contraction sequence when one exists and otherwise certifies that the graph has twin-width at least $2$.
- Distance-hereditary graphs have twin-width $0$, $1$, or $2$; optimal contraction sequences for them can be produced in linear time using the split decomposition.
- The recognition algorithm needs to guess only the last vertex to become incident to a red edge, and there are at most four candidates because they are extremal in the realiser.
Reading between the lines
- A natural next test is whether the same 'guess the last red endpoint' scheme can be pushed to twin-width $2$ on permutation graphs, where the extremal-vertex structure of the unique realiser might still anchor the search.
- Because the proof constructs the realiser from the contraction sequence, one could try to derive a direct linear-time conversion from sequence to permutation diagram, bypassing the modular decomposition.
- The characterisation of distance-hereditary graphs suggests that for other hereditary classes with split-decomposition characterisations, twin-width might be computable from the shape of the graph-labelled tree alone.
- The paper's observation that bipartite twin-width-1 graphs have sequences where all trigraphs stay bipartite could be extended to test whether every bipartite permutation graph of bounded twin-width admits sequences respecting the bipartition.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies graphs of twin-width at most 1. Its main structural result (Theorem 8) is that every such graph is a permutation graph; the proof is constructive and yields a realiser whose blocks match the parts of any 1-contraction sequence (Lemma 11). The paper then gives a recursive decomposition of prime twin-width-1 graphs (Lemma 16) and uses it to design a linear-time recognition algorithm that either outputs a 1-contraction sequence or certifies twin-width at least 2 (Theorem 24). A final section gives a characterisation of the twin-width of distance-hereditary graphs (0 for cographs, 1 for AT-free/permutation DH graphs, 2 otherwise) and a linear-time computation of optimal sequences on that class.
Significance. If the main results are correct, the paper settles the structure and recognition of twin-width-1 graphs: it places the class inside permutation graphs, provides a linear-time recogniser, and gives a clean split-decomposition description for distance-hereditary graphs. The constructive induction behind Theorem 8 and the explicit use of the realiser to guide contractions are genuinely useful ideas. The paper is largely self-contained except for the use of Lemma 7 from [9] and the modular-decomposition/transitive-orientation machinery from [28]; the dependence on Lemma 7 is legitimate but should be stated clearly wherever it is load-bearing.
major comments (2)
- [Section 4, Lemma 23] The induction in Lemma 23 is not well-founded because the recursive call is made on G[M∪{s′}] without proving that this induced subgraph satisfies the lemma's hypothesis that the input is prime. Lemma 16(i) explicitly allows M to be a pair of consecutive twins, in which case G[M∪{s′}] is a three-vertex graph and is not prime; even in case (ii) the module rooted at a prime node of G_i is not necessarily a prime graph itself, and induced subgraphs of prime graphs are in general not prime. The proof of the reject branch says that rejection 'contradicts the existence of π guaranteed by Lemma 16', but Lemma 16 is stated for a prime graph and no analogue is provided for the recursive subinstance. Since a rejection inside the recursive call makes the whole algorithm reject, the soundness of the reject branch, and hence of Theorem 24, is not established by the current proof. The authors should either prove that G[M∪{s′}] is prime in the recursive branch, or state and prove a version of Lemma 23 that applies to the non-prime subinstances actually occurring.
- [Section 3, Corollary 12] The statement that the first contraction involves two vertices with exactly one vertex between them in the other ordering is stronger than what the proof establishes. The proof shows that the third vertex of the red edge lies between the two contracted vertices in the other ordering, but it does not rule out additional vertices lying between them. If the exact-one claim is needed, an argument must be supplied; otherwise it should be weakened to 'at least one vertex between them'. The overclaim is not used in the final linear-time algorithm, but it is stated as a structural consequence and should be corrected.
minor comments (3)
- [Section 2.1 / Lemma 16] The notation for the two sides of an extremal vertex is confusing: the text writes both G1=G[N(s)] and G2=G[N(s)], which are indistinguishable in the printed text. Use \overline{N}(s) for the non-neighbour set and keep the overline visible.
- [Observation 14] The proof should be written inductively: for each i one needs a chosen representative set S_i ⊆ V(G) with S_{i-1} ⊆ S_i. The current text describes a choice for each Gi separately and asserts distinctness, but does not explicitly prove the nestedness that is needed for the 'induced subgraph' chain. The argument is probably correct, but it should be spelled out.
- [Theorem 24] The linear-time implementation details are only sketched. In particular, the claim that realisers of the quotient graphs of prime nodes can be obtained from [28] in linear time, and that false rejection in a non-prime quotient cannot happen, needs to be tied to the discussion in Lemma 23. Please add a few sentences on how the output of [28] is converted into the diagrams used by Lemma 23.
Circularity Check
No significant circularity: the structural and algorithmic claims are derived from the definition of contraction sequences plus independent prior lemmas.
full rationale
The paper's central derivation (Theorem 8 via Lemma 11) is an induction on a fixed 1-contraction sequence that constructs a permutation realiser, and the linear-time recognizer (Lemma 23, Theorem 24) is a self-contained recursive algorithm whose rejection soundness is argued from Lemma 16. The only author-overlap citation of note is Lemma 7 from [9] (shared coauthor Reinald), used to force the single-red-edge shape of intermediate trigraphs; however Lemma 7 is a parameter-free prior theorem with stated assumptions that do not include the paper's target results, so under the review rules it is independent support rather than circular input. No fitted parameter is renamed as a prediction, no uniqueness claim is imported from the authors to forbid alternatives, and no equation is defined in terms of the quantity it purports to derive. The recursive call in Lemma 23 on G[M union {s'}] may raise a separate correctness question about whether that subgraph is prime, but that is a proof-gap concern, not a circularity, and does not affect this score.
Assumptions & free parameters
assumptions (5)
- domain assumption Lemma 5: tww(G) = max over any modular partition M of { tww(G/M), max_i tww(G[M_i]) }.
- domain assumption Lemma 7: a prime graph of twin-width 1 has, in every 1-contraction sequence, exactly one red edge in each intermediate trigraph.
- domain assumption Observation 3: common intervals of a permutation realiser are modules of the graph, and strong modules are common intervals in every realiser.
- domain assumption For a prime permutation graph, the permutation diagram is unique up to symmetry (references [20,23]).
- domain assumption Modular decomposition and split decomposition can be computed in linear time (references [28], [13]).
Cite this review
Pith. "Pith review of Twin-width one." pith.science (2026). https://pith.science/paper/JWDYAHHC
@misc{pith2026250100991,
author = {Pith},
title = {Pith review of: Twin-width one},
year = {2026},
howpublished = {\url{https://pith.science/paper/JWDYAHHC}},
note = {Machine review of arXiv:2501.00991}
}
abstract
We investigate the structure of graphs of twin-width at most $1$, and obtain the following results: - Graphs of twin-width at most $1$ are permutation graphs. In particular they have an intersection model and a linear structure. - There is always a $1$-contraction sequence closely following a given permutation diagram. - Based on a recursive decomposition theorem, we obtain a simple algorithm running in linear time that produces a $1$-contraction sequence of a graph, or guarantees that it has twin-width more than $1$. - We characterise distance-hereditary graphs based on their twin-width and deduce a linear time algorithm to compute optimal sequences on this class of graphs.
Forward citations
Cited by 1 Pith paper
-
Orthology and Near-Cographs in the Context of Phylogenetic Networks
A graph is explainable by a level-1 phylogenetic network if and only if every primitive induced subgraph is a near-cograph, and such graphs can be recognized in linear time.
Reference graph
Works this paper leans on
-
[9]
10 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant
doi:10.1007/ s00453-022-00965-5. 10 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: Tractable FO model checking.J. ACM, 69(1):Art. 3, 46, 2022.doi:10.1145/3486655. 11 Andreas Brandstädt and Vadim V. Lozin. On the linear structure and clique-width of bipartite permutation graphs. Ars Comb., 67,
doi:10.1145/3486655 2022
-
[1]
Twin-width of subdivisions of multigraphs
1 Jungho Ahn, Debsoumya Chakraborti, Kevin Hendrey, and Sang-il Oum. Twin-width of subdivisions of multigraphs. arXiv:2306.05334,
-
[4]
Twin-Width Meets Feedback Edges and Vertex Integrity
URL: https://doi.org/10.48550/arXiv. 2407.15514, arXiv:2407.15514, doi:10.48550/ARXIV.2407.15514. 5 Pierre Bergé, Édouard Bonnet, and Hugues Déprés. Deciding twin-width at most 4 is np- complete. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors,49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-...
-
[5]
6 Anne Bergeron, Cédric Chauve, Fabien de Montgolfier, and Mathieu Raffinot
URL: https://doi.org/10.4230/LIPIcs.ICALP.2022.18, doi:10.4230/LIPICS.ICALP.2022.18. 6 Anne Bergeron, Cédric Chauve, Fabien de Montgolfier, and Mathieu Raffinot. Computing common intervals of K permutations, with applications to modular decomposition of graphs. SIAM J. Discret. Math. , 22(3):1022–1039,
-
[8]
9 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant
doi:10.1145/3651151. 9 Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, Stéphan Thomassé, and Rémi Watrigant. Twin-width and polynomial kernels. Algorithmica, 84(11):3300–3337,
-
[13]
URL: https://doi.org/10.1016/j.dam.2011.03.020, doi:10.1016/J.DAM.2011.03
-
[16]
22 Emeric Gioan and Christophe Paul
URL:https://doi.org/10.4230/LIPIcs.ESA.2023.53, doi:10.4230/ LIPICS.ESA.2023.53. 22 Emeric Gioan and Christophe Paul. Split decomposition and graph-labelled trees: Character- izations and fully dynamic algorithms for totally decomposable graphs.Discret. Appl. Math. , 160(6):708–733,
-
[17]
doi:10.1016/j.dam.2011.05.007. 23 M.C. Golumbic. Algorithmic graph theory and perfect graphs . Academic Press,
Show all 22 references
-
[1967]
21 Colin Geniet and Stéphan Thomassé
German. 21 Colin Geniet and Stéphan Thomassé. First order logic and twin-width in tournaments. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors,31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Net...
2023
-
[1980]
Finding small patterns in permutations in linear time
24 Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Chandra Chekuri, editor,Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014 , pages 82–101. SIAM,
2014
-
[1982]
1137/0603021
arXiv:https://doi.org/10.1137/0603021, doi:10. 1137/0603021. 18 Fabien de Montgolfier.Décomposition modulaire des graphes. Théorie, extension et algorithmes. (Graph Modular Decomposition. Theory, extension and algorithms) . PhD thesis, Montpellier 2 University, France,
-
[1999]
29 Szymon Torunczyk
doi:10.1016/S0012-365X(98)00319-7. 29 Szymon Torunczyk. Flip-width: Cops and robber on dense graphs. In64th IEEE Annual Sym- posium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 663–700. IEEE, 2023.doi:10.1109/FOCS57990.2023.0004...
2023
-
[2002]
13 Pierre Charbit, Fabien de Montgolfier, and Mathieu Raffinot
URL: https://doi.org/10.46298/dmtcs.298, doi:10.46298/DMTCS.298. 13 Pierre Charbit, Fabien de Montgolfier, and Mathieu Raffinot. Linear time split decomposition revisited. SIAM J. Discret. Math. , 26(2):499–514,
-
[2006]
15 Derek G
URL:http://dx.doi.org/ 10.4007/annals.2006.164.51, doi:10.4007/annals.2006.164.51. 15 Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, and Udi Rotics. Polynomial-time recognition of clique-width≤3 graphs. Discret. Appl. Math. , 160(6):834–865,
2006 doi
-
[2008]
7 Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, and Marek Sokolowski
doi:10.1137/060651331. 7 Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guspiel, Petr Hlinený, Filip Pokrývka, and Marek Sokolowski. Sparse graphs of twin-width 2 have bounded tree-width. In Satoru Iwata and Naonori Kakimura, editors, 34th International Symposium on Algorithms...
-
[2010]
01.001, doi:10.1016/J.COSREV.2010.01.001
URL:https://doi.org/10.1016/j.cosrev.2010. 01.001, doi:10.1016/J.COSREV.2010.01.001. 22 Twin-width one 26 Ekkehard Köhler. Graphs Without Asteroidal Triples . PhD thesis, Technischen Universität Berlin,
2010 doi
-
[2011]
28 Ross M
URL:http://dx.doi.org/10.1007/s00026-011-0117-2, doi: 10.1007/s00026-011-0117-2. 28 Ross M. McConnell and Jeremy P. Spinrad. Modular decomposition and transitive orientation. Discret. Math., 201(1-3):189–241,
-
[2012]
14 Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas
doi:10.1137/10080052X. 14 Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas. The strong perfect graph theorem. Annals of Mathematics , 164(1):51–229, July
-
[2014]
25 Michel Habib and Christophe Paul
doi:10.1137/1.9781611973402.7. 25 Michel Habib and Christophe Paul. A survey of the algorithmic aspects of modular decompos- ition. Comput. Sci. Rev. , 4(1):41–59,
-
[2022]
3 Jakub Balabán, Robert Ganian, and Mathis Rocton
doi:10.1137/21m1452834. 3 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 ...
-
[2023]
3 There is no constraint for stars on the path J
URL:https://doi.org/ 10.4230/LIPIcs.ISAAC.2023.11, doi:10.4230/LIPICS.ISAAC.2023.11. 3 There is no constraint for stars on the path J. Ahn, H. Jacob, N. Köhler, C. Paul, A. Reinald, and S. Wiederrecht 21 8 Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, S...
2023 doi
-
[2024]
4 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. 4 Jakub Balabán, Robert Ganian, and Mathis Rocton. Twin-width meets feedback edges and vertex integrity. CoRR, abs/2407.15514,
2024 arXiv
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.