{"id":"c8c434a7-8d80-48c5-ab9b-40eb0acdb025","arxiv_id":"2411.13171","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Disk scaling is proposed as a parameterized graph modification operation, with subexponential FPT algorithms, polynomial kernels, EPTASes, and NP-hardness results for shrinking to independence, acyclicity, and connectivity.","lead":"This paper introduces a new kind of graph modification for disk intersection graphs: instead of deleting vertices or edges, you shrink or expand the disks themselves. It gives fast parameterized algorithms, small kernels, and approximation schemes for making the resulting graph edgeless, acyclic, or connected.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Even granting Proposition 4, Lemma 14's Claim 4 appears false: in the natural grid embedding the branch at (3,3) lies outside the 8-cycle C_{1,1}, so the asserted containment in the interior set does not follow and the proof of Theorem 3 breaks.","rationale":"The reader's CONDITIONAL verdict pins the main risk on Proposition 4, the unproved well-behaved minor extension. I agree that the grid case of the connectivity algorithm is the load-bearing part of Theorem 3, but the more acute problem is downstream: Claim 4 in Lemma 14 uses the well-behaved minor in a way that is not justified by the stated definitions, and the claim is false for a natural well-behaved minor. If Claim 4 fails, Lemma 14 collapses and Theorem 3 is unproved. The authors may be able to repair the proof by choosing the 8-cycles so that the missing corner is genuinely enclosed, or by adding an explicit property to Proposition 4 that forces the branch to lie inside; but as written the argument is not merely missing a routine detail, it contains an identifiable geometric error. Because Theorem 3 is the flagship algorithmic result and no machine-checked proof or code is supplied, the current submission cannot be accepted on the strength of the written proof. I therefore move the verdict from CONDITIONAL to UNVERDICTED: the central claim is not established, though I am not asserting it is false. The kernel, FPT, and EPTAS results for the other problems appear more self-contained and are not implicated by this concern.","tokens_in":54626,"tokens_out":19276,"duration_ms":187010,"concrete_test":"Check Claim 4 on the concrete well-behaved minor for the 7x7 grid: let P be the integer grid points and phi(v)={v}. For i=j=1, let C_{1,1} be the 8-cycle on {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2)} and let W be the closed walk through these vertices in the unit disk graph. Compute the area enclosed by the union of the eight unit disks (Definition 7) and test whether the unit disk centered at (3,3) is contained in it. Geometrically it is not: (3,3) lies outside the polygonal cycle, and the union has no bounded hole containing it. This refutes Claim 4 and shows Lemma 14 needs a stronger geometric premise on the minor model. Alternatively, formally re-derive Claim 4 from Definition 6 to see that the containment of C inside C_{1,1} does not imply containment of the disjoint outside branch.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"The flagship Theorem 3 depends on Lemma 14 (Section 7.3), whose Claim 4 asserts that in a well-behaved grid minor, the branch phi(v_{3+7(i-1),3+7(j-1)}) is contained in the interior set of the closed walk W_{i,j}. This is used to infer that W_{i,j} is shrinkable, and then that the larger walks W*_{i,j} are reducible, yielding k disjoint shrinkable disks. The inference is a non-sequitur. In the natural embedding, C_{i,j} is the 3x3 grid block minus its bottom-right corner, and the 4-cycle C used in the proof is the top-left 2x2 block. The corner (3,3) is outside the polygon of C_{i,j}, not inside it. Definition 6's Property 1 only transfers containment of the area of C into the area of W_{i,j}; it says nothing about a branch that is not part of C and lies outside the enclosing cycle. With the identity minor (each grid vertex mapped to its own point), which is well-behaved for this pair, the unit disk centered at (3,3) is not contained in the area enclosed by the eight unit disks of W_{i,j}: it intersects them but protrudes outside, so it belongs to the relevant set R, not the interior set Q. Thus Claim 4 is false as stated, and Lemma 14's proof does not establish a yes-instance. This gap is independent of whether Proposition 4's asserted extension of [34] is true: even a perfect well-behaved minor of the kind stated does not supply the missing property.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper initiates the study of graph modification problems on disk intersection graphs where the modification operation is geometric, namely shrinking or expanding disks, rather than the usual combinatorial vertex/edge operations. It defines k-Shrinking to Independence, k-Shrinking to Acyclicity, k-Shrinking to Connectivity, and k-Expanding to Connectivity, together with cost-minimization variants. The main algorithmic claims are subexponential FPT algorithms for the three shrinking problems (Theorems 1, 2, and 3), polynomial kernels and partial compressions for the independence and acyclicity problems (Theorems 4, 5, 7, 9), FPT algorithms for the minimization variants (Theorems 6, 8), and bi-criteria EPTASes for the independence variants (Theorem 10). The paper also proves NP-hardness for all three shrinking problems and W[1]-hardness for a generalized expanding-to-connectivity problem. The flagship result is Theorem 3, a subexponential FPT algorithm for k-Shrinking to Connectivity whose proof depends on a new well-behaved grid-minor theorem and a cycle-based reduction argument.","tokens_in":54994,"tokens_out":11246,"duration_ms":122218,"significance":"If established, this framework is a meaningful conceptual contribution: disk scaling is a natural geometric modification operation from topology control, and the paper demonstrates that it fits into the parameterized-complexity toolkit. The combination of linear programming, kernelization, branching, and bidimensionality for geometric objects is novel, and several results, such as the partial kernels and the EPTAS for independence, appear independent of the contested connectivity theorem. The paper is also careful to avoid circularity: the main results are not assumed, and the reliance on the earlier grid-minor and treewidth results of [34] is explicit. However, the flagship result Theorem 3 is not established by the current text: its key structural lemma contains a false containment inference, and a load-bearing extension of [34] is asserted without proof. The remaining results, if supported by full proofs, would still be valuable, but the paper as a whole requires substantial revision before its central connectivity claim can be accepted.","major_comments":[{"comment":"The proof of Claim 4 is not valid as written. In the natural identity minor, the cycle C_{i,j} of Definition 9 is the 3x3 grid block without its bottom-right corner (3+7(i-1), 3+7(j-1)), and the 4-cycle C used in the claim is the top-left 2x2 block. The enclosed area of C does not contain the missing corner: for i=j=1, the point (3,3) lies outside the polygon formed by the eight vertices of C_{1,1}. Property 1 of Definition 6 only transfers the area enclosed by C into the area enclosed by W_{i,j}; it says nothing about the branch phi(v_{3+7(i-1),3+7(j-1)}), which is not part of C and is not inside the transferred area. Thus the conclusion that W_{i,j} is non-empty, and the subsequent construction of k reducible closed walks with disjoint relevant sets, does not follow. Since Theorem 3's large-grid case depends directly on this step, the proof of Theorem 3 is incomplete.","section":"Section 7.3, Lemma 14, Claim 4"},{"comment":"Proposition 4 states that the grid minor obtained from Corollary 4.10 of [34] can be required to be well-behaved in the sense of Definition 6, but the proof is only the sentence \"It can be verified that the proof of Corollary 4.10 in [34] yields...\". This is a load-bearing assertion: the connectivity algorithm's Step 8 and Lemma 14 use both containment of enclosed areas (Property 1) and disjointness of enclosed areas for disjoint grid cycles (Property 2). If this extension fails, the dichotomy into a well-behaved grid minor or a small-treewidth decomposition is unsupported. Please supply a complete derivation from the original proof, or a full self-contained proof of Proposition 4.","section":"Section 7.1, Proposition 4"},{"comment":"These dynamic programming lemmas are stated without proofs: Lemma 7 and Lemma 8 say only that a straightforward DP works, and Lemma 15 says \"details are omitted\". These lemmas are load-bearing for Theorems 1, 2, and 3, because they provide the bounded-treewidth case of each subexponential algorithm. In particular, Lemma 15 must handle marked unshrinkable disks, compatible solutions, and the exact requirement of the connectivity problem, which is not the standard vertex-cover or feedback-vertex-set DP. Please include the DP state, transitions, and correctness argument, or a clear pointer to an existing result that covers this exact annotated problem.","section":"Lemmas 7, 8, and 15"}],"minor_comments":[{"comment":"The displayed definition of d_max uses \"min\" where the text clearly intends the maximum distance between consecutive internal vertices of a reducible path; this should be corrected.","section":"Section 6.1, proof of Lemma 3"},{"comment":"The text says that W*_{i,j} traverses all vertices in the union over v in V(C_{i,j}) of phi(v), but from the definition and the purpose of the claim it should be the union over v in V(C*_{i,j}); otherwise W*_{i,j} is the same as W_{i,j}.","section":"Section 7.3, after Claim 4"},{"comment":"The proof says a vertex w_{i,j} is picked \"from the relevant set of W_{i,j}\", but Lemma 13 applies to the interior set; the statement should refer to the interior set.","section":"Section 7.3, final paragraph of Lemma 14"},{"comment":"For open unit disks, non-adjacency gives |pq| >= 2, not |pq| > 2 as stated in item (2). The subsequent packing bound still works with a weak inequality, but the observation should be stated correctly for the open-disk convention used in this section.","section":"Section 5.1, Observation 2"},{"comment":"The construction sometimes refers to spacing by a fixed distance 5 and sometimes by 2r-1; for general alpha and r = ceil(2/(1-alpha)), these agree only when r=3. Please make the notation uniform so the construction is unambiguous.","section":"Section 9.3, NP-hardness construction"}],"recommendation":"major_revision","confidential_remarks":"The paper is an interesting preprint with a clear conceptual contribution, but the connectivity algorithm is the main advertised result and its proof currently has a concrete false inference in Lemma 14 and an unproved extension in Proposition 4. I recommend major revision rather than rejection because the framework and the independence/acyclicity results may be salvageable, but the authors should be told clearly that Theorem 3 must either receive a repaired proof or be removed/weakened. The many \"details omitted\" markers, especially for the treewidth DPs, should also be resolved in a journal version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The scaling model is genuinely new and the paper does a lot of solid work around it, but I don't trust the proof of the flagship Theorem 3. Lemma 14's Claim 4 asserts that the branch at the bottom-right corner of each 3x3 block sits in the interior set of the closed walk W_{i,j}. In the natural grid embedding, the unit disk at (3,3) is not contained in the area enclosed by the eight unit disks of W_{i,j}; it intersects them and protrudes, so it belongs to the relevant set R rather than the interior set Q. Property 1 in Definition 6 only transfers containment from the 4-cycle's area, and (3,3) lies outside that 4-cycle. So the inference is a non-sequitur, and it is independent of Proposition 4. This gap is load-bearing: the grid case of the connectivity algorithm collapses without it.\n\nThe rest of the paper is more solid. The independence results—partial kernel, LP-based FPT for the cost variant, and the EPTAS—are clean and, as far as I checked, correct. The acyclicity compression is intricate but plausible, and the NP-hardness reductions look careful. The model itself—disk scaling as a parameterized modification operation—is worth exporting to other geometric graph classes.\n\nThe soft spots are real but mostly the usual preprint syndrome: Proposition 4 is asserted with 'It can be verified' and no derivation; Lemmas 7, 8, and 15 are treewidth DPs with details omitted. Those would be acceptable if the connectivity proof were not already suspect. Given the broken Claim 4, Theorem 3 needs to be reworked or restated, and the proof should be written out fully.\n\nVerdict: send to peer review. The paper has enough genuine value in the independence/acyclicity parts and the model that it deserves referee time, but the editor should expect a substantial revision. I would not cite Theorem 3 until the gap is fixed; the independence kernel and the model are citable now.","headline":"The scaling model and the independence/acyclicity results are a real contribution, but the proof of the subexponential connectivity algorithm (Theorem 3) rests on a containment claim in Lemma 14 that looks plainly false.","tokens_in":55498,"tokens_out":5834,"would_cite":true,"duration_ms":52403,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","68Q27","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shrinking disks, not deleting vertices, can repair geometric intersection graphs, and the paper shows the repair is fast in theory.","keywords":["disk intersection graphs","parameterized complexity","graph modification","disk scaling","kernelization","bidimensionality","subexponential FPT algorithms","topology control"],"falsifier":"Construct a unit disk graph that contains a large grid minor, and check whether every minor model violates the containment or disjointness conditions of Definition 6. If a single such graph exists, then Proposition 4 is false, and the grid case of the connectivity algorithm loses its structural premise; a concrete candidate is a small grid drawn with disks whose branch sets overlap in a way that forces enclosed areas to cross.","tokens_in":54443,"feed_emoji":"📐","tokens_out":3885,"duration_ms":40420,"temperature":0.7,"pith_summary":"This paper proposes a new way to modify geometric intersection graphs: instead of deleting vertices or edges, change the radii of the disks themselves. It argues that shrinking at most k disks to a fixed fraction $\\alpha$ of their original radius can make a unit disk graph edgeless or acyclic, and that shrinking at least k disks can preserve connectivity, and it gives parameterized algorithms for all three goals. The central algorithmic claim is that these problems admit subexponential fixed-parameter algorithms when $\\alpha$ is constant, with running times of the form $2^{{O(sqrt k)}}$ or (k/$\\alpha$)^{O($k^{{3/4}}$)} times a polynomial in n. The paper also provides polynomial kernels, a partial compression for the cost-minimization variant, approximation schemes for the independence version, and matching NP-hardness and W[1]-hardness lower bounds. If correct, this opens a research direction where topology-control-style geometric operations, not combinatorial edits, define the parameterized complexity of graph modification.","feed_headline":"Shrinking disks can repair graphs in subexponential time","feed_subtitle":"Scaling disk radii, not deleting vertices, achieves edgeless, acyclic, or connected intersection graphs with fast parameterized algorithms.","key_machinery":"The main machinery is a combination of clique elimination, bidimensionality, and linear programming. For the subexponential algorithms, the paper first caps the clique size using packing arguments: a disk of radius r can contain at most (r/t)^2 pairwise disjoint disks of radius t, and at most five pairwise disjoint unit disks can intersect a common unit disk. It then uses a grid-minor-versus-treewidth dichotomy for unit disk graphs: either the graph contains a large grid as a minor, in which case the instance is a No-instance for independence and acyclicity, or it has bounded treewidth and a dynamic program solves the problem. For connectivity, the paper introduces the notion of a well-behaved grid minor, whose cycles enclose disk areas in a nested and disjoint fashion, and classifies closed walks as unshrinkable, non-empty, or reducible according to whether the disks inside them can be shrunk. For the minimization variants, the paper reduces the instance to a bounded annotated multigraph, guesses the structure of a solution, and solves a linear program over the real-valued radii; the LP solver used is a deterministic Real-RAM algorithm.","core_discovery":"The paper's central discovery is that scaling disk radii is a meaningful and algorithmically tractable modification operation for disk intersection graphs. It proves that k-Shrinking to Independence is solvable in $2^{{O((1/alpha)^2 sqrt k)}}$ $n^{{O(1)}}$ time, k-Shrinking to Acyclicity in (k/$\\alpha$)^{O((1/$\\alpha$)^2 sqrt k)} $n^{{O(1)}}$ time, and k-Shrinking to Connectivity in (k/$\\alpha$)^{O((1/$\\alpha$)^2 $k^{{3/4}}$)} $n^{{O(1)}}$ time. The key structural insight is that large cliques can be eliminated geometrically, and that the remaining instance either has a large grid minor or bounded treewidth; for connectivity, the grid-minor case requires a new notion of a well-behaved minor model whose cycle boundaries enclose disk areas in a nested, non-crossing way. On the kernelization side, the paper shows that k-Shrinking to Independence and k-Shrinking to Acyclicity admit true polynomial kernels, while the cost-minimization versions admit partial polynomial compressions, solved by combining enumeration with linear programming. The paper also establishes that all main problems are NP-hard, and that a natural generalization of k-Expanding to Connectivity is W[1]-hard.","pith_inferences":["A likely next step is to study whether the connectivity problem admits a polynomial kernel or a cost-minimization version, since the paper explicitly leaves these open; the partial-compression and LP techniques used for acyclicity seem natural candidates.","The well-behaved grid minor property is the most fragile part of the connectivity argument. If a counterexample to Proposition 4 exists, the claimed k^{3/4} exponent would need a different structural premise, and the connectivity algorithm would lose its main grid-case reduction.","The same combination of kernelization and linear programming may transfer to other continuous parameterized problems, such as scaling squares or balls in higher dimensions, where the continuous search space can be tamed by first reducing the instance size.","The area-based closed-walk analysis suggests a general principle: for connectivity-style problems on geometric intersection graphs, one may need to reason about the geometry of enclosed regions, not just the combinatorial structure of graph minors."],"forward_implications":["If the algorithms are correct, then shrinking disks is a viable parameterized modification operation: the three most basic graph properties, edgelessness, acyclicity, and connectivity, are all fixed-parameter tractable with subexponential parameter dependence.","The true polynomial kernels for the independence and acyclicity variants mean that large inputs can be reduced to size polynomial in the number of allowed shrinks, which is a practical preprocessing guarantee.","The EPTAS for k-Shrinking to Independence implies that near-optimal solutions can be found in time exponential only in 1/epsilon, which is useful for applications where an approximate answer suffices.","The W[1]-hardness of generalized expansion shows that not every natural disk-scaling modification problem is tractable, delineating a boundary within this new model.","The new grid-minor decomposition for unit disk graphs, where the minor model is required to be well-behaved with respect to enclosed areas, may be applicable to other geometric problems that involve connectivity or coverage."],"supporting_citations":[{"why":"Supplies the clique-grid representation and the grid-minor-versus-treewidth dichotomy for unit disk graphs, which the paper extends to well-behaved minor models in Proposition 4.","marker":"[34]"},{"why":"Provides the deterministic Real-RAM linear programming solver used to determine optimal real-valued radii in the minimization algorithms.","marker":"[21]"},{"why":"Gives the polynomial-time maximum clique algorithm on unit disk graphs used in the clique-elimination steps of the subexponential algorithms.","marker":"[22]"},{"why":"Establishes NP-hardness of monotone planar 3-SAT, the source problem for the NP-hardness reduction for k-Shrinking to Connectivity.","marker":"[46]"},{"why":"Provides rectilinear embeddings of planar graphs with few bends, used to construct the NP-hardness reductions for the independence and acyclicity variants.","marker":"[47]"},{"why":"Shows W[1]-hardness of covering points by unit disks, which is the reduction source for the W[1]-hardness of generalized k-Expanding to Connectivity.","marker":"[52]"},{"why":"Supplies the bound that at most five pairwise non-intersecting unit disks can intersect a common unit disk, used in the clique-elimination arguments for the independence and acyclicity problems.","marker":"[6]"}],"fun_headline_variants":["Scaling disks to fix graphs in subexponential time","Disk shrinking yields fast parameterized graph repair","Shrink disks, not vertices, for fast graph fixes","Geometric graph repair via disk scaling, subexponential","Disk scaling gives subexponential fixes for graph classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The connectivity algorithm's grid case assumes that the proof of a cited decomposition result for unit disk graphs can be strengthened to guarantee a 'well-behaved' grid minor, meaning that nested cycles enclose nested regions and disjoint cycles enclose disjoint regions, but this strengthening is asserted by inspection rather than derived in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Scaling disks to fix graphs in subexponential time","Disk shrinking yields fast parameterized graph repair","Shrink disks, not vertices, for fast graph fixes","Geometric graph repair via disk scaling, subexponential","Disk scaling gives subexponential fixes for graph classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000197,"raw_usage":{"total_tokens":1421,"prompt_tokens":1056,"completion_tokens":365,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":288}},"tokens_in":672,"tokens_out":365,"duration_ms":4178,"temperature":1.0,"reasoning_tokens":288,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:47:32.516384+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a unit disk graph that contains a large grid minor, and check whether every minor model violates the containment or disjointness conditions of Definition 6. If a single such graph exists, then Proposition 4 is false, and the grid case of the connectivity algorithm loses its structural premise; a concrete candidate is a small grid drawn with disks whose branch sets overlap in a way that forces enclosed areas to cross.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the clique-grid representation and the grid-minor-versus-treewidth dichotomy for unit disk graphs, which the paper extends to well-behaved minor models in Proposition 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the deterministic Real-RAM linear programming solver used to determine optimal real-valued radii in the minimization algorithms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the polynomial-time maximum clique algorithm on unit disk graphs used in the clique-elimination steps of the subexponential algorithms."},{"cited_title":"Lichtenstein, Planar formulae and their uses, SIAM J","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of monotone planar 3-SAT, the source problem for the NP-hardness reduction for k-Shrinking to Connectivity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides rectilinear embeddings of planar graphs with few bends, used to construct the NP-hardness reductions for the independence and acyclicity variants."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows W[1]-hardness of covering points by unit disks, which is the reduction source for the W[1]-hardness of generalized k-Expanding to Connectivity."},{"cited_title":"Atminas and V","cited_arxiv_id":null,"evidence_quote":"Supplies the bound that at most five pairwise non-intersecting unit disks can intersect a common unit disk, used in the clique-elimination arguments for the independence and acyclicity problems."}],"review_version":1}