{"id":"0bd54923-8434-4d21-9067-52336559cc09","arxiv_id":"2504.20780","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A fully dynamic maximal matching can be maintained deterministically in O~(n^(8/9)) amortized update time, the first sublinear deterministic bound.","lead":"This paper gives the first deterministic fully dynamic algorithm that maintains a maximal matching in sublinear time per edge update, with O~(n^(8/9)) amortized update time, plus a faster randomized version with O~(n^(3/4)) amortized time against an adaptive adversary. It breaks a long-standing Omega(n) deterministic barrier for dense graphs and introduces a new way to use edge-degree constrained subgraphs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The deterministic O~(n^{8/9}) bound is supported by an unproved refined Even-Shiloach guarantee (Theorem 5.7); this guarantee is the single load-bearing assumption and should be verified before acceptance.","rationale":"The reader's weakest_assumption identifies exactly the same point: Theorem 5.7 is load-bearing for the deterministic result and is cited rather than proved. I read the rest of the paper in good faith and found the EDCS-based framework, the degree-gap layering, the random-walk algorithm, and the phase amortization internally coherent; no independent fatal flaw emerged. The concern is not that the ES guarantee is known to be false, but that the deterministic n^{8/9} claim is conditioned on a non-routine extension of a classic data structure. If Theorem 5.7 holds, the assembled lemmas do yield the claimed bounds for the chosen parameters. If it does not, the deterministic result loses its supporting proof while the randomized adaptive result may survive. Since the central advertised contribution is deterministic sublinear update time, acceptance should be conditional on a complete proof or a precise citation establishing Theorem 5.7 in the weighted, Remove-supporting setting used by Algorithm 1. The recommendation is CONDITIONAL rather than REJECT because the gap appears to be a missing justification, not a demonstrated contradiction.","tokens_in":47293,"tokens_out":33669,"duration_ms":348903,"concrete_test":"Independently derive the total update time of the ES data structure in Theorem 5.7 for the exact operation sequence in Algorithm 1: unit-weight edges, edges (v,t) inserted with weight equal to the current dist(v,t), ordinary deletions, and Remove(v). The derivation must show that each vertex v is rescanned at most O(distmax(v,t)) times; if the proof instead needs an extra factor of q_ep, a bound on weighted insertions, or the removal of the Remove operation, then Lemma 5.20's epoch bound is unsupported. As a sanity check, instrument a small simulation (n about 20, gamma about 0.1, q_ep about 2) of the weighted ES tree over random degree-gap deletion sequences and compare the actual number of edge scans against the claimed formula; a violation would falsify Theorem 5.7 as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The deterministic half of Theorem 1.1 is carried by Lemma 5.1(1), whose proof is the ES-tree argument in Section 5.3. That argument depends on Theorem 5.7, a \"refined\" Even-Shiloach guarantee for a directed graph with positive integer weights, distance-non-decreasing insertions, and a Remove(v) operation. The paper does not prove this theorem; it only asserts that it is easy to check that [SE81, Kin99] give O(total updates + sum_v degmax(v)*distmax(v,t)). This is not a routine consequence of the standard ES analysis: standard ES trees handle unweighted decremental graphs, charge O(deg(v)) per distance increase, and do not by themselves justify the weighted t-edges (whose weights are set equal to the current dist(v,t) in Algorithm 1) or the batch deletion of all edges incident to a removed vertex. Lemma 5.20's per-epoch bound, and hence the deterministic O~(n^{8/9}) update time in Theorem 1.1, would not be supported if the true cost of maintaining the tree in this weighted monotone setting is any larger than the stated sum. The randomized O~(n^{3/4}) bound uses random walks rather than the ES tree and is not exposed to this particular gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a fully dynamic maximal matching algorithm with a deterministic O~(n^{8/9}) amortized update time and a randomized O~(n^{3/4}) amortized update time that is correct with high probability against an adaptive adversary. The approach maintains an EDCS, classifies vertices by EDCS degree into high/medium/low sets, and reduces the task of matching all high-degree vertices to maintaining a left-perfect matching in a bipartite graph with a degree gap. This left-perfect matching is maintained either by random alternating walks (randomized version) or by a deterministic residual-graph shortest-path tree using a refined Even-Shiloach guarantee (deterministic version). A maximal matching in the remaining adjunct graph is maintained by exploiting the low arboricity of that graph. The claimed result would be the first deterministic sublinear update time for fully dynamic maximal matching and would answer a long-standing open problem.","tokens_in":47470,"tokens_out":16130,"duration_ms":160326,"significance":"If the deterministic analysis is complete, this is a landmark result for dynamic graph algorithms: it breaks the Omega(n) deterministic barrier for maximal matching in dense graphs and introduces a genuinely new use of the EDCS. The randomized half is well supported by the random-walk argument on Eulerian expanders, and the overall phase-based accounting is coherent and parameter-free. The paper also gives an honest discussion of limitations and open problems. However, the deterministic half currently rests on a load-bearing refined Even-Shiloach guarantee that is asserted rather than proved, and there is a clear algebraic/typographical error in the formula that drives the deterministic exponent. These issues must be fixed before the deterministic n^{8/9} claim is established.","major_comments":[{"comment":"Theorem 5.7 is the sole engine for the deterministic Left Perfect Matching bound in Lemma 5.1(1), but it is not proved. The paragraph \"Comparison to Standard ES guarantees\" asserts that the refined guarantee follows easily from [SE81, Kin99]; this is not a routine consequence for the setting used here, which involves positive integer weights, insertions that merely do not decrease distances, and a batch Remove(v) operation. In particular, the claim that removing v by deleting all incident edges \"in a single batch\" costs only O(degmax(v) * distmax(v,t)) does not by itself account for distance increases at other vertices whose shortest paths used v; that work must be charged somewhere, and the cited standard ES analyses do not explicitly provide this accounting for weighted graphs with Remove(v). Since Lemma 5.20 and hence the deterministic O~(n^{8/9}) bound in Theorem 1.1 depend entirely on Theorem 5.7, the authors must supply a full proof of Theorem 5.7 or replace it by a published theorem with exactly the stated guarantees. The randomized half is not exposed to this issue.","section":"Section 5.3, Theorem 5.7"},{"comment":"There is a serious formula/typo problem in the deterministic total update time. Lemma 5.1(1) states a factor (1 + u*sqrt(n*gamma)), but the proof of that lemma uses q_ep = sqrt(n*gamma) and obtains (1 + u/q_ep) epochs, i.e., (1 + u/sqrt(n*gamma)). The derivation in the proof of Lemma 6.6 exhibits the same inconsistency: it writes O~( (nB/delta) * (delta*n*sqrt(n*delta)) ) and claims this equals O~( B*n^{1/2}*delta^{-3/2} * delta*n ). The left-hand side simplifies to B*n^{5/2}*delta^{1/2}, whereas the right-hand side is B*n^{3/2}*delta^{-1/2}; these differ by a factor of n*delta. With the printed formulas and B=n^{2/9}, delta=n^{-1/9}, the deterministic amortized update time would be O~(n^{16/9}), not O~(n^{8/9}). If the intended factor is u/sqrt(n*gamma), as the proof in Section 5.3.4 strongly indicates, then the deterministic n^{8/9} balance works. Both Lemma 5.1(1) and the display in Lemma 6.6 must be corrected, and the proof must be consistent with the corrected statement.","section":"Lemma 5.1(1) and Section 6.3.5"}],"minor_comments":[{"comment":"As written, Observation 5.10 says that T is still a shortest path tree \"to v\" after adding (v,u), but T is a tree to the sink t and the subsequent use in Algorithm 1 requires that no distances to t decrease. This appears to be a typo; please restate the observation as \"T remains a shortest path tree to t\" and justify it for weighted edges.","section":"Section 5.3.2, Observation 5.10"},{"comment":"The notation L_i(v) is introduced with a parameter v that is never used; it should just be L_i. This is confusing because v is also used for vertices in R.","section":"Section 5.3.5, Claim 5.21"},{"comment":"The sentence \"each LPM.Delete adss at most one vertex to Raff\" contains a typo (\"adss\" should be \"adds\").","section":"Section 5.3.4, Claim 5.19"},{"comment":"In the proof of Corollary 6.16, the text says \"bounding the number of incident edges on v in Gres\"; from context this should be Gadj, not Gres.","section":"Section 6.4, Corollary 6.16"}],"recommendation":"major_revision","confidential_remarks":"This is a potentially landmark paper, and the overall architecture is convincing. My recommendation of major_revision is driven by two specific issues: (1) the deterministic half depends on Theorem 5.7, a refined Even-Shiloach guarantee that is asserted but not proved, and (2) the formula in Lemma 5.1(1) and the corresponding calculation in Lemma 6.6 contain an error that, if taken literally, invalidates the deterministic exponent. Both are fixable in a revision, but they are load-bearing for the main theorem. I would also ask the authors to double-check the algebra in Lemma 6.6 before the next submission; the current display does not compute."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a strong paper and I'd send it out. It gives deterministic O~(n^{8/9}) and randomized adaptive O~(n^{3/4}) amortized update for fully dynamic maximal matching, breaking the Omega(n) deterministic barrier and answering an open question from BGS15/BCHN18/Sol22. The EDCS-for-perfect-matching idea is genuinely new: instead of using EDCS for approximation, they use its degree gap to maintain a matching covering all high-degree nodes, then handle the low-degree residual with standard maximal matching. The randomized algorithm via random alternating walks on the contracted degree-gap graph is clean and I believe correct. The phase-based amortization checks out, and the fully dynamic extension via the buffer of new edges is standard but fine.\n\nWhat's actually new: first deterministic sublinear update for maximal matching in dense graphs; first adaptive-adversary randomized bound below n; tools like monotone ES-trees and Eulerian expander walks are new to dynamic matching. No fitting, no circularity; parameters B and delta are balanced asymptotics. The citation pattern looks honest—the claimed novelty relative to GSSU22a, Sol16b, arboricity-based algorithms, etc. is real.\n\nSoft spots, in proportion: the deterministic half leans on Theorem 5.7, a refined Even-Shiloach guarantee for directed weighted graphs with distance-non-decreasing insertions and a Remove(v) operation. The paper cites [SE81, Kin99] and gives a short justification, but it is not a routine corollary of standard ES analyses. Standard ES charges O(deg(v)) each time a distance increases; the weighted t-edges and the batched vertex removal need careful checking. If that guarantee fails, Lemma 5.20 and the n^{8/9} bound fall. I don't think it fails—the paper's argument is plausible—but a referee should ask for a self-contained proof or a precise pointer to where King's algorithm gives that exact bound. The randomized n^{3/4} bound does not use the ES tree, so it is not exposed to this gap. There's also a small off-by-one in Section 5.1 (the inequality involving (1-gamma)(1+gamma/2) is not exactly (1 - gamma/2)), but it doesn't change the asymptotics.\n\nWho should read this: anyone working on dynamic matchings, symmetry breaking, or adaptive-adversary dynamic algorithms. I'd bring it to reading group and would cite it. It deserves a serious referee; the ES-tree issue is a request for revision, not a desk reject.","headline":"Breaks the Omega(n) barrier for deterministic fully dynamic maximal matching with a novel EDCS-based framework; the main risk is a cited, unproved refined ES-tree guarantee that the deterministic half depends on.","tokens_in":48084,"tokens_out":3091,"would_cite":true,"duration_ms":30657,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims the first deterministic fully dynamic algorithm for maximal matching with sublinear amortized update time, $\\tilde{O}(n^{8/9})$, breaking the long-standing $\\Omega(n)$ barrier on dense graphs.","keywords":["fully dynamic algorithms","maximal matching","edge-degree constrained subgraph","degree gap","left-perfect matching","Even-Shiloach tree","adaptive adversary","sublinear update time"],"falsifier":"Run the deterministic left-perfect-matching data structure on a degree-gap bipartite graph for one epoch with $q_{\\mathrm{ep}}=\\sqrt{n\\gamma}$ deletions of matched edges, recording every vertex's distance to the sink; if more than $O(q_{\\mathrm{ep}}/\\gamma)$ vertices ever have maximum distance $\\omega(\\log n/\\gamma)$, or if any allowed reverse-edge insertion decreases a distance to the sink, the structural lemma behind the $\\tilde{O}(n^{8/9})$ bound is false.","tokens_in":47025,"feed_emoji":"🧩","tokens_out":6961,"duration_ms":68091,"temperature":0.7,"pith_summary":"Fully dynamic maximal matching asks to keep a maximal matching as edges are inserted and deleted. Until now, every deterministic algorithm needed $\\Omega(n)$ time per update in dense graphs. This paper claims the first deterministic algorithm with sublinear amortized update time, $\\tilde{O}(n^{8/9})$, and a randomized variant with $\\tilde{O}(n^{3/4})$ that is correct with high probability even against an adaptive adversary. The barrier breaks because the algorithm maintains a small set of high-degree vertices, matches all of them cheaply using the degree structure of an edge-degree constrained subgraph, and then only needs to scan the remaining low-degree graph.","feed_headline":"Dynamic maximal matching in O~(n^(8/9)) update time, deterministically","feed_subtitle":"A deterministic bound below n ends the Ω(n) barrier for dense graphs; the randomized counterpart runs in O~(n^(3/4)).","key_machinery":"The load-bearing object is the edge-degree constrained subgraph (EDCS): a subgraph $H$ of $G$ where every kept edge has degree-sum at most $B$ and every omitted edge has degree-sum at least $(1-\\epsilon)B$. The paper uses it in a new way, not to approximate maximum matching but to force a bipartite high-low subgraph with a $\\gamma$-degree gap: every high vertex has degree at least $X$, every low vertex at most $(1-\\gamma)X$. That gap gives Hall's condition with slack and guarantees short augmenting paths, which a left-perfect-matching data structure exploits: deterministically through a monotone dynamic shortest-path tree on the residual graph, and randomly through matching-walks that behave like random walks on an Eulerian expander.","core_discovery":"The central claim is that maximal matching is not intrinsically $\\Omega(n)$ per update: one can keep a maximal matching deterministically in $\\tilde{O}(n^{8/9})$ amortized update time, and with randomness in $\\tilde{O}(n^{3/4})$ against an adaptive adversary. The algorithm splits the vertex set into high and low parts. A subgraph with a degree gap makes the high part expand into the low part, so a matching covering all safe high vertices can be maintained in sublinear time; once every high vertex is matched, an unmatched vertex only needs to scan low-degree neighbors. This converts maximal matching into a small core problem plus a low-degree boundary problem.","pith_inferences":["The EDCS degree-gap trick is likely reusable: any dynamic problem whose hard part can be isolated behind a subgraph with Hall slack could use the same left-perfect core plus low-degree boundary decomposition.","The phase-based amortization suggests the approach cannot reach below roughly $\\sqrt{n}$ without a new idea; the next test is whether the amortization can be deamortized to obtain worst-case sublinear updates.","A direct stress test of the refined dynamic-shortest-path guarantee, total update time proportional to $\\sum_v \\deg_{\\max}(v)\\,\\operatorname{dist}_{\\max}(v,t)$ under delete, reverse-insertion, and remove operations, would be valuable independently of the rest of the algorithm, since the deterministic bound leans on it."],"forward_implications":["In dense graphs, the deterministic update time drops below $n$, so the trivial $O(n)$ scan is no longer the best known deterministic solution.","The randomized $\\tilde{O}(n^{3/4})$ bound removes the usual oblivious-adversary assumption for fast dynamic maximal matching.","Full edge insertions and deletions are both absorbed at the same asymptotic update time via a phase partition into a decremental core and a small set of new edges.","If the internal left-perfect-matching routine for degree-gap graphs could match the static $\\tilde{O}(m/\\gamma)$ time deterministically, the authors' decomposition would immediately give an $\\tilde{O}(n^{4/5})$ update time."],"supporting_citations":[{"why":"Maintains a $(B,(1-\\epsilon)B)$-EDCS deterministically with $O(n/(B\\epsilon))$ worst-case update time, supplying the degree-gap subgraph the whole algorithm builds on.","marker":"[GSSU22a]"},{"why":"Supplies the Even-Shiloach tree that maintains shortest paths to a sink in a decremental graph, which the deterministic left-perfect-matching data structure relies on.","marker":"[SE81]"},{"why":"Extends the Even-Shiloach tree to directed graphs, needed for the residual graph orientation and for the refined update-time guarantee used in Theorem 5.7.","marker":"[Kin99]"},{"why":"Provides the randomized subroutine for matching almost all near-maximum-degree vertices used to initialize the matching of high-degree vertices in Lemma 3.1.","marker":"[Ass24]"},{"why":"Provides the deterministic edge-coloring subroutine used to obtain the deterministic version of Lemma 3.1 and hence the deterministic phase initialization.","marker":"[EK24]"}],"fun_headline_variants":["Deterministic sublinear update for dynamic maximal matching","Maximal matching in O~(n^(8/9)) update time, deterministically","Breaking the linear-time barrier for dynamic maximal matching","Sublinear amortized update for maximal matching, no randomness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The deterministic half of the paper depends on a refined accounting guarantee for a dynamic shortest-path tree to a sink, namely total update time $O(\\text{total updates} + \\sum_v \\deg_{\\max}(v)\\,\\operatorname{dist}_{\\max}(v,t))$ including a vertex-removal operation, which the paper treats as an easy consequence of earlier algorithms rather than proving in its own text.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic sublinear update for dynamic maximal matching","Maximal matching in O~(n^(8/9)) update time, deterministically","Breaking the linear-time barrier for dynamic maximal matching","Sublinear amortized update for maximal matching, no randomness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000655,"raw_usage":{"total_tokens":2973,"prompt_tokens":891,"completion_tokens":2082,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":2012}},"tokens_in":507,"tokens_out":2082,"duration_ms":16637,"temperature":1.0,"reasoning_tokens":2012,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:21:42.318987+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the deterministic left-perfect-matching data structure on a degree-gap bipartite graph for one epoch with $q_{\\mathrm{ep}}=\\sqrt{n\\gamma}$ deletions of matched edges, recording every vertex's distance to the sink; if more than $O(q_{\\mathrm{ep}}/\\gamma)$ vertices ever have maximum distance $\\omega(\\log n/\\gamma)$, or if any allowed reverse-edge insertion decreases a distance to the sink, the structural lemma behind the $\\tilde{O}(n^{8/9})$ bound is false.","supporting_citations":[],"review_version":1}