Pith. sign in

REVIEW 3 major objections 5 minor 61 references

Parameterized Geometric Graph Modification with Disk Scaling

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Shrinking disks, not deleting vertices, can repair geometric intersection graphs, and the paper shows the repair is fast in theory.

desk verdict 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. read the letter →

arxiv 2411.13171 v1 pith:47GPUBJD submitted 2024-11-20 cs.CG cs.DS

Fedor V. Fomin , Petr A. Golovach , Tanmay Inamdar , Saket Saurabh , Meirav Zehavi This is my paper · ORCID
classification cs.CGcs.DS MSC 68U0568Q2705C85
keywords diskintersectiongraphsparameterizedcomplexitygraphmodificationscalingkernelizationbidimensionalitysubexponentialFPTalgorithmstopologycontrol
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 7.3, Lemma 14, Claim 4] 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.
  2. [Section 7.1, Proposition 4] 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.
  3. [Lemmas 7, 8, and 15] 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.
minor comments (5)
  1. [Section 6.1, proof of Lemma 3] 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.
  2. [Section 7.3, after Claim 4] 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}.
  3. [Section 7.3, final paragraph of Lemma 14] 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.
  4. [Section 5.1, Observation 2] 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.
  5. [Section 9.3, NP-hardness construction] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation chain is self-contained modulo external structural theorems; the unproved extension in Proposition 4 is a correctness gap, not a circular step.

full rationale

No step in the derivation chain is circular. The algorithms for k-Shrinking to Independence and Acyclicity reduce to exact LP reformulations and standard branching/kernelization; the LP constraints (e.g., r(p)+r(q) ≤ |pq|) are direct reformulations of disk non-intersection, not fitted parameters or definitional re-statements of the target answer. The connectivity algorithm rests on Lemmas 11–14 and Proposition 4. Proposition 4 is an asserted extension of Corollary 4.10 of [34], a paper with overlapping authors, claiming either a well-behaved grid minor or an ℓ-NCTD. Although this is load-bearing and the extension is not proved in the preprint, the cited Corollary 4.10 is an external structural theorem whose assumptions do not include the target problem; the claimed extension is a statement about that proof, not a re-use of Theorem 3 as a premise. Similarly, Lemma 14's Claim 4 may be geometrically doubtful, as the skeptic's objection observes, but an incorrect or insufficiently justified inference is an error, not circularity. The polynomial kernels use the standard device of reducing an NP-member back to the NP-complete target problem, where the NP-hardness of the target problems is established independently from planar Independent Set, Feedback Vertex Set, and Monotone Planar 3-SAT. No prediction is generated from a fitted constant, and no target theorem is assumed within its own proof. The paper's self-citations are genuine supporting tools, not a self-referential uniqueness argument. Verdict: no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central algorithms rest on several imported geometric black boxes plus internally stated but unproved lemmas. There are no fitted parameters or new postulated entities.

assumptions (5)
  • domain assumption Real RAM model with unit-cost exact real arithmetic (Section 4).
    All algorithms assume real coordinates and exact LP solving; bit-length and numerical precision are ignored, which matters for practical implementation.
  • standard math Unit disk graphs admit a clique-grid representation and the grid/treewidth dichotomy of [34] (Propositions 2 and 3).
    Imported as proved black boxes; Proposition 3 says either a gamma l by gamma l grid minor or a 5l-NCTD with width O(l) can be found in 2^{O(l)} n^{O(1)}.
  • ad hoc to paper The grid minor from [34] can be chosen well-behaved in the sense of Definition 6 (Proposition 4).
    Stated as an extension of [34] with no proof in this preprint; it is load-bearing for k-Shrinking to Connectivity.
  • domain assumption Standard treewidth dynamic programs solve the bounded-width cases (Lemmas 7, 8, 15).
    The paper says these are straightforward and omits details; used in all three subexponential algorithms.
  • standard math NP-hardness of the source problems: Monotone Planar 3-SAT, planar cubic independent set, planar max-degree-4 feedback vertex set, and Covering Points by Unit Disks.
    Used in lower-bound reductions in Section 9.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Geometric Graph Modification with Disk Scaling." pith.science (2026). https://pith.science/paper/47GPUBJD

@misc{pith2026241113171,
  author       = {Pith},
  title        = {Pith review of: Parameterized Geometric Graph Modification with Disk Scaling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/47GPUBJD}},
  note         = {Machine review of arXiv:2411.13171}
}
abstract

The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph $G$ and an integer $k\in\mathbb{N}$ as input, the goal is to determine whether we can perform at most $k$ operations on $G$ to transform it into a graph belonging to a specified graph class $\mathcal{F}$. Typical operations are combinatorial and include vertex deletions and edge deletions, insertions, and contractions. However, in many real-world scenarios, when the input graph is constrained to be a geometric intersection graph, the modification of the graph is influenced by changes in the geometric properties of the underlying objects themselves, rather than by combinatorial modifications. It raises the question of whether vertex deletions or adjacency modifications are necessarily the most appropriate modification operations for studying modifications of geometric graphs. We propose the study of the disk intersection graph modification through the scaling of disks. This operation is typical in the realm of topology control but has not yet been explored in the context of Parameterized Complexity. We design parameterized algorithms and kernels for modifying to the most basic graph classes: edgeless, connected, and acyclic. Our technical contributions encompass a novel combination of linear programming, branching, and kernelization techniques, along with a fresh application of bidimensionality theory to analyze the area covered by disks, which may have broader applicability.

Figures

Figures reproduced from arXiv: 2411.13171 by the authors.

Figure 1
Figure 1. Left: Original intersection graph G = G(P, 1) denoting an instance (P, 1/2, 3) of k-Shrinking to Independence. Right: Edgeless graph G(P, r) that shrinks three disks to radius 1/2 (shown in red). Another common theme with the work of [30] is that they also combine enumeration of partial solutions from the (partial) kernel, and then reduce the problem to checking a system of polynomial inequalities. This high level s… view at source ↗
Figure 2
Figure 2. Left: Original intersection graph G = G(P, 1) corresponding to an instance (P, 1/2, 3) of k￾Shrinking to Acyclicity. Note that {u, v} is a minimum feedback vertex set for G. However, even after shrinking the corresponding disks to 1/2 (shown in blue), the edges {uw1, uw2, vx1, v2} (shown in red) are present in the resulting intersection graph, showing that shrinking disks is not equivalent to vertex deletion. Right:… view at source ↗
Figure 3
Figure 3. Left: Original intersection graph G = G(P, 1) corresponding to an instance (P, 1/2, 4) of k￾Shrinking to Connectivity. Right: A solution that shrinks 4 disks to radius 1/2 while maintaining connectivity in the resulting intersection graph G(P, r). The next problem, which we call k-Expanding to Connectivity, is in a sense, the “comple￾ment version” of k-Shrinking to Independence. Here, we are given a unit disk graph … view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: There is a solution that shrinks some of the disks in the clique; however, shrinking all the disks in the clique results in the disconnected graph (due to the red disks) compared to all previously known subexponential-time algorithms for problems on geometric intersect…
Figure 5
Figure 5. Figure 5: Each disk corresponding to the vertices of the grid minor is “touching” its neighbors, and shrinking any of the disks results in a disconnected graph. (according to the minor model) to its 4-cycles have some particular embedding on the plane. Then, we are able to show …
Figure 6
Figure 6. Figure 6: (a) Given intersection graph after removing the vertices of degree at most 1. Vertices of degree [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: Top row: Pairs of disks with varying distances between the centers, with [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Graphs Gφ and G′ φ for φ = (v1 ∨ v2 ∨ v3) ∧ (v1 ∨ v3 ∨ v4) ∧ (v1 ∨ v4 ∨ v5) ∧ (v1 ∨ v2 ∨ v5) ∧ (v2 ∨ v3 ∨ v5) ∧ (v3 ∨ v4 ∨ v5)) (a) and the drawing of Gφ (b). disks of radius β to radius 1. Thus, k-Shrinking to Connectivity and k-Expanding to Connectivity are indeed du…
Figure 9
Figure 9. Figure 9: The variable gadget for vi. The radius scaling corresponding to the positive assignment of vi is shown by dashed blue circles. 42 [PITH_FULL_IMAGE:figures/full_fig_p042_9.png]
Figure 10
Figure 10. Figure 10: The connection of the variable gadgets and the construction of the clause gadgets; here [PITH_FULL_IMAGE:figures/full_fig_p043_10.png]
Figure 11
Figure 11. Figure 11: Reduction of a Yes-instance of Covering Points by Unit Disks to a Yes-instance of Scaling to Connected Graph. On the left side, the points are colored black, and the possible poitions for centers are colored red. On the right, only the new-unit disks colored red can b…
Figure 12
Figure 12. Figure 12: Example for construction of the instance of [PITH_FULL_IMAGE:figures/full_fig_p048_12.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 61 canonical work pages

  1. [1]

    Acharyya, M

    A. Acharyya, M. De, S. C. Nandy, and B. Roy , Range assignment of base-stations maximizing coverage area without interference , Theoretical Computer Science, 804 (2020), pp. 81–97. 2

    work page 2020

  2. [34]

    , Finding, hitting and packing cycles in subexponential time on unit disk graphs , Discret. Comput. Geom., 62 (2019), pp. 879–911. 2, 7, 27, 28

    work page 2019

  3. [2]

    Agrawal, D

    A. Agrawal, D. Lokshtanov, P. Misra, S. Saurabh, and M. Zehavi, Feedback vertex set inspired kernel for chordal vertex deletion , ACM Trans. Algorithms, 15 (2019), pp. 11:1– 11:28. 1

    work page 2019

  4. [3]

    Agrawal, P

    A. Agrawal, P. Misra, S. Saurabh, and M. Zehavi , Interval vertex deletion admits a polynomial kernel, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, 2019, pp. 1711–1730. 1

    work page 2019

  5. [4]

    Alber and J

    J. Alber and J. Fiala , Geometric separation and exact solutions for the parameterized independent set problem on disk graphs , Journal of Algorithms, 52 (2004), pp. 134–151. 2

    work page 2004

  6. [5]

    Aloupis, M

    G. Aloupis, M. Damian, R. Y. Flatland, M. Korman, ¨O. ¨Ozkan, D. Rappaport, and S. Wuhrer , Establishing strong connectivity using optimal radius half-disk antennas , Comput. Geom., 46 (2013), pp. 328–339. 2

    work page 2013

  7. [6]

    Atminas and V

    A. Atminas and V. Zamaraev , On forbidden induced subgraphs for unit disk graphs , Dis- cret. Comput. Geom., 60 (2018), pp. 57–97. 29

    work page 2018

  8. [7]

    B. S. Baker, Approximation algorithms for np-complete problems on planar graphs, J. ACM, 41 (1994), pp. 153–180. 11

    work page 1994

Show all 61 references
  1. [8]

    Basavaraju, M

    M. Basavaraju, M. C. Francis, M. S. Ramanujan, and S. Saurabh, Partially polyno- mial kernels for set cover and test cover , SIAM J. Discret. Math., 30 (2016), pp. 1401–1423. 14

    2016

  2. [9]

    Betzler, J

    N. Betzler, J. Guo, C. Komusiewicz, and R. Niedermeier , Average parameterization and partial kernelization for computing medians, J. Comput. Syst. Sci., 77 (2011), pp. 774–789. 14

    2011

  3. [10]

    Biniaz, P

    A. Biniaz, P. Bose, P. Carmi, A. Maheshwari, J. I. Munro, and M. Smid , Faster al- gorithms for some optimization problems on collinear points, arXiv preprint arXiv:1802.09505, (2018). 2

    2018 arXiv

  4. [11]

    Bliznets, M

    I. Bliznets, M. Cygan, P. Komosa, L. Mach, and M. Pilipczuk , Lower bounds for the parameterized complexity of minimum fill-in and other completion problems , in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2016, pp. 1132–1151. 1 52

    2016

  5. [12]

    Bliznets, F

    I. Bliznets, F. V. Fomin, M. Pilipczuk, and M. Pilipczuk , Subexponential parameter- ized algorithm for interval completion , ACM Transactions on Algorithms (TALG), 14 (2018), p. 35. 1

    2018

  6. [13]

    Bonnet and P

    ´E. Bonnet and P. Rzazewski, Optimality program in segment and string graphs, Algorith- mica, 81 (2019), pp. 3047–3073. 2

    2019

  7. [14]

    Bougeret, B

    M. Bougeret, B. M. P. Jansen, and I. Sau , Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel, in 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr¨ ucken, Germany (Vi...

    2020

  8. [15]

    Calinescu and P.-J

    G. Calinescu and P.-J. Wan , Range assignment for high connectivity in wireless ad hoc networks, in International Conference on Ad-Hoc Networks and Wireless, Springer, 2003, pp. 235–246. 2

    2003

  9. [16]

    Cao, Linear recognition of almost interval graphs , in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2016, pp

    Y. Cao, Linear recognition of almost interval graphs , in Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, SIAM, 2016, pp. 1096–1115. 1

    2016

  10. [17]

    Cao and R

    Y. Cao and R. Sandeep, Minimum fill-in: Inapproximability and almost tight lower bounds , in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2017, pp. 875–880. 1

    2017

  11. [18]

    Caragiannis, C

    I. Caragiannis, C. Kaklamanis, and P. Kanellopoulos , Energy-efficient wireless net- work design, Theory of Computing Systems, 39 (2006), pp. 593–617. 2

    2006

  12. [19]

    Carmi and M

    P. Carmi and M. J. Katz , Power assignment in radio networks with two power levels , Algorithmica, 47 (2007), pp. 183–201. 2

    2007

  13. [20]

    E. W. Chambers, S. P. Fekete, H. Hoffmann, D. Marinakis, J. S. B. Mitchell, S. Venkatesh, U. Stege, and S. Whitesides , Connecting a set of circles with minimum sum of radii , Comput. Geom., 68 (2018), pp. 62–76. 2

    2018

  14. [21]

    T. M. Chan , Improved deterministic algorithms for linear programming in low dimensions , ACM Trans. Algorithms, 14 (2018), pp. 30:1–30:10. 9, 14

    2018

  15. [22]

    B. N. Clark, C. J. Colbourn, and D. S. Johnson , Unit disk graphs , Discrete mathe- matics, 86 (1990), pp. 165–177. 30, 36

    1990

  16. [23]

    Crespelle, P

    C. Crespelle, P. G. Drange, F. V. Fomin, and P. A. Golovach , A survey of param- eterized algorithms and the complexity of edge modification , Comput. Sci. Rev., 48 (2023), p. 100556. 1

    2023

  17. [24]

    Cygan, F

    M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh , Parameterized Algorithms, Springer, 2015. 1, 13, 14, 29, 35, 52

    2015

  18. [25]

    de Berg, H

    M. de Berg, H. L. Bodlaender, S. Kisfaludi-Bak, D. Marx, and T. C. van der Zanden, A framework for eth-tight algorithms and lower bounds in geometric intersection graphs, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Comput- ing, STOC 2018, Los Angeles, C...

    2018

  19. [26]

    de Berg, S

    M. de Berg, S. Kisfaludi-Bak, and G. J. Woeginger , The complexity of dominating set in geometric intersection graphs , Theor. Comput. Sci., 769 (2019), pp. 18–31. 2

    2019

  20. [27]

    Diestel, Graph Theory, 4th Edition, vol

    R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer,

  21. [28]

    R. G. Downey and M. R. Fellows , Fundamentals of parameterized complexity , vol. 4, Springer, 2013. 1, 52

    2013

  22. [29]

    Eppstein , Maximizing the sum of radii of disjoint balls or disks , arXiv preprint arXiv:1607.02184, (2016)

    D. Eppstein , Maximizing the sum of radii of disjoint balls or disks , arXiv preprint arXiv:1607.02184, (2016). 2

    2016 arXiv

  23. [30]

    F. V. Fomin, P. A. Golovach, T. Inamdar, S. Saurabh, and M. Zehavi, Kernelization for spreading points, in 31st Annual European Symposium on Algorithms, ESA 2023, Septem- ber 4-6, 2023, Amsterdam, The Netherlands, I. L. Gørtz, M. Farach-Colton, S. J. Puglisi, and G. Herman, ed...

    2023

  24. [31]

    F. V. Fomin, P. A. Golovach, T. Inamdar, and M. Zehavi , (re)packing equal disks into rectangle, in 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, M. Bojanczyk, E. Merelli, and D. P. Woodruff, eds., vol. 229 of...

    2022

  25. [32]

    F. V. Fomin, T. Le, D. Lokshtanov, S. Saurabh, S. Thomass ´e, and M. Zehavi , Subquadratic kernels for implicit 3-hitting set and 3-set packing problems , ACM Trans. Algo- rithms, 15 (2019), pp. 13:1–13:44. 1

    2019

  26. [33]

    F. V. Fomin, D. Lokshtanov, F. Panolan, S. Saurabh, and M. Zehavi, Decomposition of map graphs with applications , in 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, 2019, pp. 60:1–60:15. 2, 7

    2019

  27. [35]

    44:1–44:18

    , Eth-tight algorithms for long path and cycle on unit disk graphs , in 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Z¨ urich, Switzerland, 2020, pp. 44:1–44:18. 2, 7

    2020

  28. [36]

    F. V. Fomin, D. Lokshtanov, and S. Saurabh , Bidimensionality and geometric graphs , in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, 2012, pp. 1563–1575. 2, 7

    2012

  29. [37]

    ACM, 65 (2018), pp

    , Excluded grid minors and efficient polynomial-time approximation schemes , J. ACM, 65 (2018), pp. 10:1–10:44. 28

    2018

  30. [38]

    F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi , Kernelization: theory of parameterized preprocessing, Cambridge University Press, 2019. 1, 14, 52

    2019

  31. [39]

    Giannopoulos, C

    P. Giannopoulos, C. Knauer, and S. Whitesides , Parameterized complexity of geomet- ric problems, The Computer Journal, 51 (2008), pp. 372–384. 2, 45

    2008

  32. [40]

    D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI , J. ACM, 32 (1985), pp. 130–136. 11

    1985

  33. [41]

    Jansen, Polynomial kernels for hard problems on disk graphs , in Scandinavian Workshop on Algorithm Theory (SWAT), Springer, 2010, pp

    B. Jansen, Polynomial kernels for hard problems on disk graphs , in Scandinavian Workshop on Algorithm Theory (SWAT), Springer, 2010, pp. 310–321. 2

    2010

  34. [42]

    B. M. Jansen and M. Pilipczuk , Approximation and kernelization for chordal vertex dele- tion, SIAM Journal on Discrete Mathematics, 32 (2018), pp. 2258–2301. 1

    2018

  35. [43]

    D. E. Knuth and A. Raghunathan , The problem of compatible representatives , SIAM J. Discret. Math., 5 (1992), pp. 422–427. 40, 41 54

    1992

  36. [44]

    Kulik and H

    A. Kulik and H. Shachnai , Analysis of two-variable recurrence relations with application to parameterized approximations, CoRR, abs/1911.02653, Accepted to Symposium on Foun- dations of Computer Sciences (FOCS 2020) (2019). 1

    2019 arXiv

  37. [45]

    Li and J

    J. Li and J. Nederlof , Detecting feedback vertex sets of size k in O*(2.7k) time, in Pro- ceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, 2020, pp. 971–989. 1

    2020

  38. [46]

    Lichtenstein, Planar formulae and their uses, SIAM J

    D. Lichtenstein, Planar formulae and their uses, SIAM J. Comput., 11 (1982), pp. 329–343. 40

    1982

  39. [47]

    Y. Liu, A. Morgana, and B. Simeone, A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid , Discret. Appl. Math., 81 (1998), pp. 69–91. 47

    1998

  40. [48]

    E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan, and S. S. Ravi , Algorithmic aspects of topology control problems for ad hoc networks , Mobile Networks and applications, 10 (2005), pp. 19–34. 2

    2005

  41. [49]

    Lokshtanov, F

    D. Lokshtanov, F. Panolan, S. Saurabh, J. Xue, and M. Zehavi , Subexponential parameterized algorithms on disk graphs (extended abstract), in Proceedings of the 2022 ACM- SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12...

    2022

  42. [50]

    D. Marx , Efficient approximation schemes for geometric problems? , in Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, 2005, pp. 448–459. 2, 45

    2005

  43. [51]

    , Parameterized complexity of independence and domination on geometric graphs , in Pa- rameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z¨ urich, Switzerland, September 13-15, 2006, Proceedings, 2006, pp. 154–165. 2

    2006

  44. [52]

    , On the optimality of planar and geometric approximation schemes , in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, IEEE Computer Society, 2007, pp. 338–348. 8

    2007

  45. [53]

    Matousek, M

    J. Matousek, M. Sharir, and E. Welzl, A subexponential bound for linear programming, Algorithmica, 16 (1996), pp. 498–516. 9

    1996

  46. [54]

    Mohar, Face covers and the genus problem for apex graphs , J

    B. Mohar, Face covers and the genus problem for apex graphs , J. Comb. Theory, Ser. B, 82 (2001), pp. 102–117. 47

    2001

  47. [55]

    Panolan, S

    F. Panolan, S. Saurabh, and M. Zehavi , Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity , in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9...

    2019

  48. [56]

    Santi, Topology control in wireless ad hoc and sensor networks , ACM computing surveys (CSUR), 37 (2005), pp

    P. Santi, Topology control in wireless ad hoc and sensor networks , ACM computing surveys (CSUR), 37 (2005), pp. 164–194. 2

    2005

  49. [57]

    Speckenmeyer , Untersuchungen zum Feedback-vertex-set-Problem in ungerichteten Graphen, PhD thesis, University of Paderborn, Germany, 1983

    E. Speckenmeyer , Untersuchungen zum Feedback-vertex-set-Problem in ungerichteten Graphen, PhD thesis, University of Paderborn, Germany, 1983. 49

    1983

  50. [58]

    Graph Theory, 12 (1988), pp

    , On feedback vertex sets and nonseparating independent sets in cubic graphs , J. Graph Theory, 12 (1988), pp. 405–412. 49

    1988

  51. [59]

    Thomass ´e, A 4 k2 kernel for feedback vertex set , ACM Trans

    S. Thomass ´e, A 4 k2 kernel for feedback vertex set , ACM Trans. Algorithms, 6 (2010), pp. 32:1–32:8. 1 55

    2010

  52. [60]

    P.-J. Wan, G. C ˘alinescu, X.-Y. Li, and O. Frieder , Minimum-energy broadcasting in static ad hoc wireless networks , Wireless Networks, 8 (2002), pp. 607–617. 2

    2002

  53. [61]

    Zehavi, F

    M. Zehavi, F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh , Eth-tight algorithms for long path and cycle on unit disk graphs , J. Comput. Geom., 12 (2021), pp. 126–

    2021

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.