{"id":"6b996c3b-a53c-404d-9e07-d1a03e093abb","arxiv_id":"2607.22384","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Fully dynamic polylogarithmic-time data structures for distance-r dominating-set and distance-r independent-set queries on bounded-expansion graphs, resolving the Dvořák–Tůma open question for these two problems.","lead":"This paper gives randomized dynamic data structures that maintain answers to two hard sparse-graph problems — distance-r domination and distance-r independence — under edge insertions and deletions, with polylogarithmic amortized update time. It closes a twelve-year gap left by Dvořák–Tůma's 2013 counting data structure, which could count solutions but not return them.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 6.5 can fail to preserve faithfulness after deletions: deleting an edge from G_i can activate an existing fork without any change to D_i, so the required fraternal edge is never added.","rationale":"The reader identified Claim 6.5 as the weakest spot, focusing on amortized multiplication and intermediate class membership. My stress-test found a different, more concrete defect in the same claim: the update procedure does not add fraternal edges that become necessary when a deletion removes an obstacle (an existing edge in G_i) without changing D_i. This is a correctness gap in the maintained invariant (A4), not merely a missing proof of amortization. It threatens the central reduction because every farVertex query rests on the faithfulness of the augmentation via Lemma 6.9. The gap is patchable by maintaining counters for all potential fraternal pairs, so I would not reject the paper outright; the verdict stays CONDITIONAL. However, since the reader's own concern was about the same lemma and my concrete counter-scenario sharpens it, the reader's conditional verdict is unchanged.","tokens_in":60652,"tokens_out":22831,"duration_ms":231457,"concrete_test":"Implement Claim 6.5's maintenance rules exactly as written on a 3-vertex graph with edges u-w, w-v, u-v, r=2. Initialize D_1 with orientation w→u, w→v, u→v. Delete uv, and during the update process only D_1 edge removals (the removal of u→v) and their cascading effects on D_2. Then inspect D_2: if it contains no shortcut for the length-2 path u-w-v, the maintained augmentation is not faithful, confirming the gap. For broader evidence, run randomized small tests: generate a small graph in a bounded-expansion class (e.g., a planar graph), perform arbitrary edge deletions, and after each update verify condition (A4) for all paths of length ≤r; any violation indicates Claim 6.5's update protocol is incorrect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Lemma 6.4's construction, G'_{i+1} is defined by adding edge uv only if uv ∉ G_i, for triples (w,u),(w,v)∈E(D_i) with len(w,u)+len(w,v)=i+1. Claim 6.5 maintains G'_{i+1} by processing changes to D_i and updating counters cnt_{e,i} for edges e currently in G'_{i+1}. Consider a triangle u-w-v with an additional edge uv, so uv ∈ G_1. The fork at w (w→u, w→v) exists, but because uv ∈ G_1, no edge uv is placed in G'_2 and no counter for it is kept. Now delete the edge uv from G. The path u-w-v of length 2 remains, and it now needs a shortcut, so (if u and v are not otherwise connected) the fraternal edge uv should appear in G'_2. But the deletion of uv from G changes D_1 only by removing the oriented copy of uv; the edges w→u and w→v are untouched. Claim 6.5's update procedure therefore has no event that increments a counter for uv, and the edge is never added. Hence D_2 is no longer a faithful (Λ,2)-augmentation: Claim 6.6's shortcut property fails for the path u-w-v. This invalidates Claim 6.10 (dist(u,v)≤r iff some pattern is realized) and the Inclusion-Exclusion computation of |V_far| in Lemma 6.9. The error would make farVertex return vertices that are actually at distance ≤r, a false positive, and the polylog guarantee of Theorem 1.1 would break. The gap is fixable — one can maintain counters for all potential fraternal pairs, even those currently shadowed by G_i-edges, at the same O(Δ_i) cost per D_i change — but as written, Claim 6.5 does not do this.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes randomized fully dynamic data structures for Distance-r Dominating Set (outputting a witnessing set) and Distance-r Independent Set (existence only) on any fixed bounded-expansion class, with amortized polylog n · log(1/eps) update/query time. The reduction chain is explicit: the progressive-exploration algorithms of Fabiański et al. are reduced (Section 4) to nearVertex and farVertex queries; nearVertex is implemented through Dvořák–Tůma dynamic counting plus fingerprint retrieval (Theorems 6.1, 5.8, Lemma 5.2); farVertex is implemented through a dynamically maintained iterated fraternal augmentation (Lemma 6.4) and an Inclusion–Exclusion formula over shortcut patterns (Lemma 6.9). The paper also gives a simpler r=1 implementation for d-degenerate graphs (Theorem 1.3, Sections 7) and a dynamic O(d^2)-approximation for minimum dominating set (Theorem 1.4, Section 8).","tokens_in":61101,"tokens_out":12423,"duration_ms":136991,"significance":"If the main theorems are correct, this is a substantial advance: it closes a 12-year gap since Dvořák–Tůma by giving the first polylog fully dynamic maintenance of ∃∀ FO-definable problems (domination and independence) on bounded-expansion classes, and it resolves the example-reporting question raised in [9] via the fingerprint retrieval toolbox. The paper is unusually explicit about its reduction chain, the probability analysis in Lemma 5.2 is detailed and sound, and the weighted-counting appendix is a useful contribution. However, the central claim rests on the dynamic correctness of the fraternal augmentation maintenance, and that is exactly where I find a load-bearing gap (see Major Comment 1).","major_comments":[{"comment":"Claim 6.5 maintains counters cnt_{e,i} only for edges e that are currently in G'_{i+1}. This misses fraternal edges that become necessary after a deletion. Concretely, let u,w,v form a triangle with uv in G_1 and w->u, w->v in D_1. At construction time uv is not placed in G'_2 because uv is already in G_1. Now delete uv from G, hence from D_1. The fork w->u, w->v is untouched, so the update procedure has no event that increments a counter for uv, and uv is never added to G'_2 even though it is now required. Thus D_2 is not a faithful (Λ,2)-augmentation: the path u-w-v has no shortcut, violating (A4) and making Claim 6.6 false. Since Claim 6.10, Lemma 6.9, and Theorem 6.7 all rest on faithfulness, farVertex can return a false positive and the polylog guarantee of Theorem 1.1 breaks. The issue is fixable, e.g. by maintaining counters for all potential fraternal pairs satisfying the length","section":"§6.2, Claim 6.5 (proof of Lemma 6.4)"}],"minor_comments":[{"comment":"The displayed bound 'O_C(log^{O_{B⟨x⟩,Σ}(1)} log n)' looks like a typo; it should presumably read (log n)^{O_{B,Σ}(1)} or a similar polylogarithmic expression.","section":"§5.2, Theorem 5.8"},{"comment":"Shortcut indices are written both as 0=α_1<... and as 0=α_0<... (see also Figure 2). Please harmonize the indexing with Definition 6.3, where α_0=0.","section":"§2.3 and Definition 6.3"},{"comment":"The stated amortized complexity includes a factor 2^{|S|}, but |S| is a query parameter. Updates cannot depend on |S| unless a maximum |S| is fixed in advance. The statement should clarify whether |S| is a fixed bound or whether the bound is per query.","section":"Theorem 7.6"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about Claim 6.5 lands: as written, the dynamic augmentation maintenance fails on a simple triangle example after a deletion. I still believe the theorem is very likely salvageable by maintaining counters for all potential fraternal pairs, and the rest of the architecture is coherent, so major revision rather than rejection is appropriate. The report to the authors should ask for a rewritten Claim 6.5 with explicit handling of deletions of shadowed pairs, and a re-verification of the amortized cascade bound under that fix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper deserves serious attention: it is the first polylogarithmic dynamic data structure for distance-r dominating set and distance-r independent set on bounded-expansion classes, breaking a twelve-year standstill on the Dvořák–Tůma question for ∃∀ FO-definable problems. The fingerprint retrieval lemma (Lemma 5.2) is a clean, reusable idea that turns the counting-only structure into an example-reporting one, and the reduction chain from semi-ladder/ladder algorithms to near/farVertex queries is laid out explicitly. The paper is also honest about its model: oblivious adversary, bounded expansion only, existence-only for independence. The degenerate-graph and dynamic approximation results (Theorems 1.3 and 1.4) are solid side contributions.\n\nThat said, the stress-test note lands. In Claim 6.5, the counters cnt_{e,i} are only maintained for edges currently present in G'_{i+1}. When an edge uv is deleted from G, and uv had previously prevented a fraternal edge uv from being inserted into G'_2 (because uv ∈ G_i at construction time), the deletion does not touch the fork edges w→u and w→v, so no counter event fires for uv. The result is that the augmentation D_2 stops being faithful: a length-2 path now requiring a shortcut has none, Claim 6.6's shortcut property fails, and the Inclusion-Exclusion computation of |V_far| in Lemma 6.9 collapses. Since every farVertex query rests on that lemma, the polylogarithmic guarantee of Theorems 1.1 and 1.2 is not supported as written.\n\nThe gap is fixable—maintain counters for all potential fraternal pairs, including those shadowed by G_i-edges—and the authors' overall architecture is sound enough that the main results are very likely recoverable. But it is a load-bearing flaw, not a cosmetic one. The other soft spots the reader identified are real but in proportion: Theorem 5.6 is actually backed by an appendix, while the MappingExample half of Theorem 5.8 is explicitly left to the reader, and the amortized cascade argument in Claim 6.5 is a sketch. Those would need fuller treatment in a revision.\n\nWho is this for? Researchers in dynamic graph algorithms and in sparse graph theory; anyone working on dynamic FO model checking. The paper deserves a serious referee, but with the expectation of a major revision focused on fixing the augmentation maintenance. I would not cite the main theorems as established until that fix appears, but I would bring the paper to a reading group now.","headline":"Major progress on a twelve-year-open problem, but as written the fraternal augmentation maintenance in Claim 6.5 has a genuine deletion-triggered gap that undermines the main theorems until fixed.","tokens_in":61688,"tokens_out":2263,"would_cite":false,"duration_ms":25129,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R10","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A dynamic data structure answers distance-r domination and independence queries on sparse graphs in polylog amortized time per edge update, and can report the actual dominating set when one exists.","keywords":["dynamic graph data structures","bounded expansion","distance-r dominating set","distance-r independent set","fraternal augmentation","degenerate graphs","dominating set approximation","fingerprint retrieval"],"falsifier":"Take a bounded-expansion graph—say a constant-degree grid or bounded-degree expander—and run the proposed augmentation maintenance under adversarial edge insertions and deletions, instrumenting each level to count reorientations per update and verifying after every batch that the maintained decorated supergraph is a faithful augmentation (every length-≤r path has a shortcut and every shortcut corresponds to a real path). A single amortized violation—any level with ω(log^{r-1} n) reorientations per update, or a farVertex query that returns a vertex actually within distance r of S—would refute t","tokens_in":60479,"feed_emoji":"⚙️","tokens_out":5245,"duration_ms":53369,"temperature":0.7,"pith_summary":"The paper aims to prove that two canonical local search problems—whether a sparse dynamic graph has a distance-r dominating set of size k, and whether it has a distance-r independent set of size k—can be solved with polylogarithmic amortized update time under edge insertions and deletions. Bounded expansion classes, the sparse graph families targeted here, include bounded-degree, planar, and minor-closed graphs. If correct, this is the first polylog-time fully dynamic maintenance of an ∃∀ first-order query on such classes, a gap that has stood open for over a decade. The data structures are randomized, with error bounded by ε against an oblivious adversary, and the dominating-set variant reports an actual set. The paper also gives a simplified structure for ordinary domination in d-degenerate graphs and a (4d+1)²-approximation of the domination number with expected polylog update time.","feed_headline":"Distance-r domination solved in polylog time on sparse graphs","feed_subtitle":"New randomized data structures track dominating and independent sets of size k through edge edits, with polylog amortized cost per update.","key_machinery":"Two mechanisms carry the argument. First, the semi-ladder and ladder exploration algorithms: iterative candidate–witness procedures that terminate in a constant number of rounds on bounded-expansion classes, each round reducing to a constant number of nearVertex and farVertex queries on small sets. Second, the fraternal augmentation: a constant-degree, labelled, directed supergraph built level by level in which every pair of vertices at distance at most r is connected by a unique oriented shortcut whose edge labels and lengths form a small pattern. Farness from a vertex can then be expressed as an inclusion–exclusion sum over homomorphism counts from finitely many fixed shortcut patterns. Ne","core_discovery":"The central claim is that on any fixed bounded-expansion class, distance-r dominating sets of size k and distance-r independent sets of size k admit randomized fully dynamic data structures with amortized update time log^{O_{C,r,k}(1)} n · log(1/ε) and correctness probability 1−ε. The key reduction is algorithmic: a bounded-round candidate–witness exploration, called progressive exploration, shows that both problems reduce to two primitive queries—find a vertex close to a small set within given radii, and find a vertex far from a small set. Close-vertex queries are implemented through rooted homomorphism counting enhanced with a fingerprint-retrieval technique that converts counts into repor","pith_inferences":["The far-vertex machinery—maintaining the fraternal augmentation—is the only step that currently blocks lifting these bounds from bounded expansion to nowhere-dense classes; if the augmentation cascade could be amortized on nowhere-dense classes, the same argument would plausibly give n^{o(1)}-type update times.","The fingerprint-retrieval conversion from counting to example-reporting looks like a general template: any dynamic counting structure whose homomorphism, subgraph, or induced-subgraph counts can be weighted can likely be upgraded to report witnesses at polylog overhead.","A practical stress test of the paper's key invariant would be to instrument the augmentation cascade under adversarial edge deletions: if any level ever suffers superlogarithmic reorientations in an amortized sequence, or an intermediate graph leaves the bounded-expansion class, the shortcut patterns used by farVertex queries would silently become unfaithful."],"forward_implications":["If the central claim is correct, both distance-r domination and distance-r independence can be maintained exactly, with reporting, in polylog amortized update time on every fixed bounded-expansion class.","It closes a decade-old gap between dynamically counting small subgraph patterns and actually returning an example mapping, with only a log n · log(1/ε) overhead over counting-only structures.","For distance-1 domination, the assumption can be relaxed to bounded degeneracy: updates run in 2^{k^{O(d)}} · log³ n · log(1/ε), showing that the full bounded-expansion machinery is unnecessary for the radius-1 case.","It also yields the first dynamic constant-factor approximation of the domination number in d-degenerate graphs, maintaining a dominating set of size at most (4d+1)² times the optimum with expected amortized d^{O(1)} log n update time."],"fun_headline_variants":["Dynamic Domination & Independence on Sparse Graphs","Sparse Graphs: k-Domination Queries in Near-Log Time","Edges Change, Answers Stay: Polylog-Time on Sparse Graphs","Live Update Dominating Sets in Sparse Graphs","Polylog Updates for Distance-r Domination on Sparse Graphs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire polylog bound rests on the claim that the iterated fraternal augmentation can be maintained with amortized O_{C,r}(log^{r-1} n) structural changes per update by cascading bounded-outdegree orientation updates level by level; if deletions ever force more than polylog reorientations at one level, or a transient intermediate graph leaves the bounded-expansion class, the shortcut patterns used by farVertex queries cease to be faithful and the polylog guarantee breaks.","fun_headline_variants_meta":{"raw":{"variants":["Dynamic Domination & Independence on Sparse Graphs","Sparse Graphs: k-Domination Queries in Near-Log Time","Edges Change, Answers Stay: Polylog-Time on Sparse Graphs","Live Update Dominating Sets in Sparse Graphs","Polylog Updates for Distance-r Domination on Sparse Graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00064,"raw_usage":{"total_tokens":2846,"prompt_tokens":871,"completion_tokens":1975,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":615,"completion_tokens_details":{"reasoning_tokens":1889}},"tokens_in":615,"tokens_out":1975,"duration_ms":13061,"temperature":1.0,"reasoning_tokens":1889,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T04:55:58.437776+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a bounded-expansion graph—say a constant-degree grid or bounded-degree expander—and run the proposed augmentation maintenance under adversarial edge insertions and deletions, instrumenting each level to count reorientations per update and verifying after every batch that the maintained decorated supergraph is a faithful augmentation (every length-≤r path has a shortcut and every shortcut corresponds to a real path). A single amortized violation—any level with ω(log^{r-1} n) reorientations per update, or a farVertex query that returns a vertex actually within distance r of S—would refute t","supporting_citations":[],"review_version":1}