CS Paper Radar

Revisiting separators in string graphs, region intersection graphs, and induced-minor-free graphs

James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak

cs.CG math.COcs.DMmath.MG ·submitted 2026-10-16 17:20 UTC · v1
top venuetheoryhighly cited

Abstract

String graphs are intersection graphs of continuous curves in the plane. In 2010, Fox and Pach proved that string graphs with $m$ edges admit balanced vertex separators of size $\mathcal{O}(m^{3/4}\sqrt{\log m})$ and conjectured that this bound can be improved to $\mathcal{O}(\sqrt{m})$, which would be optimal. After partial progress, Lee claimed in 2017 to prove this conjecture, and more generally to prove analogous separator theorems for region intersection graphs over minor-closed graph families. A key intermediate step in Lee's approach was a padded decomposition scheme for region intersection graphs. In 2024, Korhonen and Lokshtanov extended Lee's approach to the broader setting of graph classes excluding a fixed graph as an induced minor. These results have since found applications in a wide range of works. Later in 2024, a flaw was discovered in the construction of Lee's padded decomposition scheme, invalidating Lee's as well as Korhonen and Lokshtanov's separator results, and many works relying on them. In this work, we prove that string graphs with $m$ edges admit balanced separators of size $\mathcal{O}(\sqrt{m})$, and more generally obtain analogous $\mathcal{O}(\sqrt{m})$ bounds for region intersection graphs over fixed minor-closed graph families and for graphs excluding a fixed graph as an induced minor, thereby repairing the vast majority of the affected works. Furthermore, our balanced separators can be found in polynomial time. Our proof uses a different approach from Lee's and does not rely on padded decompositions. Since padded decompositions have also found applications independent of the separator theorems, particularly for string graphs, we also prove a padded decomposition result for region intersection graphs that is optimal for string graphs. We have formalized both the balanced separator and the padded decomposition results in Lean 4 with mathlib.

Comment
To appear at SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Induced-Minor-Free Graphs Admit a Star-Based Separator of Size $\tilde{O}(\sqrt{n})$

cs.DS math.CO ·2026-11-08 ·Arnold Filtser, Nikolai Karol, Hung Le, Florian Lehner
theory similarity 0.71
Abstract

Given an $H$-induced-minor-free graph $G$ with $n$ vertices, we construct a balanced separator of $G$ consisting of $\tilde{O}(|V(H)|\sqrt{n})$ star subgraphs. Our result is an induced-minor-free analog of the famous separator theorem for $H$-minor-free graphs by Alon, Seymour, and Thomas [J. Amer. Math. Soc., 1990]. A key idea in our construction is a new decomposition of $H$-induced-minor-free graphs, analogous to the cop decomposition for $H$-minor-free graphs by Andreae [J. Combin. Theory Ser. B, 1986]. We also discuss several algorithmic applications of our result.

0.12

QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators

cs.DS cs.DMcs.LOmath.CO ·2026-10-12 ·Édouard Bonnet, Yeonsu Chang
theoryhighly cited similarity 0.67
Abstract · 23 pages

A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding specific induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].

0.45

$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$

cs.DM math.CO ·2026-10-31 ·Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
theory similarity 0.67
Abstract

We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\sqrt{n})$ for any parameter $h \in \mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

0.49

Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized Leader

cs.DS ·2026-11-03 ·Hung Le, Jack Spalding-Jamieson
similarity 0.66
Abstract · 34 pages, 4 figures

We give a new algorithm for finding balanced separators in minor-free and induced-minor-free graphs. A key technical idea is a new connection to online learning: we formulate a continuous, non-convex optimization problem and solve it using the Follow the Regularized Leader (FTRL) framework. Our implementation of each FTRL step yields a purely combinatorial algorithm that assigns and adjusts vertex weights over multiple rounds. For graphs with $n$ vertices and $m$ edges, we obtain the following results. (1) For $H$-induced-minor-free graphs, we find a balanced separator of size $O(\log(|V(H)|)\sqrt{|V(H)|+|E(H)|}\sqrt{m})$ in expected linear time for fixed $H$. As a corollary, we find balanced separators of size $O(\sqrt{m})$ in string graphs in expected linear time, without requiring string representations. (2) For $K_h$-minor-free graphs, we find a balanced separator of size $O(h\log h\sqrt{n})$ in expected linear time for fixed $h$. Our algorithm unifies two long lines of work on separators in minor-free graphs, dating back to Alon, Seymour, and Thomas (1990): one optimizing separator size and the other optimizing running time. It also gives a natural interpretation of the vertex weighting scheme in a recent linear-time algorithm by Bonnet, Korhonen, Le, Li, and Masarik (2026). The separator bounds for both graph classes are flow-optimal: techniques based on flow-cut duality, including ours, cannot yield balanced separators of asymptotically smaller size.

0.52

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

cs.DS cs.DM ·2026-11-06 ·Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
similarity 0.65
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 $H$, fixed nonnegative integer $t$, and fixed monadic second-order formula $φ$, we consider the problem of finding a minimum-cardinality set $S$ such that $G-S$ has treewidth at most $t$ 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 $2^{k^{2/3} \log^{O(1)} k}n^{O(1)}$ on $H$-induced-minor-free graphs, where $k$ 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+\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.

0.20

Local Important Separators with Applications to Unbreakable Decomposition and Multicut

cs.DS ·2026-10-28 ·Aditya Anand, Euiwoong Lee, Yaowei Long, Thatchaphol Saranurak
top venue similarity 0.64
Abstract · To appear in SODA 2027

We present the first local FPT algorithm for finding important separators: Given an undirected graph $G$ with $n$ vertices and $m$ edges, vertices $s,t$ and parameters $k$ and $ν$, we can enumerate all $s$-$t$ important separators of size at most $k$ and volume at most $ν$ in time $\tilde{O}(ν2^{O(k)})$. Known approaches spend either $Ω(m)$ time (not local) or $ν^{Ω(k)}$ time (not FPT). Using this local algorithm, we show the following applications. (1) The first is an improved construction of unbreakable decomposition, a powerful generalization of tree decompositions. For any $k$, we can compute a $(5k,k)$-unbreakable decomposition with adhesion $4k$ in $\tilde{O}(k^{O(k)}m)$ time. This strictly subsumes the result of Anand, Lee, Li, Long, and Saranurak (SODA 2025) and is faster than the recent $O(k^{O(k^2)}m)$-time algorithm by Korhonen (STOC 2025) when $k = ω\Bigl(\sqrt{\frac{\log \log n}{\log \log \log n}}\Bigr)$. Our algorithm is also simpler than that of Korhonen (STOC 2025). (2) We give a near-linear time algorithm for single-sink important separators. For any sink $t$, we can list all $v$-$t$ important separators of size at most $k$ across all $v \in V(G)$ in time $\tilde{O}(2^{O(k)}m)$. Known approaches trivially compute $v$-$t$ important separators for each $v$, taking $Ω(4^k k mn)$ time. (3) Using the above result on single-sink important separators, we speed up undirected shadow removal and give the first almost-linear time FPT algorithm for Edge Multicut.

0.71

Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation

cs.DM ·2026-10-07 ·Anand Babu N B, Ashwin Jacob, Manjusha M S, Renjith P
similarity 0.62
Abstract · Submitted to CALDAM 2027

A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O(n^4)$ time algorithm for split graphs on $n$ vertices. We note that this is in contrast to Roman, Italian, and perfect Roman domination, which are NP-complete on split graphs. We further show that this tractability boundary is tight: PID is NP-hard on graphs at deletion distance one from split graphs. We also provide dichotomy results for PID on restricted extensions of split graphs formed by attaching pendant stars, and establish inapproximability results for the same.

0.09

An approximate cactus-decomposition for vertex-connectivity

cs.DM math.CO ·2026-11-01 ·Romain Bourneuf, Johannes Carmesin, Jan Kurkofka, Tim Planken
theory similarity 0.61
Abstract

The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus. For vertex-separations, Tutte's theorem gives an exact cactus-decomposition for connectivity $2$, but exact cactus-decompositions fail for higher connectivity. Extending earlier approximate cactus-decomposition results for connectivities $3$ and $4$ by Carmesin and Kurkofka [FOCS 2023] and Kurkofka and Planken [SODA 2026] to all connectivities, we prove that for every $k\in\mathbb{N}$ there is a constant $d=d(k)$ such that every $k$-connected graph $G$ admits a cactus-decomposition displaying $k$-separations such that every $k$-separation of $G$ has edit-distance at most $d$ to a displayed separation. Our proof develops tools that may be useful beyond this result. The first is a three-dimensional version of the classical corner-diagram method, which we use to show that triples of crossing $k$-separations have a controlled two-dimensional behaviour. The second is a covering-space approach for studying local crossing patterns from a global perspective. Third, we advance the theory of flowers, which originated in matroid theory.

0.30