betaFeedback

WorksComputer Science

Vertex Deletion on HH-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes

Abstract

We study vertex-deletion problems on string graphs and, more generally, on graphs excluding a fixed graph as an induced minor. For every fixed graph HH, fixed nonnegative integer tt, and fixed monadic second-order formula ϕϕ, we consider the problem of finding a minimum-cardinality set SS such that G−SG-S has treewidth at most tt and satisfies ϕϕ. This captures classic problems such as Vertex Cover, Feedback Vertex Set, and deletion to graphs of any fixed bounded treewidth. We give an algorithm with running time 2k2/3log⁡O(1)knO(1)2^{k^{2/3} \log^{O(1)} k}n^{O(1)} on HH-induced-minor-free graphs, where kk is the optimum deletion-set size. This resolves in the affirmative the open problem highlighted by Bonnet and Rzążewski [Algorithmica 2019] and Berthe, Bougeret, Gonçalves, and Raymond [ICALP 2025] regarding the existence of a subexponential parameterized algorithm for Feedback Vertex Set on string graphs. Our algorithm significantly improves over existing parameterized algorithms for more restricted classes of problems on more restricted classes of graphs. When the property defined by ϕϕ is hereditary, we also obtain a quasi-polynomial time approximation scheme, namely an algorithm that produces a (1+ε)(1+\varepsilon)-approximate solution in quasi-polynomial time. Both the sub-exponential algorithm and the quasi-polynomial time approximation scheme build on the same new structural and algorithmic insights.

Introduction

Many fundamental graph optimization problems remain NP-hard even on highly structured inputs. Three complementary responses to this difficulty are to seek fixed-parameter algorithms, to settle for approximate solutions, and to exploit restrictions on the input graph. The interaction between these approaches has been particularly fruitful on planar graphs and, more generally, on graphs excluding a fixed minor. Bidimensionality provides a unified explanation for much of this tractability: for broad families of problems, suitable structural and algorithmic hypotheses yield subexponential parameterized algorithms exhibiting the square-root phenomenon (the running time dependence on the parameter kk is about 2O(k)2^{O(\sqrt{k})}), efficient polynomial-time approximation schemes (EPTASes), and linear kernels [24, 25, 34, 36]. A key structural ingredient in the planar case is the linear relation between treewidth and the size of a largest grid minor.

There are two natural directions in which to look. One is to consider more general sparse graph classes; another is to consider geometric intersection graphs, including unit disk graphs, disk graphs, rectangle intersection graphs, and string graphs. The first direction already encounters a basic obstruction: Vertex Cover is APX-complete on cubic graphs [3]. Since bounded-degree classes have bounded expansion and exclude suitable fixed topological minors, these restrictions alone cannot support a general approximation-scheme theorem unless P = NP. Geometric classes offer a different source of structure. They may contain arbitrarily large cliques, yet still admit useful separator and decomposition theorems. De Berg et al. [23] developed a general framework for subexponential algorithms on intersection graphs of similarly sized fat objects, based on geometric separators and treewidth techniques. Fomin, Lokshtanov, and Saurabh [35] extended bidimensionality techniques to obtain EPTASes and subexponential parameterized algorithms for several deletion problems on unit disk and map graphs. Further subexponential parameterized algorithms on unit disk and disk graphs illustrate the potential of this approach [5, 43, 4]. Lokshtanov et al. [44] subsequently developed a representation-free EPTAS framework for deletion problems on disk graphs, including Vertex Cover and Feedback Vertex Set.

Feedback Vertex Set has been a central test case for these extensions. On unit disk graphs, Fomin et al. [33] obtained a 2O(klog⁡k)nO(1)2^{O(\sqrt{k\log k})}n^{O(1)} algorithm, and An and Oh [5] improved this to 2O(k)(n+m)2^{O(\sqrt{k})}(n+m) without requiring a representation. Baste and Thilikos [7] extended bidimensionality to further geometric classes, including bounded-degree string graphs. Subsequent work developed algorithms for disks [4], squares and contact segments [9], and pseudo-disks [10, 8].

Recent work has developed broader frameworks beyond these classes. Berthe et al. [11] give sufficient conditions for subexponential parameterized algorithms for Feedback Vertex Set, covering, in particular, segment graphs and ss-string graphs for fixed ss. Lokshtanov et al. [46] give a framework for hitting a fixed finite family of forbidden subgraphs on classes with suitable separator bounds, including classes of polynomial expansion and several geometric classes. A fixed finite family of forbidden subgraphs does not capture Feedback Vertex Set, since cycles can have unbounded length. Our bounded-treewidth target formulation accommodates this problem together with more general MSO constraints.

From string graphs to excluded induced minors. A string graph is the intersection graph of a family of curves in the plane. This class includes disk and rectangle intersection graphs, as well as all planar graphs. A useful common setting is provided by graphs excluding a fixed graph as an induced minor, where an induced minor is obtained by vertex deletions and edge contractions. For a fixed graph HH, let GH\mathcal{G}_H denote the class of HH-induced-minor-free graphs. Every string graph excludes the graph obtained by subdividing each edge of K5K_5 once as an induced minor [41]. Thus, an algorithmic theorem for every fixed HH applies, in particular, to all string graphs. Figure 1 summarizes the graph classes covered by this framework.

Graph classes covered by the framework

Figure 1. Graph classes covered by our framework. Solid arrows indicate containment; only selected containments are shown. Dashed arrows indicate applications of the framework, with the excluded graph chosen for the class: the same HH for HH-minor-free graphs, and the once-subdivided K5K_5 for string graphs [41]. The highlighted box summarizes Theorems 1.1 and 1.2; no geometric representation is required.

The relevant structural ingredient is an edge-based separator theorem: graphs in GH\mathcal{G}_H with mm edges have balanced separators of size OH(m)O_H(\sqrt{m}). Lee [42] and Korhonen and Lokshtanov [41] originally claimed these bounds, but their proofs relied on a flawed padded-decomposition argument. Davies, Rzążewski, Spalding-Jamieson, and Walczak [22] give new proofs and polynomial-time separator algorithms. Both of our main results, Theorems 1.1 and 1.2, rely on this repaired separator theorem. It also restores the separator input underlying the 2O~(n2/3)2^{\widetilde{O}(n^{2/3})} algorithms of Korhonen and Lokshtanov. Unlike the separators of sparse minor-free graphs, these bounds are expressed in terms of the number of edges. Controlling dense parts of the input is therefore essential to obtaining algorithms whose complexity is governed by the solution size.

The deletion framework. We study vertex-deletion problems to classes of graphs with bounded treewidth and satisfying a fixed logical property. More precisely, fix an integer tt and a monadic second-order (MSO) sentence ϕ\phi. The objective is to delete as few vertices as possible so that the remaining graph has treewidth at most tt and satisfies ϕ\phi. This formulation includes Vertex Cover, by requiring the remaining graph to be edgeless; Feedback Vertex Set, by taking t=1t = 1 and imposing no further condition; and deletion to treewidth at most tt. For approximation, we require the property defined by ϕ\phi to be hereditary, meaning that it is preserved under taking induced subgraphs. The problem is stated formally below (where t∈Nt \in\mathbb{N} and ϕ\phi is an MSO formula).

(t,ϕ)(t,\phi)-DeletionParameter: k=∣S∣k = |S|
Input: A graph GG with nn vertices
Output: A minimum subset S⊆V(G)S \subseteq V(G) satisfying tw⁡(G−S)≤t\operatorname{tw}(G-S) \le t and G−SG-S satisfies ϕ\phi

Table 2.

A very closely related class of problems is Planar F\mathcal{F}-Deletion: delete vertices such that the resulting graph excludes every graph in a fixed finite family F\mathcal{F} as a minor. The family F\mathcal{F} is required to contain at least one planar graph. It follows from the excluded grid theorem of Robertson and Seymour [49] that every graph excluding a fixed planar graph as a minor has treewidth bounded by a constant; see also Cames van Batenburg et al. [18] for a recent improvement of the grid theorem for planar graphs. Further, containing a fixed graph as a minor is MSO definable. Thus, for every finite family F\mathcal{F} containing a planar graph, there exists an integer tt and MSO formula ϕ\phi such that Planar F\mathcal{F}-Deletion is a (t,ϕ)(t,\phi)-Deletion problem. Fomin et al. [32] established constant-factor approximation algorithms and polynomial kernels for Planar F\mathcal{F}-Deletion, as well as single-exponential parameterized algorithms when every graph in F\mathcal{F} is connected. Kim et al. [39] removed this connectivity assumption for the single-exponential algorithm. Subsequent work of Gupta et al. [37] gave deterministic approximation algorithms with improved guarantees. More recently, Włodarczyk [52] obtained a randomized polynomial-time constant-factor approximation algorithm for the vertex-weighted version.

Our focus is the additional algorithmic power obtained by restricting the input to CH\mathcal{C}_H.

Our results. Our first main result is a subexponential parameterized algorithm for every (t,ϕ)(t,\phi)-Deletion problem. We use kk for the size of an optimum deletion set; the notation O~\widetilde{O} suppresses polylogarithmic factors.

Theorem 1.1. Let HH be a fixed graph, t∈Nt \in\mathbb{N} be a fixed number, and ϕ\phi be a fixed MSO formula. Then (t,ϕ)(t,\phi)-Deletion on CH\mathcal{C}_H admits an algorithm that runs in 2O~(k2/3)nO(1)2^{\widetilde{O}(k^{2/3})}n^{O(1)} time.

The technical framework behind Theorem 1.1 also yields quasipolynomial-time approximation schemes for almost every (t,ϕ)(t,\phi)-Deletion problem, which is our second main result. The only additional property that we require is that the target graph class is closed under vertex deletion.

Theorem 1.2. Let HH be a fixed graph, t∈Nt \in\mathbb{N} be a fixed number, and ϕ\phi be a fixed hereditary MSO formula. Then (t,ϕ)(t,\phi)-Deletion on CH\mathcal{C}_H admits a quasipolynomial-time approximation scheme.

Theorem 1.1 measures the exponential part of the running time in the number kk of deleted vertices. The size kk of the solution is always at most the number nn of vertices in the input graph, and it can be much smaller. Korhonen and Lokshtanov [41], generalizing earlier work by Bonnet and Rzążewski [16], obtained 2O~(n2/3)2^{\widetilde{O}(n^{2/3})}-time algorithms for a broad family of induced-subgraph problems that includes every (t,ϕ)(t,\phi)-Deletion problem. The running time bound of Theorem 1.1 improves over the running time bounds for more restricted classes of problems on more restricted classes of graphs (such as Disk Graphs) [4, 8, 9, 11], see Table 1 (PDF p. 5). It answers in the affirmative an open problem in Section 6 of the full version of [11]: obtaining a subexponential algorithm for Feedback Vertex Set parameterized by kk on classes excluding a fixed induced minor, and in particular on string graphs.

Graph classRepresentation needed before?Earlier α\alphaOur α\alpha
Disk graphsNo9/10 [4]2/3
Disk graphsYes7/8 [4]2/3
Pseudo-disk graphsYes6/7 [8]2/3
Pseudo-disk graphsNo10/11 [8]2/3
Axis-parallel square graphsNo9/10 [9]2/3
ss-string graphs, fixed ssNo52/53 [11]2/3
All string graphs—Open [11]2/3

Table 1 (PDF p. 5). Selected comparisons for Feedback Vertex Set. An exponent α\alpha denotes a bound 2O~(kα)nO(1)2^{\widetilde{O}(k^\alpha)}n^{O(1)}; all bounds from this paper require only the input graph. The pseudo-disk bounds 6/7 and 10/11 are from arXiv:2410.23878v1 [8]; the published WG version [10] states the earlier represented bound 9/10. The 52/53 bound is explicit in Section 5.2 of arXiv:2504.17708v2 [11]. The 6/7 pseudo-disk bound also applies to represented disk graphs. Open refers to a subexponential algorithm parameterized by kk, not by nn.

The running time dependence on kk of Theorem 1.1 essentially matches the running time dependence on nn of Korhonen and Lokshtanov [41]. Thus any further improvement to the running time of Theorem 1.1 must be preceeded by faster algorithms for these problems in terms of the number of vertices.

Theorem 1.2 states that, for every fixed ε>0\varepsilon> 0 and hereditary ϕ\phi, a deletion set of size at most (1+ε)k(1+\varepsilon)k can be found in quasipolynomial time. Both results apply to the graph itself and do not require a geometric representation. For Vertex Cover and Feedback Vertex Set on disk graphs, representation-free EPTASes were already obtained by Lokshtanov et al. [44]. Our approximation contribution for these problems is therefore the extension to broader classes.

Related Work on Approximation Algorithms

We next place our approximation result in the context of earlier work on geometric intersection graphs and excluded-induced-minor classes. We first discuss Vertex Cover, and then approximation schemes for finding large independent sets and other induced subgraphs.

Approximation of Vertex Cover on geometric graphs. The approximation literature also goes well beyond the factor-2 guarantee available on general graphs. Erlebach, Jansen, and Seidel [30] gave PTASes for weighted Vertex Cover on intersection graphs of fat objects. For axis-parallel rectangles, Bar-Yehuda, Hermelin, and Rawitz [6] obtained a (3/2+ε)(3/2+\varepsilon)-approximation, also in the weighted case. Bar-Yehuda et al. [6] also gave an EPTAS for unweighted Vertex Cover on pseudo-disk graphs. The unweighted independent-set PTAS of Chan and Har-Peled [19], combined with the transfer discussed by Har-Peled [38], yields a PTAS for Vertex Cover on pseudo-disk graphs. These results concern subclasses of string graphs.

For general string graphs, Lokshtanov et al. [45] gave a 1.9999-approximation, including a weighted version. Its original proof relied on a flawed decomposition result of Lee, as explained by Bonnet and Rzążewski [17]. Davies et al. [22 Theorem 1.4 and Section 8] repair the required decomposition theorems for string graphs, without requiring a representation, thereby restoring the weighted 1.9999-approximation. The claimed extension of that argument to all fixed excluded-induced-minor classes remains unresolved. Bonnet and Rzążewski [17] obtained an 11/6-approximation for unweighted Vertex Cover in time polynomial in the size of a supplied string representation, as well as a representation-free polynomial-time 11/6 gap-decision algorithm. Thus the representation model and the distinction between producing a cover and solving a gap-decision problem must be kept explicit. These polynomial-time constant-factor results complement the quasipolynomial-time schemes discussed next.

QPTASes for geometric packing and retained subgraphs. The QPTAS of Adamaszek and Wiese [2] for maximum-weight independent set of axis-parallel rectangles initiated a line of geometric approximation schemes. Adamaszek, Har-Peled, and Wiese [1] extended this approach to polygons and to finding large sparse induced subgraphs of their intersection graphs. Pilipczuk, van Leeuwen, and Wiese [48] developed a combinatorial formulation through packing connected subgraphs of a planar host. These geometric algorithms use the corresponding representations. In a different direction, Dvořák [26] and Dvořák and Lahiri [28] obtained QPTASes for weighted independent set and related problems under strongly sublinear vertex-separator assumptions. Dvořák [27] subsequently established approximation meta-theorems for monotone first-order maximization problems. For induced-minor restrictions, Bonnet et al. [15] obtained QPTASes on sCℓs\mathcal{C}_\ell-induced-minor-free graphs, for fixed s,ℓs,\ell, both for weighted independent set and for maximizing the order of a bounded-treewidth induced subgraph satisfying a fixed CMSO2_2 property closed under induced subgraphs and disjoint unions; the latter includes Maximum Induced Forest.

The recent theorem of Bonnet and Chang [14 Theorem 2] gives a deterministic QPTAS for Maximum Weight Independent Set on every hereditary class with balanced separators of size O(1+mb)O(1+m^b), for a fixed b<1b<1, where mm is the number of edges. In particular, it applies to GH\mathcal{G}_H for every fixed HH. Even though they do not state this explicitly, their approximation schemes very likely extend to the maximization version of (t,ϕ)(t,\phi)-Deletion.

In general, an approximation scheme for the maximization version of a problem does not imply an approximation scheme for the minimization version of the same problem, or vice versa. Thus the results in Theorem 1.2 and the algorithm of Bonnet and Chang are incomparable. A notable exception is for Vertex Cover, for which a QPTAS does follow from the work of Bonnet and Chang [14] by the weighted Nemhauser–Trotter reduction, in the form discussed by Har-Peled [38].

Organization. The rest of the paper is organized as follows. § 2 gives an overview of the main ideas behind our proofs and § 3 introduces the notation and preliminary tools. In § 5, we prove the sublinear-treewidth branching theorem, which is the technical core of both the subexponential FPT algorithm and the QPTAS. § 6 presents a dynamic programming algorithm for solving (t,ϕ)(t,\phi)-Deletion parameterized by treewidth. § 6.1 and § 6.2 combine these tools to prove the subexponential FPT algorithm and the QPTAS, respectively.

Technical overview

For simplicity, we overview our algorithms for the Feedback Vertex Set (FVS) problem, which is the special case of (t,ϕ)(t,\phi)-Deletion when t=1t=1 and ϕ\phi is the dummy formula. Considering this special case is already sufficient to get most of the insights in our results.

Our subexponential FPT algorithm and QPTAS share the same technical core, which we call the sublinear-treewidth branching theorem (Theorem 4.1). Essentially, this theorem allows us to “guess” in subexponential FPT time a subset XX of the unknown solution S⊆V(G)S \subseteq V(G) such that the treewidth of G−XG-X is sublinear in kk. Below is the special case of the theorem for FVS.

Sublinear-treewidth branching (STB) theorem. Given an HH-induced-minor-free graph GG with nn vertices and two parameters k,d∈Nk,d \in\mathbb{N}, one can compute in 2O~(k/d)nO(1)2^{\widetilde{O}(k/d)}n^{O(1)} time a collection X={X1,…,Xr}\mathcal{X}=\{X_1,\ldots,X_r\} of subsets of V(G)V(G), where r=2O~(k/d)r=2^{\widetilde{O}(k/d)}, such that

(i) tw⁡(G−Xi)=O(kd)\operatorname{tw}(G-X_i)=O(\sqrt{kd}) for all i∈[r]i\in[r],

(ii) every FVS of GG with size at most kk contains some X∈XX\in\mathcal{X} as a subset.

Observe that this theorem directly gives us a subexponential FPT algorithm for FVS on induced-minor-free graphs with running time 2O~(k2/3)nO(1)2^{\widetilde{O}(k^{2/3})}n^{O(1)}. Indeed, we apply the STB theorem with d=k1/3d=k^{1/3} to compute X={X1,…,Xr}\mathcal{X}=\{X_1,\ldots,X_r\} in 2O~(k2/3)nO(1)2^{\widetilde{O}(k^{2/3})}n^{O(1)} time. Then for each XiX_i, we compute a minimum FVS SiS_i of G−XiG-X_i, which can be done in 2O~(kd)nO(1)=2O~(k2/3)nO(1)2^{\widetilde{O}(\sqrt{kd})}n^{O(1)}=2^{\widetilde{O}(k^{2/3})}n^{O(1)} time by standard DP on bounded-treewidth graphs. By property (ii) above, there exists Xi∈XX_i\in\mathcal{X} that is contained in some FVS of size at most kk. Thus, Xi∪SiX_i\cup S_i is also an FVS of size at most kk, a solution we want.

References

  1. [1]Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independent set and sparse subsets of polygons. Journal of the ACM, 66(4):29:1–29:40, 2019. 5arxiv.org/abs/1703.04758
  2. [2]Anna Adamaszek and Andreas Wiese. Approximation schemes for maximum weight independent set of rectangles. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 400–409, 2013. 5arxiv.org/abs/1307.1774
  3. [3]Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237(1–2):123–134, 2000. 2DOI
  4. [4]Shinwoo An, Kyungjin Cho, and Eunjin Oh. Faster algorithms for cycle hitting problems on disk graphs. In Algorithms and Data Structures (WADS 2023), volume 14079 of Lecture Notes in Computer Science, pages 29–42. Springer, 2023. 2, 4, 5arxiv.org/abs/2311.03665
  5. [5]Shinwoo An and Eunjin Oh. Feedback vertex set on geometric intersection graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021), volume 212 of Leibniz International Proceedings in Informatics (LIPIcs), pages 47:1–47:12, 2021. 2arxiv.org/abs/2107.03861
  6. [6]Reuven Bar-Yehuda, Danny Hermelin, and Dror Rawitz. Minimum vertex cover in rectangle graphs. Computational Geometry, 44(6–7):356–364, 2011. 4, 5
  7. [7]Julien Baste and Dimitrios M. Thilikos. Contraction bidimensionality of geometric intersection graphs. Algorithmica, 84(2):510–531, 2022. 2
  8. [8]Gaëtan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Feedback vertex set for pseudo-disk graphs in subexponential FPT time. arXiv:2410.23878v1, 2024. Full version, 31 October 2024; see Theorem 3.1 and Section 6, Table 1. 2, 4, 5arxiv.org/abs/2410.23878
  9. [9]Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Subexponential algorithms in geometric graphs via the subquadratic grid minor property: The role of local radius. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, 2024. Full version: arXiv:2306.17710v3. 2, 4, 5arxiv.org/abs/2306.17710
  10. [10]Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Feedback vertex set for pseudo-disk graphs in subexponential FPT time. In Graph-Theoretic Concepts in Computer Science (WG 2024), volume 14760 of Lecture Notes in Computer Science, pages 65–78. Springer, 2025. 2, 5arxiv.org/abs/2410.23878
  11. [11]Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Pushing the frontiers of subexponential FPT time for Feedback Vertex Set. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 26:1–26:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. Full version: arXiv:2504.17708v2, January 2026. 2, 4, 5arxiv.org/abs/2504.17708
  12. [12]Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317, 1996. 26
  13. [14]Édouard Bonnet and Yeonsu Chang. QPTAS for max weight independent set in graphs with strongly edge-sublinear separators, 2026. arXiv:2610.16025. 5, 6arxiv.org/abs/2610.16025
  14. [15]Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, and Paweł Rzążewski. QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026), volume 370 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:14, 2026. 5
  15. [16]Édouard Bonnet and Paweł Rzążewski. Optimality program in segment and string graphs. Algorithmica, 81(7):3047–3073, 2019. 4
  16. [17]Édouard Bonnet and Paweł Rzążewski. An 11/6-approximation algorithm for Vertex Cover on string graphs. In 41st International Symposium on Computational Geometry (SoCG 2025), volume 332 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:15, 2025. 5arxiv.org/abs/2409.18820
  17. [18]Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret, Robin Petit, Jean-Florent Raymond, and Eileen Robinson. An improved bound on the treewidth of planar graphs excluding a grid minor, 2026. arXiv:2609.15596v1. 3arxiv.org/abs/2609.15596
  18. [19]Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373–392, 2012. 5
  19. [20]Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Information and Computation, 85(1):12–75, 1990. 25, 26DOI
  20. [21]Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, volume 138 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2012. 25, 26
  21. [22]James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, and Bartosz Walczak. Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs, 2026. arXiv:2610.23792. To appear in SODA 2027. 2, 5, 16arxiv.org/abs/2610.23792
  22. [23]Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom 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 Computing (STOC), pages 574–586, 2018. 2
  23. [24]Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. Journal of the ACM, 52(6):866–893, 2005. 2, 6
  24. [25]Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. The Computer Journal, 51(3):292–302, 2008. 2, 6DOI
  25. [26]Zdeněk Dvořák. On classes of graphs with strongly sublinear separators. European Journal of Combinatorics, 71:1–11, 2018. 5arxiv.org/abs/1710.03117
  26. [27]Zdeněk Dvořák. Approximation theorems for classes with bounded expansion. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022), volume 227 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:17, 2022. 5arxiv.org/abs/2103.08698
  27. [28]Zdeněk Dvořák and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs. In 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1–40:10, 2021. 5arxiv.org/abs/2105.01780
  28. [29]Zdeněk Dvořák and Sergey Norin. Treewidth of graphs with balanced separations. Journal of Combinatorial Theory, Series B, 137:137–144, 2019. 16arxiv.org/abs/1408.3869
  29. [30]Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing, 34(6):1302–1323, 2005. 4DOI
  30. [31]Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing, 38(2):629–657, 2008. 30
  31. [32]Fedor V. Fomin, Daniel Lokshтанov, Neeldhara Misra, and Saket Saurabh. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pages 470–479, 2012. 3arxiv.org/abs/1204.4230
  32. [33]Fedor V. Fomin, Daniel Lokshтанov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, hitting and packing cycles in subexponential time on unit disk graphs. Discrete & Computational Geometry, 62(4):879–911, 2019. Preliminary version in ICALP 2017. 2arxiv.org/abs/1704.07279
  33. [34]Fedor V. Fomin, Daniel Lokshтанov, Venkatesh Raman, and Saket Saurabh. Bidimensionality and EPTAS. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 748–759, 2011. 2, 6arxiv.org/abs/1005.5449
  34. [35]Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. Bidimensionality and geometric graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1563–1575, 2012. 2
  35. [36]Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. SIAM Journal on Computing, 49(6):1397–1422, 2020. 2, 6
  36. [37]Anupam Gupta, Eujiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk. Losing treewidth by separating subsets. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1731–1749, 2019. 4, 15arxiv.org/abs/1804.01366
  37. [38]Sariel Har-Peled. Approximately: Independence implies vertex cover, 2023. arXiv:2308.00840; version 3, 2026. 5, 6
  38. [39]Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2), 2015. 3
  39. [40]Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 184–192, 2021. 11, 14, 27arxiv.org/abs/2104.07463
  40. [41]Tuukka Korhonen and Daniel Lokshtanov. Induced-minor-free graphs: Separator theorem, subexponential algorithms, and improved hardness of recognition. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5249–5275. SIAM, 2024. 2, 3, 4, 7, 10, 16, 17, 18, 38arxiv.org/abs/2308.04795
  41. [42]James R. Lee. Separators in region intersection graphs. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:8, 2017. 2arxiv.org/abs/1608.01612
  42. [43]Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Subexponential parameterized algorithms on disk graphs (extended abstract). In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2005–2031, 2022. 2DOI
  43. [44]Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A framework for approximation schemes on disk graphs. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2228–2241, 2023. 2, 4arxiv.org/abs/2211.02717
  44. [45]Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. A 1.999-approximation algorithm for Vertex Cover on string graphs. In 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of Leibniz International Proceedings in Informatics (LIPIcs), pages 72:1–72:11, 2024. 5
  45. [46]Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Subexponential parameterized algorithms for hitting subgraphs. In Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC), pages 1975–1984, 2025. 2arxiv.org/abs/2409.04786
  46. [47]Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, and Meirav Zehavi. Fine-grained bounds for courcelle’s theorem. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 2254–2265, 2026. 25
  47. [48]Michał Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs. Algorithmica, 82(6):1703–1739, 2020.
  48. [49]Neil Robertson and Paul D. Seymour. Graph minors. V. excluding a planar graph. Journal of Combinatorial Theory, Series B, 41(1):92–114, 1986.DOI
  49. [50]Neil Robertson and Paul D. Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004.DOI
  50. [51]Andrew Thomason. The extremal function for complete minors. Journal of Combinatorial Theory, Series B, 81(2):318–338, 2001.DOI
  51. [52]Michał Wlodarczyk. Losing treewidth in the presence of weights. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3743–3761, 2025.arxiv.org/abs/2410.06343

Paper details

vlnc:W_qc9drs63
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents