{"id":"98b9b7e8-80f2-4906-a3e2-a6a86f8b5abe","arxiv_id":"2411.13708","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Hsu's 1995 decomposition trees for circular-arc graphs do not correctly describe all normalized intersection models, and the paper supplies counterexamples.","lead":"This paper gives explicit counterexamples showing that Wen-Lian Hsu's 1995 decomposition trees for circular-arc graphs, and the recognition algorithm built on them, do not correctly describe all intersection models. It corrects a long-standing published result and tells algorithm designers which Hsu constructions cannot be trusted.","discovery_kind":"replication","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Counterexample 1.1 rests on unverified 'easy to check' assertions: the non-consistency of M1 and M4 and the uniqueness of R up to reflection; neither is proved or machine-checkable from the text.","rationale":"The reader's weakest assumption—that the uniqueness and consistency checks in Counterexample 1.1 are correct—is indeed load-bearing. However, the truly essential assertion is not uniqueness but consistency: even if G had many normalized models, a single normalized model in which a parallel child is not consistent would already falsify Lemma 6.3 and hence break Hsu's decomposition-tree description. Uniqueness only serves the stronger statement 'all normalized models do not follow the description'; it is not required for the algorithmic refutation. The paper gives no proof for either assertion, and the diagrams are not machine-checkable, making the counterexample unverifiable as written. Because the reader's verdict of CONDITIONAL already reflects this gap, our stress-test does not change the verdict. The concrete test above would settle the concern by independently enumerating models and applying Hsu's formal consistency definition.","tokens_in":9232,"tokens_out":8965,"duration_ms":80012,"concrete_test":"Produce an explicit adjacency list for G from Figure 2.2(A) (contact the author if needed) and run an independent verifier that: (1) enumerates all normalized circular-arc models of G with pairwise distinct endpoints, up to reflection, and checks whether exactly two exist; (2) instantiates Hsu's definition of consistency from [6, Section 6.1] and tests M1 and M4 in every normalized/chord model. If the count differs from two, or if M1 or M4 is consistent in any model, Counterexample 1.1 fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Counterexample 1.1 is the linchpin: it must exhibit a circular-arc graph G whose normalized models contradict Hsu's Lemma 6.3, which says that any maximal submodule of Gc that is not consistent must be a series module. The note claims M1 and M4 are parallel children of the neighborhood module V(Gc) and are 'not consistent in D'. But 'consistent' is never defined in the note—the reader is referred to Hsu's very technical Section 6.1, the very text under dispute—and the assertion is accompanied only by 'one can also check'. The figure is a hand-drawn diagram, not machine-readable data, so the claimed adjacency structure and derived chord model cannot be independently verified from the text. The additional uniqueness claim that R and its reflection are the only normalized models of G is likewise unproved. If, under Hsu's actual definition, M1 or M4 turned out to be consistent, or if G admitted a normalized model in which they are consistent, Lemma 6.3 would not be refuted and the decomposition-tree counterexample collapses. Hence the central conclusion—that Hsu's decomposition-tree construction is incorrect—hangs on these unchecked 'easy to check' statements.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript claims to refute two of Hsu's 1995 results for circular-arc graphs: the construction of decomposition trees representing all normalized models, and the O(nm) recognition algorithm. The main vehicle is Counterexample 1.1 in Section 3.2 (Figure 2.2): a circular-arc graph G whose normalized model R gives a circle graph Gc with V(Gc) a neighborhood module and with maximal modular-decomposition children M1,...,M4 all parallel; the note asserts that M1 and M4 are not consistent, contradicting Hsu's Lemma 6.3. Section 3.1 gives counterexamples to Claims A and B, the two steps in Hsu's proof of the uniqueness theorem (Theorem 5.7). Section 4 argues that the parallel-module case is incomplete and incorrect. The paper concludes that Hsu's decomposition-tree description and recognition algorithm are flawed, complementing the earlier 2013 refutation of the isomorphism algorithm.","tokens_in":9457,"tokens_out":6149,"duration_ms":46438,"significance":"If the counterexamples are correct, the paper is significant: it would demonstrate that the central structural claim of Hsu's paper fails and that the recognition algorithm cannot be justified by the stated decomposition-tree machinery. The small explicit graphs are an appropriate and potentially decisive form of counterexample, and the paper usefully separates the issue of Property (H1) (which it says is true, via the companion paper [7]) from the false proof and false Property (H3). The paper deserves credit for identifying the exact claims to attack. However, the current text leaves several load-bearing verifications to the reader, and the central refutation is not yet fully substantiated in a self-contained way.","major_comments":[{"comment":"The term 'consistent' is never defined in this note; the reader is directed to Hsu's Section 6.1, which is the very material being challenged. The assertion that M1 and M4 are 'not consistent in D' is therefore not checkable from the text. Please give a self-contained definition (or quote Hsu's definition) and a direct proof, based on the endpoint order of the displayed model, that M1 and M4 fail it. Without this, the contradiction with Lemma 6.3 is not established.","section":"Section 3.2, Counterexample 1.1"},{"comment":"The sentence 'One can also check that the model R and its reflection are the only two normalized models of G' is load-bearing: if G had another normalized model in which M1 and M4 were consistent, Hsu's Lemma 6.3 would not be contradicted. Since G has only eight vertices, a finite verification (exhaustive enumeration over endpoint orders or a short structural argument) should be supplied rather than delegated to the reader.","section":"Section 3.2, Counterexample 1.1"},{"comment":"The graphs Gs and G are specified only by schematic figures and by 'we leave the reader to verify that the model Rs is normalized' and 'again, we leave the reader to verify that R is a normalized model of G.' The subsequent assertions that Gc is s-inseparable and that the displayed partition is a join with the stated properties are also not demonstrated. Without explicit vertex and edge data, or a machine-checkable adjacency list, the counterexamples to Claims A and B are not independently verifiable from the text. The same issue applies to the Claim B counterexample in Figure 3.2.","section":"Section 3.1, Claim A and Claim B counterexamples"},{"comment":"The assertion that 'Lemma 6.5 and Theorem 6.6 from [6] are also false' is too compressed. The note does not state these lemmas in sufficient detail, nor does it show which specific condition of Lemma 6.5 or Theorem 6.6 fails for the graph of Figure 2.2. The argument should be expanded into a point-by-point violation of each lemma.","section":"Section 3.2, closing paragraph"}],"minor_comments":[{"comment":"The introduction contains a contradictory pair: it says Hsu correctly deals with the case when Gc is disconnected and later says this case is incomplete and incorrect; presumably the first occurrence should read 'when the complement of Gc is disconnected' (the series case).","section":"Introduction"},{"comment":"Notation such as 'Gc /integerdivide{s}', 'V /integerdivideM', and 'V /integerdivideN(v1)' should use standard set-difference symbols; the current rendering appears to be an OCR artifact and makes the paper hard to read.","section":"Throughout"},{"comment":"The text says 'the proof of Theorem 5.4 is concluded' but the theorem under discussion is Theorem 5.7; please correct the numbering.","section":"Section 3.1"},{"comment":"The sentence 'V (G) is the neighbourhood module in the modular decomposition tree of Gc' should read 'V (Gc)' since the neighborhood module is a module of Gc.","section":"Section 3.2, Counterexample 1.1"},{"comment":"The vertex names in Figure 3.1(A) do not match the text: the text introduces s1,...,s6 while the figure appears to label endpoints with superscripts; please align the notation.","section":"Figure 3.1"},{"comment":"The statement that 'Nowhere in [6] we found how Hsu defines consistent modules (T-modules) for series components' is a strong claim that should be substantiated by a precise quotation or page/line reference; as written it is not checkable.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"This is a critique of a specific historical algorithm and a companion to the author's own paper [7]. The central counterexample is plausible and, if fully verified, would be a useful erratum to Hsu's work. However, the paper is not yet at publication standard because its main claims are supported by 'the reader can check' and 'one can also check' statements rather than by supplied proofs or data. I would encourage the authors to add the missing verifications; if they do, the paper could be accepted as a concise counterexample note."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this: Krawczyk's note gives explicit counterexamples to two claims in the proof of Hsu's Theorem 5.7 and to Lemma 6.3. If the drawings are accurate, Hsu's decomposition trees do not represent all normalized models, and the correctness proof of his recognition algorithm is invalid. The counterexamples to Claims A and B are small and self-contained, and they look right. The graph in Figure 3.1 makes Gc\\{s} disconnected; the graph in Figure 3.2 gives H1 and H2 with the promised non-trivial modules. Those two alone show Hsu's proof of the unique-N-model theorem is wrong, even if the statement itself is true (the author cites his companion paper for a correct proof). That is a useful and clearly explained contribution.\n\nThe soft spots are in Counterexample 1.1, the linchpin for Lemma 6.3. The note asserts that M1 and M4 are not consistent, and that R and its reflection are the only normalized models, with 'one can also check.' Since 'consistent' is defined in Hsu's Section 6.1—the very text under dispute—this is not fully self-contained. A referee should ask for a definition and a proof, or at least a machine-checkable certificate. The hand-drawn figures make independent verification tedious but not impossible; this is a short note, not a formal proof.\n\nOne more thing: the paper says the recognition algorithm is flawed, but strictly it shows the decomposition-tree construction and its correctness proof are flawed. It does not produce an input where Hsu's recognition algorithm answers incorrectly. That might be enough, since the algorithm's correctness proof relies on those trees, but the wording overstates slightly.\n\nThis is a credible, honestly framed erratum. It deserves a serious referee. I'd send it, and ask for the gaps to be filled in revision.","headline":"A short, credible refutation note that gives explicit counterexamples to two claims in Hsu's Theorem 5.7 proof and to Lemma 6.3, though the central counterexample leans on some unproved 'easy to check' assertions.","tokens_in":9981,"tokens_out":3268,"would_cite":false,"duration_ms":30393,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The structural description of normalized circular-arc models given in a 1995 paper is false, and the recognition algorithm built on it is invalid as stated.","keywords":["circular-arc graphs","normalized intersection models","decomposition trees","recognition algorithm","isomorphism algorithm","consistent modules","counterexample","modular decomposition"],"falsifier":"Independently enumerate all normalized models of the graph in Figure 2.2(A) by exhaustive search over circular orderings of endpoints subject to the four arc-relationship rules; if any model beyond the displayed one and its reflection exists, or if in some model the chords of $M_1$ and $M_4$ can be partitioned into two consecutive endpoint sets, Counterexample 1.1 collapses.","tokens_in":8974,"feed_emoji":"⭕","tokens_out":10489,"duration_ms":106687,"temperature":0.7,"pith_summary":"This note attacks the structural core of a 1995 algorithm paper on circular-arc graphs: a decomposition tree designed to represent all normalized intersection models of the graph, in the spirit of PQ-trees for interval graphs. It exhibits a small circular-arc graph whose normalized models do not follow the description that the 1995 paper gives, and argues that the decomposition-tree construction and the recognition algorithm built on it therefore fail. An earlier 2013 paper had already shown that the 1995 isomorphism algorithm is wrong; this note extends the failure to the other two announced results. A companion paper is pointed to as containing a corrected description of the models.","feed_headline":"A single graph disproves the 1995 circular-arc decomposition trees","feed_subtitle":"The paper shows that all normalized models of one small graph contradict the 1995 structural description, so the recognition algorithm…","key_machinery":"The central object is a normalized model (N-model) of a circular-arc graph, in which five arc-pair relationships are required to mirror the graph's vertex-neighborhood relationships; any ordinary circular-arc model can be turned into an N-model by extending arcs. The 1995 paper's description works through the associated chord model of the circle graph $G_c$, whose vertices are exactly the strictly-but-not-strongly adjacent pairs of the original graph. The load-bearing notion is a consistent module (T-submodule): a set of vertices whose chord endpoints, in every conformal chord model, lie in two disjoint consecutive arcs, each containing one endpoint of every chord of the module. The paper's mechanism is a graph in which two parallel children of the neighbourhood module $V(G_c)$ violate this consistency, contradicting the criticized paper's Lemma 6.3 and showing that the decomposition-tree description is false.","core_discovery":"The note's central claim is that the structural description given in the 1995 paper for the normalized models of a circular-arc graph is false. The paper constructs a circular-arc graph G whose associated circle graph $G_c$ has, as its maximal nontrivial modules, four parallel modules $M_1,\\ldots,M_4$. The criticized paper's Lemma 6.3 says a maximal submodule of the neighbourhood module can be inconsistent only if it is a series module; in the constructed graph, $M_1$ and $M_4$ are parallel children and are not consistent in any normalized model. Since the graph has exactly two normalized models and neither follows the criticized description, the decomposition-tree construction and the recognition algorithm built on it are claimed to be invalid. The note also identifies two false supporting claims in the proof of the uniqueness theorem and finds the parallel-module case to be both incomplete and incorrect.","pith_inferences":["The small counterexample graph is a ready-made regression test: a correct circular-arc recognition implementation must accept it and produce a model equivalent up to reflection, while any implementation faithful to the disproved description would fail.","The failure suggests that the modular decomposition of the associated circle graph alone cannot determine the normalized models of a circular-arc graph; the model itself carries orientation information that the module structure does not encode.","A natural follow-up would be to implement the corrected structural description from the companion paper and check whether the claimed $\\mathcal{O}(m\\cdot n)$ bound actually holds.","The construction that pastes three copies of a small auxiliary graph into a chord model may serve as a reusable test pattern for other claimed characterizations of circular-arc models."],"forward_implications":["Any correctness proof of the 1995 recognition algorithm that relies on the published decomposition-tree description cannot be completed, because the tree does not represent all normalized models.","The failure is not a minor gap: the partition into consistent modules itself is wrong, since parallel children can be inconsistent, so the description must be rebuilt from a different partition.","The isomorphism algorithm, already known to be flawed, is not salvaged by the decomposition-tree route either.","The modular-decomposition approach to circular-arc models can still work, but only with a different notion of conformity, as the note says is done in the companion paper."],"supporting_citations":[{"why":"The SIAM 1995 paper whose decomposition-tree description, Lemma 6.3, and recognition algorithm are the claims being disproved.","marker":"[6]"},{"why":"The 2013 paper that already identified a separate flaw in the 1995 isomorphism algorithm; the current note extends the failure to the remaining results.","marker":"[2]"},{"why":"Supplies the modular decomposition tree construction and the framework that the 1995 paper adapts to circular-arc graphs.","marker":"[5]"},{"why":"Provides the uniqueness of chord models for j-inseparable circle graphs, invoked inside the proof that the note attacks.","marker":"[4]"},{"why":"The companion paper that, according to the note, gives a corrected definition of conformal models and the right uniqueness result.","marker":"[7]"},{"why":"The earlier structural result for co-bipartite circular-arc graphs that gives the base case where the modular-decomposition approach works.","marker":"[9]"}],"fun_headline_variants":["One graph invalidates 1995 circular-arc decomposition trees","Hsu's 1995 recognition algorithm contradicted by single graph","Decomposition trees and recognition algorithm from 1995 fail","Counterexample sinks Hsu's circular-arc decomposition claims"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The counterexample rests on the claim that the graph in Figure 2.2(A) has exactly two normalized models, the displayed one and its reflection, and that the modules $M_1$ and $M_4$ are not consistent in either of them.","fun_headline_variants_meta":{"raw":{"variants":["One graph invalidates 1995 circular-arc decomposition trees","Hsu's 1995 recognition algorithm contradicted by single graph","Decomposition trees and recognition algorithm from 1995 fail","Counterexample sinks Hsu's circular-arc decomposition claims"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000884,"raw_usage":{"total_tokens":3810,"prompt_tokens":926,"completion_tokens":2884,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":2814}},"tokens_in":542,"tokens_out":2884,"duration_ms":19153,"temperature":1.0,"reasoning_tokens":2814,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:58:02.747011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Independently enumerate all normalized models of the graph in Figure 2.2(A) by exhaustive search over circular orderings of endpoints subject to the four arc-relationship rules; if any model beyond the displayed one and its reflection exists, or if in some model the chords of $M_1$ and $M_4$ can be partitioned into two consecutive endpoint sets, Counterexample 1.1 collapses.","supporting_citations":[{"cited_title":"O(m*n) algorithms for the recognition and isomorp hism problems on circular-arc graphs","cited_arxiv_id":null,"evidence_quote":"The SIAM 1995 paper whose decomposition-tree description, Lemma 6.3, and recognition algorithm are the claims being disproved."},{"cited_title":"Curtis, Min Chih Lin, Ross M","cited_arxiv_id":null,"evidence_quote":"The 2013 paper that already identified a separate flaw in the 1995 isomorphism algorithm; the current note extends the failure to the remaining results."},{"cited_title":"Transitiv orientierbare Graphen","cited_arxiv_id":null,"evidence_quote":"Supplies the modular decomposition tree construction and the framework that the 1995 paper adapts to circular-arc graphs."},{"cited_title":"Gabor, Kenneth J","cited_arxiv_id":null,"evidence_quote":"Provides the uniqueness of chord models for j-inseparable circle graphs, invoked inside the proof that the note attacks."},{"cited_title":"On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited","cited_arxiv_id":"2411.13374","evidence_quote":"The companion paper that, according to the note, gives a corrected definition of conformal models and the right uniqueness result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The earlier structural result for co-bipartite circular-arc graphs that gives the base case where the modular-decomposition approach works."}],"review_version":1}