{"id":"ad9422f3-ecdf-4693-93b9-a4f84fc2c31a","arxiv_id":"2501.04555","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Dilation 2-Augmentation is fixed-parameter tractable on K_{d,d}-free graphs, while dilation 3 and weighted metric variants are W[1]- or W[2]-hard.","lead":"This paper maps when adding at most k edges can quickly reduce a graph's dilation, or stretch, in a metric space. It gives fast parameterized algorithms for sparse graphs and shows several natural variants are hard.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Reduction Rule 4 in Section 3.3 is unsafe: deleting all but one representative per O(A,B) can turn a yes-instance into a no-instance, so Theorem 17 is not established.","rationale":"The reader's weakest assumption was the integrality of unweighted Gamma distances. That is a genuine limitation, but it does not threaten the paper's main theorem within its stated model. The load-bearing defect is different and more severe: the kernelization in Section 3.3 is unsound. I constructed a small annotated instance satisfying all the stated conditions—G is K_{d,d}-free, the conflict graph has a bounded vertex cover R, and Vc has size 2—where Reduction Rule 4 deletes an unmarked vertex and converts a yes-instance into a no-instance. The equivalence classes O(A,B) only preserve information about Vc, so paths through deleted non-conflicting vertices that were needed to keep pairs like z,x out of conflict are lost. The proof of Lemma 15 only replaces solution edges incident to deleted vertices; it does not account for new conflicts created among remaining vertices whose only short paths used deleted vertices. This is not a localized typo or labeling error: it breaks the central FPT algorithm's correctness. The theorem may be salvageable with a more careful reduction (e.g., trying all representative choices or refining the equivalence classes), but as written the proof is invalid. I therefore recommend REJECT rather than CONDITIONAL, since the main claim is unsupported by the current argument.","tokens_in":23805,"tokens_out":48862,"duration_ms":497914,"concrete_test":"Run the 7-vertex annotated instance (vertices z,u,v,x,p,w; Gamma edges z-u,u-x,z-x,v-x,x-p,x-w,w-p,v-w; G edges z-u,u-x,v-x,v-w,w-p; R={x,p}; k=1) through Reduction Rule 4, marking v as the representative of O({x},emptyset) and deleting u. Verify that the original annotated instance is a yes-instance (add edge x-w) and the reduced instance is a no-instance: x-p requires adding x-w, but z-x then remains unresolved because z is isolated after deleting u. This directly falsifies Lemma 15 and shows the kernelization is unsound.","verdict_should_be":"REJECT","load_bearing_attack":"The FPT proof of Theorem 17 relies on Reduction Rule 4 / Lemma 15, which deletes all but one marked vertex from each equivalence class O(A,B). The classes only record adjacencies to Vc in G and to Vc in Gamma; they do not preserve short paths that pass through non-Vc vertices. Deleting such a vertex can create new adjacent conflicts among remaining vertices that the original solution never had to resolve. Concretely, take vertices z,u,v,x,p,w. Let Gamma have edges z-u, u-x, z-x, v-x, x-p, x-w, w-p, v-w; let G have edges z-u, u-x, v-x, v-w, w-p. The only adjacent conflict is x-p, so R={x,p} and Vc={x,p}. The annotated instance with k=1 is a yes-instance: adding edge x-w (one endpoint in R) resolves x-p via x-w-p, and all other adjacent pairs are already fine. In class O({x},emptyset), vertices u and v are equivalent; if the rule arbitrarily marks v and deletes u, the reduced instance has z isolated, so z-x is a new adjacent conflict. With one allowed added edge, x-p can only be resolved by adding x-w, but then z-x remains unresolved; no single edge resolves both. Thus the reduced instance is no, contradicting Lemma 15. Since Reduction Rule 4 is the kernelization step that bounds the instance size in Section 3.3, the main FPT claim collapses unless the rule and representative choice are repaired.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Dilation t-Augmentation when the metric is the shortest-path metric of an unweighted graph Γ. The central algorithmic claim is an FPT algorithm for Dilation 2-Augmentation parameterized by k and d when G is K_{d,d}-free (Theorem 17). The paper also gives FPT algorithms when G or Γ has bounded degree, a polynomial-time algorithm for tree Γ and t=2, W[1]- and W[2]-hardness results for t=3 on star forests and star metrics, NP-hardness for edgeless G, W[2]-hardness for clique Γ, and W[2]-hardness for weighted Γ. The proofs are structurally ambitious and use standard parameterized reductions, but several load-bearing claims are incorrect as written.","tokens_in":24119,"tokens_out":18657,"duration_ms":184360,"significance":"If Theorem 17 were established, it would be a substantial contribution: it would give a parameterized dichotomy for sparse G and would cover forests, planar graphs, bounded-degeneracy graphs, and other K_{d,d}-free graph classes. The bounded-degree FPT results for arbitrary t are also natural and potentially useful. The hardness reductions are based on well-known W[1]- and W[2]-hard problems and show no circularity or fitted parameters. However, the main FPT theorem is not established because Reduction Rule 4 is unsafe, and several other proofs contain load-bearing errors. The current version is not ready for publication without major revision.","major_comments":[{"comment":"Reduction Rule 4 is unsafe, and the counterexample in the stress-test note is valid. Let Γ have edges z-u, u-x, z-x, v-x, x-p, x-w, w-p, v-w, and let G have edges z-u, u-x, v-x, v-w, w-p. The only adjacent conflict is (x,p), so R={x,p} is a vertex cover, and u and v both lie in O({x},∅). With k=1 this is a yes-instance: adding x-w resolves x-p via x-w-p. If the rule marks v and deletes u, then z-x becomes a new adjacent conflict in G', and one added edge cannot resolve both z-x and x-p. Thus the reduced instance is a no-instance, contradicting Lemma 15. The proof of Lemma 15 only moves solution edges incident to deleted vertices; it does not account for paths that use a deleted vertex as an internal vertex without being incident to a solution edge. Since Reduction Rule 4 is the kernelization step that bounds the instance size in Section 3.3, Theorem 17 is not established as written.","section":"Section 3.3, Lemma 15 / Reduction Rule 4"},{"comment":"The set A is defined as A=E(G)\\E(Γ), but Observation 35 implies that every edge of E(Γ) must be present in G+S, so the algorithm should compare k with |E(Γ)\\E(G)| and output G+(E(Γ)\\E(G)). With A=E(G)\\E(Γ), the condition k<|A| and the output G+A do not follow from the preceding observation. The argument is easily repaired by correcting the definition of A to E(Γ)\\E(G), but the written proof of Theorem 36 is incorrect.","section":"Section 5.3, Theorem 36"},{"comment":"Case (ii) of Lemma 40 contains a false assertion. For e=(p,q) not in E(Γ), dΓ(p,q)≥2, so the edge e itself has weighted length at least 2; if dΓ(p,q)=2, then e is a shortest path of length at most two between p and q. The statement that 'there exists no shortest path of length at most two containing e' is therefore false, and the minimality contradiction does not follow. A correct proof would need to use Lemma 1 and argue that every edge of a minimal solution lies on a length-2 resolving path for some adjacent conflict, and that all such paths consist solely of weight-1 edges. That argument is absent, so the NP-hardness proof for edgeless G is incomplete as written.","section":"Section 7.1, Lemma 40"},{"comment":"The proof of Claim 30 asserts that for distinct u,u' in U'_i ⊆ U_i we have (u,u')∈E(Γ). This is false: in the construction of Γ, the set U_i is independent and edges inside U_i are not included in the edge set EU. Since Claim 30 is used to force some vertex of U'_i to have its unique incident solution edge in E(Γ), the W[1]-hardness proof for star forests is incomplete as written. A repair would require a different argument, for example using the Γ-distance-2 path through V_i, but no such argument is supplied.","section":"Section 5.1, Claim 30"}],"minor_comments":[{"comment":"The text says that the problem 'more strongly admits no XP algorithm parameterized by t+Δ'. This statement is not supported by the W[2]-hardness result, which is parameterized by k, and appears to confuse the role of t and w. Also, the instance is described 'with t=3n/2ε', but the large value in the construction is w, not the dilation target t; this should be corrected.","section":"Section 6, paragraph before Theorem 37"},{"comment":"The row for 'General Star' lists the result as W[1]-hard, but Theorem 34 states W[2]-hardness. The table and the theorem should be made consistent.","section":"Table 1"},{"comment":"The abstract claims FPT for 't≤2', while Section 3 only proves the case t=2. The wording should be adjusted to match the proved statement.","section":"Abstract and Section 3"}],"recommendation":"major_revision","confidential_remarks":"The counterexample to Reduction Rule 4 is decisive for the main theorem: the kernelization step in Section 3.3 does not preserve yes-instances, so Theorem 17 is not proved. The errors in Section 5.1 and Section 7.1 are also load-bearing, though they may be repairable with additional arguments. If the authors cannot repair Reduction Rule 4 and the Claim 30 gap, the paper's headline results would need to be substantially weakened. I would only accept after a very substantial revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result, FPT for Dilation 2-Augmentation on K_{d,d}-free graphs, is not established by the written proof. Reduction Rule 4 is unsafe, and I have a concrete counterexample. That said, the paper should not be dismissed: several other results are solid and the general research direction is good.\n\nWhat is actually new: the K_{d,d}-free FPT attempt, the t=2 versus t>=3 dichotomy, the W[2]-hardness for (1,w)-weighted metrics, and the polynomial case when Gamma is a tree. The reductions from Diameter-2 Augmentation and 2-Spanner are fresh applications. The conflict/adjacent-conflict framework is clean, and Lemma 1 is correct. The decreasing-Turing-reduction machinery is creative, even if it breaks at the final kernelization step.\n\nThe main soft spot is Reduction Rule 4 / Lemma 15. The classes O(A,B) record only adjacencies to Vc, not how vertices outside Vc connect to each other. Deleting unmarked vertices can create new conflicts. Concretely: take Gamma with edges z-u, u-x, z-x, v-x, x-p, x-w, w-p, v-w, and G with edges z-u, u-x, v-x, v-w, w-p. With k=1 the only conflict is x-p, and adding x-w resolves it. The class O({x},empty) contains u and v; if the rule marks v and deletes u, then z becomes isolated, so z-x is a new conflict. One added edge cannot resolve both x-p and z-x. Thus Lemma 15 is false, and Corollary 16 does not bound a kernel. The main theorem needs a new idea or a much more careful representative choice that preserves paths through O.\n\nA second real flaw: Lemma 40, Case (ii), claims a non-Gamma edge in a minimal solution cannot lie on a shortest path of length at most two. That is false; a chord can be useful even if its endpoints already have a Gamma-path of the same weight. The 2-Spanner reduction needs a different argument.\n\nSmaller errors: Section 5.3 defines A as E(G)\\E(Gamma) when it should be E(Gamma)\\E(G); Section 6 writes t=3n/(2epsilon) where it means w; the star-metric result is labeled W[1] in the header and table but proved as W[2]-hard. These are fixable typos, not conceptual issues.\n\nThe bounded-degree algorithms (Theorems 22 and 27) look correct and genuinely useful. The weighted-metric W[2]-hardness is interesting. This paper is for parameterized complexity researchers and the spanner/augmentation community; it deserves a serious referee, but the referee must be told to put Reduction Rule 4 under a microscope. I would not cite Theorem 17 in its current form.","headline":"Main FPT theorem is not proven—Reduction Rule 4 is unsafe—but the bounded-degree and hardness results are worth a careful referee.","tokens_in":24667,"tokens_out":12683,"would_cite":false,"duration_ms":129013,"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":"This paper proves that making a sparse graph's dilation at most 2 by adding k edges is fixed-parameter tractable whenever the graph excludes a fixed biclique, and gives matching hardness for stretch 3.","keywords":["metric dilation","edge augmentation","geometric spanner","fixed-parameter tractability","biclique-free graphs","shortest-path metric","stretch factor","diameter augmentation"],"falsifier":"A W[1]-hardness reduction from Multicolored Clique to Dilation 2-Augmentation with G a forest would falsify Theorem 17, since forests are $K_{2,2}$-free; a minimal solution that Reduction Rule 4's representative substitution cannot simulate would also refute the compression step.","tokens_in":23629,"feed_emoji":"📏","tokens_out":12195,"duration_ms":107976,"temperature":0.7,"pith_summary":"The paper studies Dilation t-Augmentation: given a graph G whose edge lengths are distances from the shortest-path metric of an unweighted graph Γ, can at most k added edges make every distance in G at most t times the corresponding Γ-distance? It establishes a parameterized dichotomy for sparse graphs. When G excludes a fixed biclique $K_{d,d}$ as a subgraph, Dilation 2-Augmentation is fixed-parameter tractable, solvable in $f(k,d)n^{O(1)}$; this covers forests, planar graphs, bounded-treewidth graphs, $H$-minor-free graphs, and bounded-degeneracy graphs. The same tolerant regime cannot extend to $t=3$: Dilation 3-Augmentation is W[1]-hard even when G is a disjoint union of stars and isolated vertices. The paper also shows the whole problem is FPT when either G or Γ has bounded maximum degree, and that this last result fails for weighted metrics, where Dilation $(2+\\epsilon)$-Augmentation is W[2]-hard even for subcubic G.","feed_headline":"Adding k edges to fix stretch-2 is fast on biclique-free graphs","feed_subtitle":"A parameterized dichotomy: stretch 2 is tractable on sparse graph classes, stretch 3 is hard even on star forests","key_machinery":"The load-bearing object is the conflict graph $C$ on the same vertex set as $G$, with an edge $uv$ whenever $u$ and $v$ are adjacent in $\\Gamma$ but their distance in $G$ exceeds $t$. Lemma 1 guarantees that resolving adjacent conflicts resolves all conflicts, because any $\\Gamma$-shortest path decomposes into adjacent pairs. For $t=2$, Lemma 3 says every edge of $C$ must be incident to an endpoint of some solution edge; hence a maximum matching in $C$ of size greater than $2k$ rejects the instance, and otherwise its endpoints form a vertex cover $R$ of size at most $4k$. The algorithm guesses solution edges inside $R$, then applies decreasing FPT-Turing reductions that branch on a carefully chosen set $W_v$ of fewer than $d$ vertices whose common neighbors in the conflict graph shrink; the $K_{d,d}$-freeness of $G$ is exactly what bounds $|W_v| < d$. These reductions shrink the parameter each time and eventually bound the conflict set $V_c$ by a function $h(k,d)$. The final compression step partitions the conflict-free vertices $O$ by their exact adjacency pattern to $V_c$ in both $G$ and $\\Gamma$; keeping one representative per pattern class preserves the effect of any solution edge, so the instance shrinks to $g(k,d)$ vertices and all candidate edge sets can be enumerated.","core_discovery":"The central discovery is a sharp tractability boundary driven by the target dilation $t$ and by how sparse the input graph $G$ is. The main positive result is that Dilation 2-Augmentation is solvable in time $f(k,d)n^{O(1)}$ whenever $G$ is $K_{d,d}$-free, with no restriction on the metric graph $\\Gamma$: adding at most $k$ edges suffices to turn $G$ into a 2-spanner of the shortest-path metric of $\\Gamma$. The proof shows that only pairs of vertices that are adjacent in $\\Gamma$ and too far apart in $G$ need attention, and that for $t=2$ every such adjacent conflict must be touched by an added edge; this makes the endpoints of a maximum matching in the conflict graph a small vertex cover, and $K_{d,d}$-freeness forces the iterative guessing of solution edges to stop after fewer than $d$ rounds. After all conflict vertices are bounded in number, the remaining vertices are replaced by one representative per adjacency-pattern class, so brute-force enumeration over at most $k$ edges finishes the argument. The paper pairs this with a W[1]-hardness result for Dilation 3-Augmentation on star forests, showing the $t=2$ tractability is not an artifact of sparsity, and with FPT algorithms for bounded-degree $G$ or $\\Gamma$ under the combined parameter $k+t+\\Delta$.","pith_inferences":["A natural next step is to determine whether the $f(k,d)n^{O(1)}$ algorithm can be turned into an FPT-approximation or a kernel; the current bound grows very rapidly in $k$ and $d$, so the theorem is primarily a tractability result rather than a practical algorithm.","The adjacent-conflict reduction idea is not tied to $t=2$: for any $t$ where a solution edge only helps conflicts near its endpoints, a version of the conflict graph should yield FPT algorithms for sparse classes, provided a hop bound replaces the length bound; testing this on Dilation $(t+1)$-Augmentation for biclique-free graphs would be a direct extension.","The hardness for weighted $\\Gamma$ suggests that in practical geometric settings, where edge weights come from continuous distances, a different parameter such as the number of distinct edge lengths or the weight ratio may be needed to recover fixed-parameter tractability.","The polynomial case when $\\Gamma$ is a tree hints that the metric's global structure matters as much as $G$'s sparsity; studying other tree-like metrics, such as bounded-treewidth or bounded-pathwidth $\\Gamma$, is a natural next step."],"forward_implications":["Dilation 2-Augmentation is fixed-parameter tractable on every graph class that excludes a fixed biclique, including forests, planar graphs, $H$-minor-free graphs, bounded-treewidth graphs, nowhere-dense graphs, and bounded-degeneracy graphs (Corollary 18).","The dichotomy is sharp: for $t=3$ the problem is W[1]-hard even when $G$ is a star forest, so a fixed-parameter algorithm for $t \\geq 3$ on these sparse classes would collapse the W-hierarchy.","If either $G$ or $\\Gamma$ has maximum degree $\\Delta$, the problem is FPT in the combined parameter $k+t+\\Delta$, with running time exponential only in $\\Delta^{O(kt)}$ or $\\Delta^{O(kt^2)}$.","Weighted metrics are strictly harder: when $\\Gamma$ has edge weights in $\\{1,w\\}$ and $G$ is subcubic, even Dilation $(2+\\epsilon)$-Augmentation is W[2]-hard, so the unweighted shortest-path metric is essential for the bounded-degree tractability.","When $\\Gamma$ is a tree, Dilation 2-Augmentation is polynomial-time solvable, because any solution must contain every tree edge (Observation 35 and Theorem 36)."],"supporting_citations":[{"why":"Defines decreasing FPT-Turing reductions, the framework used in Section 3.2 to branch and reduce k while bounding the conflict set.","marker":"[2]"},{"why":"Provides the polynomial-time maximum matching algorithm that finds a vertex cover of the conflict graph in Reduction Rule 1.","marker":"[6]"},{"why":"Establishes W[2]-hardness of Diameter 2-Augmentation, which the paper translates into hardness when Γ is a clique (Proposition 42) and uses as the source reduction in Section 6.","marker":"[10]"},{"why":"Introduces graph spanners and proves 2-Spanner NP-hardness, used in Proposition 41 for edgeless G and as the conceptual origin of dilation.","marker":"[18]"},{"why":"Shows that finding an optimal-dilation spanner by adding k edges to an empty graph is NP-hard, motivating the parameterized study.","marker":"[11]"},{"why":"Poses the problem of improving dilation by adding k edges (Problem 9), the starting point of the paper.","marker":"[17]"},{"why":"Supplies W[1]-hardness of Multicolored Clique, used in the reduction showing Dilation 3-Augmentation is hard on star forests.","marker":"[8]"}],"fun_headline_variants":["Stretch-2 augmentation is FPT on K_{d,d}-free graphs","Stretch 3 is W[1]-hard on star forests; stretch 2 is FPT on sparse","Dilation 2 augmentation FPT for biclique-free; dilation 3 hard for stars","k-edge fix for 2-spanner: FPT on sparse, W[1]-hard for 3"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes the metric is the shortest-path metric of an unweighted graph, so positive-integer edge lengths bound the number of hops in any short path; dropping this assumption (allowing weights 1 and w in Γ) makes the bounded-degree case W[2]-hard.","fun_headline_variants_meta":{"raw":{"variants":["Stretch-2 augmentation is FPT on K_{d,d}-free graphs","Stretch 3 is W[1]-hard on star forests; stretch 2 is FPT on sparse","Dilation 2 augmentation FPT for biclique-free; dilation 3 hard for stars","k-edge fix for 2-spanner: FPT on sparse, W[1]-hard for 3"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000483,"raw_usage":{"total_tokens":2537,"prompt_tokens":1247,"completion_tokens":1290,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":863,"completion_tokens_details":{"reasoning_tokens":1188}},"tokens_in":863,"tokens_out":1290,"duration_ms":10637,"temperature":1.0,"reasoning_tokens":1188,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:35:58.100574+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A W[1]-hardness reduction from Multicolored Clique to Dilation 2-Augmentation with G a forest would falsify Theorem 17, since forests are $K_{2,2}$-free; a minimal solution that Reduction Rule 4's representative substitution cannot simulate would also refute the compression step.","supporting_citations":[],"review_version":1}