{"id":"9a9cb8de-7d86-443d-bcad-056413d7602b","arxiv_id":"2501.00991","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graphs of twin-width at most 1 are exactly a subclass of permutation graphs, can be recognized in linear time, and distance-hereditary graphs have twin-width 0, 1, or 2 according to their split decomposition.","lead":"Graphs of twin-width at most 1, a recently introduced graph complexity measure, are shown to be permutation graphs, which gives them a simple geometric representation. The paper also provides a linear-time algorithm to recognize such graphs and a full twin-width classification of distance-hereditary graphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 23's recursive step calls itself on G[M∪s′] without proving this subgraph is prime, so the rejection proof's reliance on Lemma 16 is unjustified in the recursive branch.","rationale":"The reader's weakest_assumption was Lemma 7 from [9], a published lemma; while it is indeed load-bearing, it is an external result and not the most vulnerable point of the present paper. The reader's rationale also noted that Lemma 23's recursion 'needs an explicit primality check', which matches the concern I developed. I therefore partially agree: the reader identified the right area, but I would elevate the recursive primality gap over the Lemma 7 dependency. The main structural theorem (Theorem 8) appears supported by the induction in Lemma 11, and I found no internal inconsistency there after checking the ordering symmetries. The DH section is sketched, but it is secondary to the central claim. The proposed computational test on small prime permutation graphs is a direct way to see whether the recursive gap actually causes wrong rejections; until then, a conditional verdict asking for a proof that every recursive subproblem is prime or for a correctness argument covering non-prime subproblems is appropriate. Thus the reader's CONDITIONAL verdict should stand, so verdict_should_be is UNCHANGED.","tokens_in":19698,"tokens_out":32822,"duration_ms":317559,"concrete_test":"Implement Lemma 23 exactly as written, including recursive calls on G[M∪{s′}] without a primality re-check, and run it on all prime permutation graphs up to 10 vertices, comparing acceptance against an exhaustive contraction-sequence search for twin-width at most 1. If any graph with tww≤1 is rejected, the concern lands. Independently, instrument the recursion to record whether each recursive input is prime; if non-prime subproblems occur, verify whether Lemma 16's hypotheses (or a direct cograph argument) hold in those cases, and if not, the rejection proof needs repair.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The correctness of the linear-time recognizer (Theorem 24) rests on Lemma 23, whose input contract explicitly says 'a prime permutation graph G'. In its recursive branch, Lemma 23 sets s′ to the single vertex in one of the intervals A or B, sets M to the other interval, and 'applies the algorithm recursively to G[M∪{s′}]'. The proof that rejection is sound uses Lemma 16's guaranteed ordering π: 'If the algorithm rejects, it contradicts the existence of π guaranteed by Lemma 16.' But Lemma 16 is stated for a prime graph, and the paper never proves that G[M∪{s′}] is prime. It need not be: Lemma 16(i) allows M to be a pair of consecutive twins, in which case G[M∪{s′}] is a three-vertex non-prime graph, and induced subgraphs of prime graphs are generally not prime. The paper gives no analogue of Lemma 16 for non-prime inputs and no separate correctness argument for the recursive call. Consequently, the soundness of the reject branch is not established: a valid prime graph could in principle be rejected inside a recursive call on a non-prime subgraph, which would invalidate Theorem 24. This is a proof gap rather than a demonstrated counterexample, but it is load-bearing because the algorithm's linear-time rejection claim depends on it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19856,"tokens_out":24381,"duration_ms":265762,"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":[{"comment":"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":"Section 4, Lemma 23"},{"comment":"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.","section":"Section 3, Corollary 12"}],"minor_comments":[{"comment":"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.","section":"Section 2.1 / Lemma 16"},{"comment":"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.","section":"Observation 14"},{"comment":"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.","section":"Theorem 24"}],"recommendation":"major_revision","confidential_remarks":"The paper is readable and the structural theorem is attractive. The main obstacle to acceptance is the missing justification of the recursive call in Lemma 23; this is not a cosmetic issue because the reject branch of the algorithm is load-bearing for Theorem 24. If the authors can close that gap, I would expect the paper to be a solid contribution. I did not find a demonstrated counterexample to the algorithm, but the proof as written does not establish its soundness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper gives twin-width 1 graphs a concrete geometric model — they are permutation graphs — and turns that into a linear-time recognition algorithm. The structural theorem is the main event, and I think it holds up. The algorithm is the part with a real, fixable proof gap.\n\nWhat's new and good: Theorem 8 is a genuinely new containment, proved constructively in Lemma 11 by building a realiser from a 1-contraction sequence. That is the right way to do it, and Corollary 15 — the converse direction that any realiser can be followed by a 1-contraction sequence — makes the correspondence two-way. It also explains why recognition is tractable: Lemma 16 reduces the search to at most four extremal vertices. The distance-hereditary trichotomy (twin-width 0, 1, or 2) is a clean by-product, as is the linear-time consequence for those graphs.\n\nWhere the paper is soft: the correctness proof of the linear-time recognizer (Lemma 23) has a gap in the recursive step. Lemma 16 is stated for a prime permutation graph, but the algorithm recurses on G[M∪{s′}] without proving that this induced subgraph is prime. In the twin-pair case it is a P3, so there it is fine; but when M is larger there is no argument, and the rejection proof 'contradicts the existence of π guaranteed by Lemma 16' only goes through if Lemma 16 applies to the recursive input. This is load-bearing for the 'or conclude that no such sequence exists' part of Lemma 23, and the stress-test note has the details right. I don't see a counterexample, and a natural fix is to prove that the recursive input is prime or to generalize Lemma 16 to the non-prime case, but as written the proof is incomplete.\n\nThe distance-hereditary section is also more compressed than the rest. Lemma 31's proof is a sketch ('we find A2,2', 'we find A1') and Lemma 34's induction over the split decomposition needs the red-edge cases spelled out more carefully. These are presentation issues rather than obvious errors.\n\nThe reliance on Lemma 7 from [9] is fine: it is a published lemma, and the author overlap does not make the argument circular. No free parameters, no invented entities, and the inductive main argument (Lemma 11) is coherent.\n\nBottom line: this is a significant paper for the twin-width community, and the structural theorem will be cited. The linear-time algorithm's rejection branch needs another pass before I'd fully trust it, but the gap looks patchable. Worth serious peer review, with a request to close the recursion gap and expand the DH proofs. I'd take it to our reading group.","headline":"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.","tokens_in":20510,"tokens_out":4987,"would_cite":true,"duration_ms":42425,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C75","05C62","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["twin-width","contraction sequence","permutation graphs","modular decomposition","linear-time recognition","distance-hereditary graphs","split decomposition","trigraphs"],"falsifier":"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.","tokens_in":19415,"feed_emoji":"📐","tokens_out":7346,"duration_ms":66358,"temperature":0.7,"pith_summary":"Twin-width measures how a graph can be collapsed to a single vertex by repeatedly merging pairs of vertices, with at most one 'red edge' of disagreement allowed at each step for width 1. This paper pins down what graphs of twin-width at most 1 look like: they are permutation graphs, so they admit a diagram of crossing line segments between two parallel lines and inherit a linear structure. That structural insight yields a linear-time algorithm that either produces a 1-contraction sequence or correctly says the graph has twin-width greater than 1, improving on earlier polynomial-time recognition. The paper also shows that among distance-hereditary graphs, twin-width is 0 for cographs, 1 for the asteroidal-triple-free (equivalently permutation) ones, and 2 otherwise, giving a linear-time computation of optimal contraction sequences on that class.","feed_headline":"Every twin-width-1 graph is a permutation graph","feed_subtitle":"That linear structure yields a linear-time recognizer that builds a contraction sequence or says no.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies Lemma 5 (modular partitions reduce twin-width) and Lemma 7 (every intermediate trigraph in a prime 1-sequence has exactly one red edge), which the structure lemmas and the linear-time recognition proof build on.","marker":"[9]"},{"why":"Introduces twin-width and contraction sequences, and supplies Observation 4 that twin-width is stable under induced subgraphs and complementation.","marker":"[10]"},{"why":"Gives the linear-time modular decomposition and transitive orientation machinery used to reduce recognition to prime quotient graphs and to find realisers.","marker":"[28]"},{"why":"Characterises permutation graphs as exactly the comparability and co-comparability graphs, the target class for Theorem 8.","marker":"[19]"},{"why":"Provides graph-labelled trees and the characterisations of distance-hereditary graphs and cographs used in Section 5.","marker":"[22]"},{"why":"Gives the linear-time split decomposition algorithm used to compute optimal contraction sequences for distance-hereditary graphs.","marker":"[13]"},{"why":"Provides the caterpillar characterisation of trees of twin-width at most 1, which the distance-hereditary results generalise.","marker":"[2]"},{"why":"Gives the linear-time permutation-pattern finding algorithm that is shown to be insufficient by itself for twin-width-1 recognition.","marker":"[24]"}],"fun_headline_variants":["Twin-width 1 graphs are permutation graphs","Linear-time algorithm for twin-width 1 recognition","Permutation diagram structure behind twin-width 1","Twin-width 1 captured by permutation diagrams","Recognizing twin-width 1 in linear time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Twin-width 1 graphs are permutation graphs","Linear-time algorithm for twin-width 1 recognition","Permutation diagram structure behind twin-width 1","Twin-width 1 captured by permutation diagrams","Recognizing twin-width 1 in linear time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0003,"raw_usage":{"total_tokens":1693,"prompt_tokens":870,"completion_tokens":823,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":486,"completion_tokens_details":{"reasoning_tokens":762}},"tokens_in":486,"tokens_out":823,"duration_ms":7050,"temperature":1.0,"reasoning_tokens":762,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:40:49.137780+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the linear-time split decomposition algorithm used to compute optimal contraction sequences for distance-hereditary graphs."}],"review_version":1}