{"id":"77cd6be7-235d-412a-ba80-5bb333d528ec","arxiv_id":"1908.08411","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Graph metric repair, the generalization of repairing a corrupted metric to arbitrary weighted graphs, is APX-hard, has no constant-factor approximation under the Unique Games Conjecture, is FPT on ς-chordal graphs, and admits L- and O(κ log n)-approximations.","lead":"Researchers extend the 'sparse metric repair' problem from complete distance matrices to arbitrary weighted graphs, where the goal is to change as few edge weights as possible so that shortest-path distances obey a metric. The paper gives hardness results, a fixed-parameter tractable algorithm for chordal graphs, and new approximation algorithms, connecting the problem to the well-studied MULTICUT problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"O(κ log n)-approximation proof misapplies the greedy set-cover bound; the number of deficit-δ cycles can be exponential, so the stated O(log n) factor is not justified.","rationale":"The reader's strongest claim, Theorem 3.2, is the structural characterization that the support of a solution is exactly a regular or light cover. My reading of the proof suggests this theorem is correct; the increase-only argument is sound because a light cover forces any shorter path to be broken, and the construction with maximum-weight edges handles disconnected components correctly. The hardness reductions from MULTICUT and LB-CUT also appear valid, and the FPT algorithm for ς-chordal graphs is plausible. The reader's weakest-assumption concern about Lemma 6.5 is largely resolved by the maximal-deficit condition: if a cycle of maximum deficit uses a non-shortest path, replacing that path by a true shortest path would create a cycle with larger deficit, contradicting maximality; similarly, any shared vertex in the concatenated shortest paths would yield a strictly shorter path, violating the equality required by Lemma 6.5. However, my stress-test identifies a more serious problem in the same approximation theorem: the proof of the O(κ log n) ratio relies on the standard greedy set-cover guarantee, whose approximation factor is logarithmic in the number of sets, not in the graph size. Since the number of maximum-deficit cycles can be exponential, the standard guarantee is O(log N) = O(n), not O(log n). This is not a matter of disagreeing with a community consensus; it is an internal gap between the cited theorem and the bound claimed. The paper could potentially repair this by proving a polynomial bound on the number of deficit-δ cycles or by deriving a graph-specific analysis, but as written the O(κ log n)-approximation is unproven. Because the paper's other main contributions still stand and the affected result may be salvageable, the appropriate verdict remains conditional rather than reject; the reader already set CONDITIONAL, so my read does not change the verdict.","tokens_in":20721,"tokens_out":31613,"duration_ms":313169,"concrete_test":"Build the layered-graph example: vertices s,t plus k layers with two vertices per layer, unit-weight complete bipartite edges between consecutive layers, and set w(s,t)=k+δ. There are 2^k shortest s-t paths, hence 2^k distinct broken cycles of deficit δ, so |C'_α| is exponential while |V|=Θ(k). Verify that applying the standard greedy hitting-set analysis to this sub-instance gives an approximation factor Θ(log |C'_α|)=Θ(k), not O(log |V|)=O(log k). This settles that the proof of Theorem 6.7 does not follow from the cited greedy bound and would require a genuinely new argument to retain O(κ log n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The O(κ log n)-approximation in Theorem 6.7 is not established as stated. The proof groups iterations with a fixed deficit δ into a hitting-set instance (E'_α, C'_α) and invokes the 'well known' fact that greedy hitting set has approximation ratio O(log n). The standard greedy set-cover/hitting-set bound is O(log |C'_α|), where |C'_α| is the number of sets (cycles) in the instance. Here |C'_α| is the number of distinct deficit-δ broken cycles, which can be exponential in |V|. For example, take a heavy edge (s,t) of weight d(s,t)+δ and connect s to t by a layered graph with two vertices per level and unit-weight edges between consecutive levels; there are 2^Ω(n) shortest s-t paths, each forming a distinct max-deficit cycle. Thus the cited greedy analysis yields only O(κ log |C'_α|) = O(κ·n), not O(κ log n), and the paper provides no additional argument bounding |C'_α| polynomially. There is also a second, more mechanical gap: Algorithm 4 line 7 computes #sp(s,t) only for edges, while Lemma 6.5 and Corollary 6.6 require #sp(a,s) and #sp(t,b) for arbitrary pairs of vertices, so the pseudocode as written cannot compute count(e) as claimed. Both gaps affect a central advertised contribution, although Theorem 3.2 and the hardness reductions appear sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces and studies Graph Metric Repair (MR(G,Ω)): given a positively weighted graph and a set of allowed edge-weight modifications Ω, find the minimum number of edges whose weights must be modified so that the resulting graph distances satisfy a metric. It generalizes earlier complete-graph results. The main contributions are: a cubic-time algorithm for the decrease-only case; a support characterization (Theorem 3.2) identifying supports of solutions with regular and light covers of broken cycles; a cubic-time Verifier; approximation-preserving reductions from MULTICUT and LB-CUT; an FPT algorithm for ς-chordal graphs parameterized by OPT; an L-approximation and an O(κ log n)-approximation via greedy hitting set; and improved analysis for the complete-graph case in the appendix.","tokens_in":20911,"tokens_out":33380,"duration_ms":321191,"significance":"The support characterization and the Verifier are clean and give a genuinely combinatorial view of the problem. The reductions from MULTICUT and LB-CUT are careful and correctly connect the problem to well-studied cut problems, and the FPT result for ς-chordal graphs answers an open question and extends the complete-graph case. If the O(κ log n)-approximation were established, it would be a notable contribution; however, that theorem currently rests on an incorrect application of the standard greedy set-cover bound, so the advertised approximation factor is not proved. The remaining results appear sound modulo local fixes, and the paper is likely to be useful to researchers in metric repair and graph algorithms.","major_comments":[{"comment":"The proof that the greedy sub-instances give an O(log n) approximation misapplies the standard greedy set-cover bound. In the sub-instance (E'_α,C'_α) the universe is the set of deficit-δ broken cycles, and the standard greedy bound is O(log |C'_α|); the tighter classical bound is O(log Δ), where Δ is the maximum number of deficit-δ cycles containing a single edge. Neither quantity is polynomially bounded. For example, take a layered graph with two vertices per level and unit-weight edges between consecutive levels, plus a heavy edge (s,t) of weight d(s,t)+1; there are 2^{Ω(n)} distinct shortest s-t paths, each forming a max-deficit broken cycle containing (s,t), so Δ and |C'_α| are exponential. The cited bound therefore yields only O(κ · n) (or O(κ log Δ)), not O(κ log n), and no additional argument is given to bound |C'_α| or Δ. Since the claimed running time also uses the output-size bound, that part of the theorem is unsupported as well.","section":"Section 6.2, Theorem 6.7"},{"comment":"Algorithm 4, line 7 computes #sp(s,t) only for edges, but Lemma 6.5 and Corollary 6.6 require #sp(a,s) and #sp(t,b) for arbitrary vertex pairs (a,s) and (t,b), which are not necessarily edges. As written, the pseudocode cannot compute Nl(e,δ(G)) in the claimed way, and the per-iteration running time O(n^3 + m^2) in Theorem 6.7 silently assumes that all-pairs shortest-path counts are available. This is fixable by computing #sp(u,v) for all ordered pairs, but the pseudocode and the running-time accounting should be updated to state this explicitly.","section":"Section 6.2, Algorithm 4 and Corollary 6.6"}],"minor_comments":[{"comment":"The paper uses 'APX-complete' where 'APX-hard' appears to be meant. The statement in Theorem 4.3 that MR(G,R≥0) and MR(G,R) are APX-complete and simultaneously UGC-hard to approximate within any constant factor is internally inconsistent, since APX-complete problems admit constant-factor approximations. The abstract already uses 'APX-hard' correctly.","section":"Theorems 2.4 and 4.3"},{"comment":"The displayed inequality in Case 1 has W(h)+w(h) on both sides; the right-hand sum over e∈S should be over e∈S\\{h} (or the inequality should be rearranged) for the argument that the cycle C1 minimizing term (1) is also broken in GS to go through.","section":"Lemma 5.2, Case 1"},{"comment":"The bound |P|≤2ς|S|^ς is stated for every call to F, but at the root call S=∅ the right-hand side is zero. The root case should be handled separately; the same running-time bound still holds because at the root one adds at most ς edges of a single broken chordless cycle.","section":"Lemma 5.3 and Theorem 5.4"},{"comment":"The proof should explicitly justify that the concatenation of a shortest a-s path, the edge e, and a shortest t-b path forms a simple cycle. This follows from the maximality of δ(G) (otherwise a shortcut would produce a cycle of larger deficit), but the current text does not state that argument and merely speaks of cycles.","section":"Lemma 6.5"},{"comment":"The pseudocode should state whether the broken chordless cycle is sought in G or in the auxiliary graph GS used in the proof of Lemma 5.2; the proof's edge-disjoint case relies on a GS cycle that is also broken in G.","section":"Algorithm 2, line 4"},{"comment":"There are several minor typos and wording issues: 'distict' in Theorem 6.7, 'well know MULTICUT' in Section 7, and the running time in Theorem 5.4 is stated with Θ when it is an upper bound.","section":"Miscellaneous"}],"recommendation":"major_revision","confidential_remarks":"The structural characterization, the hardness reductions, and the FPT algorithm are solid and worth publishing after revision. The main risk is the O(κ log n)-approximation theorem: the proof as written does not establish the advertised factor, and if the authors cannot supply a structural argument for the O(log n) bound, the theorem should be weakened to the bound actually implied by the greedy analysis. Please also ensure the 'APX-complete' terminology is corrected throughout, as it is currently inconsistent with the stated inapproximability results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper before citing it for the O(κ log n) approximation. The real contributions are the graph generalization of metric repair, the broken-cycle characterization, the MULTICUT and LB-CUT hardness reductions, and the FPT algorithm for ς-chordal graphs. The approximation section is where things fall apart.\n\nWhat is genuinely new: the paper moves metric repair from complete graphs to arbitrary weighted graphs, and Theorem 3.2 gives a clean characterization of optimal supports as regular or light covers of broken cycles. That theorem is simple and drives everything else. The reductions from MULTICUT and LB-CUT are careful and give UGC-hardness for constant-factor approximation, plus the Ω(√L) lower bound for bounded-weight instances. The FPT algorithm for ς-chordal graphs is a real extension of the earlier complete-graph FPT and the case analysis in Lemma 5.2 looks sound, though I did not machine-check it. The decrease-only cubic algorithm is standard but nicely packaged.\n\nThe soft spot is Theorem 6.7, the O(κ log n)-approximation. Three things are wrong with it. First, the proof invokes the standard greedy set-cover/hitting-set bound as O(log n), but that bound is O(log N) where N is the number of sets in the universe—here, the number of broken cycles at the current deficit value. That number can be exponential in n (e.g., a layered graph with 2^Ω(n) shortest paths), so the bound becomes O(log N) = O(n), not O(log n). Second, Lemma 6.5 counts products #sp(a,s)·#sp(t,b) as distinct broken cycles containing e and heavy edge f. Concatenated shortest paths need not be internally vertex-disjoint; if they share vertices, you do not get a simple cycle, so the product overcounts. Third, Algorithm 4 computes #sp only for edges, but Lemma 6.5 requires #sp for arbitrary vertex pairs, so the pseudocode as written cannot even compute the claimed counts. These are not cosmetic issues; they hit the main advertised approximation result.\n\nThe other results survive this. Theorem 3.2 is solid, the reductions appear correct, and the FPT running-time analysis is plausible. The complete-graph appendix is secondary but fine.\n\nWho this is for: anyone working on metric repair, graph cut reformulations, or FPT on chordal graphs. It deserves a serious referee—the core is worth publishing. I would send it out, but with a clear request to fix or weaken Theorem 6.7, either by proving a different bound or by adding a condition that bounds the number of max-deficit cycles.","headline":"The structural and hardness contributions are solid and worth knowing, but the advertised O(κ log n)-approximation is not proven as stated: the greedy set-cover bound is applied to a universe of cycles that can be exponential.","tokens_in":21569,"tokens_out":5009,"would_cite":true,"duration_ms":53293,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q17","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that repairing a weighted graph's distances to satisfy a metric is equivalent to hitting every broken cycle, and derives hardness, fixed-parameter, and approximation results from that equivalence.","keywords":["graph metric repair","metric violation distance","broken cycles","hitting set","MULTICUT","fixed-parameter tractable","approximation algorithms","chordal graphs"],"falsifier":"Construct a small positively weighted graph where two maximum-deficit broken cycles containing the same light edge have shortest-path decompositions that share an internal vertex, then compute $N_l(e,\\delta(G))$ by the lemma's formula and compare it with brute-force enumeration of all maximum-deficit broken cycles containing $e$; a mismatch would invalidate the counting lemma and break the approximation guarantee.","tokens_in":20429,"feed_emoji":"🔧","tokens_out":5771,"duration_ms":257201,"temperature":0.7,"pith_summary":"This paper studies how to repair a weighted graph's edge weights with the fewest changes so that the resulting shortest-path distances satisfy a metric. Its central claim is that the repair problem reduces to a covering problem: a set of edges is the support of some valid repair exactly when it touches every 'broken cycle'—a cycle where one edge is heavier than the sum of all others. The general version needs one edge from each broken cycle, while the increase-only version needs a non-heavy edge from each broken cycle. This equivalence turns metric repair into a minimum hitting set problem on broken cycles, and the paper uses it to prove hardness results, give a fixed-parameter algorithm for graphs with bounded chordless cycles, and design approximation algorithms.","feed_headline":"Graph metric repair reduces to covering broken cycles","feed_subtitle":"A characterization of repair supports yields hardness, FPT, and approximation algorithms for fixing noisy graph distances.","key_machinery":"The central object is the broken cycle and its cover. A broken cycle is a cycle containing one 'heavy' edge whose weight exceeds the sum of the other edges; the amount of that excess is its deficit. The characterization reduces any solution's support to a hitting set for broken cycles: a regular cover for the general problem, and a light cover for the increase-only problem. The algorithmic tools then use shortest-path computations to find broken cycles—an edge whose weight exceeds the shortest distance between its endpoints witnesses one—and, for the $O(\\kappa \\log n)$-approximation, to count how many maximum-deficit broken cycles contain each edge by summing products of shortest-path counts over eligible heavy edges.","core_discovery":"The paper establishes Theorem 3.2: for any positively weighted graph, a set of edges $S$ is the support of a solution to the general graph metric repair problem $\\mathrm{MR}(G, \\mathbb{R})$ if and only if $S$ is a regular cover (it contains at least one edge from every broken cycle), and $S$ supports an increase-only solution $\\mathrm{MR}(G, \\mathbb{R}_{\\geq 0})$ if and only if $S$ is a light cover (it contains at least one non-heavy edge from every broken cycle). The proof shows that if a broken cycle is left untouched, no modification to $S$ can repair it, and conversely, assigning each selected edge its shortest-path distance in the graph with $S$ removed yields a valid repair, with weights only increasing in the light-cover case. From this point onward, the metric repair problem is a purely combinatorial hitting-set problem over broken cycles, and every later hardness, FPT, and approximation result builds on this characterization.","pith_inferences":["The hitting-set equivalence suggests that graph metric repair may inherit stronger lower bounds or algorithmic techniques from multicut research, such as primal-dual schemes or oblivious routing ideas, beyond the direct reductions shown in the paper.","Because the counting lemma for maximum-deficit cycles relies on shortest-path decomposition, a dynamic data structure that maintains these counts under edge deletions could turn the $O(\\kappa \\log n)$-approximation into a faster online algorithm.","The LB-CUT reduction uses a single heavy edge with unit-weight paths, which hints that instances with few distinct deficit values may be the hardest core of the problem; testing the algorithm on such structured instances could reveal whether the $\\kappa$ dependence is truly necessary.","For complete graphs, the improved 5-cycle analysis suggests that optimal covers might be approximately recoverable by enumerating only short broken cycles, potentially leading to practical algorithms for dense metric repair instances."],"forward_implications":["The decrease-only version of graph metric repair can be solved in $O(n^3)$ time, while allowing even a single positive repair value makes the problem APX-complete.","Assuming the Unique Games Conjecture, neither $\\mathrm{MR}(G, \\mathbb{R})$ nor $\\mathrm{MR}(G, \\mathbb{R}_{\\geq 0})$ can be approximated within any constant factor, and for instances with maximum edge weight $L$ the approximation factor is hard within $\\Omega(\\sqrt{L})$.","For any fixed constant $\\varsigma$, metric repair on $\\varsigma$-chordal graphs is fixed-parameter tractable when parameterized by the optimal solution size, with running time $O((2\\varsigma\\,\\mathrm{OPT}^{\\varsigma})^{\\mathrm{OPT}+1} n^{\\varsigma})$.","The short-path-cover algorithm is an $(L+1)$-approximation for $\\mathrm{MR}(G, \\mathbb{R})$ and an $L$-approximation for $\\mathrm{MR}(G, \\mathbb{R}_{\\geq 0})$ in $O(n^3 \\cdot \\mathrm{OPT})$ time, where $L+1$ is the largest number of edges in a broken cycle.","When at most $\\kappa$ distinct deficit values occur, the greedy algorithm over maximum-deficit cycles gives an $O(\\kappa \\log n)$-approximation, and a cubic-time verifier decides whether any given edge set supports a valid solution."],"supporting_citations":[{"why":"Defines the metric violation distance problem on complete graphs and gives the broken-cycle cover characterization that this paper generalizes.","marker":"[10]"},{"why":"Defines sparse metric repair and provides the complete-graph algorithms and the IOMR-fixed algorithm analyzed in Appendix C.","marker":"[13]"},{"why":"Proves MULTICUT hardness under the Unique Games Conjecture, which the reduction uses to rule out constant-factor approximations.","marker":"[9]"},{"why":"Proves length-bounded cut hardness, the source of the $\\Omega(\\sqrt{L})$ lower bound.","marker":"[17]"},{"why":"Formulates the Unique Games Conjecture, on which the inapproximability results depend.","marker":"[16]"},{"why":"Shows that counting paths is #P-hard, motivating why the approximation algorithm counts only maximum-deficit cycles rather than all broken cycles.","marker":"[19]"}],"fun_headline_variants":["Broken cycles decide metric repair on graphs","Graph metric repair: hit broken cycles","Repair graph distances by covering broken cycles","Metric repair on graphs: a cover problem","Broken cycles unlock FPT for metric repair"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The $O(\\kappa \\log n)$-approximation rests on the assumption that each maximally broken cycle containing a given light edge is formed by concatenating shortest paths that touch one another only at the cycle's vertices; if those paths share vertices, the cycle count used by the greedy algorithm overestimates how many broken cycles an edge can fix.","fun_headline_variants_meta":{"raw":{"variants":["Broken cycles decide metric repair on graphs","Graph metric repair: hit broken cycles","Repair graph distances by covering broken cycles","Metric repair on graphs: a cover problem","Broken cycles unlock FPT for metric repair"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2917,"prompt_tokens":1078,"completion_tokens":1839,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":1773}},"tokens_in":694,"tokens_out":1839,"duration_ms":12929,"temperature":1.0,"reasoning_tokens":1773,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:52:37.053908+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small positively weighted graph where two maximum-deficit broken cycles containing the same light edge have shortest-path decompositions that share an internal vertex, then compute $N_l(e,\\delta(G))$ by the lemma's formula and compare it with brute-force enumeration of all maximum-deficit broken cycles containing $e$; a mismatch would invalidate the counting lemma and break the approximation guarantee.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the metric violation distance problem on complete graphs and gives the broken-cycle cover characterization that this paper generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines sparse metric repair and provides the complete-graph algorithms and the IOMR-fixed algorithm analyzed in Appendix C."},{"cited_title":"Chawla, R","cited_arxiv_id":null,"evidence_quote":"Proves MULTICUT hardness under the Unique Games Conjecture, which the reduction uses to rule out constant-factor approximations."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves length-bounded cut hardness, the source of the $\\Omega(\\sqrt{L})$ lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Formulates the Unique Games Conjecture, on which the inapproximability results depend."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows that counting paths is #P-hard, motivating why the approximation algorithm counts only maximum-deficit cycles rather than all broken cycles."}],"review_version":1}