Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"

Tomasz Krawczyk

REVIEW 4 major objections 6 minor 1 cited by

Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"

T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2411.13708 v2 pith:234HABOS submitted 2024-11-20 cs.DS math.CO

Tomasz Krawczyk This is my paper · ORCID

classification cs.DSmath.CO MSC 05C6205C8568R10

keywords circular-arcgraphsnormalizedintersectionmodelsdecompositiontreesrecognitionalgorithmisomorphismconsistentmodulescounterexamplemodular

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

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

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

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

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

Referee Report

4 major / 6 minor

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.

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

[Section 3.2, Counterexample 1.1] 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 3.2, Counterexample 1.1] 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 3.1, Claim A and Claim B counterexamples] 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 3.2, closing paragraph] 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.

minor comments (6)

[Introduction] 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).
[Throughout] 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 3.1] 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 3.2, Counterexample 1.1] 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.
[Figure 3.1] 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 4] 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.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters and no invented entities are introduced. The note relies on standard graph theory facts plus the correctness of the drawn diagrams and several unproved 'easy to check' assertions.

assumptions (4)

standard math The modular decomposition tree of a graph exists and is unique.
Used to frame Hsu's decomposition tree; quoted from Gallai [5] in Section 2.1.1.
standard math Two arcs in a circular-arc model cross exactly when their endpoint chords cross in the associated chord model, yielding the same circle graph Gc.
Invoked in Section 2.2 to pass from normalized models R to chord models D of Gc.
domain assumption Hsu's definitions of normalized models, conformal models, similar pairs, D-vertices, and strongly or strictly adjacent vertices are taken as given.
The counterexamples are built inside Hsu's framework; the note does not redefine these notions.
ad hoc to paper The intersection models drawn in Figures 2.2(B), 3.1(A), and 3.2(A) are valid normalized circular-arc models with exactly the described adjacencies.
The paper says "we leave the reader to verify"; these unproved diagram facts are load-bearing for the counterexamples.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"." pith.science (2026). https://pith.science/paper/234HABOS

@misc{pith2026241113708,
  author       = {Pith},
  title        = {Pith review of: Comments on "$\mathcalO(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/234HABOS}},
  note         = {Machine review of arXiv:2411.13708}
}

abstract

In the work [$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs, SIAM J. Comput. 24(3), 411--439, (1995)], Wen-Lian Hsu claims three results concerning the class of circular-arc graphs: - the design of so-called \emph{decomposition trees} that represent the structure of all normalized intersection models of circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ recognition algorithm for circular-arc graphs, - an $\mathcal{O}(m\cdot n)$ isomorphism algorithm for circular-arc graphs. In [Discrete Math. Theor. Comput. Sci., 15(1), 157--182, 2013] Curtis, Lin, McConnell, Nussbaum, Soulignac, Spinrad, and Szwarcfiter showed that Hsu's isomorphism algorithm is incorrect. In this note, we show that the other two results -- namely, the construction of decomposition trees and the recognition algorithm -- are also flawed.

Figures

Figures reproduced from arXiv: 2411.13708 by the authors.

**Figure 2.1.** From left to right: u1 and u2 are independent, u1 contains u2, u1 is contained in u2, u1 and u2 cover the circle, and u1 and u2 strictly overlap. Following Hsu (see page 414, lines 3 to 8), two vertices v1 and v2 in a graph G are said to be: (1) independent if v1 is not adjacent to v2. (2) strictly adjacent if v1 is adjacent to v2 but neither N(v1) nor N(v2) is contained in the other. (3) strongly adjacent if v1 and… view at source ↗

**Figure 2.2.** (A) shows an exemplary circular-arc graph and Figure 2.2.( [PITH_FULL_IMAGE:figures/full_fig_p006_2_2.png] view at source ↗

**Figure 3.1.** Counterexample to Claim A. Next, we define a circular-arc graph G by taking Gs and two its isomorphic copies, say Gv and Gu over the vertex sets {v, v1, . . . , v6} and {u, u1, . . . , u6}, respectively. Again, we define the edges of G by providing an intersection model R of G. Given the schematic view of the model R as shown in [PITH_FULL_IMAGE:figures/full_fig_p008_3_1.png] view at source ↗

Figures from the paper (2 more)

**Figure 3.** Figure 3: (E). Note that [PITH_FULL_IMAGE:figures/full_fig_p008_3.png]

**Figure 3.2.** Figure 3.2: Counterexample to Claim B. Consider a circular-arc graph G whose normalized model R is shown in [PITH_FULL_IMAGE:figures/full_fig_p009_3_2.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited
cs.DS 2024-11 conditional novelty 8.0 of 10

A PQSM-tree data structure captures all normalized models of a circular-arc graph and yields a linear-time canonization and isomorphism algorithm.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · cited by 1 Pith paper

[7]

On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited

Tomasz Krawczyk. On the structure of normalized models of circ ular-arc graphs – Hsu’s approach revisited. CoRR, abs/2411.13374, 2024

work page Pith review arXiv 2024
[6]

O(m*n) algorithms for the recognition and isomorp hism problems on circular-arc graphs

Wen-Lian Hsu. O(m*n) algorithms for the recognition and isomorp hism problems on circular-arc graphs. SIAM J. Comput. , 24(3):411–439, 1995

work page 1995
[1]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecu tive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. , 13(3):335–379, 1976

work page 1976
[2]

Curtis, Min Chih Lin, Ross M

Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum , Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcﬁter. Isomorphism of gr aph classes related to the circular- ones property. Discret. Math. Theor. Comput. Sci. , 15(1):157–182, 2013

work page 2013
[3]

Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math. , 63:600–610, 1941

work page 1941
[4]

Gabor, Kenneth J

Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recogn izing circle graphs in polynomial time. J. ACM , 36(3):435–473, 1989

work page 1989
[5]

Transitiv orientierbare Graphen

Tibor Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. , 18(1–2):25–66, 1967

work page 1967
[8]

Tze-Heng Ma and Jeremy P. Spinrad. On the 2-chain subgraph co ver and related problems. J. Algo- rithms, 17(2):251–268, 1994

work page 1994

Show all 9 references

[9]

Jeremy P. Spinrad. Circular-arc graphs with clique cover number two. J. Comb. Theory B , 44(3):300– 306, 1988. (T. Krawczyk) F aculty of Mathematics and Information Science, W arsaw Uni versity of Technology, W arsaw, Poland Email address : tomasz.krawczyk@pw.edu.pl

1988

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [7]

On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited

Tomasz Krawczyk. On the structure of normalized models of circ ular-arc graphs – Hsu’s approach revisited. CoRR, abs/2411.13374, 2024

work page Pith review arXiv 2024

[2] [6]

O(m*n) algorithms for the recognition and isomorp hism problems on circular-arc graphs

Wen-Lian Hsu. O(m*n) algorithms for the recognition and isomorp hism problems on circular-arc graphs. SIAM J. Comput. , 24(3):411–439, 1995

work page 1995

[3] [1]

Booth and George S

Kellogg S. Booth and George S. Lueker. Testing for the consecu tive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. , 13(3):335–379, 1976

work page 1976

[4] [2]

Curtis, Min Chih Lin, Ross M

Andrew R. Curtis, Min Chih Lin, Ross M. McConnell, Yahav Nussbaum , Francisco J. Soulignac, Jeremy P. Spinrad, and Jayme Luiz Szwarcﬁter. Isomorphism of gr aph classes related to the circular- ones property. Discret. Math. Theor. Comput. Sci. , 15(1):157–182, 2013

work page 2013

[5] [3]

Ben Dushnik and E. W. Miller. Partially ordered sets. Amer. J. Math. , 63:600–610, 1941

work page 1941

[6] [4]

Gabor, Kenneth J

Csaba P. Gabor, Kenneth J. Supowit, and Wen-Lian Hsu. Recogn izing circle graphs in polynomial time. J. ACM , 36(3):435–473, 1989

work page 1989

[7] [5]

Transitiv orientierbare Graphen

Tibor Gallai. Transitiv orientierbare Graphen. Acta Math. Acad. Sci. Hung. , 18(1–2):25–66, 1967

work page 1967

[8] [8]

Tze-Heng Ma and Jeremy P. Spinrad. On the 2-chain subgraph co ver and related problems. J. Algo- rithms, 17(2):251–268, 1994

work page 1994