CS Paper Radar

Local Important Separators with Applications to Unbreakable Decomposition and Multicut

Aditya Anand, Euiwoong Lee, Yaowei Long, Thatchaphol Saranurak

cs.DS ·submitted 2026-10-28 23:02 UTC · v1
top venue

Abstract

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.

Comment
To appear in SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection

cs.DS ·2026-11-05 ·Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki
similarity 0.72
Abstract

The Minimum Bisection problem asks whether an $n$-vertex graph can be split into two halves with at most $k$ edges between them. We give a single exponential time algorithm for minimum bisection, running in time $2^{O(k)}n^{O(1)}$. This improves the previous bound of $2^{O(k\log k)}n^{O(1)}$ due to Cygan, Komosa, Lokshtanov, Pilipczuk, Pilipczuk, Saurabh, and Wahlström (TALG 2021). Our algorithm counts solutions instead of only finding if one exists. We show that our dynamic program can be implemented on top of an unbreakable decomposition using algebraic techniques. Along the way, we compute in time $2^{O(k)}n^{O(1)}$ a tree decomposition with adhesions of size at most $2k$ whose bags are $(3k,k)$-edge-unbreakable inside their own subtrees.

0.19

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

Important Cuts with Logical Constraints: A Meta-Theorem for Eulerian Digraphs

cs.DS ·2026-11-14 ·Václav Blažej, Satyabrata Jana, Jędrzej Olkowski, M. S. Ramanujan, Peter Strulo
top venuetheory similarity 0.68
Abstract · To appear at SODA 2027

Important separators are a standard tool in parameterized cut algorithms. An $S$-$T$ separator is important if it is inclusion-wise minimal and no separator of at most the same size leaves a strict superset of the vertices reachable from $S$ after deletion. Their use relies on a boundedness theorem: for fixed $k$, the number of important $S$-$T$ separators of size at most $k$ is at most a constant ($4^k$ to be precise) independent of the input size, even in directed graphs, and they can be enumerated efficiently. The classical theory, however, controls only the size of the separator, not the structure of the source side cut off by it. Once the source side is required to satisfy a condition such as acyclicity, bipartiteness, or another logical property, the corresponding maximal source sides can be unbounded in general digraphs. This obstruction is fundamentally related to hardness phenomena in directed deletion problems such as Directed Odd Cycle Transversal}. Prior to this work, even in undirected graphs, boundedness of such maximal constrained source sides was known only in more specialized settings, not at the level of generality considered in our work.

0.64

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

Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition

cs.DS ·2026-11-04 ·Soh Kumabe
similarity 0.66
Abstract

Minimum Bisection asks whether the vertices of a graph can be partitioned into two parts whose sizes differ by at most one and with at most k edges between the two parts. Cygan, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saurabh (SICOMP 2019) gave the first fixed-parameter algorithm, which runs in O*(2^(O(k^3))) time, by introducing an unbreakable decomposition. Cygan, Komosa, Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saurabh, and Wahlström (TALG 2021) strengthened the decomposition and improved the running time to O*(2^(O(k log k))). However, whether the running time could be improved to single-exponential remained open. In this paper, we give a deterministic O*(2^(O(k)))-time algorithm for Minimum Bisection. Our algorithm also counts all feasible bisections. To obtain an O*(2^(O(k)))-time algorithm, we introduce two new techniques. First, we give a new algorithm that computes a (2k,k)-edge-unbreakable decomposition with adhesion at most 2k in O*(2^(O(k))) time by relaxing the unbreakability and adhesion guarantees of the decomposition in (TALG 2021). Second, we improve the running time of the dynamic program over the decomposition from O*(2^(O(k log k))) to O*(2^(O(k))) using important cuts, inclusion-exclusion, and formal logarithms and exponentials. Together with color coding, the same techniques give a deterministic O*(2^(O(k)))-time algorithm for Matching Cut, which asks for a cut whose crossing edges form a matching. This improves the O*(2^(O(k log k)))-time algorithm of Aravind and Saxena (IWOCA 2021).

0.46

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

Claw-Free and Line Graph Edge Deletion on Block Graphs

cs.DS cs.DMmath.CO ·2026-10-14 ·Rajat Adak
hot direction similarity 0.65
Abstract

Edge deletion problems ask for the fewest edges whose deletion gives a graph with a specified property. We study two such problems on block graphs. First making the graph claw-free, and second making it a line graph. Since every line graph is claw-free, the second problem is at least as difficult as the first. We show that on block graphs the two optimum values are always equal, and both are attained by the line graph of a forest. The main step is a completion argument, in which starting from any claw-free solution, we put back edges to get some nice structure inside each block still maintaining the claw-free property. This reduces both edge-deletion problems to the same problem of selecting vertices within the blocks of the input graph. We solve it by dynamic programming in $O(n+m)$ time, which also produces an optimal deletion set and a forest whose line graph is what remains after the completion argument. We also extend the method to $K_{1,r+1}$-free edge deletion for every fixed $r$.

0.26

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

cs.CG math.COcs.DMmath.MG ·2026-10-16 ·James Davies, Paweł Rzążewski, Jack Spalding-Jamieson, Bartosz Walczak
top venuetheoryhighly cited similarity 0.64
Abstract · To appear at SODA 2027

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.

0.70