{"id":"2b77b78c-722f-48f9-8087-071c2269b90e","arxiv_id":"2411.13374","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A PQSM-tree data structure captures all normalized models of a circular-arc graph and yields a linear-time canonization and isomorphism algorithm.","lead":"This paper introduces a tree data structure, the PQSM-tree, that represents every normalized circular-arc model of a circular-arc graph, and proves it can be built in linear time. It uses this to give the first correct linear-time algorithm for deciding whether two circular-arc graphs are isomorphic, closing a 40-year gap.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Concern: Lemma 8.4's induction that every prime induced subgraph of the overlap graph has exactly two conformal models may miss a case; if so, the prime-case characterization and the PQSM-tree canonization collapse.","rationale":"The reader identified Lemma 8.4 as the weakest assumption, and I agree. The entire structural characterization of normalized models in the prime case rests on this uniqueness statement: if a prime induced subgraph of the overlap graph had three or more conformal models, then the set Π(Q) in Section 6.2 would need more than the two claimed circular orders, and the PQSM-tree representation would fail to capture all conformal models. Consequently, the linear-time canonization algorithm, which relies on the PQSM-tree as a complete isomorphism invariant, would also collapse. Other parts of the paper, such as the sufficiency direction of Theorem 6.2 and the linear-time construction details in Section 10, contain 'leave to the reader' handwaves, but these are fillable if the structural characterization is correct. The lemma's proof has two concrete danger points: the induction hypothesis appears to be applied to arbitrary prime subgraphs (probes) rather than just the stated class, and the tie-breaking rule for the maximal-split algorithm is used in a critical contradiction in the non-(*) subcase. Both need to be resolved for the proof to be considered sound. A computational enumeration of all small prime overlap subgraphs would directly test the statement and could surface a missing case; while it cannot prove the general lemma, it would be a meaningful sanity check. I therefore recommend keeping the reader's CONDITIONAL verdict unchanged until the proof of Lemma 8.4 is tightened or a counterexample is found.","tokens_in":71541,"tokens_out":11920,"duration_ms":128249,"concrete_test":"Enumerate all circular-arc graphs with no universal vertices and no twins on n≤10 vertices (e.g., sample arcs with distinct endpoints on a discrete circle). For each such G, compute the overlap graph Gov and enumerate every induced subgraph U with |U|≥4 that is prime in Gov. For each U, brute-force all oriented chord models of (U,∼) on a circle with 2|U| labeled endpoints (up to global reflection), and filter those satisfying conformality constraints left(v), right(v) inherited from G. Verify that the number of conformal models is exactly 2 for every U. If any U yields a different count, Lemma 8.4 is refuted; if all small cases pass, the concern is mitigated but not fully resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem (Theorem 1.2) depends on Theorem 6.2, whose prime case rests on Lemma 8.4: every prime induced subgraph of the overlap graph has exactly two conformal models, one the reflection of the other. The proof of Lemma 8.4 is a long induction over the split decomposition of the circle graph, with several case splits and a subtle subcase when Condition (*) fails. Two specific gaps make this the weakest point. First, the induction hypothesis appears stronger than the stated lemma: in Claim 8.6 the induction is applied to arbitrary probe graphs, which are not necessarily sets of representatives of children of a prime module, so the written lemma statement does not justify the induction step unless the lemma is implicitly meant for all prime induced subgraphs. Second, in the subcase where Condition (*) fails, the argument relies on a tie-breaking rule in the maximal-split algorithm ('the algorithm always takes the first option') to rule out the existence of a non-trivial module M; if the rule is not precisely defined or admits alternative executions, the contradiction is unsupported. A single missed configuration here would allow more than two conformal models, breaking the claim Π(Q)={π0,π1} in the prime case, and thereby invalidating the PQSM-tree representation and the linear-time canonization algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a complete structural description of all normalized intersection models of a circular-arc graph, encoded in a new data structure called a PQSM-tree. It further claims that the PQSM-tree can be built in linear time, yielding a linear-time canonization algorithm and hence a linear-time isomorphism test for circular-arc graphs. The approach follows Hsu's 1995 strategy but replaces non-oriented chords with oriented chords, and reduces normalized models of the circular-arc graph to conformal models of its overlap graph. The main structural theorem (Theorem 6.2) is split into serial, prime, and parallel cases; the prime case rests on a long induction over split decompositions, culminating in Lemma 8.4, which asserts that every prime induced subgraph of the overlap graph has exactly two conformal models, one the reflection of the other.","tokens_in":71784,"tokens_out":3904,"duration_ms":45475,"significance":"If the main results are correct, they resolve a long-standing open problem: circular-arc graph isomorphism in linear time. The paper contains no fitted parameters and no circular argumentation: the positive proof builds on external theorems (Gabor-Supowit-Hsu, Chaplick-Fulek-Klavik, McConnell, Gallai) rather than on the claims being proved. The proposed PQSM-tree is a substantial and plausible generalization of PQ-trees, and the reframing using oriented chords is a genuine improvement over Hsu's setup. However, the correctness of the central structure theorem depends critically on Lemma 8.4, and the proof of that lemma as written has gaps in the induction and in one case of the maximal-split argument. Because Theorem 1.2 and the linear-time algorithm inherit those gaps, the contribution is not yet fully established.","major_comments":[{"comment":"The induction in Lemma 8.4 is not justified by the stated lemma. Lemma 8.4 is formulated for a graph (U,∼) consisting of one vertex from each child of a prime component Q of the overlap graph. In the proof of Claim 8.6, the induction hypothesis is applied to arbitrary prime induced subgraphs (P,∼) of (U,∼), such as (P\\{z},∼), which need not be of the form 'one representative from each child of a prime component'. Either Lemma 8.4 must be stated and proved for every prime induced subgraph of the overlap graph, or an additional argument must show that each probe graph has exactly the form covered by the induction hypothesis. Without this, the induction step for the case Z=∅ and for the prime subgraph in the case Z={z} is unsupported.","section":"Section 8 (Lemma 8.4 and Claim 8.6)"},{"comment":"The treatment of the case where Condition (*) fails relies on a tie-breaking rule for the maximal-split algorithm: the text says 'in each step, having the choice of extending (A,B) into a non-trivial or a trivial split, the algorithm always takes the first option', and later uses this rule to rule out the possibility M1=∅. This rule is not a well-defined deterministic tie-breaker when there are multiple non-trivial extensions, and no proof is given that the 'second option' mentioned in the contradiction is the unique non-trivial alternative. If the maximal-split algorithm admits alternative executions, the contradiction is not established. This is a load-bearing point: a missed configuration in this subcase would allow more than two conformal models of a prime overlap graph, invalidating the prime-case characterization.","section":"Section 8 (Condition (*) fails, around equation (8.6.3))"},{"comment":"The sufficiency proof of the central equivalence is left almost entirely to the reader: after describing the allowed transformations, the text says 'We leave the reader to check that all those transformations keep the left/right relation between non-intersecting chords'. This check is not a formality, because transformations of the first type operate inside CA-modules while transformations of the second type permute or reflect slots at the PQS-tree level, and one must verify that the two operations interact correctly for all pairs of non-intersecting chords, including chords that belong to different CA-modules or different components. A complete verification is required for Theorem 6.2 to support the canonization claim.","section":"Section 6 (sufficiency direction of Theorem 6.2)"},{"comment":"The linear-time algorithm for constructing the PQSM-tree contains two 'we leave it to the reader' steps: verifying that the set S of CA-modules can be computed using Property (R), and checking that the bottom-up computed sets S(M) comprise all CA-modules contained in M. Since the linear-time bound and the correctness of the data structure both depend on this step, these claims need a proof rather than a reader exercise. In particular, the assertion that each module in M(Gov) can be processed in time linear in the number of its children is plausible but not demonstrated; the computation of S(M) for serial, parallel, and prime cases must be specified in enough detail to rule out hidden superlinear behavior.","section":"Section 10 (linear-time construction of CA-modules)"}],"minor_comments":[{"comment":"The text uses the symbol 'integerdivide' in many places where set difference (\\\\setminus) is clearly intended, e.g., 'V /integerdivide X' and 'Q /integerdivide Mi'. This should be fixed in the final typeset version.","section":"Throughout"},{"comment":"The abstract and the introduction contain nearly identical sentences about errors in Hsu's decomposition trees pointed out in [18]; consider unifying these two passages to avoid repetition.","section":"Abstract and Introduction"},{"comment":"The footnote about the author's earlier arXiv paper [17] and publishing difficulties is not relevant to the technical content and could be removed or moved to an acknowledgements section.","section":"Section 1"},{"comment":"In the definition of normalized models, the paper refers to [25,14] for the fact that every circular-arc model without twins and universal vertices can be normalized; the provided text does not show the bibliography, so the reader cannot easily verify these references. Please ensure all cited works are included.","section":"Section 2"}],"recommendation":"major_revision","confidential_remarks":"This is a serious and potentially important contribution, and the oriented-chord reformulation is a genuine step forward. However, the proof of Lemma 8.4, which is the pivot of the entire structure theorem, contains the two gaps described in the major comments. These are not cosmetic issues: they concern the induction domain and the deterministic behavior of the split-decomposition algorithm. I recommend major revision, and suggest that the editor seek an additional expert review focused on Section 8 and on the split-decomposition arguments from [6] that the paper relies on."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a real attempt at the long-open linear-time isomorphism and canonization problem for circular-arc graphs, and the overall approach looks right. I think the main theorem is probably true, but the submitted proof is not complete enough to accept as is. The PQSM-tree description of normalized models is genuinely new, and the canonization algorithm built on it is a clean idea.\n\nThe paper does several things well. It correctly diagnoses why Hsu's 1995 decomposition trees fail, and it avoids the trap by using oriented chords and tracking left/right relations explicitly. The reduction to conformal models of the overlap graph is sound, and the use of split decomposition (Gabor-Supowit-Hsu, Chaplick-Fulek-Klavik) is appropriate. There are no fitted parameters, and the only self-citation supports a negative claim about Hsu's work, not the positive theorem. That is honest scholarship.\n\nThe soft spots are real, though. The stress-test note lands: Lemma 8.4 is the keystone of the prime case, and the induction in Claim 8.6 applies the induction hypothesis to arbitrary probes that are not necessarily sets of representatives of children of a prime module. As written, the lemma statement does not justify that step unless the lemma is implicitly meant for all prime induced subgraphs, which is not stated. The subcase where Condition (*) fails also leans on a tie-breaking rule in the maximal-split algorithm ('the algorithm always takes the first option') to rule out a non-trivial module; if that rule is not precisely defined, the contradiction is unsupported. Section 10, which computes CA-modules, and part of the sufficiency proof in Section 6 are explicitly left to the reader. These are gaps in presentation and proof detail, not signs of a counterexample. The architecture is coherent, and the prior negative results on Hsu's algorithm are not in question.\n\nWho this is for: researchers in algorithmic graph theory, especially those working on graph isomorphism or geometric intersection graphs. It deserves a serious referee, but with the expectation of heavy revision. I would engage with it and ask the author to expand the missing proofs, or to provide machine-checked formalization for the crucial induction. My verdict is conditional: if the gaps close, this is a major result.","headline":"A serious, likely-correct resolution of a 40-year-open problem, but the written proof has load-bearing gaps that need a full referee pass.","tokens_in":72309,"tokens_out":2131,"would_cite":false,"duration_ms":25040,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C60","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every circular-arc graph has a canonical string representation computable in linear time, which yields a linear-time isomorphism test.","keywords":["circular-arc graphs","normalized intersection models","PQSM-tree","overlap graph","graph isomorphism","canonization","modular decomposition","conformal chord models"],"falsifier":"Enumerate, for all connected circular-arc graphs with no twins and no universal vertices up to, say, ten vertices, all conformal models of their overlap graphs; if any prime induced subgraph has three non-equivalent conformal models, Lemma 8.4 fails. A more direct check is to implement the PQSM-tree construction and compare the set of models it generates with brute-force enumeration for random instances: any conformal word that is not admissible by the tree would refute Theorem 6.2.","tokens_in":71320,"feed_emoji":"🔄","tokens_out":9711,"duration_ms":101271,"temperature":0.7,"pith_summary":"Circular-arc graphs are intersection graphs of arcs on a circle, and the paper claims that the normalized arc drawings—those that mirror the neighborhood relation of vertices—have a complete structural description. The description is a linear-space data structure, the PQSM-tree, which records every normalized model of a given graph: the tree encodes all possible circular orders of blocks of endpoints and all ways to permute vertices inside each block. The paper proves this tree can be built in linear time and that it gives a canonical string for the graph in linear time. Since two circular-arc graphs are isomorphic exactly when their canonical strings agree, the same result solves graph isomorphism for this class in linear time.","feed_headline":"Every circular-arc graph gets a linear-time canonical string","feed_subtitle":"A new data structure, the PQSM-tree, encodes all normalized models and yields canonical strings in O(n).","key_machinery":"The PQSM-tree is a linear-size ordered tree representation of all conformal chord models of the overlap graph: S-nodes are endpoint slots, Q-nodes are connected components, P-nodes are regions of the circular drawing, and M-nodes come from modular decomposition trees of the CA-modules that serve as metachords. The important property is that every conformal model is obtained by choosing one circular order of slots allowed by the tree and then replacing each slot with an admissible permutation of its vertices; Theorem 6.2 states exactly this equivalence. It is the object that makes the structural description algorithmic, since canonization reduces to canonically ordering the PQM-nodes level by level.","core_discovery":"On the paper's own terms, the central discovery is a characterization theorem: after converting normalized arc models into oriented chord models, normalized models of G correspond one-to-one with conformal models of the overlap graph Gov (Theorem 3.3), and a circular word is a conformal model precisely when it is admissible for the quadruple DS=(S,S*,MC,Π), represented compactly as the PQSM-tree (Theorem 6.2). The proof splits according to whether the root of the modular decomposition is serial, prime, or parallel, and handles both prime and serial components uniformly through CA-modules and metachords. From this structural theorem the paper derives Theorem 1.2: the canonization problem for circular-arc graphs can be solved in linear time, and hence the isomorphism problem for this class is also linear-time.","pith_inferences":["A concrete test the paper leaves implicit: implement the PQSM-tree on the known counterexample graphs from earlier work on circular-arc isomorphism and check that the tree reproduces all normalized models, which would validate the corrected structural claim directly.","Because canonization is organized as level-wise canonical forms of PQM-nodes, the same framework should adapt to other geometric graph classes whose models are described by modular-decomposition-style trees, such as circle graphs or permutation graphs, although the paper does not claim this.","The paper's operational description of how conformal models transform into one another gives, as a byproduct, a way to count or uniformly sample normalized models of a circular-arc graph in polynomial time; the paper only uses the description for canonization."],"forward_implications":["If the central theorems are right, circular-arc graph isomorphism is decidable in linear time because two graphs are isomorphic exactly when their canonical strings are equal.","The PQSM-tree is a complete registry of normalized models, so every structural operation on models—reflections of Q-nodes, permutations of P-nodes, and replacements of admissible metachord models—stays inside the described class.","The linear-time bound covers the full class, not just proper, Helly, or co-bipartite circular-arc graphs, because universal vertices and twins are stripped into a separate representation (G,m,u).","The construction algorithm for the PQSM-tree starts from a normalized model supplied by circular-arc recognition, so the canonization pipeline is compatible with existing linear-time recognition."],"supporting_citations":[{"why":"Supplies the decomposition-tree approach, the serial-case description, and the definition of conformal models that the paper extends and corrects.","marker":"[14]"},{"why":"Gives the counterexample showing the earlier isomorphism algorithm is incorrect, the failure this work must overcome.","marker":"[8]"},{"why":"Proves that a connected circle graph with no non-trivial split has exactly two chord models; used in the base case of the prime-subgraph uniqueness lemma.","marker":"[11]"},{"why":"Provides the split-decomposition characterization of chord models of circle graphs that structures the induction for prime overlap subgraphs.","marker":"[6]"},{"why":"Introduces split decomposition, the tool the probe construction inherits.","marker":"[7]"},{"why":"Supplies modular decomposition and transitive-orientation results from which CA-modules and M-nodes are derived.","marker":"[12]"},{"why":"Linear-time circular-arc recognition that outputs a normalized model, providing the input model for building the conformal model.","marker":"[21]"},{"why":"Linear-time modular decomposition algorithm used to compute the modular decomposition tree of the overlap graph.","marker":"[22]"},{"why":"Characterizes normalized models of co-bipartite circular-arc graphs, the template for admissible models of a metachord.","marker":"[24]"}],"fun_headline_variants":["Linear-time canonization for circular-arc graphs","PQM-tree encodes all normalized models in O(n)","Fixing Hsu: circular-arc isomorphism in linear time","Canonical strings for every circular-arc graph in O(n)","One tree to encode all circular-arc models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction depends on the uniqueness lemma that every prime induced subgraph of the overlap graph has exactly two conformal models, one being the reflection of the other; if any prime piece had a third conformal model, the induction behind the PQSM-tree would miss models and the linear-time canonization would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time canonization for circular-arc graphs","PQM-tree encodes all normalized models in O(n)","Fixing Hsu: circular-arc isomorphism in linear time","Canonical strings for every circular-arc graph in O(n)","One tree to encode all circular-arc models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000218,"raw_usage":{"total_tokens":1484,"prompt_tokens":1033,"completion_tokens":451,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":649,"completion_tokens_details":{"reasoning_tokens":372}},"tokens_in":649,"tokens_out":451,"duration_ms":4969,"temperature":1.0,"reasoning_tokens":372,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:29:31.672387+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate, for all connected circular-arc graphs with no twins and no universal vertices up to, say, ten vertices, all conformal models of their overlap graphs; if any prime induced subgraph has three non-equivalent conformal models, Lemma 8.4 fails. A more direct check is to implement the PQSM-tree construction and compare the set of models it generates with brute-force enumeration for random instances: any conformal word that is not admissible by the tree would refute Theorem 6.2.","supporting_citations":[{"cited_title":"O(m*n) algorithms for the recognition and isomor phism problems on circular-arc graphs","cited_arxiv_id":null,"evidence_quote":"Supplies the decomposition-tree approach, the serial-case description, and the definition of conformal models that the paper extends and corrects."},{"cited_title":"Gabor, Kenneth J","cited_arxiv_id":null,"evidence_quote":"Proves that a connected circle graph with no non-trivial split has exactly two chord models; used in the base case of the prime-subgraph uniqueness lemma."},{"cited_title":"Extending pa rtial representations of circle graphs","cited_arxiv_id":null,"evidence_quote":"Provides the split-decomposition characterization of chord models of circle graphs that structures the induction for prime overlap subgraphs."},{"cited_title":"Cunningham","cited_arxiv_id":null,"evidence_quote":"Introduces split decomposition, the tool the probe construction inherits."},{"cited_title":"Transitiv orientierbare Graphen","cited_arxiv_id":null,"evidence_quote":"Supplies modular decomposition and transitive-orientation results from which CA-modules and M-nodes are derived."},{"cited_title":"McConnell","cited_arxiv_id":null,"evidence_quote":"Linear-time circular-arc recognition that outputs a normalized model, providing the input model for building the conformal model."},{"cited_title":"McConnell and Jeremy P","cited_arxiv_id":null,"evidence_quote":"Linear-time modular decomposition algorithm used to compute the modular decomposition tree of the overlap graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Characterizes normalized models of co-bipartite circular-arc graphs, the template for admissible models of a metachord."}],"review_version":1}