{"id":"6732c3a3-7c0c-4682-b660-bf550f23dcfe","arxiv_id":"2505.06222","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Adding edges to equalize the closeness centralities of two nodes is NP-hard; the ratio version has a quasilinear 6/11-approximation, and the gap version has no multiplicative approximation unless P=NP.","lead":"This paper studies how to add edges to a social network so that two chosen people become equally central, a fairness-motivated version of network design. The authors prove these equalization problems are computationally hard and give a fast approximation algorithm that achieves over half of the best possible balance.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"The paper's central claim is that Algorithm 1 is a quasilinear-time 6/11-approximation for Closeness Ratio Improvement. The reader's conditional verdict rests on an alleged missing orientation assumption in Lemma 4. That assumption is not needed: Claim 5(ii) gives cc-ratio_{G*}(a,b) > 11/12, which is min/max > 11/12, so max < (12/11) min. Therefore, irrespective of whether cc_{G*}(a) is the larger or smaller centrality, we have cc_{G*}(a) < (12/11) cc_{G*}(b). The proof steps that use this inequality are therefore valid without a case split. I also checked the surrounding structure: Lemmas 1–4, Claims 3–8, and the reduction arguments in Theorems 1–3 are coherent. The runtime claim is supported by the observation that when the algorithm does not terminate early, k is bounded by the number of private neighbors of b, which is at most n−1; the binary-search description, though terse, can be made rigorous by precomputing a fixed order of candidates and doing O(log k) BFS evaluations. The paper has minor exposition issues, such as the imprecise 'n>3' statement and the informal runtime sketch, but these do not affect correctness. Hence, the reader's identified concern is not load-bearing, and the conditional verdict can remain as a minor-revision recommendation rather than a correctness objection.","tokens_in":23781,"tokens_out":50258,"duration_ms":418640,"concrete_test":"Run a brute-force verification on all graphs with n ≤ 6 and k ≤ 2: enumerate all edge sets of size at most k, compute the optimal closeness ratio, and compare with the ratio produced by Algorithm 1. If any instance shows Algorithm 1's ratio below (6/11) of the optimum, the central theorem is false; otherwise, the reader's orientation concern is settled and the 6/11 guarantee is supported in the small-graph regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's flagged orientation gap in Lemma 4 does not land. Claim 5(ii) states cc-ratio_{G*}(a,b) > 11/12, i.e., min/max > 11/12, which implies max < (12/11)·min. Since cc_{G*}(a) is either the max or the min, in both cases cc_{G*}(a) ≤ max < (12/11)·min ≤ (12/11)·cc_{G*}(b). Thus the inequality cc_{G*}(a) ≤ 12/11·cc_{G*}(b) used in Claims 7, 8, and the d=2 analysis holds unconditionally; no orientation assumption or case split is needed. I re-examined the rest of Section 4 (Claims 3–8, Lemmas 1–4) and the reductions; I found no load-bearing gap. The runtime claim is also consistent: in the nontrivial case where the loop runs to completion, k < |N_G(b)\\N_G(a)| ≤ n−1, so O((n+m) log k) is plausible via binary search over prefixes, and the output size is O(n). The informal runtime sketch and the imprecise 'n>3' statement are expository issues, not correctness gaps.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two graph-modification problems in which a budget of k edge additions is used to equalize the closeness centralities of two designated vertices a and b: Closeness Ratio Improvement, which maximizes the ratio min(cc(a),cc(b))/max(cc(a),cc(b)), and Closeness Gap Minimization, which minimizes the absolute difference |cc(a)-cc(b)|, where closeness is the sum of shortest-path distances. The authors prove that both problems are NP-hard, give a quasilinear-time 6/11-approximation for the ratio version, and prove a bicriteria inapproximability bound for the ratio version as well as the non-approximability of the gap version. The main algorithmic contribution is a simple strategy: add the edge ab, then repeatedly add edges from a to vertices in b's neighborhood, with early-termination rules.","tokens_in":23912,"tokens_out":44317,"duration_ms":414260,"significance":"If the results are correct, this is a solid contribution to the emerging literature on algorithmic fairness through network modification. The paper introduces a well-motivated pair of problems, establishes hardness thresholds, and provides a nontrivial constant-factor approximation with a quasilinear runtime, which is a good algorithmic result for a non-submodular, non-monotone objective. The bicriteria inapproximability result is also of interest. The hardness reductions are carefully constructed and mostly check out, and the paper is generally well written. However, two load-bearing proofs contain errors that currently prevent the central claims from being regarded as established.","major_comments":[{"comment":"The proof of the Termination Lemma contains an incorrect set inclusion. The text claims that because u∈N_G(b), we have A_{G+au}⊆A_G, where A_H={v:d_H(a,v)<d_H(b,v)}. In fact, adding the edge au can only decrease distances from a, and when ab∈E and u∈N_G(b), distances from b are unchanged (any path through the new edge has length at least d_G(b,v)+1 by the triangle inequality). Hence A_G⊆A_{G+au}, and the asserted contradiction between |A_{G+au}|>(n-2)/2 and |B_G|>(n-2)/2 does not follow. Since Lemma 2 is used to justify the early-termination condition in Algorithm 1 and is then relied upon by Lemmas 3 and 4 and Theorem 4, the 6/11-approximation proof is incomplete as written. The lemma may be true, but a different or corrected argument is required.","section":"§4, Lemma 2"},{"comment":"The final calibration algebra in the bicriteria inapproximability proof is incorrect. Starting from (1-ε')(5ec+1-ecδ)≥5ec+1-ε, the correct rearrangement is ε≥ε'(5ec+1)+ecδ(1-ε'), not ε≥ε'(5ec-1)+ecδ(1-ε') as written. With the stated choices ε'=ε/(2(5ec-1)) and δ=ε/(2ec(1-ε')), the required inequality fails: the right-hand side becomes ε+ε/(5ec-1)>ε. The claimed approximation barrier 5ec/(5ec+1-ε) is therefore not established by the proof as written. The argument appears repairable (e.g., setting ε'=ε/(2(5ec+1)) would make the condition hold with equality), but the current text needs correction.","section":"§3, Theorem 3"},{"comment":"In the lower-bound argument for cc_{G*}(a), the set O is defined in the text as V\\(A_p∪{a,b}), but the subsequent computation uses O=V\\(B_p∪{a,b}) with |B_p|=4(n-2)/5+x. This is a typo in a central bound; it should be corrected to avoid confusion. As written, the notation makes the proof difficult to follow, though the intended argument is clear.","section":"§4, Lemma 4, Claim 7"},{"comment":"The claimed O((n+m) log k) runtime is only sketched. The binary search over the k-1 previous states of S requires a precise implementation: the algorithm must record the sequence of added edges and, for a queried prefix length ℓ, compute distances from a and b in G plus the first ℓ added edges. Since each BFS costs O(n+m+ℓ) and ℓ<k, the claim is plausible, but the manuscript would benefit from an explicit description of how the prefix evaluations are performed without re-running the entire loop.","section":"§4, Theorem 4"}],"minor_comments":[{"comment":"The displayed chain 'n/(n+ck) > n/(n·1/(1+ε′)) > 1−ε′' appears garbled; the intended inequality is n/(n+ck) > 1/(1+ε′) > 1−ε′.","section":"§3, Theorem 3"},{"comment":"The inference from '3n/11−8/11<k' to 'n/6<k' is not valid as a direct real inequality for all n>3 (e.g., n=6), though it becomes true for integral k in the cases that matter, and the final conclusion k+|N_G(a)|≥n/6 still holds. The proof should state the integrality argument explicitly.","section":"§4, Lemma 4"},{"comment":"The statement that for n<7 one may assume d_{G*}(a,b)<3 because otherwise part (iii) of Claim 5 is impossible is incorrect; for n=6, |B_p|=4 can satisfy |B_p|>4(n-2)/5 with d_{G*}(a,b)=3. The small-n case is easily handled because the lemma's conclusion is trivial for n≤6, but the current sentence should be revised.","section":"§4, Lemma 4"},{"comment":"Observation 1 invokes Observation 2 before Observation 2 is stated; reordering or an explicit forward reference would improve readability.","section":"§2.2, Observation 1"}],"recommendation":"major_revision","confidential_remarks":"The errors identified are localized and appear repairable, so I do not recommend rejection. However, the incorrect inclusion in Lemma 2 and the algebra error in Theorem 3 are load-bearing for the two main advertised results (the 6/11 approximation and the bicriteria inapproximability), so the authors need to provide corrected proofs before the paper is acceptable. The hardness results and the overall framing are solid, and the approximation ratio may well be salvageable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper is a genuine contribution, not a repackaging. It introduces two new problems—Closeness Ratio Improvement and Closeness Gap Minimization—and backs them with real results: NP-hardness for every target ratio above 1/2, W[2]-hardness, a bicriteria inapproximability bound near 0.932, and a quasilinear 6/11-approximation for the ratio version. The gap variant is shown to admit no multiplicative approximation. The counterexamples in Section 2.1 are worth the price of admission: they clearly demonstrate why the standard toolbox (submodularity, greedy improvement, diameter minimization) fails for ratio objectives.\n\nI checked the Set Cover reductions in Theorems 1 and 2 and the exchange argument in Claim 1; they are sound. The reader's flagged orientation issue in Lemma 4 does not survive contact with the definition of cc-ratio. Claim 5(ii) asserts cc-ratio_{G*}(a,b) > 11/12, i.e., min/max > 11/12, which gives max < (12/11) min. Then cc_{G*}(a) ≤ max < (12/11) min ≤ (12/11) cc_{G*}(b), with no need to know which of a and b is more central. So the 6/11 analysis stands as written.\n\nSoft spots are minor. Theorem 3's epsilon-delta bookkeeping is informal in places; the choices of ε' and δ are asserted rather than derived, and the \"we may assume n > ck/ε'\" justification is terse. The runtime sketch for Algorithm 1 says binary search over prefixes without specifying the data structure; the claim is plausible and the O((n+m) log k) bound is likely right, but it deserves a fuller proof in the final version. Also, Claim 8 says \"n>3\" when the algebra gives 3n/11 - 8/11 < k, which is fine for n large; the small-n case is dismissed in one clause. None of these affect the main theorems.\n\nThis is a paper for the algorithms-and-fairness crowd: people working on network interventions, centrality optimization, and graph modification. It deserves a serious referee. I'd take it.","headline":"A solid, original contribution to network-fairness algorithms with sound hardness results and a 6/11-approximation that holds up; the one flagged concern in Lemma 4 dissolves on inspection.","tokens_in":24532,"tokens_out":2583,"would_cite":true,"duration_ms":23065,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68W25","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A near-linear-time algorithm equalizes two nodes' closeness centralities to at least 6/11 of the best possible ratio, while the gap variant is unapproximable.","keywords":["closeness centrality","edge additions","graph modification","fairness in networks","approximation algorithm","NP-hardness","social capital"],"falsifier":"Run Algorithm 1 on every graph with, say, at most 9 vertices and compare its output against exhaustive search over all $\\binom{\\binom{n}{2}}{k}$ edge sets; a single instance in which the algorithm's ratio is below $\\frac{6}{11}$ of the optimal ratio would refute Theorem 4. Since the algorithm and the optimum are both finitely computable, this is a direct computational check.","tokens_in":23497,"feed_emoji":"⚖️","tokens_out":10402,"duration_ms":96226,"temperature":0.7,"pith_summary":"Closeness centrality measures a node's network position by its total distance to everyone else. This paper studies the algorithmic-fairness question of adding at most $k$ edges to make two specified nodes $a,b$ equally central, and finds a sharp difference between two natural objectives. The ratio version, Closeness Ratio Improvement, is $\\mathsf{NP}$-hard for every target ratio in $(\\frac12,1]$, yet admits a quasilinear-time $\\frac{6}{11}$-approximation: a simple strategy---add the edge $ab$, then edges from $a$ to $b$'s neighbors---is guaranteed to achieve at least $\\frac{6}{11}$ of the best possible ratio. The gap version, Closeness Gap Minimization, is $\\mathsf{NP}$-hard and cannot have any multiplicative approximation unless $\\mathsf{P}=\\mathsf{NP}$. The paper thereby shows that equalizing social capital through link additions is tractable in a principled sense for the ratio objective, and hopeless for the difference objective.","feed_headline":"Quasilinear edge additions hit 6/11 of optimal closeness ratio","feed_subtitle":"Adding k new edges can balance two nodes' closeness to 6/11 of best; the gap variant has no approximation.","key_machinery":"The engine of the result is Algorithm 1, which adds the edge $ab$ (if absent) and then repeatedly adds an edge from $a$ to a vertex in $b$'s private neighbourhood $\\mathcal N_{G+S}(b)\\setminus \\mathcal N_{G+S}[a]$ until the budget is spent or $a$'s closeness falls below $b$'s. The correctness rests on three structural lemmas: the No Switching Lemma, which says that if adding $ab$ reverses the centrality order then one of the current graphs already achieves $\\frac{6}{11}$; the Termination Lemma, which guarantees early stopping is safe; and a sufficient-condition lemma showing that $k+|\\mathcal N_G(a)|\\ge n/6$ forces a $\\frac{6}{11}$ outcome. Lemma 4 supplies the converse: when neither $G$ nor $G+ab$ is $\\frac{6}{11}$-approximate, the optimal solution must have $d_{G^*}(a,b)\\in\\{1,2\\}$ and the large-neighbourhood condition must hold. The proof repeatedly uses a ratio-monotonicity observation: for nonnegative $w\\le p\\le q$, the fraction $(p+w)/(q+w)$ is at least $p/q$, which lets the paper strip away error terms.","core_discovery":"The paper's central discovery is a structural description of the hard instances of Closeness Ratio Improvement. It proves that if neither the original graph nor the graph obtained by adding the single edge $ab$ already achieves a $\\frac{6}{11}$ ratio, then the optimal solution $G^*$ must place $a$ and $b$ at distance $1$ or $2$, and $b$ must have a very large private neighborhood; in that situation $k+|\\mathcal N_G(a)|\\ge n/6$, which lets a simple greedy edge-addition algorithm reach the $\\frac{6}{11}$ guarantee. Equivalently, the only graphs where the trivial edge $ab$ is inadequate are graphs in which $b$ has so many private neighbors that adding edges from $a$ to those neighbors is provably effective. The same construction that gives $\\mathsf{NP}$-hardness for target ratio $1$ is extended to every $\\tau\\in(1/2,1)$, and the same reduction shows the gap-minimization variant has no multiplicative approximation.","pith_inferences":["The omitted orientation case in Lemma 4 looks repairable from the paper's own bounds: if $d_{G^*}(a,b)\\ge3$, the structural claims force $a$ to be the less central node, and the opposite orientation gives stronger estimates on $k$; a filled-in proof should keep the $6/11$ theorem intact.","Because Algorithm 1 is deterministic and near-linear, an empirical study could test whether the $6/11$ guarantee is loose on real social graphs; the lemmas suggest hard instances are sparse graphs where $b$ has an enormous private neighbourhood.","The same private-neighbourhood decomposition is a plausible starting point for the two proposed generalizations, Group Closeness Ratio Improvement and All-Pairs Closeness Ratio Improvement, though the $1/2$ trivial baseline from adding $ab$ does not carry over."],"forward_implications":["For every input $(G,a,b,k)$, Algorithm 1 runs in $O((n+m)\\log k)$ time and returns an edge set with closeness ratio at least $\\frac{6}{11}$ of the optimum.","Exact optimization is out of reach in general: Closeness Ratio Improvement is $\\mathsf{NP}$-hard and $\\mathsf{W}[2]$-hard in $k$ for every target ratio in $(\\frac{1}{2},1]$.","The trivial bound of $\\frac{1}{2}$ from adding the single edge $ab$ is tight, so $\\frac{6}{11}$ is a real improvement over the naive intervention.","Closeness Gap Minimization is not only hard but inapproximable: no multiplicative factor is possible unless $\\mathsf{P}=\\mathsf{NP}$.","Any algorithm allowed $ck$ edges, for constant $c\\ge1$, cannot guarantee a ratio better than $\\frac{5ec}{5ec+1}-\\epsilon$ for any $\\epsilon>0$, unless $\\mathsf{P}=\\mathsf{NP}$. "],"supporting_citations":[{"why":"Provides the set-cover gap assumption used in the bicriteria inapproximability theorem.","marker":"[23]"},{"why":"Part of the stronger hardness assumption behind the $5ec/(5ec+1)$ bound.","marker":"[25]"},{"why":"Completes the same strengthened hardness assumption for the bicriteria result.","marker":"[24]"},{"why":"The greedy closeness-improvement baseline shown not to approximate the ratio objective.","marker":"[17]"},{"why":"Represents submodular centrality-improvement objectives the ratio objective is shown not to satisfy.","marker":"[9]"},{"why":"The diameter-minimizing shortcut objective from which the paper contrasts the ratio problem.","marker":"[21]"}],"fun_headline_variants":["Edge additions can balance closeness to 6/11 of optimal","For equalizing closeness, ratio variant gets 6/11; gap variant none","Adding edges to equalize closeness: NP-hard, yet 6/11 approx","Quasilinear-time 6/11 approximation for closeness ratio equalization","Closeness gap: no approximation; ratio: 6/11 via edge additions"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The chain of inequalities in Lemma 4 is load-bearing and silently presumes that in an optimal solution $G^*$, the node $b$ is at least as central as $a$ (i.e. $\\operatorname{cc}_{G^*}(a)\\ge\\operatorname{cc}_{G^*}(b)$); without that orientation, the bound $\\operatorname{cc}_{G^*}(a)\\le \\frac{12}{11}\\operatorname{cc}_{G^*}(b)$ does not follow from the written text.","fun_headline_variants_meta":{"raw":{"variants":["Edge additions can balance closeness to 6/11 of optimal","For equalizing closeness, ratio variant gets 6/11; gap variant none","Adding edges to equalize closeness: NP-hard, yet 6/11 approx","Quasilinear-time 6/11 approximation for closeness ratio equalization","Closeness gap: no approximation; ratio: 6/11 via edge additions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001289,"raw_usage":{"total_tokens":5276,"prompt_tokens":970,"completion_tokens":4306,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":4205}},"tokens_in":586,"tokens_out":4306,"duration_ms":32094,"temperature":1.0,"reasoning_tokens":4205,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:51:50.777806+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on every graph with, say, at most 9 vertices and compare its output against exhaustive search over all $\\binom{\\binom{n}{2}}{k}$ edge sets; a single instance in which the algorithm's ratio is below $\\frac{6}{11}$ of the optimal ratio would refute Theorem 4. Since the algorithm and the optimum are both finitely computable, this is a direct computational check.","supporting_citations":[{"cited_title":"Crescenzi, G","cited_arxiv_id":null,"evidence_quote":"The greedy closeness-improvement baseline shown not to approximate the ratio objective."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the set-cover gap assumption used in the bicriteria inapproximability theorem."},{"cited_title":"Feige, L","cited_arxiv_id":null,"evidence_quote":"Part of the stronger hardness assumption behind the $5ec/(5ec+1)$ bound."},{"cited_title":"Feige and J","cited_arxiv_id":null,"evidence_quote":"Completes the same strengthened hardness assumption for the bicriteria result."},{"cited_title":"Bergamini, P","cited_arxiv_id":null,"evidence_quote":"Represents submodular centrality-improvement objectives the ratio objective is shown not to satisfy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The diameter-minimizing shortcut objective from which the paper contrasts the ratio problem."}],"review_version":1}