{"id":"43ee41fa-814b-4c08-b546-6e6dc51f2016","arxiv_id":"2608.04583","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact graph edit distance can be computed in O*((4+eps)^n) time and polynomial space whenever one input graph has strictly sublinear balanced separators.","lead":"This paper gives a recursive algorithm that computes exact graph edit distance between two n-node graphs in about 4^n time instead of factorial time, for structured graph families such as planar graphs or bounded-treewidth graphs. A generalist might read it because graph edit distance powers molecular similarity, drug design, and malware detection, and this is the first worst-case exponential improvement for those structured families.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 19/Theorem 20 contain a sign error: c=2^{⌈log_β(1/ε)⌉} is <1 for β∈(0,1), ε<1, so the separator-size increase is undefined; the depth should be ⌈log_β(ε)⌉. The O*((4+ε)^n) proof is incomplete as written.","rationale":"The hereditary separability assumption identified by the reader is genuinely load-bearing but is satisfied by all stated applications (planar, K_h-minor-free, bounded treewidth), so it does not threaten the claims. The concrete flaw is the sign error in Lemma 19 and Theorem 20. It appears in the proof of the main runtime theorem and makes the derivation of the (4+ε)^n bound fail at the point where the rebalanced separator size is estimated. The error is localized and correctable: replace log_β(1/ε) by log_β(ε) (equivalently log_{1/β}(1/ε)). With that correction, c is a constant for fixed ε, the product bound remains 2^{o(n)}, and the O*((4+ε)^n) result follows. Because the manuscript as written contains an incorrect proof step, acceptance should be conditional on fixing this exponent. I do not see a deeper flaw in the recursion or the separator decomposition beyond this.","tokens_in":17053,"tokens_out":50080,"duration_ms":475476,"concrete_test":"Recompute Lemma 19 for β=2/3, ε=0.1: log_{2/3}(1/0.1)=log_{2/3}(10)≈-5.68, so c=2^{⌈-5.68⌉}=2^{-5}≈0.03, an impossible separator-size multiplier. The correct depth is ⌈log_{2/3}(0.1)⌉=6, giving c≤64. Verify that after 6 recursive separator removals, components have size ≤(2/3)^6 n≈0.088 n ≤0.1 n, whereas the paper's formula gives a negative depth. This check settles whether the proof's exponent is a typo.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 19 (Section 4.2) claims a balanced α-separator of size at most c·s(n) with c=2^{⌈log_β(1/ε)⌉}, and Theorem 20 later uses c_μ=2^{log_β(1/μ)}. Since β∈(0,1) and ε,μ∈(0,1/2), log_β(1/ε)<0, so the exponent is negative and c<1. This cannot be: the construction in the proof removes separators recursively until components have size ≤ ε n; after i levels, component size ≤ β^i n, so the required depth satisfies β^i n ≤ ε n, i ≥ log_β(ε) (positive because both β and ε are <1). The correct level count is ⌈log_β(ε)⌉ (equivalently ⌈log_{1/β}(1/ε)⌉), not ⌈log_β(1/ε)⌉. With the typo, c<1 means the supposed α-separator is smaller than the original β-separator, contradicting the need to enlarge separators when rebalancing closer to 1/2. Theorem 20's bound n^{c_μ t} then uses a negative exponent, so the product factor is not 2^{o(n)} as claimed. The runtime proof of the central O*((4+ε)^n) claim is therefore invalid as written; the intended constant is a fixed (possibly large) power of 1/μ and the asymptotic result survives after correction.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes SR-GED, a recursive exact algorithm for the Graph Edit Distance (GED) on undirected labeled graphs with equal numbers of vertices. At each recursive step the algorithm computes a balanced separator S in one input graph G, enumerates all injective images of S in H, adapts the node edit costs to absorb the cut costs between S and the remaining graph, and then splits the remaining graph into two independent subproblems by enumerating all bipartitions of the remaining vertices of H. The paper proves correctness by an induction using Lemma 11, Corollary 13, and Lemma 15, and analyzes the running time for hereditary graph classes with balanced separators, claiming O^*((4+ε)^n) time and polynomial space when the separator size is o(n/log^2 n), with applications to planar, K_h-minor-free, bounded-treewidth, TSP, and QAP instances.","tokens_in":17398,"tokens_out":42496,"duration_ms":399834,"significance":"If the runtime claim holds, the main result is a substantial improvement over the trivial O(n!) enumeration for exact GED on several important graph classes, and the authors argue it is the first worst-case c^n algorithm for these classes. The recursive decomposition with adapted node edit costs is clean, and the correctness argument is well structured. The paper also gives concrete applications to TSP and a class of QAP instances. However, the runtime proof contains a sign error in the logarithmic expression in Lemma 19 and Theorem 20 that makes the currently stated separator-size amplification false; the intended argument is easily repaired and the asymptotic claim is likely salvageable, but the formal proof as written is incomplete.","major_comments":[{"comment":"Lemma 19 defines c = 2^{ceil(log_β(1/ε))} with β∈(0,1) and ε∈(0,1/2), which makes the exponent negative and c<1. The proof's level count l := ceil(log_β(1/ε)) is negative, so the claimed α-separator of size at most c·s(n) is not established; indeed, rebalancing from a β-separator to a more balanced α=1/2+ε separator cannot shrink the separator. The correct depth is ceil(log_{1/β}(1/ε)) (equivalently ceil(log_β ε)), giving c>1. The same sign error propagates to the constant c_μ in Theorem 20, which should be 2^{ceil(log_{1/β}(1/μ))} (or 2^{ceil(log_β μ)}). Because Lemma 19 is the step that converts (β,s)-separability into (α,c·s)-separability, the proof of the O*((4+ε)^n) bound is incomplete as written; the intended conclusion survives after the correction, since the corrected c_μ is a fixed constant for fixed ε and β.","section":"Section 4.2, Lemma 19 and Theorem 20"}],"minor_comments":[{"comment":"The runtime in the abstract should be written O^*((4+ε)^n), not O^*(4+ε)^n, and the definition of c_μ in Theorem 20 lacks the braces around log_β(1/μ).","section":"Abstract and Theorem 20"},{"comment":"The text says a call 'enumerates (n_i choose s(n_i))' separator embeddings, but the algorithm enumerates injective maps from S into V(H), whose number is n_i!/(n_i-s(n_i))!; the bound ≤ n_i^{s(n_i)} used later is still valid.","section":"Section 4.2, proof of Theorem 18"},{"comment":"The statement that the ETH lower bound n^{o(n)} is 'essentially the asymptotic runtime of a brute-force approach' is imprecise, since n^{o(n)} is much smaller than n!.","section":"Section 2"},{"comment":"The sentence 'the tree has at most l levels, giving a total of c≤2l nodes' should read c≤2^l, and the level count should be ceil(log_{1/β}(1/ε)) as discussed in the major comment.","section":"Lemma 19 proof"},{"comment":"Definition 17 allows α∈(0,1), while Theorem 18 and Lemma 19 use α∈[1/2,1); the parameter ranges should be made consistent.","section":"Definition 17 and Theorem 18"},{"comment":"The phrase 'strictly sublinear balanced separators' in the abstract is informal; the formal hypothesis in Theorem 20 is s(n)=o(n/log^2 n), which is not identical to the O(n^{1-ε}) definition given in Section 3.","section":"Abstract and Theorem 20"}],"recommendation":"major_revision","confidential_remarks":"The sign error in Lemma 19/Theorem 20 is real and must be corrected; once corrected, the main result appears sound. I recommend revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a serious look. It gives the first exact algorithm for GED with a c^n worst-case bound on planar, K_h-minor-free, and bounded-treewidth classes, achieving O*((4+ε)^n) in polynomial space. The separator recursion with adapted node edit costs (Definition 9) and the cut-cost decomposition (Lemma 15) are genuinely new, and the correctness induction is clean. The runtime analysis up to the point of Lemma 19 is coherent, and the external separator theorems are cited correctly.\n\nThe main problem is that Lemma 19 as written is wrong. With β∈(0,1), log_β(1/ε) is negative, so the claimed separator-size increase c = 2^{⌈log_β(1/ε)⌉} is less than 1. The correct expression is 2^{⌈log_{1/β}(1/ε)⌉} (equivalently, the recursion depth is ⌈log_β(ε)⌉). This is a typo rather than a conceptual gap—the intended rebalancing argument is clear and the asymptotic result survives after replacing the constant—but as written, Theorem 20's proof is invalid. A referee should require this fix.\n\nTwo minor issues: adapted node edit costs are computed in O(|S| n^2), not O(n^2) as claimed in the proof of Theorem 18; this is still polynomial, so the O* bound is unaffected. The TSP reduction (Theorem 27) is terse; I believe it works because deleting a cycle edge is made prohibitively expensive, but the text should spell out why non-edges in the target graph do not create zero-cost shortcuts.\n\nThis is a final-style paper for researchers in exact exponential algorithms, especially for GED, TSP, and QAP. It is a serious contribution with a plausible, novel result. I would send it to peer review rather than desk-reject, with an explicit note to the referees to verify the constants in Lemmas 19 and Theorem 20.","headline":"Genuinely new separator-based exact GED algorithm with O*((4+ε)^n) on planar/minor-free/bounded-treewidth graphs; runtime proof currently has a fixable sign error in Lemma 19 that a referee must catch before publication.","tokens_in":17944,"tokens_out":6046,"would_cite":true,"duration_ms":60630,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q25","05C85","68R10","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper presents SR-GED, a recursive separator-based algorithm that computes exact graph edit distance in $O^*((4+\\epsilon)^n)$ time and polynomial space when one input graph admits strictly sublinear balanced separators, covering…","keywords":["Graph Edit Distance","exact exponential-time algorithms","balanced separators","planar graphs","minor-free graphs","treewidth","Traveling Salesman Problem","Quadratic Assignment Problem"],"falsifier":"One direct check: for a candidate graph class, compute the size of the smallest balanced separator of every induced subgraph along the recursion tree of SR-GED. A single graph whose induced subgraph at size $m$ requires a balanced separator of size $\\Omega(m/\\log m)$ would place that graph outside Corollary 22, and an instance family where the total separator size along a root-to-leaf path is $\\Omega(n/\\log n)$ rather than $o(n/\\log n)$ would make the exponent in Theorem 18 larger than $\\log_2(4+\\epsilon)n$, refuting the $(4+\\epsilon)^n$ claim for that family.","tokens_in":16848,"feed_emoji":"⚡","tokens_out":12476,"duration_ms":133908,"temperature":0.7,"pith_summary":"The paper claims that exact graph edit distance (GED) between two $n$-node graphs can be computed in $O^*((4+\\epsilon)^n)$ time and polynomial space whenever one of the two graphs belongs to a hereditary graph class, closed under taking induced subgraphs, that admits strictly sublinear balanced separators. Such classes include planar graphs, graphs excluding a fixed $K_h$ minor, and graphs of bounded treewidth, so the result replaces the brute-force $O^*(n!)$ worst-case bound for exact GED on these classes. The algorithm also returns an optimal node mapping and edit sequence, and the same runtime bound carries over to the traveling salesman problem and to quadratic assignment problems with a suitably separable nonzero-flow graph. The paper further observes that the result cannot extend to arbitrary graphs unless the exponential time hypothesis fails.","feed_headline":"Separators shrink graph edit distance from n! to (4+ε)^n","feed_subtitle":"A recursive separator algorithm computes exact GED in (4+ε)^n time on separable graph classes.","key_machinery":"The load-bearing mechanism is the pair consisting of a balanced separator and adapted node edit costs. A balanced $\\alpha$-separator is a vertex set whose removal leaves two parts of size at most $\\alpha n$; the named graph classes supply such separators at every induced subgraph. Adapted node edit costs add the cost of the cut edges between a remaining vertex and the already-fixed separator image to that vertex's substitution cost, so the two sides of the recursion no longer interact through the cut. Lemma 15 turns this into the decomposition $\\mathrm{GED}(G_1\\cup G_2,H)=\\min_{W_1}(\\mathrm{GED}(G_1,H[W_1])+\\mathrm{GED}(G_2,H-W_1)+c^+_\\delta(W_1))$, where the last term is the insertion cost for edges crossing the image cut in $H$, and this is what makes independent recursive calls possible. The runtime analysis multiplies the separator-enumeration factor $n^{s(n)}$ against the bipartition-branching factor $2^n$ at every level; the condition $s(n)=o(n/\\log^2 n)$ keeps the cumulative product at $2^{o(n)}$, giving the base $4$.","core_discovery":"The central discovery is that separator-based divide-and-conquer can solve GED exactly despite the need to match two graphs at once. At each recursive step the algorithm picks a small balanced separator $S$ in the 'easy' graph $G$, enumerates every injective image of $S$ in the other graph $H$, and rewrites the node edit costs so that the costs of editing edges crossing the separator cut are charged to the remaining vertices. Once $S$ is removed, $G$ splits into two disconnected pieces; by enumerating all bipartitions of $H$'s remaining vertices into the two image sets, the two pieces become independent subproblems. The paper proves this recursion is exact and shows that when the separator size is $s(n)=o(n/\\log^2 n)$, the total work is $O^*((4+\\epsilon)^n)$ after rebalancing the separators.","pith_inferences":["The adapted-cost decomposition is a template for other injective-mapping optimization problems, not just GED: any objective that can be written as node costs plus edge costs over a bijection should admit the same separator recursion.","The constant 4 comes from the product of separator enumeration and bipartition enumeration; pruning bipartitions with labels or degree statistics, or trading memory for time with dynamic programming, may lower the base in practice and possibly in theory.","When comparing two real-world graphs, the algorithm's asymmetry suggests always routing the recursion through the graph with better separator structure, which could be decided by a quick treewidth or separator heuristic.","The reported low treewidths of GEDLIB benchmarks indicate that, once engineered, this worst-case improvement may translate into exact solutions on much larger instances than current tree-search or ILP solvers handle, though that extrapolation is an empirical hope rather than a theorem of the paper."],"forward_implications":["Exact GED and an optimal node map can be computed in $O^*((4+\\epsilon)^n)$ time and polynomial space for planar graphs, $K_h$-minor-free graphs, and hereditary bounded-treewidth graph classes.","The same bound applies to the traveling salesman problem, matching the known $O^*(4^n)$ polynomial-space bound up to the $\\epsilon$.","Quadratic assignment instances with symmetric distances and a nonzero-flow interaction graph that is $(\\alpha, O(n^{1-\\delta}))$-balanced-separable inherit the same runtime.","Because the argument needs the separator structure in only one of the two input graphs, the improvement is available whenever either graph of a GED instance is planar, minor-free, or low-treewidth.","The recursive structure allows SR-GED to be combined with practical exact solvers such as ILP-based or $A^*$-based methods at the leaves of the recursion."],"supporting_citations":[{"why":"Supplies the planar separator theorem used to place planar graphs inside the runtime corollaries.","marker":"[33]"},{"why":"Extends sublinear balanced separators to $K_h$-minor-free graphs, one of the named graph classes.","marker":"[4]"},{"why":"Provides the separator theorem for graphs of bounded treewidth.","marker":"[36]"},{"why":"Gives the metric-cost equivalence between node maps and edit sequences, and the triangle-inequality preprocessing that justifies the node-map formulation.","marker":"[9]"},{"why":"Establishes the ETH-based lower bound for subgraph isomorphism, used to argue the result cannot be generalized to all graphs.","marker":"[16]"},{"why":"Held-Karp dynamic programming for TSP, the classic baseline the TSP corollary improves on in space or matches in time.","marker":"[23]"},{"why":"Gurevich and Shelah's $O^*(4^n)$ polynomial-space bound for Hamiltonian path and TSP, which the new TSP result matches up to $\\epsilon$.","marker":"[22]"},{"why":"The GED benchmark library whose treewidth measurements show that typical real-world instances satisfy the bounded-treewidth hypothesis.","marker":"[7]"}],"fun_headline_variants":["GED drops from n! to (4+ε)^n with separators","Exact GED in (4+ε)^n time via separator recursion","Separator divide-and-conquer solves GED in (4+ε)^n","From factorial to exponential: GED now (4+ε)^n","Exact graph edit distance: separators yield (4+ε)^n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every induced subgraph of the separable input graph that the recursion produces has a balanced separator of size $s(m)=o(m/\\log^2 m)$; if any recursive subproblem lacks such a separator, the product bound in the runtime proof stops being $2^{o(n)}$ and the $(4+\\epsilon)^n$ guarantee is not established.","fun_headline_variants_meta":{"raw":{"variants":["GED drops from n! to (4+ε)^n with separators","Exact GED in (4+ε)^n time via separator recursion","Separator divide-and-conquer solves GED in (4+ε)^n","From factorial to exponential: GED now (4+ε)^n","Exact graph edit distance: separators yield (4+ε)^n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000851,"raw_usage":{"total_tokens":3684,"prompt_tokens":915,"completion_tokens":2769,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":2667}},"tokens_in":531,"tokens_out":2769,"duration_ms":19258,"temperature":1.0,"reasoning_tokens":2667,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:29:04.271663+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"One direct check: for a candidate graph class, compute the size of the smallest balanced separator of every induced subgraph along the recursion tree of SR-GED. A single graph whose induced subgraph at size $m$ requires a balanced separator of size $\\Omega(m/\\log m)$ would place that graph outside Corollary 22, and an instance family where the total separator size along a root-to-leaf path is $\\Omega(n/\\log n)$ rather than $o(n/\\log n)$ would make the exponent in Theorem 18 larger than $\\log_2(4+\\epsilon)n$, refuting the $(4+\\epsilon)^n$ claim for that family.","supporting_citations":[],"review_version":1}