Finding small separators in linear time via treewidth reduction

1 Introduction

• Preserving small minimal s-t separators in a bounded-treewidth graph lets standard techniques find separators with MSO-expressible constraints.The paper describes a construction that preserves minimal separators of size at most k while bounding treewidth by a function of k.Source: §1 · pp. 1–2

1.1 Results

• Stable cuts and multicut variants with hereditary constraints are linear-time solvable for fixed k, including multicut parameterized by k and the number of terminal pairs.The results also cover multicut-uncut, which requires separating specified pairs while keeping other pairs connected.Source: §1.1 · p. 2
• Connected s-t cuts are linear-time FPT even though connectivity is not hereditary and solutions need not be minimal separators.The paper extends the framework with problem-specific ideas related to connectivity.Source: §1.1 · p. 2
• The framework also handles edge-induced vertex cuts and variants that mix edge and vertex deletions or impose color-specific deletion requirements.The edge-induced vertex cut result answers an open problem posed in 2007.Source: §1.1 · pp. 2–3
• Stable and exact stable bipartization, hereditary-class bipartization, and a corresponding edge-deletion variant receive almost-linear-time or FPT algorithms.The stable and exact stable bipartization results answer open questions posed by Fernau and Díaz et al..Source: §1.1 · p. 3
• Bipartite contraction is almost-linear-time FPT as a corollary of the results on hereditary-class edge bipartization.Earlier work established FPT for bipartite contraction using a problem-specific algorithm [38].Source: §1.1 · p. 3
• The paper proves almost-linear-time FPT for (H,C,≤K)-coloring when H\C consists of two adjacent loopless vertices.The result removes one roadblock toward a full dichotomy for this coloring family.Source: §1.1 · p. 3

2.1 Treewidth, brambles, and monadic second order logic

• Treewidth equals bramble number minus one, and brambles support the paper’s upper-bound proofs; Courcelle’s theorem gives linear-time recognition of MSO-definable properties on bounded-treewidth graphs.The recognition time is fφ(tw(G))·(|E(G)|+|V(G)|) for a formula φ.Source: §2.1 · p. 4

2.2 Separators

• A nested chain of minimum s-t cuts covers every minimum separator, and an O(ℓ(|V(G)|+|E(G)|))-time algorithm outputs the chain’s successive differences.The full chain may have quadratic total size, but its differences contain the information needed.Source: §2.2 · p. 5

2.3 Torso

• Torsos preserve separators contained in their vertex sets; adjoining components lets treewidth bounds combine, while adding X vertices raises torso treewidth by at most |X|.For the component-combination bound, the resulting treewidth is at most w1+w2+1.Source: §2.3 · pp. 6–8

2.4 Treewidth bound for minimal s−t separators

• For minimum separator size ℓ and excess e, an f(ℓ,e)(|E|+|V|)-time algorithm finds a set covering all minimal separators of size ≤ℓ+e, with torso bramble number at most g(ℓ,e).Only inclusionwise minimal separators are covered; every vertex other than s and t belongs to some separator of excess 1.Source: §2.4 · p. 8
• For each component R of G\C0, bn(torso(G[R], C′∩R)) ≤ 32ℓ·g(k,e−1); thus bn(torso(G,C′)) ≤ 2ℓ + 32ℓ·g(k,e−1), with bn(torso(G,C0)) ≤ 2ℓ.Source: §2.4 · p. 10
• The treewidth bound has exponential dependence on separator size and excess, and hypercube examples show this dependence must be exponential.The recurrence for g(ℓ,e) yields g(ℓ,e) = 2^O(eℓ); for the n-dimensional hypercube, the resulting lower bound is Ω(2^n/√n).Source: §2.4 · p. 11
• The torso approach can add edges that alter separator-induced structure, so the construction subdivides each new edge using k + 1 copies to preserve the original induced graph.This lets bounded-treewidth methods handle additional requirements on the graph induced by a separator.Source: §2.4 · pp. 11–12
• For fixed k and |T|, a linear-time algorithm constructs a graph of treewidth bounded by h(k,|T|) that preserves the relevant minimal s-t separators.For every s,t in T, separators of size at most k in the constructed graph correspond exactly to those in G whose vertices lie in C ∪ T, where C contains vertices participating in such separators; the induced graph on C ∪ T is unchanged.Source: §2.4 · pp. 11–12

3.1 Hereditary graph classes

• For a decidable hereditary graph class G, G-MINCUT is linear-time solvable for every fixed k, including the minimum stable s-t cut problem.The framework handles constraints on the induced graph of the separator; the at-most-k condition matters because the approach does not apply to separators of exactly k vertices.Source: §3.1 · pp. 12–13

3.2 Edge-induced vertex cuts

• EDGE-INDUCED VERTEX-CUT is linear-time solvable for every fixed k, answering an open question.The reduction relates a separator coverable by k edges to G_k-MINCUT with parameter 2k, where G_k contains graphs whose vertex count minus maximum matching size is at most k.Source: §3.2 · pp. 13–14

3.3 Connected vertex cuts

• A connected s-t separator of size at most k can be found in linear-time FPT, although connectedness is not hereditary and solutions need not be minimal separators.The method enlarges the candidate set so a minimal separator can be extended to a connected solution, then checks the condition on a bounded-treewidth torso using monadic second-order logic.Source: §3.3 · pp. 14–15

3.4 Multicut problems

• SET-MULTICUT is not a trivial extension of ordinary MULTICUT: replacing each vertex-set pair by added terminal vertices can fail even for two pairs.The section handles set pairs through adapted torso arguments, and Theorem 3.8 also gives a criterion for identifying vertices that occur in minimal small s-t separators.Source: §3.4 · pp. 15–18
• For decidable hereditary G, G-MULTICUT-UNCUT is linear-time FPT parameterized by k and ℓ.The approach builds a bounded-treewidth torso from candidate separators for the ℓ′ pairs that must be separated; the treewidth bound does not depend on the number ℓ of pairs required to remain unseparated.Source: §3.4 · pp. 16, 18

4 Constrained Bipartization Problems

• G-BIPARTIZATION is almost linear-time FPT for hereditary, decidable graph classes, using a known bipartization solution and a reduction of compatible solutions to an s-t separation problem.The reduction permits the deleted set to induce a graph in the specified class.Source: §4 · pp. 18–19
• Independent bipartization is almost linear-time FPT for both deletion sets of size at most k and exactly k.For the exact-size variant, a smaller independent solution can be extended under the algorithm’s cycle-based conditions; finding an exact-size independent s-t separator is W[1]-hard.Source: §4 · pp. 19–21

4.1 Edge bipartization

• If the graph class is decidable and closed under subgraphs, G-EDGEBIPARTIZATION is almost linear-time FPT by reduction to constrained vertex bipartization.The reduction encodes edge deletion as a vertex-deletion instance over a finite hereditary class.Source: §4.1 · pp. 21–22

4.2 Bipartite contraction

• BIPARTITE CONTRACTION is equivalent to edge deletion of a subgraph whose rank is at most k, yielding an almost-linear-time FPT algorithm.The equivalence translates a contraction solution into a bipartization edge set with rank at most k, and conversely uses a spanning forest for contraction.Source: §4.2 · pp. 23–24

• The cardinality-constrained coloring framework includes problems such as BIPARTIZATION, and the result covers the case where H\C is a single edge without loops.The paper notes that this case includes BIPARTIZATION and STABLE BIPARTIZATION; a full dichotomy for exact (H,C,K)-coloring would require resolving BICLIQUE’s open parameterized complexity.Source: §5 · pp. 24–25
• List (H,C,≤K)-coloring is almost linear-time FPT for fixed H when H\C is a single loopless edge.Source: §5 · p. 25
• The reduction preserves exceptional sets of all minimal colorings, because a solution need not have an inclusionwise minimal bipartization set.Every solvable instance has a minimal coloring under the paper’s definition, which minimizes the exceptional set by inclusion.Source: §5 · p. 25
• For nonbipartite G, the method finds at most k vertices whose removal makes G bipartite, branches on their colors, and updates neighboring lists and bounds.Source: §5 · pp. 26–27
• For bipartite G, the algorithm finds C′′ containing every minimal coloring’s exceptional set, with torso treewidth bounded by a function of k and |V(H)|.The proof uses induction on k, separating X from Y and applying the induction hypothesis to components with updated lists and reduced cardinality bounds.Source: §5 · pp. 26–27
• After treewidth reduction, each component outside C′′ is replaced by two adjacent vertices representing its bipartition, preserving the coloring instance while keeping treewidth bounded.The reduced instance is then solved in linear time on bounded-treewidth graphs using Courcelle’s Theorem.Source: §5 · p. 27

• Treewidth reduction gives linear-time algorithms for restricted separation problems for each fixed separator bound, with applications to constrained bipartization and homomorphism problems.The paper links separator and bipartization problems and cites MINIMUM STABLE s-t CUT as an example whose parameterized complexity had been open.Source: §6 · p. 28
• An exponential treewidth bound in k means the resulting algorithms typically have at least double-exponential dependence on k.Source: §6 · p. 28
• The technique extends to certain nonhereditary restrictions, including CONNECTED s-t CUT, but further extensions remain an open direction.Source: §6 · p. 28
• Open directions include global balance requirements, directed graphs, broader MULTICUT results, and complexity dichotomies for cardinality-constrained coloring.For exact (H,C,K)-coloring, a dichotomy would require first understanding the parameterized complexity of BICLIQUE.Source: §6 · p. 28

• The separation predicate uses a path test: every set of vertices connecting s to t must intersect the chosen separator.The construction builds on ideas from and uses a unary relation labeling s and t.Source: §A.1 · p. 33
• The size predicate rules out k + 1 mutually distinct elements, while the induced-graph predicate checks whether the chosen set matches one of the permitted graphs.Source: §A.1 · p. 33
• The formula’s three conditions check that the chosen set has size at most k, separates s and t, and induces a graph in the required class.Source: §A.1 · p. 33
• The proof establishes both directions: a valid separator satisfies the formula, and any set satisfying the formula is a valid separator of size at most k.Source: §A.1 · pp. 33–34

A.2 MSO formula in the proof of Lemma 5.5

• The formula expresses that V1,...,Vr partition V(G) and tests whether A is a subset of B.Source: §A.2 · p. 34
• The constructed formula holds exactly when the instance has an (H,C,≤K)-coloring, with color classes represented by vertex sets V1,...,Vr.The coloring assigns v to xi exactly when v belongs to Vi.Source: §A.2 · p. 34
• The formula’s length depends only on k and H.Source: §A.2 · p. 34