{"id":"ad31f3bb-9518-42f3-b39f-67030c91a92d","arxiv_id":"1908.09151","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Circle graph isomorphism and canonization can be solved in O((n+m)α(n+m)) time using minimal split decomposition and linear-time canonization of split trees.","lead":"This paper presents a faster algorithm for deciding whether two circle graphs are the same, where circle graphs encode which chords of a circle cross each other. The new method runs in almost linear time, improving on a decades-old quadratic algorithm.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 3 cannot root edge-centered graph-labeled trees: inserting a single-vertex node violates Definition 2.1 and causes conflicting child-color assignments; Theorem 1.1's canonization step is undefined for these trees.","rationale":"The central claim is Theorem 1.1. For it to hold, the meta-algorithm of Lemma 3.2 must canonize every minimal split tree of a connected circle graph, and Lemma 2.5 must reduce graph isomorphism to split-tree isomorphism. Both are needed; I focused on the meta-algorithm because it contains a concrete, demonstrable failure rather than a missing sentence. The rooting insertion creates a vertex incident to two tree edges, which is explicitly forbidden by Definition 2.1, and the algorithm's parent-marker color propagation would require the new root to hold two distinct colors in one vertex. This is not merely a formal nuisance: edge-centered graph-labeled trees are reachable as minimal split trees (e.g., a tree of two nodes), so the proof of Lemma 3.2 does not cover all inputs of Section 5. The fix is likely small, but it is absent. The Lemma 2.5 converse also omits the minimality-preservation argument; this is a genuine but trivial omission because isomorphism preserves the prime/degenerate property and the join condition. I do not see a deeper flaw in the split-decomposition reduction; the use of minimal split trees and the unique representation of prime circle graphs is sound. The paper's citations to Cunningham and Gioan et al. provide independent support for the heavy machinery. Thus the honest verdict is conditional: the approach is credible and likely repairable, but the current text does not fully prove the theorem.","tokens_in":11369,"tokens_out":26065,"duration_ms":237466,"concrete_test":"Take the valid graph-labeled tree consisting of two nodes, each with a single vertex, connected by one tree edge. Run the rooting step of Lemma 3.2 literally: remove the central edge and insert a new single-vertex root, connecting it to both original vertices by tree edges. Trace the bottom-up coloring: each of the two leaf nodes is processed and tries to set the color of its parent marker vertex, which is the single vertex of the new root, so the second assignment overwrites the first or the vertex holds two colors. This demonstrates that the described algorithm is not well-defined for edge-centered graph-labeled trees.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Lemma 3.2 (Canonization of graph-labeled trees), the rooting step states: 'If a tree edge is central, we insert there another node having a single vertex.' Under Definition 2.1, a node is a connected component of (V,E_N) and 'no vertex is incident to two tree edges.' The inserted single-vertex node is incident to both tree edges of the central edge, so the resulting object is not a valid graph-labeled tree. Beyond the definitional conflict, the algorithm's coloring mechanism fails: for a non-root node, the parent marker vertex is the unique vertex in the parent incident to the outgoing tree edge; a single-vertex root with two children has only one vertex, so the two child subtrees would both write their assigned colors to that same vertex, overwriting each other. Consequently, Lemma 3.2 does not compute a canonization for any graph-labeled tree with an edge center, which includes minimal split trees with two nodes joined by a single tree edge. Since Section 5 applies Lemma 3.2 to every connected circle graph's minimal split tree, Theorem 1.1 is not established as written. This is a repair rather than a fatal flaw, but the manuscript contains no patch or alternative handling of edge-centered trees. Separately, the converse direction of Lemma 2.5 omits the argument that the image of a minimal split decomposition under isomorphism is minimal; that omission is real yet easily filled.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an algorithm for testing isomorphism and computing canonical forms of circle graphs in time O((n+m)alpha(n+m)), improving the previous O(nm) bound of Hsu. The approach is to reduce the problem to canonizing the unique minimal split tree of the graph: for a connected graph the minimal split tree is unique (Cunningham), its nodes are prime or degenerate circle graphs, prime circle graphs have unique circle representations up to reversal, and the recognition algorithm of Gioan et al. computes the minimal split tree together with those representations in almost linear time. The authors give a meta-algorithm that canonizes graph-labeled trees when a linear canonization for the node labels is available, and provide linear-time canonizations for prime and degenerate circle graphs. For disconnected graphs the component encodings are sorted. The paper also gives an O(n+m) bound when a circle representation is supplied as input, and discusses open problems on Weisfeiler-Leman dimension, logspace algorithms, and partial representation extension.","tokens_in":11622,"tokens_out":30378,"duration_ms":281469,"significance":"If correct, the result is a substantial improvement: it gives an almost linear-time isomorphism test and canonical form for circle graphs, matching the complexity of circle graph recognition and providing a clean structural algorithm via minimal split decomposition. The paper is clearly written and builds on solid external results; the meta-algorithm for graph-labeled trees is a reusable tool. The claimed running time is concrete and falsifiable, and the algorithm is structured so that the only super-linear bottleneck is the recognition/decomposition subroutine. However, the proof as written contains a gap in the canonization of edge-centered graph-labeled trees, which affects the main theorem, and a smaller omission in Lemma 2.5. Both appear repairable, so the central approach seems sound.","major_comments":[{"comment":"The rooting step for edge-centered trees is invalid under the paper's own definitions. The sentence \"If a tree edge is central, we insert there another node having a single vertex\" produces a vertex incident to two tree edges, directly contradicting Definition 2.1 (\"no vertex is incident to two tree edges\"). The subsequent coloring mechanism also fails: a single-vertex root would be the parent marker vertex for both incident child subtrees, so the two children would assign their colors to the same vertex, and one assignment would overwrite the other. This case is not excluded by the application: a minimal split tree can have exactly two nodes joined by one tree edge (for example, the minimal split tree of K_{2,3} consists of two star nodes), and then the center is an edge. Since Section 5 applies Lemma 3.2 to every connected circle graph, Theorem 1.1 is not established as written for such graphs. The authors should add a treatment of central edges, for instance by canonizing the two rooted subtrees on either side of the central edge and combining their encodings in a canonical order; alternatively they may insert a two-vertex root gadget that satisfies Definition 2.1 and define the parent-marker mechanism for it.","section":"Section 3, Lemma 3.2"},{"comment":"The converse direction of Lemma 2.5 begins with a minimal split decomposition D_G of G, applies an isomorphism pi to obtain a split decomposition D_H of H, and then invokes Theorem 2.3 to conclude that the minimal split tree of H is isomorphic to the constructed T_H. The missing step is the verification that D_H is minimal. This follows because isomorphism preserves the terminal-node types (prime/degenerate) and the condition that no two neighboring degenerate nodes can be joined, but the argument is not given. Since uniqueness of the minimal split tree applies only to minimal split decompositions, the converse direction of the lemma is currently incomplete.","section":"Section 2, Lemma 2.5"}],"minor_comments":[{"comment":"The statement of Lemma 4.3 needs a precondition: for prime circle graphs, the O(n) canonization uses a circle representation as auxiliary input. Without a representation, even reading a dense graph may require Omega(n+m) time. In Section 5 such representations are available from Theorem 2.4, but the interface to Lemma 3.2 should state that the canonization subroutine may depend on auxiliary data attached to the nodes.","section":"Section 4, Lemma 4.3"},{"comment":"The final encoding is described as \"an encoded concatenation\" of variable-length sequences epsilon(2),...,epsilon(c); to make the encoding explicitly decodable, the paper should specify how the boundaries between entries are marked (for example, by prefixing each sequence by its length).","section":"Section 3, Lemma 3.2"},{"comment":"A graph that is both complete and a star (such as K_2) can receive two different canonical encodings depending on whether it is classified as complete or star. The authors should specify a deterministic tie-breaking between the two degenerate types (or exclude such graphs from one of the cases) so that gamma is a well-defined function on isomorphism classes.","section":"Section 4, Canonization of Degenerate Graphs"},{"comment":"Typographical errors: \"cannonical\" for \"canonical\" (throughout), \"Cunnigham\" for \"Cunningham\" (abstract and reference [10]), \"incidance\" for \"incidence\" (Definition 2.1), \"the the lexicographically minimal\" (Section 4), \"an cycle canonization\" (Lemma 4.2), and \"faster that O(n^3)\" (Problem 6.4).","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope and the main structural idea is sound. The edge-centered tree gap in Lemma 3.2 is a genuine obstruction to the proof as written, but it is a repair rather than a fatal flaw; the result is likely correct after adding a central-edge case. The Lemma 2.5 omission is easily filled. I would like to see the revised manuscript with the edge-centered case handled explicitly before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper likely contains a correct O((n+m)α(n+m)) algorithm for circle graph isomorphism, improving Hsu's O(nm). The high-level architecture is sound: compute the minimal split tree, canonize the node labels, then canonize the tree. The meta-algorithm for graph-labeled trees (Lemma 3.2) is a genuine new tool, and the linear canonization of circle representations in Section 4 looks right.\n\nThe soft spots are in the proof details. The stress-test note is correct: Section 3's rooting step inserts a single-vertex node on a central edge, and that node is incident to two tree edges. That violates Definition 2.1 and, more concretely, breaks the coloring because two child subtrees would both write to the same parent marker vertex. So Lemma 3.2 as stated is undefined for edge-centered trees. Since minimal split trees of connected circle graphs can have two nodes joined by one edge, Theorem 1.1 is not established as written. This is a repair, not a fatal flaw—you could handle the edge center by rooting at the two sides and comparing carefully—but the manuscript doesn't include the patch.\n\nAlso, the converse direction of Lemma 2.5 skips the argument that the image of a minimal split decomposition under isomorphism is minimal. That's a short omission; minimality is isomorphism-invariant, so the step can be filled without difficulty. I would not call it a deep problem.\n\nThe paper depends on heavy external machinery (split decomposition, Gioan et al.), which makes verification slow, but the citations look appropriate, and I saw no circularity.\n\nWho should read this: people working on graph isomorphism for structured classes and anyone who wants to use split decomposition as a canonicalization tool. I would bring it to my reading group. As a referee, I would ask for a fix to the edge-centered case and a clean statement of Lemma 2.5; after that, the result is publishable.","headline":"A solid almost-linear isomorphism algorithm for circle graphs, but the tree-canonization lemma has an unpatched edge case that invalidates the theorem as written; worth a round of revision.","tokens_in":12169,"tokens_out":3646,"would_cite":true,"duration_ms":34609,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C62","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Circle graph isomorphism now solvable in almost linear time","keywords":["circle graphs","graph isomorphism","graph canonization","split decomposition","minimal split tree","circle representations","almost linear time","inverse Ackermann function"],"falsifier":"The decisive test is to search for two non-isomorphic connected circle graphs whose minimal split trees are isomorphic; any such pair would produce identical canonical strings and refute the claimed equivalence.","tokens_in":11168,"feed_emoji":"⭕","tokens_out":8136,"duration_ms":77590,"temperature":0.7,"pith_summary":"This paper establishes that the graph isomorphism problem for circle graphs, the intersection graphs of chords of a circle, can be solved in time $O((n+m)\\alpha(n+m))$, where $n$ and $m$ are the numbers of vertices and edges and $\\alpha$ is the inverse Ackermann function. It also produces a canonical string for each circle graph in the same time, so two circle graphs are isomorphic exactly when their canonical strings are equal. The result matters because it replaces the previous $O(nm)$ algorithm and brings isomorphism testing in line with the fastest known recognition algorithm for the class. The argument works by decomposing a circle graph into its unique minimal split tree, canonizing the small prime pieces, and assembling their canonical forms bottom-up.","feed_headline":"New algorithm solves circle graph isomorphism in near-linear time","feed_subtitle":"A canonical fingerprint for every circle graph, computed in $O((n+m)\\alpha(n+m))$ time and beating the old $O(nm)$.","key_machinery":"The load-bearing object is the minimal split tree of a graph: the unique graph-labeled tree obtained by recursively cutting a connected graph along splits (complete-bipartite cuts) until only prime and degenerate graphs remain, with no two neighboring pieces joinable back into a degenerate graph. Each node carries a graph, and neighboring nodes are linked through marker vertices; the original graph is recovered by joining marker-adjacent nodes. The algorithm also uses a canonical rotational encoding of a circle representation: for each chord endpoint it records the color of its vertex and the clockwise gap to the other endpoint of the same chord, producing a circular string whose lexicographically minimal rotation is invariant under relabeling. The canonization of the whole graph is assembled by processing the tree layer by layer from the leaves to the root, replacing each node by an encoding that summarizes its entire rooted subtree.","core_discovery":"The central discovery is a reduction: two connected circle graphs are isomorphic if and only if their minimal split trees are isomorphic, and this tree is unique for each connected graph. A circle graph's minimal split tree has only two kinds of nodes, prime circle graphs, each of which has at most one circle representation up to reversal, and degenerate graphs (complete graphs and stars), whose canonization is immediate. The paper gives a linear-time canonization of circle representations themselves, encodes the unique minimal split tree node by node, and then runs a bottom-up color refinement on the tree whose final color word is a canonical string for the whole graph. Because the minimal split tree can be computed in $O((n+m)\\alpha(n+m))$ time, the whole canonization, and hence isomorphism testing, runs in the same bound; with a circle representation supplied as input, the bound improves to $O(n+m)$.","pith_inferences":["The same pipeline suggests a route to a logarithmic-space isomorphism test for circle graphs: if minimal split-tree construction and circular-string canonization can be implemented in logspace, the bottom-up encoding would likely carry through; the paper leaves this question open.","The paper's open question about partial representation extension could be attacked through minimal split trees: because the canonical encoding stores all node representations up to reversal, a partial representation might be checked against it by local consistency, potentially improving on the stated $O(n^3)$ benchmark.","The inverse-Ackermann factor is the exact cost of the recognition and minimal-split-tree subroutine; a future linear-time recognition algorithm would automatically upgrade the $O((n+m)\\alpha(n+m))$ result to $O(n+m)$."],"forward_implications":["Circle graph isomorphism and canonization can be tested in $O((n+m)\\alpha(n+m))$ time for all inputs, and in $O(n+m)$ time when a circle representation is given.","The output is a true canonical form: the same circle graph always produces the same string, so repeated or distributed isomorphism queries reduce to string comparison.","The canonical-form algorithm doubles as a recognition test: if any prime node fails to have a circle representation, the input graph is not a circle graph.","Because proper circular-arc graphs form a subclass of circle graphs, their isomorphism also becomes decidable in almost linear time.","The bottom-up tree canonization is generic: any graph class closed under split decomposition and supplied with a linear-time canonization for its prime and degenerate pieces inherits an almost linear-time isomorphism test."],"supporting_citations":[{"why":"supplies the uniqueness theorem for minimal split trees, the object that makes the reduction well-defined","marker":"[10]"},{"why":"gives the almost linear-time computation of the minimal split tree and the unique circle representation of every prime circle node","marker":"[20]"},{"why":"characterizes minimal split trees by local non-joinability of neighboring complete and star nodes, used to build the canonical tree","marker":"[21]"},{"why":"is the previous $O(nm)$ isomorphism algorithm whose running time this paper improves","marker":"[24]"},{"why":"provides the $O(n+m)$ split decomposition used in the representation-given case","marker":"[13]"},{"why":"supplies the lexicographically minimal rotation routine that makes circle-representation canonization linear","marker":"[41]"}],"fun_headline_variants":["Near-linear algorithm for circle graph isomorphism","Beat O(nm): circle graph isomorphism in near-linear time","Minimal split trees give near-linear circle graph isomorphism","Circle graph isomorphism via unique split trees"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the minimal split tree is a perfect fingerprint: two connected graphs are isomorphic exactly when their uniquely determined minimal split trees are isomorphic.","fun_headline_variants_meta":{"raw":{"variants":["Near-linear algorithm for circle graph isomorphism","Beat O(nm): circle graph isomorphism in near-linear time","Minimal split trees give near-linear circle graph isomorphism","Circle graph isomorphism via unique split trees"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001139,"raw_usage":{"total_tokens":4679,"prompt_tokens":846,"completion_tokens":3833,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":462,"completion_tokens_details":{"reasoning_tokens":3774}},"tokens_in":462,"tokens_out":3833,"duration_ms":25735,"temperature":1.0,"reasoning_tokens":3774,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:23:20.522801+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The decisive test is to search for two non-isomorphic connected circle graphs whose minimal split trees are isomorphic; any such pair would produce identical canonical strings and refute the claimed equivalence.","supporting_citations":[{"cited_title":"Decomposition of directed graphs","cited_arxiv_id":null,"evidence_quote":"supplies the uniqueness theorem for minimal split trees, the object that makes the reduction well-defined"},{"cited_title":"Gioan, C","cited_arxiv_id":null,"evidence_quote":"gives the almost linear-time computation of the minimal split tree and the unique circle representation of every prime circle node"},{"cited_title":"Gioan, C","cited_arxiv_id":null,"evidence_quote":"characterizes minimal split trees by local non-joinability of neighboring complete and star nodes, used to build the canonical tree"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"is the previous $O(nm)$ isomorphism algorithm whose running time this paper improves"},{"cited_title":"Dahlhaus","cited_arxiv_id":null,"evidence_quote":"provides the $O(n+m)$ split decomposition used in the representation-given case"},{"cited_title":"Fast canonization of circular strings","cited_arxiv_id":null,"evidence_quote":"supplies the lexicographically minimal rotation routine that makes circle-representation canonization linear"}],"review_version":1}