{"id":"b5293664-6bba-4c6c-b7b6-49323341bf1e","arxiv_id":"1908.05700","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A one-round next-higher-ID neighbor selection rule achieves backup placement with load at most c in graphs of neighborhood independence c, and enables a (2+epsilon)-approximate maximum matching in O(log* n) rounds.","lead":"This paper gives a one-round distributed algorithm for backup placement in dense networks: each node picks the neighbor whose ID comes next after its own on a circular ID list. The same simple rule improves maximum matching approximation and gives a one-round self-stabilizing backup placement.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's matching approximation is not supported: the proof bounds remaining vertices rather than matching size, and K_{c,c} with monotone IDs is a concrete counterexample to the claimed (2+ε) factor.","rationale":"The one-round backup placement result (Theorem 2.1) appears correct: the triangle argument that two adjacent vertices cannot both select the same vertex is sound, and the bounded-neighborhood-independence assumption is exactly what is needed to cap the number of selectors. The self-stabilizing backup placement section is a straightforward corollary of that theorem and seems fine. The load-bearing problem is in the maximum matching application, which the abstract and introduction advertise as a principal contribution. The proof of Theorem 3.3 conflates 'vertices removed' with 'vertices matched'. Once isolated vertices are deleted, the geometric decrease in the number of remaining vertices does not lower-bound the number of matched edges, so the claimed (1+ε)-approximation to maximal matching, and hence the (2+ε)-approximation to maximum matching, does not follow. The K_{c,c} example with monotone IDs shows the failure is not merely a gap in the proof: the algorithm as specified provably outputs a matching of size at most 2, while the optimum has size c. This is a genuine counterexample for constant c, so the theorem cannot be repaired by a small edit to the proof. The paper still contains a correct and interesting backup placement algorithm, but one of its two main applications is invalid as stated. Therefore the reader's CONDITIONAL verdict should be moved to REJECT, since a headline theorem is false and a correct version would require either a different algorithm or substantially weaker approximation guarantees.","tokens_in":7656,"tokens_out":19995,"duration_ms":200018,"concrete_test":"Run Algorithm 2 on K_{6,6} with V = L1..L6 ∪ R1..R6 and ID(Li)=i, ID(Rj)=6+j. The backup placement G′ has edges Li→R1 for all i and Rj→L1 for all j; its maximum matching has size 2. Execute any maximal-matching subroutine on G′, remove the matched edges and all adjacent edges, and delete isolated vertices as the pseudocode specifies. Verify that the residual graph is empty and the returned matching has at most 2 edges, whereas the maximum matching of K_{6,6} has 6 edges, giving approximation factor 3 > 2+ε for ε<1.","verdict_should_be":"REJECT","load_bearing_attack":"The central matching application (Theorem 3.3) is not established by the given proof, and as stated the theorem is false. The proof argues that after each iteration at least 1/(c+1) of the remaining vertices are matched and removed, so after a constant number of iterations few vertices remain, and the final matching is a (1+ε)-approximation to a maximal matching. The flaw is that the algorithm removes not only matched vertices but also all vertices that become isolated after deleting edges adjacent to matched edges (Algorithm 2, line 7 comment: 'remove from G the edges of MM(G′), the adjacent edges in G of MM(G′), and all isolated vertices'). Those isolated vertices are not matched, so a small residual vertex count does not imply a large matching. In fact, n_{t+1} ≤ (c/(c+1)) n_t is only an upper bound on remaining vertices; it gives no lower bound on the number of matched edges, and the total matching size can be far below n/2. A concrete counterexample is K_{c,c} with left IDs 1..c and right IDs c+1..2c. The one-round backup placement G′ has all left vertices select the minimum-ID right vertex and all right vertices select the minimum-ID left vertex; this double-star has maximum matching size 2. After any maximal matching of G′ is removed together with adjacent edges, every vertex of K_{c,c} is removed, so the output has at most 2 edges, while the maximum matching has size c. For c=6, the approximation factor is 3, contradicting any (2+ε) bound with ε<1. Thus the matching approximation theorem, a headline application, is false as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a one-round distributed backup-placement algorithm for graphs with neighborhood independence at most c. Each vertex selects the neighbor with the smallest ID larger than its own, or the minimum-ID neighbor if no such neighbor exists (Algorithm 1). Theorem 2.1 claims that under this rule each vertex is selected by at most c neighbors. The paper then presents a maximum-matching approximation algorithm (Algorithm 2) that iteratively computes backup placements and maximal matchings, claiming a (2+ε)-approximation in O(log* n) rounds for constant c. Finally, Section 4 observes that since the backup-placement rule depends only on IDs, the same algorithm is self-stabilizing in one round after faults cease.","tokens_in":7973,"tokens_out":19303,"duration_ms":201419,"significance":"If the central backup-placement theorem is valid, it is a genuinely clean and surprising result: a one-round, ID-only algorithm achieves factor c backup placement, improving both the running time and approximation ratio of prior multi-stage algorithms for dense graph families. The self-stabilizing corollary is natural and potentially useful because the computation depends only on failure-free ROM values. The matching application, if correctly established, would also be a significant contribution. The paper is readable and the proof of Theorem 2.1 is self-contained, with no fitted parameters or empirical components.","major_comments":[{"comment":"The proof of Theorem 3.3 does not establish the claimed approximation. The inequality n_{t+1} ≤ (c/(c+1))n_t bounds only the number of vertices remaining after line 7 of Algorithm 2; vertices that become isolated after adjacent edges are deleted are removed without being matched. Consequently, a small residual vertex count does not imply that the matching accumulated in MCMA is large. The statement that all removed vertices are either matched or have all their neighbors matched describes the removed vertices, but only the matched ones contribute to the matching. A concrete illustration is the path P4 with IDs 1-2-3-4, for which c=2. If the maximal matching of the backup subgraph G' is the middle edge, the two endpoints are the only matched vertices, the other two vertices are removed as isolated, and the output has size 1 while the maximum matching of P4 has size 2. This contradicts the intermediate claim that the result is a (1+ε)-approximation to a maximal matching.","section":"3, Theorem 3.3"},{"comment":"There is a mismatch between the algorithm as written and the proof. Algorithm 2 returns MCMA after k iterations without computing a maximal matching of the remaining graph, whereas the proof of Theorem 3.3 argues about adding 'any subset of remaining edges of G' to make the result maximal. Either the algorithm must explicitly include this final residual maximal matching step, or the proof must be rewritten to analyze MCMA exactly as defined. In addition, the composition step 'Since MM is a 2-approximation to MCM' yields 2(1+ε), not 2+ε, as written; this part is reparable by reparameterizing ε, but it is still a gap in the current proof.","section":"3, Algorithm 2 and proof of Theorem 3.3"},{"comment":"The claimed (2+ε)-approximation to maximum matching is weaker than the guarantee already provided by any maximal matching, since every maximal matching is a 2-approximation to maximum matching. If the final output is intended to be a maximal matching, the theorem is vacuous; if the final output is not a maximal matching, the proof does not establish the stated bound. The authors should clarify what approximation guarantee is actually being claimed, why it is nontrivial, and how it improves on the standard 2-approximation of a maximal matching.","section":"3, Theorem 3.3 statement"}],"minor_comments":[{"comment":"The proof switches between notation v, v1, v2, u1, and u2 in the case analysis; the argument is sound but should be rewritten with consistent vertex names for readability.","section":"2, proof of Theorem 2.1"},{"comment":"The captions of Figures 2-4 are incomplete: they contain a bare '*' and do not explain which ID belongs to which vertex, making the case analysis harder to follow.","section":"2, Figures 2-4"},{"comment":"The comment in Algorithm 1 refers to Γ(v) ∪ v, but the formal definition of next-modulo uses only Γ(v); the comment should be corrected to match the definition.","section":"2, Algorithm 1"},{"comment":"The phrase 'for each vertex in the graph with c+1 neighbors, at least two neighbors are connected by an edge' should be replaced by the precise definition: every independent set contained in any neighborhood has size at most c.","section":"2, Theorem 2.1 statement"},{"comment":"Line 7 uses the same variable G for the input graph and the current residual graph; renaming the residual graph would avoid ambiguity when the algorithm is described and analyzed.","section":"3, Algorithm 2 line 7"},{"comment":"The statement O(f1(c)·f2(n)) = O(f2(n)) is only valid because c is a fixed constant; it would be clearer to say 'for constant c, this is O(f2(n))'.","section":"4, Theorem 4.2"}],"recommendation":"major_revision","confidential_remarks":"The backup-placement contribution and the self-stabilizing consequence are sound and likely publishable. The matching application, however, is advertised as a key result and currently rests on an invalid proof; Section 3 needs a substantial rewrite before the paper can be accepted. The authors should also decide whether the stated (2+ε) bound is meant literally, since it is weaker than the standard maximal-matching bound of 2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The one-round 'next-modulo' backup placement is the real contribution. It's genuinely simple, the c-approximation beats the previous 2c+1, and Theorem 2.1's proof is correct. I checked the case analysis; no hole there. That result alone makes the paper worth reading.\n\nThe matching section is not in the same shape. The proof of Theorem 3.3 claims that each iteration matches and removes at least 1/(c+1) of the remaining vertices. That's false because the algorithm also removes isolated vertices, which are not matched. The vertex count can drop without contributing to the output matching. The correct argument is to track the maximum matching of the residual graph: a maximal matching in G' has size at least one (c+1)-th of the current maximum matching (Lemma 3.1 essentially), and the residual maximum matching drops by at least that much. That gives a geometric decrease, and after O(c/ε) iterations you get a (2+ε)-approximation. So the theorem is very likely true, but the paper as written doesn't prove it. This is more than a 'factor 2' slip; it's the wrong invariant.\n\nThe stress-test note's K_{c,c} counterexample doesn't hold up. After the first iteration you remove a maximal matching of the double-star and all edges of G adjacent to it. In K_{c,c} with the natural IDs, a maximal matching of G' can be the single edge (1,c+1); removing it and its adjacent edges in G leaves K_{c-1,c-1}, not an empty graph, because edges like (2,c+2) are not adjacent to (1,c+1). The algorithm is supposed to repeat on that residual. For c=6, three iterations already give a 2-approximation. So the theorem isn't falsified by that example.\n\nThe self-stabilizing section is straightforward given the one-round rule, and the citations look fine. The paper is for distributed algorithms people working on symmetry-breaking, matching, and fault-tolerant networks.\n\nBottom line: accept for peer review, but the authors need to fix the proof of Theorem 3.3. The core backup placement result is solid enough to carry the paper even if the matching theorem were removed.","headline":"The one-round backup placement rule is a real result; the matching section's proof is flawed, but the stress-test's counterexample doesn't hold up.","tokens_in":8484,"tokens_out":41600,"would_cite":true,"duration_ms":372520,"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":"A one-round ID-sorting rule balances backup placement in dense networks.","keywords":["backup placement","next-modulo rule","neighborhood independence","distributed algorithm","maximum matching approximation","self-stabilization","unit disk graphs","dense networks"],"falsifier":"Run the next-modulo rule on any graph with neighborhood independence $c$ and count, for each vertex $u$, how many neighbors select $u$; the first vertex selected by $c+1$ neighbors is a direct counterexample to Theorem 2.1, and a brute-force search over all labeled graphs on up to seven vertices would reveal the smallest such graph if one exists.","tokens_in":7470,"feed_emoji":"🔄","tokens_out":16519,"duration_ms":145579,"temperature":0.7,"pith_summary":"Backup placement asks every node of a network to choose one neighbor as its backup, minimizing how many nodes choose the same neighbor; it is a relaxation of perfect matching that is non-trivial in the distributed setting. This paper shows that in every graph whose vertex neighborhoods contain no independent set larger than $c$ — a class covering unit disk graphs, line graphs, and other dense topologies — a one-round rule solves backup placement with load at most $c$. The rule, called next-modulo, makes each node select the neighbor whose ID is the smallest ID larger than its own, or the minimum-ID neighbor if no larger ID exists. Because the computation uses only IDs, the same rule doubles as a self-stabilizing algorithm that stabilizes in one round, and it yields a $(2+\\epsilon)$-approximation to maximum matching in $O(\\log^* n)$ rounds.","feed_headline":"One round suffices to balance backup placement","feed_subtitle":"In dense graphs, the next-modulo ID rule caps backup load and yields a near-constant-time matching approximation.","key_machinery":"The load-bearing mechanism is the next-modulo operation: given a vertex $v$, sort the IDs of $v$ and its neighbors in a circle, and select the neighbor immediately following $v$ in that circular order — equivalently, the smallest ID larger than $v$'s own, wrapping to the global minimum if no such neighbor exists. This operation turns the local ID ordering into a directed graph $G'$ in which every vertex has outdegree exactly 1, while the neighborhood-independence bound on the input graph caps the indegree at $c$, giving maximum degree $c+1$. That bounded degree is what powers the matching application, since a known $O(\\Delta+\\log^* n)$ maximal-matching algorithm can be run on $G'$ in $O(\\log^* n)$ rounds, and it is what makes the ID-only computation carry over unchanged to the self-stabilizing setting.","core_discovery":"The paper's central claim is Theorem 2.1: in any graph with neighborhood independence $c$, the one-round next-modulo rule produces a backup placement in which each vertex is selected by at most $c$ of its neighbors. The proof assumes $c+1$ neighbors select the same vertex $u$; the neighborhood-independence condition forces two of them, $v_1$ and $v_2$, to be adjacent, forming a triangle, and an ID-order case analysis shows that $v_1$ and $v_2$ cannot both select $u$ in any of the possible orderings. Since this applies to every vertex, the maximum number of selectors is at most $c$. The resulting directed subgraph $G'$ has maximum degree $c+1$, from which the paper derives a $(2+\\epsilon)$-approximation to maximum matching in $O(\\log^* n)$ rounds by repeatedly computing maximal matchings of $G'$. It also shows that the very same one-round procedure, re-executed every round, is a self-stabilizing backup-placement algorithm that stabilizes in one round and can be used as a preprocessing step for self-stabilizing matching algorithms.","pith_inferences":["A natural test beyond the paper is to run next-modulo on graphs with unbounded neighborhood independence and measure how the maximum number of selectors per vertex grows with graph size; this would show whether the $c$ bound degrades gracefully or fails abruptly.","The next-modulo operation is a deterministic symmetry-breaking primitive that turns a graph into a functional directed graph with bounded indegree; it could plausibly serve as a building block for other dense-graph problems such as local orientation or bounded-degree cluster assignment.","Because the rule needs only the IDs of its neighbors, it is likely to transfer to bandwidth-limited or asynchronous network models with no extra round overhead, although the paper does not analyze message sizes or asynchrony."],"forward_implications":["In every graph with neighborhood independence $c$, backup placement is solved in one synchronous round with each vertex selected at most $c$ times, improving the previous constant-time algorithm's ratio from $2c+1$ to $c$.","The applicable graph family includes unit disk graphs, unit ball graphs, line graphs, and graphs of bounded diversity, all of which have constant neighborhood independence.","Maximum matching in such graphs admits a $(2+\\epsilon)$-approximation in $O(\\log^* n)$ rounds, improving on the previous best $O(\\log \\Delta + \\log^* n)$ running time for the same family.","The backup-placement rule stabilizes in one round in the self-stabilizing model, and any self-stabilizing maximal matching algorithm with time $f_1(\\Delta) f_2(n)$ can be converted into a self-stabilizing $(c+1)$-approximation that runs in $O(f_2(n))$ rounds."],"supporting_citations":[{"why":"Introduces the distributed backup-placement problem and supplies the general randomized baseline that the dense-network result improves upon.","marker":"[8]"},{"why":"Gives the previous deterministic constant-time algorithm for bounded-neighborhood-independence graphs with approximation ratio $2c+1$, which the new one-round rule improves to $c$.","marker":"[5]"},{"why":"Provides the $O(\\Delta+\\log^* n)$ maximal-matching algorithm that is run on the degree-$c+1$ subgraph $G'$ and yields the $O(\\log^* n)$ matching result.","marker":"[12]"},{"why":"Defines the self-stabilizing model with failure-free ROM and corruptible RAM, the setting for the self-stabilizing section.","marker":"[6]"},{"why":"Supplies a self-stabilizing maximal matching algorithm whose time $O(\\Delta n+\\Delta^2 \\log n)$ is converted into a self-stabilizing $(c+1)$-approximation.","marker":"[10]"},{"why":"Records the previous best $O(\\log \\Delta + \\log^* n)$ running time for an $O(1)$-approximation in graphs of bounded diversity, the comparison point for the matching result.","marker":"[4]"}],"fun_headline_variants":["One round balances backup placement in dense graphs","Next-modulo rule: one round to balanced backups","One-round backup placement improves matching approximation","Self-stabilizing backup placement in one round"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the graph's neighborhood independence is at most $c$, meaning that among any $c+1$ neighbors of any vertex at least two are adjacent; if that fails, the contradiction argument that keeps two adjacent selectors from picking the same vertex collapses, and no load bound follows.","fun_headline_variants_meta":{"raw":{"variants":["One round balances backup placement in dense graphs","Next-modulo rule: one round to balanced backups","One-round backup placement improves matching approximation","Self-stabilizing backup placement in one round"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000885,"raw_usage":{"total_tokens":3913,"prompt_tokens":1131,"completion_tokens":2782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":747,"completion_tokens_details":{"reasoning_tokens":2725}},"tokens_in":747,"tokens_out":2782,"duration_ms":18236,"temperature":1.0,"reasoning_tokens":2725,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:07:06.615592+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the next-modulo rule on any graph with neighborhood independence $c$ and count, for each vertex $u$, how many neighbors select $u$; the first vertex selected by $c+1$ neighbors is a direct counterexample to Theorem 2.1, and a brute-force search over all labeled graphs on up to seven vertices would reveal the smallest such graph if one exists.","supporting_citations":[{"cited_title":"Distributed backup placement in networks","cited_arxiv_id":null,"evidence_quote":"Introduces the distributed backup-placement problem and supplies the general randomized baseline that the dense-network result improves upon."},{"cited_title":"Fast Distributed Backup Placement in Sparse and Dense Networks","cited_arxiv_id":"1902.08819","evidence_quote":"Gives the previous deterministic constant-time algorithm for bounded-neighborhood-independence graphs with approximation ratio $2c+1$, which the new one-round rule improves to $c$."},{"cited_title":"Some simple dist ributed algorithms for sparse networks","cited_arxiv_id":null,"evidence_quote":"Provides the $O(\\Delta+\\log^* n)$ maximal-matching algorithm that is run on the degree-$c+1$ subgraph $G'$ and yields the $O(\\log^* n)$ matching result."},{"cited_title":"Dijkstra","cited_arxiv_id":null,"evidence_quote":"Defines the self-stabilizing model with failure-free ROM and corruptible RAM, the setting for the self-stabilizing section."},{"cited_title":"Sel f-stabilization and byzantine tolerance for maximal matching","cited_arxiv_id":null,"evidence_quote":"Supplies a self-stabilizing maximal matching algorithm whose time $O(\\Delta n+\\Delta^2 \\log n)$ is converted into a self-stabilizing $(c+1)$-approximation."},{"cited_title":"Distributed symmet ry breaking in graphs with bounded diversity","cited_arxiv_id":null,"evidence_quote":"Records the previous best $O(\\log \\Delta + \\log^* n)$ running time for an $O(1)$-approximation in graphs of bounded diversity, the comparison point for the matching result."}],"review_version":1}