{"id":"39f1545e-3d62-4a0b-a35e-9f3bee4e4d53","arxiv_id":"2507.04960","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Minimum dominating set can be approximated within factor 34+ε in constant rounds on any bounded-Euler-genus graph in the deterministic LOCAL model, improving the previous Θ(√g) ratio.","lead":"The authors present constant-round distributed algorithms that approximate the minimum dominating set of any graph drawn on a surface of bounded genus, with approximation quality no longer depending on the genus. The result improves earlier genus-dependent ratios and extends the known planar-graph techniques to a broader class of 'locally nice' networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's 34+ε ratio rests entirely on unproved Observation 1, which asserts a 7-uniform (11+ε)-approximation for planar graphs from [HKOdM+25]; without proof of that uniformity, the central quantitative improvement is unsupported.","rationale":"The reader's weakest assumption correctly identifies Observation 1 as the pivotal unproved step. My review confirms that Observation 1 is the only path to the 34+ε ratio; the fallback Proposition 5 only gives a 907-approximation (modulo the paper's arithmetic slip of 906), which is still constant but not the claimed improvement. The rest of the paper—Proposition 3's proof, Claim 4's genus bound, and the asymptotic dimension machinery—is largely self-contained and appears sound. The internal inconsistencies (906 vs. 907, undefined S in Algorithm 2) are real but secondary; they do not invalidate the framework, only the numerical presentation. Because the core issue is a missing derivation of a property that might be true and verifiable, a conditional acceptance is appropriate: the 34+ε theorem should be made contingent on a proof of Observation 1. I see no reason to alter the reader's conditional verdict, hence I recommend UNCHANGED. The concrete test—deriving the uniformity property from the cited work—would settle whether the observation lands. I have not found a more load-bearing concern, and I consider the possibility that the main claim is entirely wrong to be low, as the generic reduction from Proposition 3 is sound and the 907-approximation already provides a constant-factor algorithm independent of genus, which was not previously known in this generality. Credit is due for the clean reduction and the careful handling of error sets in Proposition 3; the bottleneck is purely the external uniformity assumption.","tokens_in":13265,"tokens_out":4775,"duration_ms":50266,"concrete_test":"Independently derive, from the proof of [HKOdM+25, Theorem 2.3], the subset-uniform bound: for every planar graph G and every S⊆V(G), |A(G)∩S| ≤ (11+ε)·MDS(G,N^7[S]). If the proof only yields the global bound |A(G)| ≤ (11+ε)MDS(G), or if the subset version requires additional arguments not present, then Observation 1 is unjustified and Theorem 1's 34+ε ratio collapses to the weaker 907 bound from Proposition 5.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Observation 1 (Section 3) claims that the algorithm in [HKOdM+25, Theorem 2.3] is a 7-uniform (11+ε)-approximation for planar graphs. The paper explicitly says 'Although it is not explicitly stated in their paper, we can observe the following' and gives no proof. This is load-bearing: Theorem 1 composes Proposition 3 (the asymptotic-dimension reduction) with this planar algorithm; the uniformity parameter k=7 enters the bound α(d+1)+1 = 3(11+ε)+1 = 34+3ε, and the reduction's correctness depends on the subset-uniform guarantee |A(G)∩S| ≤ (11+ε)·MDS(G,N^7[S]) for every S. If [HKOdM+25] only proves the global bound |A(G)| ≤ (11+ε)MDS(G), the steps in Proposition 3 that compare MDS of local subsets (e.g., the equality MDS(G,N^k_G[C]) = MDS(G_v,N^k_{G_v}[C])) fail because the external algorithm was never verified for such sub-instances. The paper's own Proposition 5 gives a 4-uniform 302-approximation, but plugging that into Proposition 3 yields only a 907-approximation (or 906 if the +1 error term is ignored), not the 34+ε that the abstract and Theorem 1 advertise. Thus the stated improvement over the previous 91+ε for orientable surfaces and Θ(√g) for Euler genus hinges entirely on the unproved uniformity of the cited paper. The manuscript itself flags this as an observation without proof, so this is an acknowledged gap, not a hidden one.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic LOCAL algorithms for Minimum Dominating Set (MDS) on graphs of bounded Euler genus and, more generally, on graph classes of bounded asymptotic dimension that are locally contained in a nicer class. Its main technical tool is Proposition 3, which converts a k-uniform α-approximation algorithm for a hereditary class C into an (α(d+1)+1)-approximation algorithm for a class D of asymptotic dimension d, with round complexity T+δ+2, where δ is controlled by the weak diameter of the error set. Specializing to planar C and Euler genus-g D gives, via the paper's new 4-uniform 302-approximation algorithm for planar graphs (Proposition 5), a 906-approximation, though the arithmetic in Proposition 3 actually yields 907 in the presence of errors. If one additionally accepts Observation 1, which asserts that the planar algorithm of [HKOdM+25, Theorem 2.3] is 7-uniform with ratio 11+ε, then Theorem 1 yields a 7-uniform (34+ε)-approximation for Euler genus-g graphs with f(g,ε) rounds. Theorem 2 extends the same idea to classes locally of Euler genus g. The paper is a short proof of a general reduction rather than an exhaustive algorithmic engineering study.","tokens_in":13561,"tokens_out":16343,"duration_ms":162094,"significance":"If Observation 1 were proved and the proof of Proposition 5 completed, the paper would deliver a genuinely simple and reusable reduction: any uniform local planar approximation can be lifted to bounded-genus graphs and, more generally, to bounded-asymptotic-dimension classes. The 34+ε ratio would improve on the previous 24g+O(1) bound (which is linear in g) and on the 91+ε bound for orientable surfaces. The genus-additivity argument in Claim 4 is clean and self-contained, and Proposition 3's proof is mostly transparent. I also view as a strength that the paper explicitly identifies the load-bearing external assumption in Observation 1 rather than hiding it, and it does not fit constants to data. The main limitation is that the strongest advertised quantitative result currently rests on an unproved uniformity assertion, and the self-contained 302-approximation proof is too compressed to verify.","major_comments":[{"comment":"Observation 1 is load-bearing for Theorem 1 and is stated without proof; the text explicitly says that the uniformity of [HKOdM+25, Theorem 2.3] is not explicitly stated in their paper. The parameter k=7 enters Proposition 3 both through T=f(2k+2)+max{k+1,r} and through the proof's equality MDS(G,N^k_G[C])=MDS(G_v,N^k_{G_v}[C]), which requires the external algorithm to satisfy the subset-uniform bound |A(H)∩C|≤(11+ε)MDS(H,N^k_H[C]) for every induced sub-instance H∈C. A global (11+ε)-approximation for planar graphs does not imply that bound. Please provide a complete proof of Observation 1 or cite a theorem in [HKOdM+25] that establishes it; without this, Theorem 1 is not supported.","section":"Section 3, Observation 1 and Theorem 1"},{"comment":"The abstract and Section 3 claim a 906-approximation from Proposition 5, but Proposition 3's formula is α(d+1)+1; with α=302 and d=2 this is 907 whenever the T-error set X is nonempty, which is the generic case for Euler genus g>0. The value 906 corresponds to the error-free case X=∅. Please correct the arithmetic or state explicitly that 906 is the no-error ratio and 907 is the general ratio; the same discrepancy should be reconciled with the abstract's 'α ≤ 906'.","section":"Abstract and Section 3, 'Our contributions'"},{"comment":"The proof of Claim 6 is too compressed to be verifiable and contains several unstated steps. Step 2 of Algorithm 2 refers to 'N^3[S]' although S is not an input of the algorithm; the 'first key observation' bounding the number of candidates for v_u by 2^{|C|}·MDS(G,B∪C) is asserted without proof; and the face-by-face counting leading to '3·2^5=96' choices per face and 'at most 3|X| options for f' is not derived. This proof underlies the self-contained 907/906-approximation, so it needs to be written out in full detail.","section":"Section 5, Claim 6 and Proposition 5"},{"comment":"The k-uniformity proof for B at the end of Section 4 is not correct as stated. The argument says that if the brute-force set's intersection with W were smaller than MDS(G,N_G[W]), replacing it by a minimum dominating set of N_G[W] would yield a smaller dominating set; replacing a smaller set by a larger one cannot decrease the size, and it is not shown that the replacement still dominates V(G)\\N[S]. Please supply a rigorous proof of the uniform bound |B(G)∩W| ≤ (α(d+1)+1)MDS(G,N^k_G[W]), or modify the algorithm and proof accordingly.","section":"Section 4, proof of Proposition 3, k-uniformity of B"}],"minor_comments":[{"comment":"Step 2 of Algorithm 2 refers to 'N^3[S]' although S is not an input of the algorithm; this should be 'N^3[u]'.","section":"Section 5, Algorithm 2"},{"comment":"There is a typo: 'embedds' should be 'embeds'.","section":"Section 1"},{"comment":"Footnote 5 contains grammatical errors and a hard-to-parse sentence; please rewrite it for clarity.","section":"Footnote 5"},{"comment":"Theorem 2 states a 35(d+1)-approximation, while the derivation via Proposition 2 gives (34+ε)(d+1); the exact dependence on ε should be stated.","section":"Theorem 2"},{"comment":"Claim 4 states the bound δ<g(2T+5) for g≥1; please state explicitly how the g=0 case is handled, since for planar graphs the error set is empty and the ratio is α(d+1).","section":"Claim 4, Section 3"}],"recommendation":"major_revision","confidential_remarks":"I see no circularity or data-fitting; the reliance on published prior work (BBE+24 and BGPW25) is standard. The main risk is that Observation 1 may require a nontrivial argument that the authors have not included; if it turns out to be false, the 34+ε result collapses to the paper's own 907-approximation. I would encourage the editor to ask for a full proof of Observation 1 and a complete proof of Proposition 5 before further consideration."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nShort version: the paper has a real idea. Proposition 3 is a clean, self-contained reduction showing that any k-uniform α-approximation for planar MDS lifts to a (3α+1)-approximation on bounded Euler genus, with rounds depending only on the genus. The proof of that proposition is convincing, and the 4-uniform 302-approximation for planar graphs in Proposition 5 is a nice standalone result. If the headline 34+ε holds, it genuinely improves on the prior 24g+O(1), 91+ε, and Θ(√g) bounds.\n\nThe problem is that the 34+ε is not actually proved here. Theorem 1 rests entirely on Observation 1, which asserts that the cited [HKOdM+25] planar algorithm is 7-uniform (11+ε)-approximate. The authors honestly say “Although it is not explicitly stated in their paper, we can observe the following,” and then give no proof. The uniformity parameter k enters the composition directly: 3(11+ε)+1 = 34+3ε. Without a proof of the subset-uniform guarantee |A(G)∩S| ≤ (11+ε)·MDS(G,N^7[S]), the main quantitative improvement is unsupported. The fallback via Proposition 5 gives only a 907-approximation—still constant for Euler genus, but worse than the existing 91+ε for orientable surfaces.\n\nThere are two smaller issues. The abstract and text say 906 where Proposition 3's own +1 term yields 907. And Algorithm 2's pseudocode refers to “N^3[S]” with S undefined, almost certainly a typo for u. Both are cosmetic but should be fixed.\n\nWhat is solid: the asymptotic-dimension framework, the proof of Proposition 3, and the planar 302-approximation appear correct as far as I can tell. Claim 4's genus-additivity argument is clean, and the paper is honest about its dependencies on BBE+24 and BGPW25.\n\nBottom line: this deserves a serious referee. The central theorem is conditional on a check the authors should supply. If Observation 1 holds, this is a strong paper. If not, it falls back to a modest 907-approximation that beats the linear-in-g bound but not the orientable 91+ε. I'd send it to review with a request for the uniformity proof and arithmetic cleanup.","headline":"A genuinely new reduction for MDS on bounded-genus graphs, but the headline 34+ε depends on an unproved uniformity claim in a cited paper—worth refereeing with a required fix.","tokens_in":14212,"tokens_out":3715,"would_cite":true,"duration_ms":37453,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","68R10","05C69","05C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any fixed surface genus, Minimum Dominating Set can be approximated within 34+ε in a constant number of LOCAL rounds.","keywords":["distributed algorithm","LOCAL model","minimum dominating set","bounded genus graphs","asymptotic dimension","uniform approximation","planar graphs","constant-round approximation"],"falsifier":"Run the planar algorithm of [HKOdM+25] on a planar graph $G$ and a subset $S$; if for some $\\varepsilon>0$ the algorithm outputs more than $(11+\\varepsilon)\\cdot \\mathrm{MDS}(G,N^7[S])$ vertices of $S$, then Observation 1 is false and Theorem 1's $34+\\varepsilon$ ratio loses its planar ingredient. Alternatively, exhibit an Euler genus-$g$ graph where the output of algorithm $B$ exceeds $(34+\\varepsilon)\\cdot \\mathrm{MDS}(G)$, which would refute Theorem 1 directly.","tokens_in":13010,"feed_emoji":"🌐","tokens_out":8289,"duration_ms":79064,"temperature":0.7,"pith_summary":"The paper establishes that Minimum Dominating Set (MDS) on graphs embeddable in a surface of bounded Euler genus $g$ admits a deterministic constant-round distributed approximation in the LOCAL model, with approximation ratio $34+\\varepsilon$, independent of $g$. This improves on previous algorithms whose ratio grew like $\\Omega(\\sqrt{g})$ with genus, and on the $91+\\varepsilon$ ratio known only for orientable surfaces. The proof is short and modular: it converts any planar MDS algorithm with a 'uniform' approximation guarantee into an algorithm for bounded-genus graphs, using only the fact that bounded-genus graphs have asymptotic dimension at most two and that their local non-planarities are sparse. The same conversion yields a $906$-approximation from a simple self-contained planar $302$-approximation, and extends to any graph class of bounded asymptotic dimension that is locally planar or locally bounded-genus.","feed_headline":"34+ε MDS approximation in constant rounds on bounded-genus graphs","feed_subtitle":"Previous MDS ratios grew with genus; this LOCAL algorithm keeps the ratio fixed at 34+ε.","key_machinery":"The load-bearing mechanism is the generic conversion algorithm $B$ (Proposition 3). It colors the power graph $G^{2k+2}$ with $d+1$ colors so that each monochromatic component has weak diameter bounded by the control function $f(2k+2)$, then runs the uniform planar algorithm $A$ on each component while excluding the $T$-error set $X$ of vertices whose radius-$T$ ball is not planar; a final brute-force step dominates the remaining region $N^2[X]$, whose connected components have weak diameter bounded by $g(2T+5)$ via Euler-genus additivity (Claim 4). The key notion that makes composition work is $k$-uniform approximation: for every subset $S$, the algorithm selects at most $\\alpha \\cdot \\mathrm{MDS}(G,N^k[S])$ vertices inside $S$, which localizes the approximation guarantee and lets it survive the coloring decomposition.","core_discovery":"The paper's main theorem states that for every $\\varepsilon>0$ and every $g$, there is a $7$-uniform $(34+\\varepsilon)$-approximation LOCAL algorithm for Minimum Dominating Set in Euler genus-$g$ graphs, with round complexity $C(\\varepsilon,g)$ for some function $C$. In other words, the approximation ratio no longer depends on the genus at all, and the round complexity depends only on the fixed parameters $\\varepsilon$ and $g$, not on the number of vertices. The central instrument is a generic algorithm $B$ that takes any $k$-uniform $\\alpha$-approximation for a hereditary class $\\mathcal{C}$ and lifts it to a class $\\mathcal{D}$ of asymptotic dimension $d$: the lifted algorithm achieves $(\\alpha(d+1)+1)$-approximation, or $\\alpha(d+1)$ if $\\mathcal{D}$ is locally $\\mathcal{C}$, with round complexity controlled by the dimension's control function plus the weak diameter of the 'error' vertices whose local ball leaves $\\mathcal{C}$. Applied to planar graphs and Euler genus-$g$ graphs, with the observation that the known $(11+\\varepsilon)$ planar algorithm of [HKOdM+25] is $7$-uniform, this yields the $34+\\varepsilon$ ratio.","pith_inferences":["If the uniformity property is the real bottleneck, any future improvement of the planar uniform ratio automatically improves the bounded-genus ratio through the same pipeline, without revisiting the genus argument.","The same decomposition may apply to other covering and domination variants in classes with bounded local treewidth, since the brute-force step over constant-radius neighborhoods remains polynomial there.","The $906$ version is a robustness certificate: even if Observation 1 fails, the structural reduction from bounded genus to planar uniform algorithms still stands.","One could test the algorithm empirically on random triangulations and genus-$g$ grids to see whether the actual approximation ratio is closer to the planar constant than to $34$."],"forward_implications":["For every fixed genus $g$, MDS on bounded-genus graphs is approximable within $34+\\varepsilon$ in $C(\\varepsilon,g)$ rounds, independent of $n$ and of $g$; this removes the previous $\\Omega(\\sqrt{g})$ growth in the ratio.","The orientable-only $91+\\varepsilon$ bound is improved for all Euler genus graphs, including non-orientable surfaces.","The generic proposition gives a $35(d+1)$-approximation in $C(d,g,r)$ rounds for any graph class of asymptotic dimension $d$ that is locally of Euler genus $g$.","The simple self-contained planar $302$-approximation already yields a $906$-approximation for bounded-genus graphs, giving a short proof independent of the fine analysis in [HKOdM+25].","Conjecture 1 proposes that the ratio can be pushed down to $7$ for bounded-genus graphs, matching the planar constant."],"supporting_citations":[{"why":"Supplies the planar (11+ε)-approximation LOCAL algorithm whose 7-uniformity is assumed in Observation 1 and drives the 34+ε ratio.","marker":"[HKOdM+25]"},{"why":"Its Proposition 3.1 is the original conversion result that Proposition 3 extends to graphs with local errors.","marker":"[BGPW25]"},{"why":"Provides the asymptotic-dimension characterization via colorable bounded components, and the fact that bounded-genus graphs have asymptotic dimension at most two.","marker":"[BBE+24]"},{"why":"Gives the previous 24g+O(1)-approximation for Euler genus-g graphs, the baseline the new ratio improves.","marker":"[ASS19]"},{"why":"Gives the earlier 91+ε ratio for orientable bounded-genus graphs, which Theorem 1 improves and extends to non-orientable surfaces.","marker":"[CHWW19]"},{"why":"Supplies the additivity of Euler genus used in Claim 4 to bound the weak diameter of error components.","marker":"[MT01]"}],"fun_headline_variants":["34+ε MDS approximation in constant rounds for every genus","Constant-round MDS algorithm: 34+ε, no genus dependence","Bounded-genus MDS: 34+ε approximation in O_g(1) rounds","MDS ratio fixed at 34+ε for all bounded-genus surfaces","Genus-independent ratio: 34+ε in constant LOCAL rounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result's sharpest ratio inherits the unproved claim, stated as Observation 1, that the known $(11+\\varepsilon)$-approximation LOCAL algorithm for planar graphs is $7$-uniform; if that uniformity failed, the $34+\\varepsilon$ bound would not follow, though the paper's own $906$-approximation would remain intact.","fun_headline_variants_meta":{"raw":{"variants":["34+ε MDS approximation in constant rounds for every genus","Constant-round MDS algorithm: 34+ε, no genus dependence","Bounded-genus MDS: 34+ε approximation in O_g(1) rounds","MDS ratio fixed at 34+ε for all bounded-genus surfaces","Genus-independent ratio: 34+ε in constant LOCAL rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001133,"raw_usage":{"total_tokens":4757,"prompt_tokens":1043,"completion_tokens":3714,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":659,"completion_tokens_details":{"reasoning_tokens":3616}},"tokens_in":659,"tokens_out":3714,"duration_ms":29210,"temperature":1.0,"reasoning_tokens":3616,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T19:35:45.916626+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the planar algorithm of [HKOdM+25] on a planar graph $G$ and a subset $S$; if for some $\\varepsilon>0$ the algorithm outputs more than $(11+\\varepsilon)\\cdot \\mathrm{MDS}(G,N^7[S])$ vertices of $S$, then Observation 1 is false and Theorem 1's $34+\\varepsilon$ ratio loses its planar ingredient. Alternatively, exhibit an Euler genus-$g$ graph where the output of algorithm $B$ exceeds $(34+\\varepsilon)\\cdot \\mathrm{MDS}(G)$, which would refute Theorem 1 directly.","supporting_citations":[],"review_version":1}