{"id":"96f0604e-08b8-4cdd-bdea-7c062c68ae96","arxiv_id":"1908.05268","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The 2-dimensional Weisfeiler-Leman algorithm detects 2-separators and implicitly computes 3-connected decompositions, yielding a WL dimension upper bound of k for treewidth-k graphs and a factor-2-tight lower bound.","lead":"This paper proves that the 2-dimensional Weisfeiler-Leman algorithm can detect the separating pairs (2-separators) of a graph, a task previously known only for the stronger 3-dimensional version. The result gives improved upper and lower bounds on the algorithm dimension needed for graphs of bounded treewidth.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.4 depends on an unproven strengthening of [27, Lemmas 17/18]; the advertised decomposition result is conditional on deferred technical work.","rationale":"The reader's weakest-assumption analysis identifies exactly the same load-bearing concern: Theorem 5.4, which is the formal statement of the abstract's main claim about implicitly computing the 3-connected decomposition, is not fully proved. The paper supplies a complete and detailed proof for the separator-detection machinery in Sections 3 and 4, and for Corollary 5.3 and Theorem 5.5 in Section 5, but the step from separator detection to the full decomposition theorem is deferred to an unproven strengthening of two lemmas from a previous paper. I do not see a more serious flaw: the earlier sections are concrete, the two-color case in Theorem 4.5 is developed in full, and the treewidth application in Theorem 6.3 has an independent proof that does not rely on the missing decomposition argument. The gap is specific and plausibly repairable, so the appropriate verdict remains CONDITIONAL as the reader concluded.","tokens_in":32402,"tokens_out":13951,"duration_ms":144138,"concrete_test":"Write out the strengthened versions of Lemmas 17 and 18 from [27] in the setting of Section 5, replacing the dimension-3 colors χ^k_G(s1,s2,v) with χ^k_G(s1,v) for k >= 2, and verify the two properties used in the induction: (i) the partition induced by χ^k_G on V(G⊥) refines λ⊥; (ii) vertices in V(G⊥) receive different colors from vertices in V(G) \\ V(G⊥). A concrete computational check is to search over small graphs with nested or interacting 2-separators and compare, for every pair (s1,v), the k-WL color against the component size and attachment data required by Lemma 18: if two non-isomorphic situations agree on all χ^k_G(s1,v) but require the extra vertex s2 to be separated, the sketched strengthening is false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in Section 5, Theorem 5.4. The proof sketch explicitly says that after cutting off leaves of the 3-connected decomposition and encoding information in colors on former 2-separators, showing that the partition induced by χ^k_G on V(G⊥) is finer than λ⊥ 'requires some more work, breaking down to strengthening Lemma 18 in [27].' The only justification offered is that Corollary 5.3 gives special colors to separator vertices, so one may replace χ^k_G(s1,s2,v) by χ^k_G(s1,v). No strengthened statement of Lemma 17 or Lemma 18 is stated or proved, and the original induction in [27] uses those lemmas at dimension 3. If the 2-dimensional or k-dimensional version needs a stronger invariant than the colors relative to a single separator vertex—for example, information about interactions between multiple separators in the decomposition tree—the advertised implication 'orbits on arc-colored 3-connected graphs imply distinguishing all graphs in a minor-closed class' does not follow from the material in the paper. Corollary 5.3, Theorem 5.5, and the treewidth upper bound in Theorem 6.3 do not supply this missing piece, since Theorem 6.3 avoids the full decomposition theorem. This is an internal completeness gap, not a disagreement with consensus: the missing lemmas are probably repairable, but as written the central claim is conditional.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the expressive power of the Weisfeiler-Leman (WL) algorithm. It proves that for k ≥ 2, the k-dimensional WL algorithm distinguishes k-separators from other k-tuples, and specifically that the 2-dimensional algorithm detects 2-separators. Building on this, it claims that the k-dimensional WL algorithm implicitly computes the decomposition of a graph into its 3-connected components, which would imply that distinguishing graphs in a minor-closed class reduces to distinguishing arc-colored 3-connected graphs in that class. The paper further derives that connected constituent graphs of association schemes are either cycles or 3-connected, and it applies the separator results to prove a new upper bound of k on the WL dimension of graphs of treewidth at most k, together with a lower bound that is within a factor of 2 of the upper bound.","tokens_in":32619,"tokens_out":9704,"duration_ms":88802,"significance":"The separator-detection results are solid and valuable: Sections 3 through 5 up to Corollary 5.3 and Theorem 5.5 contain detailed, largely self-contained proofs, and the association-scheme corollary is a genuine new structural insight. If Theorem 5.4 were fully proved, the decomposition theorem would be a significant step toward settling the WL dimension of planar graphs and would unify several dimension bounds. The treewidth upper bound is a clean improvement over the previous k + 2, and the lower bound is asymptotically tight up to a factor of 2, although the color-encoding issue raised below needs clarification.","major_comments":[{"comment":"The paper's central decomposition claim is not established as written. The proof sketch explicitly states that showing the partition induced by χ^k_G on V(G⊥) is finer than λ⊥ \"requires some more work, breaking down to strengthening Lemma 18 in [27]\", and the only indication is that Corollary 5.3 lets one replace χ^k_G(s1,s2,v) by χ^k_G(s1,v). No strengthened statement of [27, Lemmas 17 and 18] is formulated, and no proof is supplied for the strengthened induction. Since [27] proves these lemmas only for dimension 3, the advertised implication—that orbit-determination on arc-colored 3-connected graphs implies distinguishing all graphs in a minor-closed class—is conditional on deferred technical work. Corollary 5.3, Theorem 5.5, and Theorem 6.3 do not substitute for this step, because they do not address the interaction of multiple separators in the decomposition tree.","section":"Section 5, Theorem 5.4 (proof sketch)"},{"comment":"The CFI construction yields vertex-colored graphs, while Corollary 6.9 is a statement about the WL dimension of the uncolored class T_k. The paper does not describe how the vertex colors in CFI(G_{n,n}) and CFI_x(G_{n,n}) are removed (for instance, by a standard color-encoding gadget), nor how such a removal affects treewidth. Without this clarification, the lower bound may only apply to colored graphs and would not directly bound dim_WL(T_k).","section":"Section 6.2, Theorem 6.8 and Corollary 6.9"}],"minor_comments":[{"comment":"The proof sketch says \"suppose the 2-dimensional WL algorithm determines orbits\" although the theorem is stated for arbitrary k ≥ 2; this should be \"k-dimensional\".","section":"Section 5, proof of Theorem 5.4"},{"comment":"Some displayed formulas have unbalanced parentheses, for example \"G[A_i ∪ ¯a ∪ {v}], ¯a, v)\" and \"H[B_i ∪ ¯b ∪ {w}], ¯b, w)\"; please fix the typesetting.","section":"Section 6.3, proof of Theorem 6.3"},{"comment":"The reduction to the 2-dimensional case for k > 2 is stated in a single sentence and deserves a more detailed justification that the first k−2 vertices can be chosen so that the remaining pair is a 2-separator in the reduced graph and that the color equality is preserved under this reduction.","section":"Corollary 5.3, last paragraph"},{"comment":"In Claim 1, phrases such as \"It is not hard to see\" and \"by regularity\" compress several counting arguments; expanding these steps would improve verifiability.","section":"Section 4, proof of Theorem 4.5"}],"recommendation":"major_revision","confidential_remarks":"This is a serious piece of work with a substantial proven core. The main issue is that the headline decomposition theorem (Theorem 5.4) is only sketched and depends on an unproved strengthening of two lemmas from [27]. I would encourage the editor to request a full proof of that step. If the authors supply it, the paper would be very suitable for publication; as it stands, the abstract overstates what is proven."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should look at this one. The main new results are real: 2-dimensional WL detects 2-separators (previous best was 3-dimensional from [27]); this gives a treewidth upper bound of k in place of k+2; and there's a CFI-based lower bound within a factor of 2. There's also a nice byproduct about association schemes: a connected constituent graph is either 3-connected or a cycle. Sections 3 and 4 are the heart of the separator detection, and the proofs there are detailed and largely self-contained. Corollary 5.3 (equal k-tuple colors imply separators map to separators) looks fully proved. Theorem 5.5 on component sizes also appears solid. The treewidth upper bound (Theorem 6.3) is a separate argument that avoids the full decomposition theorem, and it holds up as far as I can tell. The CFI lower bound is standard but applied cleanly.\n\nNow the soft spot, and it's a real one. The abstract and introduction advertise the headline result: the 2-dimensional WL algorithm implicitly computes the decomposition into 3-connected components. That is Theorem 5.4, and its proof is only a sketch. The sketch itself admits that showing the induced partition is finer than the arc-coloring 'requires some more work, breaking down to strengthening Lemma 18 in [27]'. The strengthened forms of Lemmas 17 and 18 are never stated, and the one-sentence justification (replace s2 with colors relative to a single separator vertex) is plausible but not a proof. The original induction in [27] used those lemmas at dimension 3, and it's not obvious that just having special colors on separator vertices is enough once multiple separators interact in the decomposition tree. So as written, Theorem 5.4 is conditional on deferred technical work, and the abstract overstates it. This is an internal completeness gap, not a disagreement with the intended claim—I'd bet the lemmas are repairable—but a serious referee should demand they be written out.\n\nMinor issues: some steps in Section 4 are hand-wavy (e.g., 'it is not hard to see' in Claim 1 of Theorem 4.5), and the k=2, non-2-connected case of Corollary 5.3 leans on [27, Theorem 6] a bit quickly. None of these bother me as much as the Theorem 5.4 gap.\n\nWho's it for: researchers in Weisfeiler–Leman, counting logics, and graph isomorphism; also people working on treewidth and descriptive complexity. It deserves a serious referee and a conditional accept or major revision, with the authors asked to either prove the strengthened lemmas or clearly mark the decomposition theorem as conditional.","headline":"A genuinely strong paper with a real gap: the separator detection and treewidth bounds are solid, but the headline decomposition theorem is only sketched and rests on unstated strengthened lemmas.","tokens_in":33206,"tokens_out":1973,"would_cite":true,"duration_ms":21206,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C60","05C40","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"The two-dimensional Weisfeiler-Leman algorithm implicitly computes the decomposition of a graph into its 3-connected components.","keywords":["Weisfeiler-Leman algorithm","graph isomorphism","triconnected decomposition","separator detection","treewidth","association schemes","counting logic C3","WL dimension"],"falsifier":"Find two 2-connected graphs $G$ and $H$ such that the stable 2-dimensional WL color of a separating pair in $G$ equals the color of a non-separating pair in $H$; such a pair would refute Theorem 5.2, the technical heart of the paper, because the entire decomposition program reduces to that statement.","tokens_in":32142,"feed_emoji":"🧩","tokens_out":9484,"duration_ms":89479,"temperature":0.7,"pith_summary":"This paper establishes that the Weisfeiler-Leman (WL) algorithm detects connectivity structure from dimension 2 upward: if a k-tuple of vertices separates a graph, no graph can give that k-tuple the same WL-k color unless the corresponding tuple separates it too. The authors use this to prove that the 2-dimensional WL algorithm implicitly computes the classical decomposition of a graph into its 3-connected components, so the dimension needed to distinguish two graphs is at most the dimension needed to distinguish their pieces. They then apply the decomposition to graphs of treewidth at most k, proving the k-dimensional WL algorithm identifies every such graph, and they show via a standard lower-bound construction that the WL dimension of treewidth-k graphs lies between $\\lceil k/2\\rceil - 3$ and $k$. As a byproduct, every connected constituent graph of an association scheme is either a cycle or 3-connected, a fact previously known only for the more restricted symmetric case.","feed_headline":"2D Weisfeiler-Leman reads a graph's 3-connected skeleton","feed_subtitle":"Starting at dimension 2, WL colors mark separating vertex tuples, yielding a new treewidth bound and a tight WL-dimension window.","key_machinery":"The load-bearing object is the stable tuple coloring $\\chi_{G,k}$ produced by the k-dimensional WL algorithm, which refines the coloring of vertex tuples by repeatedly counting, for each tuple, the multiset of colors obtained by replacing one coordinate by every vertex. Around that object, the paper's main tool is the auxiliary graph $G[[S]]$: its vertices are the vertices of $G$ whose diagonal color lies in a set $S$, and two such vertices are adjacent when connected by a path in $G$ that avoids $S$. The WL algorithm detects such paths, so $G[[S]]$ inherits stable colors; the proof shows that a 2-separator in $G$ forces $G[[S]]$ to be a cycle in the uniform-color cases, forcing $H[[S]]$ to be a cycle too, which is what transfers the separator property from $G$ to $H$. The edge-maximality argument used throughout the structural lemmas is the mechanism that rules out all non-cycle configurations.","core_discovery":"The central claim appears in Corollary 5.3: for all $k \\ge 2$, the k-dimensional WL algorithm distinguishes k-separators from other k-tuples of vertices. The proof for $k = 2$ first shows that any graph whose stable WL coloring gives one color to all vertices and that contains a 2-separator must be a cycle (Theorem 3.9), then extends the same conclusion to graphs with two vertex colors (Theorem 4.5). These uniform-color cases are lifted to arbitrary graphs through the graph $G[[S]]$, which connects vertices of a chosen color set $S$ by paths that avoid $S$; the 2-dimensional WL algorithm can see these paths, so a 2-separator in $G$ forces the corresponding tuple in any WL-equivalent graph $H$ to separate $H$ as well (Theorem 5.2). The final theorem (Theorem 5.4) states the payoff: in a minor-closed graph class, if the k-dimensional WL algorithm determines orbits on all arc-colored 3-connected graphs in the class, then it distinguishes all non-isomorphic graphs in the class.","pith_inferences":["I read the paper's closing conjecture as the natural next test: if the 2-dimensional WL algorithm determines orbits on all 3-connected planar graphs, Theorem 5.4 would imply that it identifies every planar graph, settling the open 2-versus-3 question for planar graphs.","A fully formal proof of Theorem 5.4 still requires stating and proving the strengthened versions of Lemmas 17 and 18 from the earlier planar-graph work; the paper marks this as requiring more work and leaves the details out.","Because the separator relation is definable in $C^3$, graph representations built on 2-WL colors inherit a decomposition-aware signal; one could test this by comparing 2-WL-based embeddings with explicit 3-connected-component features on graph-separation benchmarks.","The subdivided-grid lower-bound pair suggests the true WL dimension of treewidth-$k$ graphs may be closer to $k/2$ than to $k$; computing the exact dimension for small $k$, say $k = 4$ or $5$, would show whether the factor-2 gap is an artifact."],"forward_implications":["For every $k \\ge 2$, a k-separator in $G$ can share its WL-k color with a tuple in $H$ only if that tuple is also a k-separator of $H$.","For any minor-closed graph class, the WL dimension is bounded by the dimension needed to determine orbits on its arc-colored 3-connected graphs; the decomposition step adds no extra dimension.","The WL dimension of graphs of treewidth at most $k$ lies between $\\lceil k/2\\rceil - 3$ and $k$, improving the previous upper bound of $k+2$ and matching the lower bound up to a factor of 2.","Two non-isomorphic graphs can be told apart by the k-dimensional WL algorithm ($k \\ge 2$) as soon as their decompositions into 3-connected components are told apart.","Connected constituent graphs of association schemes are cycles or 3-connected, and the sizes of the components left by deleting a 2-separator are expressible in the three-variable counting logic $C^3$."],"supporting_citations":[{"why":"Supplies the decomposition-to-3-connected-components framework and the two technical lemmas whose strengthening from dimension 3 to 2 is the key step in Theorem 5.4.","marker":"[27]"},{"why":"Provides the lower-bound construction and the pebble-game equivalence used to prove WL indistinguishability results.","marker":"[9]"},{"why":"States the theorem that the k-dimensional WL algorithm cannot distinguish pairs built from graphs of treewidth larger than k, giving the lower bound.","marker":"[10]"},{"why":"Gives the previous upper bound of k+2 on the WL dimension of treewidth-k graphs, which the new upper bound of k improves.","marker":"[17]"},{"why":"Supplies the recursive separator characterization of tree decompositions used in the proof that k-dimensional WL identifies treewidth-k graphs.","marker":"[1]"},{"why":"Provides the implementation time bound for WL and the link to the counting logic C^{k+1}, used for the definability statements.","marker":"[26]"}],"fun_headline_variants":["WL sees graph separators, unlocks treewidth bound","Weisfeiler-Leman implicitly finds 3-connected components","2D WL decodes graph structure into 3-connected parts","New WL bounds from separator detection","Graph separator detection powers WL dimension limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 5.4 rests on a sketched strengthening of Lemmas 17 and 18 from the earlier planar-graph work, moving from dimension 3 to dimension 2; the paper does not state or prove those strengthened lemmas, and if that step fails, the advertised decomposition theorem would not follow from the arguments given.","fun_headline_variants_meta":{"raw":{"variants":["WL sees graph separators, unlocks treewidth bound","Weisfeiler-Leman implicitly finds 3-connected components","2D WL decodes graph structure into 3-connected parts","New WL bounds from separator detection","Graph separator detection powers WL dimension limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000235,"raw_usage":{"total_tokens":1549,"prompt_tokens":1044,"completion_tokens":505,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":660,"completion_tokens_details":{"reasoning_tokens":432}},"tokens_in":660,"tokens_out":505,"duration_ms":5213,"temperature":1.0,"reasoning_tokens":432,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:18:21.370679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find two 2-connected graphs $G$ and $H$ such that the stable 2-dimensional WL color of a separating pair in $G$ equals the color of a non-separating pair in $H$; such a pair would refute Theorem 5.2, the technical heart of the paper, because the entire decomposition program reduces to that statement.","supporting_citations":[{"cited_title":"The Weisfeiler-Leman dimension of planar graphs is at most 3","cited_arxiv_id":null,"evidence_quote":"Supplies the decomposition-to-3-connected-components framework and the two technical lemmas whose strengthening from dimension 3 to 2 is the key step in Theorem 5.4."},{"cited_title":"An optimal l ower bound on the number of variables for graph identifications","cited_arxiv_id":null,"evidence_quote":"Provides the lower-bound construction and the pebble-game equivalence used to prove WL indistinguishability results."},{"cited_title":"The power of counting log ics on restricted classes of finite structures","cited_arxiv_id":null,"evidence_quote":"States the theorem that the k-dimensional WL algorithm cannot distinguish pairs built from graphs of treewidth larger than k, giving the lower bound."},{"cited_title":"Definability and descri ptive complexity on databases of bounded tree-width","cited_arxiv_id":null,"evidence_quote":"Gives the previous upper bound of k+2 on the WL dimension of treewidth-k graphs, which the new upper bound of k improves."},{"cited_title":"Corneil, and Andrzej Proskurow ski","cited_arxiv_id":null,"evidence_quote":"Supplies the recursive separator characterization of tree decompositions used in the proof that k-dimensional WL identifies treewidth-k graphs."},{"cited_title":"Describing Graphs: A First-Order Approach to Graph Canonization, pages 59–81","cited_arxiv_id":null,"evidence_quote":"Provides the implementation time bound for WL and the link to the counting logic C^{k+1}, used for the definability statements."}],"review_version":1}