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 k k k is about 2 O ( k ) 2^{O(\sqrt{k})} 2 O ( 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 2 O ( k log k ) n O ( 1 ) 2^{O(\sqrt{k\log k})}n^{O(1)} 2 O ( k l o g k ) n O ( 1 ) algorithm, and An and Oh [5 ] improved this to 2 O ( k ) ( n + m ) 2^{O(\sqrt{k})}(n+m) 2 O ( 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 s s s -string graphs for fixed s s s . 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 H H H , let G H \mathcal{G}_H G H denote the class of H H H -induced-minor-free graphs. Every string graph excludes the graph obtained by subdividing each edge of K 5 K_5 K 5 once as an induced minor [41 ] . Thus, an algorithmic theorem for every fixed H H H applies, in particular, to all string graphs. Figure 1 summarizes the graph classes covered by this 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 H H H for H H H -minor-free graphs, and the once-subdivided K 5 K_5 K 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 G H \mathcal{G}_H G H with m m m edges have balanced separators of size O H ( m ) O_H(\sqrt{m}) O H ( 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 2 O ~ ( n 2 / 3 ) 2^{\widetilde{O}(n^{2/3})} 2 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 t t t 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 t t t and satisfies ϕ \phi ϕ . This formulation includes Vertex Cover, by requiring the remaining graph to be edgeless; Feedback Vertex Set, by taking t = 1 t = 1 t = 1 and imposing no further condition; and deletion to treewidth at most t t t . 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 ∈ N t \in\mathbb{N} t ∈ N and ϕ \phi ϕ is an MSO formula).
Table 2.
A very closely related class of problems is Planar F \mathcal{F} F -Deletion: delete vertices such that the resulting graph excludes every graph in a fixed finite family F \mathcal{F} F as a minor. The family F \mathcal{F} 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} F containing a planar graph, there exists an integer t t t and MSO formula ϕ \phi ϕ such that Planar F \mathcal{F} F -Deletion is a ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion problem. Fomin et al. [32 ] established constant-factor approximation algorithms and polynomial kernels for Planar F \mathcal{F} F -Deletion, as well as single-exponential parameterized algorithms when every graph in F \mathcal{F} 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 C H \mathcal{C}_H C H .
Our results. Our first main result is a subexponential parameterized algorithm for every ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion problem. We use k k k for the size of an optimum deletion set; the notation O ~ \widetilde{O} O suppresses polylogarithmic factors.
Theorem 1.1. Let H H H be a fixed graph, t ∈ N t \in\mathbb{N} t ∈ N be a fixed number, and ϕ \phi ϕ be a fixed MSO formula. Then ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on C H \mathcal{C}_H C H admits an algorithm that runs in 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 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) ( t , ϕ ) -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 H H H be a fixed graph, t ∈ N t \in\mathbb{N} t ∈ N be a fixed number, and ϕ \phi ϕ be a fixed hereditary MSO formula. Then ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on C H \mathcal{C}_H C H admits a quasipolynomial-time approximation scheme.
Theorem 1.1 measures the exponential part of the running time in the number k k k of deleted vertices. The size k k k of the solution is always at most the number n n n 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 2 O ~ ( n 2 / 3 ) 2^{\widetilde{O}(n^{2/3})} 2 O ( n 2/3 ) -time algorithms for a broad family of induced-subgraph problems that includes every ( t , ϕ ) (t,\phi) ( t , ϕ ) -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 k k k on classes excluding a fixed induced minor, and in particular on string graphs.
Table 1 (PDF p. 5). Selected comparisons for Feedback Vertex Set. An exponent α \alpha α denotes a bound 2 O ~ ( k α ) n O ( 1 ) 2^{\widetilde{O}(k^\alpha)}n^{O(1)} 2 O ( k α ) 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 k k k , not by n n n .
The running time dependence on k k k of Theorem 1.1 essentially matches the running time dependence on n n n 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 ε > 0 and hereditary ϕ \phi ϕ , a deletion set of size at most ( 1 + ε ) k (1+\varepsilon)k ( 1 + ε ) 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) ( 3/2 + ε ) -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 s C ℓ s\mathcal{C}_\ell s C ℓ -induced-minor-free graphs, for fixed s , ℓ s,\ell s , ℓ , both for weighted independent set and for maximizing the order of a bounded-treewidth induced subgraph satisfying a fixed CMSO2 _2 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 + m b ) O(1+m^b) O ( 1 + m b ) , for a fixed b < 1 b<1 b < 1 , where m m m is the number of edges. In particular, it applies to G H \mathcal{G}_H G H for every fixed H H H . Even though they do not state this explicitly, their approximation schemes very likely extend to the maximization version of ( t , ϕ ) (t,\phi) ( t , ϕ ) -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) ( t , ϕ ) -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) ( t , ϕ ) -Deletion when t = 1 t=1 t = 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 X X X of the unknown solution S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) such that the treewidth of G − X G-X G − X is sublinear in k k k . Below is the special case of the theorem for FVS.
Sublinear-treewidth branching (STB) theorem. Given an H H H -induced-minor-free graph G G G with n n n vertices and two parameters k , d ∈ N k,d \in\mathbb{N} k , d ∈ N , one can compute in 2 O ~ ( k / d ) n O ( 1 ) 2^{\widetilde{O}(k/d)}n^{O(1)} 2 O ( k / d ) n O ( 1 ) time a collection X = { X 1 , … , X r } \mathcal{X}=\{X_1,\ldots,X_r\} X = { X 1 , … , X r } of subsets of V ( G ) V(G) V ( G ) , where r = 2 O ~ ( k / d ) r=2^{\widetilde{O}(k/d)} r = 2 O ( k / d ) , such that
(i) tw ( G − X i ) = O ( k d ) \operatorname{tw}(G-X_i)=O(\sqrt{kd}) tw ( G − X i ) = O ( k d ) for all i ∈ [ r ] i\in[r] i ∈ [ r ] ,
(ii) every FVS of G G G with size at most k k k contains some X ∈ X X\in\mathcal{X} X ∈ 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 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) . Indeed, we apply the STB theorem with d = k 1 / 3 d=k^{1/3} d = k 1/3 to compute X = { X 1 , … , X r } \mathcal{X}=\{X_1,\ldots,X_r\} X = { X 1 , … , X r } in 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) time. Then for each X i X_i X i , we compute a minimum FVS S i S_i S i of G − X i G-X_i G − X i , which can be done in 2 O ~ ( k d ) n O ( 1 ) = 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(\sqrt{kd})}n^{O(1)}=2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k d ) n O ( 1 ) = 2 O ( k 2/3 ) n O ( 1 ) time by standard DP on bounded-treewidth graphs. By property (ii) above, there exists X i ∈ X X_i\in\mathcal{X} X i ∈ X that is contained in some FVS of size at most k k k . Thus, X i ∪ S i X_i\cup S_i X i ∪ S i is also an FVS of size at most k k k , a solution we want.
To obtain the QPTAS is slightly more difficult. The main idea is to properly combine the STB theorem with the bidimensionality technique [24 , 25 , 34 , 36 ] . First, we apply the STB theorem with d = k / log c k d=k/\log^c k d = k / log c k for a large constant c c c , which takes quasi-polynomial time. Let X = { X 1 , … , X r } \mathcal{X}=\{X_1,\ldots,X_r\} X = { X 1 , … , X r } be the collection returned and write G i = G − X i G_i=G-X_i G i = G − X i . For each i ∈ [ r ] i\in[r] i ∈ [ r ] , tw ( G i ) = k / log c / 2 k \operatorname{tw}(G_i)=k/\log^{c/2}k tw ( G i ) = k / log c /2 k . Thus, there exists a balanced separator Y i ⊆ V ( G i ) Y_i\subseteq V(G_i) Y i ⊆ V ( G i ) in the sense that every connected component of G i − Y i G_i-Y_i G i − Y i has minimum FVS size at most k / 2 k/2 k /2 . We then recursively apply the entire algorithm on each component C C C of G i − Y i G_i-Y_i G i − Y i to obtain an FVS S C S_C S C of C C C . The union of S C S_C S C ’s and Y i Y_i Y i is an FVS S i S_i S i of G i G_i G i . We do this for all i ∈ [ r ] i\in[r] i ∈ [ r ] and return the set X i ∪ S i X_i\cup S_i X i ∪ S i of the minimum size as the output. The recursion terminates when the treewidth of the current graph is bounded by f ( 1 ε ) f\left(\frac{1}{\varepsilon}\right) f ( ε 1 ) for some function f f f ; in this case, we apply the standard DP to compute a minimum FVS. A careful analysis shows that choosing f f f as an exponential function makes the returned FVS a ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) -approximation solution, and the overall time complexity is quasi-polynomial.
Proof sketch of the STB theorem
One of the key components of our proof for the STB theorem is a new structural result for H H H -induced-minor-free graphs (Corollary 4.10 ), which is of independent interest. This result bounds the treewidth of an H H H -induced-minor-free graph which admits a bounded-degeneracy FVS (or more generally, treewidth modulator) M M M such that each connected component is neighboring to a few vertices in M M M . Conventionally, for a set V ⊆ V ( G ) V\subseteq V(G) V ⊆ V ( G ) , we denote by N G ( V ) N_G(V) N G ( V ) the set of neighbors of V V V in G G G that are not contained in V V V . Below is the special case of the result for FVS.
Structural result. Let G G G be an H H H -induced-minor-free graphs. If there exists an FVS M ⊆ V ( G ) M\subseteq V(G) M ⊆ V ( G ) of G G G such that G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate and ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))|\le d ∣ N G ( V ( C )) ∣ ≤ d for every connected component C C C of G − M G-M G − M , then tw ( G ) = O ( d + Δ ⋅ ∣ M ∣ ) \operatorname{tw}(G)=O(\sqrt{d+\Delta}\cdot|M|) tw ( G ) = O ( d + Δ ⋅ ∣ M ∣ ) .
Built on the above result, our branching algorithm basically works as follows. Rather than just computing the collection X \mathcal{X} X in the STB theorem, our branching procedure computes a collection Q = { ( X 1 , M 1 ) , … , ( X r , M r ) } \mathcal{Q}=\{(X_1,M_1),\ldots,(X_r,M_r)\} Q = {( X 1 , M 1 ) , … , ( X r , M r )} of pairs of subsets of V ( G ) V(G) V ( G ) , where X = { X 1 , … , X r } \mathcal{X}=\{X_1,\ldots,X_r\} X = { X 1 , … , X r } is the desired output, and each M i M_i M i is a small FVS of G − X i G-X_i G − X i that satisfies the nice conditions in the structural result and hence witnesses the low treewidth of G − X i G-X_i G − X i , as required in (i) of the theorem. Formally, we require each M i M_i M i to satisfy the following conditions:
(a) ∣ M i ∣ = O ( k ) |M_i|=O(k) ∣ M i ∣ = O ( k ) ,
(b) G [ M i ] G[M_i] G [ M i ] is d d d -degenerate,
(c) ∣ N G − X i ( V ( C ) ) ∣ = O ( d ) |N_{G-X_i}(V(C))|=O(d) ∣ N G − X i ( V ( C )) ∣ = O ( d ) for every connected component C C C of G − ( X i ∪ M i ) G-(X_i\cup M_i) G − ( X i ∪ M i ) .
See Figure 2 for an illustration. The structural result then implies tw ( G − X i ) = O ( k d ) \operatorname{tw}(G-X_i)=O(\sqrt{kd}) tw ( G − X i ) = O ( k d ) . It turns out that condition (b) can be satisfied almost for free by adapting an algorithm of Korhonen and Lokshtanov [41 ] (Lemma 4.3). Hence, it suffices to make each M i M_i M i satisfy conditions (a) and (c).
Figure 2. Illustrating the properties of the pairs ( X i , M i ) ∈ Q (X_i,M_i)\in\mathcal{Q} ( X i , M i ) ∈ Q .
To obtain the collection Q \mathcal{Q} Q , we first compute a 2-approximation FVS M i n i t ⊆ V ( G ) M_{\mathrm{init}}\subseteq V(G) M init ⊆ V ( G ) . We have ∣ M i n i t ∣ ≤ 2 k |M_{\mathrm{init}}|\le2k ∣ M init ∣ ≤ 2 k . In the branching procedure, we maintain two disjoint sets X , M ⊆ V ( G ) X,M\subseteq V(G) X , M ⊆ V ( G ) . Initially, X = ∅ X = \emptyset X = ∅ and M = M i n i t M = M_{\mathrm{init}} M = M init . At any point of the branching, we always have the invariant X ∪ M = M i n i t X \cup M = M_{\mathrm{init}} X ∪ M = M init , which implies that M M M is an FVS of G − X G - X G − X . At (some of) the leaves of the branching, we add to Q Q Q the pair ( X i , M i ) (X_i, M_i) ( X i , M i ) where X i = X X_i = X X i = X and M i = M ∪ L M_i = M \cup L M i = M ∪ L for a properly chosen set L ⊆ V ( G ) ∖ ( X ∪ M ) L \subseteq V(G) \setminus(X \cup M) L ⊆ V ( G ) ∖ ( X ∪ M ) so that M i M_i M i satisfies conditions (a) and (c).
Consider the current sets X X X and M M M . Let F = G − ( X ∪ M ) F = G - (X \cup M) F = G − ( X ∪ M ) , which is a forest. For convenience, assume each tree of F F F is rooted, and for a vertex x ∈ V ( F ) x \in V(F) x ∈ V ( F ) contained in a tree T T T of F F F , denote by T x T_x T x the subtree of T T T rooted at x x x . We now greedily “pack” subtrees in F F F which are neighboring to more than d d d vertices in M M M . Formally, starting with T = ∅ \mathcal{T} = \emptyset T = ∅ and F 0 = F F_0 = F F 0 = F , we repeat the following procedure until no tree of F 0 F_0 F 0 has more than d d d vertices in M M M :
Find a tree T T T of F 0 F_0 F 0 with ∣ N G ( V ( T ) ) ∩ M ∣ > d \lvert N_G(V(T)) \cap M\rvert> d ∣ N G ( V ( T )) ∩ M ∣ > d ,
Find a lowest node x ∈ V ( T ) x \in V(T) x ∈ V ( T ) satisfying ∣ N G ( V ( T x ) ) ∩ M ∣ > d \lvert N_G(V(T_x)) \cap M\rvert> d ∣ N G ( V ( T x )) ∩ M ∣ > d ,
T ← T ∪ { T x } \mathcal{T} \leftarrow\mathcal{T} \cup\{T_x\} T ← T ∪ { T x } and F 0 ← F 0 − V ( T x ) F_0 \leftarrow F_0 - V(T_x) F 0 ← F 0 − V ( T x ) .
At the end, T \mathcal{T} T consists of disjoint subtrees of trees in F F F each of which has more than d d d neighbors in M M M . Let R T ⊆ V ( F ) R_{\mathcal{T}} \subseteq V(F) R T ⊆ V ( F ) consist of the roots of the trees in T \mathcal{T} T . The above packing procedure also guarantees the following good property: each connected component of F − R T F - R_{\mathcal{T}} F − R T has at most d d d neighbors in M M M . Next, we distinguish two cases: ∣ T ∣ ≤ 3 k \lvert\mathcal{T}\rvert\leq3k ∣ T ∣ ≤ 3 k and ∣ T ∣ > 3 k \lvert\mathcal{T}\rvert> 3k ∣ T ∣ > 3 k .
If ∣ T ∣ ≤ 3 k \lvert\mathcal{T}\rvert\leq3k ∣ T ∣ ≤ 3 k , then we add a pair ( X i , M i ) (X_i, M_i) ( X i , M i ) to Q Q Q and terminate the current branch. As mentioned before, we set ( X i , M i ) = ( X , M ∪ L ) (X_i, M_i) = (X, M \cup L) ( X i , M i ) = ( X , M ∪ L ) , and here L L L is defined as the LCA closure of R T R_{\mathcal{T}} R T in the trees in F F F . We have ∣ L ∣ ≤ 2 ∣ R T ∣ = 2 ∣ T ∣ = O ( k ) \lvert L\rvert\leq2\lvert R_{\mathcal{T}}\rvert= 2\lvert\mathcal{T}\rvert= O(k) ∣ L ∣ ≤ 2 ∣ R T ∣ = 2 ∣ T ∣ = O ( k ) . Thus, condition (a) holds. Each connected components of G − ( X i ∪ M i ) = F − L G - (X_i \cup M_i) = F - L G − ( X i ∪ M i ) = F − L has at most d d d neighbors in M M M and at most two neighbors in L L L (by the property of LCA closure), which implies ∣ N G − X i ( V ( C ) ) ∣ ≤ d + 2 \lvert N_{G-X_i}(V(C))\rvert\leq d + 2 ∣ N G − X i ( V ( C ))∣ ≤ d + 2 and hence condition (c) holds.
If ∣ T ∣ > 3 k \lvert\mathcal{T}\rvert> 3k ∣ T ∣ > 3 k , we first arbitrary remove some elements from T \mathcal{T} T to make ∣ T ∣ = 3 k \lvert\mathcal{T}\rvert= 3k ∣ T ∣ = 3 k . In this case, we shall create O ( k ) O(k) O ( k ) branches as follows. Let S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) be some unknown FVS of G G G with ∣ S ∣ ≤ k \lvert S\rvert\leq k ∣ S ∣ ≤ k . Then there are at least 2 k 2k 2 k trees in T \mathcal{T} T that are disjoint from S S S , which we denote by T 1 , … , T 2 k T_1, \ldots, T_{2k} T 1 , … , T 2 k (these trees are unknown to us). Each T i T_i T i survives in G − S G-S G − S , and let p i p_i p i be the number of neighbors of T i T_i T i in M ∖ S M \setminus S M ∖ S . Since G − S G-S G − S is acyclic and ∣ M ∖ S ∣ ≤ ∣ M ∣ ≤ 2 k \lvert M \setminus S\rvert\leq\lvert M\rvert\leq2k ∣ M ∖ S ∣ ≤ ∣ M ∣ ≤ 2 k , it turns out that ∑ i = 1 2 k p i ≤ 4 k − 1 \sum_{i=1}^{2k} p_i \leq4k - 1 ∑ i = 1 2 k p i ≤ 4 k − 1 and thus p j ≤ 1 p_j \leq1 p j ≤ 1 for some j ∈ [ 2 k ] j \in[2k] j ∈ [ 2 k ] . We then guess the tree T j T_j T j in T \mathcal{T} T and guess the (at most) one neighbor v v v of T j T_j T j in M ∖ S M \setminus S M ∖ S . The number of guesses is O ( k ) O(k) O ( k ) , because T = O ( k ) \mathcal{T} = O(k) T = O ( k ) and ∣ M ∣ = O ( k ) \lvert M\rvert= O(k) ∣ M ∣ = O ( k ) . For each guess ( T j , v ) (T_j, v) ( T j , v ) , we move all neighbors of T j T_j T j in M M M except v v v from M M M to X X X , and proceed the branching procedure with the new X X X and M M M . Recall that T j T_j T j has more than d d d neighbors in M M M . It follows that the new set X X X (resp., M M M ) contains at least d d d more (resp., fewer) vertices than the old one, which is crucial when bounding the time complexity. Furthermore, note that if the guess ( T j , v ) (T_j, v) ( T j , v ) is correct, then all neighbors of T j T_j T j in M M M except v v v must be contained in S S S ; in this case, the vertices added to X X X are all in S S S and thus the corresponding branch is “correct”. Since a correct branch always exists, it turns out that our branching algorithm satisfies (ii) of the STB theorem.
To analyze the time complexity of the branching procedure, observe that the depth of the branching tree is O ( k / d ) O(k/d) O ( k / d ) . Indeed, as observed above, going from one level to the next level, there are at least d d d vertices moved from M M M to X X X . Since ∣ M i n i t ∣ ≤ 2 k \lvert M_{\mathrm{init}}\rvert\leq2k ∣ M init ∣ ≤ 2 k , there cannot be a branch with depth more than 2 k / d 2k/d 2 k / d . Since the degree of the branching tree is O ( k ) O(k) O ( k ) , the size of the branching tree is bounded by 2 O ~ ( k / d ) 2^{\widetilde{O}(k/d)} 2 O ( k / d ) , implying the 2 O ~ ( k / d ) n O ( 1 ) 2^{\widetilde{O}(k/d)} n^{O(1)} 2 O ( k / d ) n O ( 1 ) running time.
Proof sketch of the structural result
Our structural result applied in the previous section is in turn the consequence of two structural lemmas (Lemma 4.8 and Lemma 4.9 ) for induced-minor-free graphs, which are also of independent interest and might find applications in other problems as well.
To present the two lemmas, we need to introduce the Torso operation on graphs. Let G G G be a graph and M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) . We define Torso ( G , M ) \operatorname{Torso}(G,M) Torso ( G , M ) as the graph obtained from G G G by adding edges ( u , v ) (u,v) ( u , v ) for all different u , v ∈ M u,v \in M u , v ∈ M satisfying that there exists a connected component C C C of G − M G-M G − M with u , v ∈ N G ( V ( C ) ) u,v \in N_G(V(C)) u , v ∈ N G ( V ( C )) . In other words, Torso ( G , M ) \operatorname{Torso}(G,M) Torso ( G , M ) is obtained from G G G by adding edges to make N G ( V ( C ) ) ∩ M N_G(V(C)) \cap M N G ( V ( C )) ∩ M a clique for each connected component C C C of G − M G-M G − M .
Our first structural lemma (Lemma 4.8 ) essentially states that applying Torso on the complement of an independent set preserves the induced-minor-freeness of the graph.
Freeness-preserving lemma. If G G G is an H H H -induced-minor-free graph and I I I is an independent set in G G G , then Torso ( G , V ( G ) \ I ) \operatorname{Torso}(G,V(G)\backslash I) Torso ( G , V ( G ) \ I ) is H ′ H' H ′ -induced-minor-free for some H ′ H' H ′ depending on H H H .
Proof sketch. Set h = ∣ V ( H ) ∣ h=|V(H)| h = ∣ V ( H ) ∣ . Let K h ∙ K_h^{\bullet} K h ∙ denote the subdivided h h h -clique, i.e., the graph obtained from K h K_h K h by subdividing each edge once. Without loss of generality, we may assume H = K h ∙ H=K_h^{\bullet} H = K h ∙ , because every H H H -induced-minor-free graph is also K h ∙ K_h^{\bullet} K h ∙ -induced-minor-free. Let G G G be a graph and I I I be an independent set in G G G . We shall show that if G ′ = Torso ( G , V ( G ) \ I ) G'=\operatorname{Torso}(G,V(G)\backslash I) G ′ = Torso ( G , V ( G ) \ I ) contains H = K h ∙ H=K_h^{\bullet} H = K h ∙ as an induced minor, then G G G also contains H H H as an induced minor.
Write X ⊆ V ( H ) X \subseteq V(H) X ⊆ V ( H ) as the set of the h h h clique vertices of H H H and Y ⊆ V ( H ) Y \subseteq V(H) Y ⊆ V ( H ) as the set of the ( h 2 ) \binom{h}{2} ( 2 h ) subdivision vertices of H H H . Assume G ′ G' G ′ contains H H H as an induced minor. For each x ∈ V ( H ) x \in V(H) x ∈ V ( H ) , let G x ′ G'_x G x ′ be the connected subgraph of G ′ G' G ′ corresponding to the vertex x x x in the induced minor. Each vertex y ∈ Y y \in Y y ∈ Y has two neighbors a y , b y a_y,b_y a y , b y in H H H , which are both vertices in X X X . As such, we can choose G y ′ G'_y G y ′ as an induced path in G ′ G' G ′ with one endpoint adjacent to G a y ′ G'_{a_y} G a y ′ and the other endpoint adjacent to G b y ′ G'_{b_y} G b y ′ , and except this, there is no adjacency between G y ′ G'_y G y ′ and G x ′ G'_x G x ′ for any x ∈ V ( H ) \ { y } x \in V(H)\backslash\{y\} x ∈ V ( H ) \ { y } . To construct the H H H -induced-minor in G G G , we define
Ext ( V ) = V ∪ { v ∈ I : N G [ v ] ∩ V ≠ ∅ } , \operatorname{Ext}(V)=V\cup\{v\in I:N_G[v]\cap V\ne\varnothing\}, Ext ( V ) = V ∪ { v ∈ I : N G [ v ] ∩ V = ∅ } ,
for V ⊆ V ( G ) V \subseteq V(G) V ⊆ V ( G ) . For each x ∈ X x \in X x ∈ X , define P x = Ext ( V ( G x ′ ) ) P_x=\operatorname{Ext}(V(G'_x)) P x = Ext ( V ( G x ′ )) . Since G x ′ G'_x G x ′ is connected, one can verify that G [ P x ] G[P_x] G [ P x ] is also connected. Then for each y ∈ Y y \in Y y ∈ Y , define P y = Ext ( V ( G y ′ ) ) \ ( ⋃ x ∈ X P x ) P_y=\operatorname{Ext}(V(G'_y))\backslash\left(\bigcup_{x\in X}P_x\right) P y = Ext ( V ( G y ′ )) \ ( ⋃ x ∈ X P x ) . Based on our choices of G y ′ G'_y G y ′ for y ∈ Y y \in Y y ∈ Y , we manage to show that G [ P y ] G[P_y] G [ P y ] is also connected for all y ∈ Y y \in Y y ∈ Y . Furthermore, by carefully checking our construction of Ext \operatorname{Ext} Ext (as well as the choices of G y ′ G'_y G y ′ ) and exploiting the fact that I I I is an independent set in G G G , one can verify that
(i) P x ∩ P y = ∅ P_x\cap P_y=\varnothing P x ∩ P y = ∅ for all different x , y ∈ V ( H ) x,y\in V(H) x , y ∈ V ( H ) ,
(ii) P x P_x P x and P y P_y P y are adjacent in G G G iff ( x , y ) ∈ E ( H ) (x,y)\in E(H) ( x , y ) ∈ E ( H ) .
Therefore, G G G contains H H H as an induced minor, in which each vertex x ∈ V ( H ) x\in V(H) x ∈ V ( H ) corresponds to the (connected) subgraph G [ P x ] G[P_x] G [ P x ] .
Our second structural lemma (Lemma 4.9 ) bounds the increase of the number of edges after applying Torso to a “nice” vertex set of an induced-minor-free graph.
Torso-sparsity lemma. Let G G G be an H H H -induced-minor-free graph, and M ⊆ V ( G ) M\subseteq V(G) M ⊆ V ( G ) such that G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate and ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))|\le d ∣ N G ( V ( C )) ∣ ≤ d for every connected component C C C of G − M G-M G − M . Then
∣ E ( Torso ( G , M ) ) ∣ − ∣ E ( G ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . |E(\operatorname{Torso}(G,M))|-|E(G)|=O((d+\Delta)\cdot|M|). ∣ E ( Torso ( G , M )) ∣ − ∣ E ( G ) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Proof sketch. Write E ∗ = E ( Torso ( G , M ) ) \ E ( G ) E^*=E(\operatorname{Torso}(G,M))\backslash E(G) E ∗ = E ( Torso ( G , M )) \ E ( G ) and we want to show ∣ E ∗ ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*|=O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) . We shall construct a random E 0 ⊆ E ∗ E_0\subseteq E^* E 0 ⊆ E ∗ such that E [ ∣ E 0 ∣ ] = O ( ∣ M ∣ / ( d + Δ ) ) \mathbb{E}[|E_0|]=O(|M|/(d+\Delta)) E [ ∣ E 0 ∣ ] = O ( ∣ M ∣/ ( d + Δ )) and Pr [ e ∈ E 0 ] = Ω ( 1 / ( d + Δ ) 2 ) \Pr[e\in E_0]=\Omega(1/(d+\Delta)^2) Pr [ e ∈ E 0 ] = Ω ( 1/ ( d + Δ ) 2 ) for each edge e ∈ E ∗ e\in E^* e ∈ E ∗ , which will imply ∣ E ∗ ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*|=O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Since G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate, we fix an orientation of the edges of G [ M ] G[M] G [ M ] for which the out-degree of every vertex is at most Δ \Delta Δ . Denote by Γ ( v ) \Gamma(v) Γ ( v ) the set of out-neighbors of v ∈ M v\in M v ∈ M in G [ M ] G[M] G [ M ] . We first independently sample each vertex v ∈ M v \in M v ∈ M with probability p = 1 d + Δ p = \frac{1}{d+\Delta} p = d + Δ 1 , and let R ⊆ M R \subseteq M R ⊆ M consist of the sampled vertices. Take the subset I ⊆ R I \subseteq R I ⊆ R that consists of all v ∈ R v \in R v ∈ R such that Γ ( v ) ∩ R = ∅ \Gamma(v) \cap R = \varnothing Γ ( v ) ∩ R = ∅ (i.e., no out-neighbor of v v v is sampled). One can verify that I I I is an independent set in G [ M ] G[M] G [ M ] (and thus in G G G ), and Pr [ v ∈ I ] ≤ p ( 1 − p ) Δ = Θ ( p ) \Pr[v \in I] \le p(1-p)^{\Delta} = \Theta(p) Pr [ v ∈ I ] ≤ p ( 1 − p ) Δ = Θ ( p ) for all v ∈ M v \in M v ∈ M . The latter implies E [ ∣ I ∣ ] = Θ ( p ∣ M ∣ ) \mathbb{E}[|I|] = \Theta(p|M|) E [ ∣ I ∣ ] = Θ ( p ∣ M ∣ ) .
Write G ′ = G − ( M ∖ I ) G' = G - (M \setminus I) G ′ = G − ( M ∖ I ) . Let G I ′ G'_I G I ′ be the graph with V ( G I ′ ) = I V(G'_I) = I V ( G I ′ ) = I in which two vertices u , v ∈ I u,v \in I u , v ∈ I are connected by an edge if there exists a component C C C of G ′ − I G' - I G ′ − I such that N G ( V ( C ) ) ∩ I = { u , v } N_G(V(C)) \cap I = \{u,v\} N G ( V ( C )) ∩ I = { u , v } . Then we define E 0 = E ( G I ′ ) E_0 = E(G'_I) E 0 = E ( G I ′ ) . Since G G G is H H H -induced-minor-free, one can show that G I ′ G'_I G I ′ must be H H H -minor-free and thus ∣ E 0 ∣ = O ( ∣ I ∣ ) |E_0| = O(|I|) ∣ E 0 ∣ = O ( ∣ I ∣ ) , which implies E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) \mathbb{E}[|E_0|] = O(p|M|) E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) .
Consider an edge e = ( u , v ) ∈ E ∗ e = (u,v) \in E^* e = ( u , v ) ∈ E ∗ . Since e ∈ E ( Torso ( G , M ) ) e \in E(\operatorname{Torso}(G,M)) e ∈ E ( Torso ( G , M )) and e ∉ E ( G ) e \notin E(G) e ∈ / E ( G ) , there exists a connected component C C C of G − M G-M G − M such that u , v ∈ N G ( V ( C ) ) u,v \in N_G(V(C)) u , v ∈ N G ( V ( C )) . By assumption, ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))| \le d ∣ N G ( V ( C )) ∣ ≤ d . Note that e ∈ E 0 e \in E_0 e ∈ E 0 if both of the following events happen:
u , v ∈ R u,v \in R u , v ∈ R ,
z ∉ R z \notin R z ∈ / R for all z ∈ Γ ( u ) ∪ Γ ( v ) ∪ ( N G ( V ( C ) ) ∖ { u , v } ) z \in\Gamma(u) \cup\Gamma(v) \cup(N_G(V(C)) \setminus\{u,v\}) z ∈ Γ ( u ) ∪ Γ ( v ) ∪ ( N G ( V ( C )) ∖ { u , v }) .
Since ∣ Γ ( u ) ∪ Γ ( v ) ∣ ≤ 2 Δ |\Gamma(u) \cup\Gamma(v)| \le2\Delta ∣Γ ( u ) ∪ Γ ( v ) ∣ ≤ 2Δ and ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))| \le d ∣ N G ( V ( C )) ∣ ≤ d , the probability that both events happen is at least p 2 ( 1 − p ) d + 2 Δ = Ω ( p 2 ) p^2(1-p)^{d+2\Delta} = \Omega(p^2) p 2 ( 1 − p ) d + 2Δ = Ω ( p 2 ) , which implies Pr [ e ∈ E 0 ] = Ω ( p 2 ) \Pr[e \in E_0] = \Omega(p^2) Pr [ e ∈ E 0 ] = Ω ( p 2 ) . Thus, ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = Ω ( p 2 ∣ E ∗ ∣ ) \sum_{e \in E^*} \Pr[e \in E_0] = \Omega(p^2|E^*|) ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = Ω ( p 2 ∣ E ∗ ∣ ) . On the other hand, ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) \sum_{e \in E^*} \Pr[e \in E_0] = \mathbb{E}[|E_0|] = O(p|M|) ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) . It follows that ∣ M ∣ = Ω ( p ∣ E ∗ ∣ ) |M| = \Omega(p|E^*|) ∣ M ∣ = Ω ( p ∣ E ∗ ∣ ) and therefore ∣ E ∗ ∣ = O ( ∣ M ∣ / p ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*| = O(|M|/p) = O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O ( ∣ M ∣/ p ) = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Now we combine the two lemmas above to prove the structural result in § 2.1 . Let G G G be an H H H -induced-minor-free graph and M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) be an FVS of G G G such that G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate and ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))| \le d ∣ N G ( V ( C )) ∣ ≤ d for every connected component C C C of G − M G-M G − M . Write G + = Torso ( G , M ) G^+ = \operatorname{Torso}(G,M) G + = Torso ( G , M ) . Applying the torso-sparsity lemma, we have
∣ E ( G + [ M ] ) ∣ − ∣ E ( G [ M ] ) ∣ ≤ ∣ E ( G + ) ∣ − ∣ E ( G ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . |E(G^+[M])| - |E(G[M])| \le|E(G^+)| - |E(G)| = O((d+\Delta)\cdot|M|). ∣ E ( G + [ M ]) ∣ − ∣ E ( G [ M ]) ∣ ≤ ∣ E ( G + ) ∣ − ∣ E ( G ) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Note that ∣ E ( G [ M ] ) ∣ = O ( Δ ∣ M ∣ ) |E(G[M])| = O(\Delta|M|) ∣ E ( G [ M ]) ∣ = O ( Δ∣ M ∣ ) since G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate. Thus, ∣ E ( G + [ M ] ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E(G^+[M])| = O((d+\Delta)\cdot|M|) ∣ E ( G + [ M ]) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Next, we show that G + [ M ] G^+[M] G + [ M ] is H ′ H' H ′ -induced-minor-free for some H ′ H' H ′ depending on H H H . Let G ′ G' G ′ be the graph obtained from G G G by contracting each connected component of G − M G-M G − M to a single vertex. Then G ′ G' G ′ is H H H -induced-minor-free. Note that I = V ( G ′ ) ∖ M I = V(G') \setminus M I = V ( G ′ ) ∖ M is an independent set in G ′ G' G ′ . Therefore, the freeness-preserving lemma implies that Torso ( G ′ , M ) \operatorname{Torso}(G',M) Torso ( G ′ , M ) is H ′ H' H ′ -induced-minor-free for some H ′ H' H ′ . Since Torso ( G ′ , M ) − I = G + [ M ] \operatorname{Torso}(G',M) - I = G^+[M] Torso ( G ′ , M ) − I = G + [ M ] , G + [ M ] G^+[M] G + [ M ] is H ′ H' H ′ -induced-minor-free as well.
Korhonen and Lokshtanov [41 ] proved that tw ( A ) = O ( ∣ E ( A ) ∣ ) \operatorname{tw}(A) = O(\sqrt{|E(A)|}) tw ( A ) = O ( ∣ E ( A ) ∣ ) for an induced-minor-free graph A A A . Therefore, the above discussion implies tw ( G + [ M ] ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) \operatorname{tw}(G^+[M]) = O(\sqrt{(d+\Delta)\cdot|M|}) tw ( G + [ M ]) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . To further bound tw ( G ) \operatorname{tw}(G) tw ( G ) , we only need to apply the standard idea of gluing tree decompositions. Let T \mathcal{T} T be a tree decomposition of G + [ M ] G^+[M] G + [ M ] with width O ( ( d + Δ ) ⋅ ∣ M ∣ ) O(\sqrt{(d+\Delta)\cdot|M|}) O ( ( d + Δ ) ⋅ ∣ M ∣ ) . Since M M M is an FVS of G G G , each connected component C C C of G − M G-M G − M is a tree and thus admits a width-1 tree decomposition T C \mathcal{T}_C T C . The neighbors of C C C in M M M form a clique in G + [ M ] G^+[M] G + [ M ] due to the torso operation, and hence there is one node x x x of T \mathcal{T} T whose bag contains all neighbors of C C C in M M M . We then append T C \mathcal{T}_C T C to x x x and add all vertices in the bag of x x x to the bags of the nodes of T C \mathcal{T}_C T C . After doing this for every component of G − M G-M G − M , we obtain a tree decomposition of G G G with width O ( ( d + Δ ) ⋅ ∣ M ∣ ) O(\sqrt{(d+\Delta)\cdot|M|}) O ( ( d + Δ ) ⋅ ∣ M ∣ ) .
Preliminaries
Basic notions. We write N = { 1 , 2 , … } \mathbb{N} = \{1,2,\ldots\} N = { 1 , 2 , … } as the set of natural numbers, and write N 0 = N ∪ { 0 } \mathbb{N}_0 = \mathbb{N} \cup\{0\} N 0 = N ∪ { 0 } . For a number n ∈ N n \in\mathbb{N} n ∈ N , we write [ n ] = { 1 , … , n } [n] = \{1,\ldots,n\} [ n ] = { 1 , … , n } and [ n ] 0 = { 0 , 1 , … , n } [n]_0 = \{0,1,\ldots,n\} [ n ] 0 = { 0 , 1 , … , n } . The notation O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) denotes O ( ⋅ ) O(\cdot) O ( ⋅ ) that suppresses logarithmic factors.
All graphs considered in this paper are finite, simple, and undirected. Let G G G be a graph. The notation V ( G ) V(G) V ( G ) denotes the set of vertices of G G G and the notation E ( G ) E(G) E ( G ) denotes the set of edges of G G G . For V ⊆ V ( G ) V \subseteq V(G) V ⊆ V ( G ) , we use N G ( V ) N_G(V) N G ( V ) to denote the set of vertices in V ( G ) ∖ V V(G) \setminus V V ( G ) ∖ V that are neighboring to V V V , and define N G [ V ] = V ∪ N G ( V ) N_G[V] = V \cup N_G(V) N G [ V ] = V ∪ N G ( V ) . Also, G [ V ] G[V] G [ V ] denotes the subgraph of G G G induced by V V V .
A graph is d d d -degenerate if every nonempty subgraph has a vertex of degree at most d d d , or equivalently, it has an edge orientation in which every vertex has at most d d d out-neighbors. A graph property is hereditary if it is preserved under taking induced subgraphs.
For a number d ∈ N d \in\mathbb{N} d ∈ N , a d d d -core of a graph G G G is a subset A ⊆ V ( G ) A \subseteq V(G) A ⊆ V ( G ) such that for every connected component C C C of G − A G - A G − A , we have ∣ N G ( V ( C ) ) ∣ ≤ d \lvert N_G(V(C)) \rvert\leq d ∣ N G ( V ( C ))∣ ≤ d .
Lemma 3.1. Let G G G be a graph and V ⊆ V ( G ) V \subseteq V(G) V ⊆ V ( G ) be a subset. If A ⊆ V ( G ) A \subseteq V(G) A ⊆ V ( G ) is a d d d -core of G G G , then A ∖ V A \setminus V A ∖ V is a d d d -core of G − V G - V G − V .
Proof. Let C C C be a connected component of G − ( V ∪ A ) G - (V \cup A) G − ( V ∪ A ) . We need to show ∣ N G − V ( V ( C ) ) ∣ ≤ d \lvert N_{G-V}(V(C)) \rvert\leq d ∣ N G − V ( V ( C ))∣ ≤ d . Note that N G − V ( V ( C ) ) ⊆ N G ( V ( C ) ) ∩ A N_{G-V}(V(C)) \subseteq N_G(V(C)) \cap A N G − V ( V ( C )) ⊆ N G ( V ( C )) ∩ A . So it suffices to show ∣ N G ( V ( C ) ) ∩ A ∣ ≤ d \lvert N_G(V(C)) \cap A \rvert\leq d ∣ N G ( V ( C )) ∩ A ∣ ≤ d . Since A ⊆ V ∪ A A \subseteq V \cup A A ⊆ V ∪ A , C C C is contained in a connected component C ′ C' C ′ of G − A G - A G − A . We have ∣ N G ( V ( C ′ ) ) ∣ ≤ d \lvert N_G(V(C')) \rvert\leq d ∣ N G ( V ( C ′ ))∣ ≤ d because A A A is a d d d -core of G G G . As V ( C ′ ) ∩ A = ∅ V(C') \cap A = \varnothing V ( C ′ ) ∩ A = ∅ , it holds that N G ( V ( C ) ) ∩ A ⊆ N G ( V ( C ′ ) ) N_G(V(C)) \cap A \subseteq N_G(V(C')) N G ( V ( C )) ∩ A ⊆ N G ( V ( C ′ )) . Thus, ∣ N G ( V ( C ) ) ∩ A ∣ ≤ ∣ N G ( V ( C ′ ) ) ∣ ≤ d \lvert N_G(V(C)) \cap A \rvert\leq\lvert N_G(V(C')) \rvert\leq d ∣ N G ( V ( C )) ∩ A ∣ ≤ ∣ N G ( V ( C ′ ))∣ ≤ d . □ \square □
Lemma 3.2. Let G G G be a graph. If A ⊆ V ( G ) A \subseteq V(G) A ⊆ V ( G ) is a d d d -core of G G G and A ′ ⊆ V ( G ) A' \subseteq V(G) A ′ ⊆ V ( G ) is a d ′ d' d ′ -core of G G G , then A ∪ A ′ A \cup A' A ∪ A ′ is a ( d + d ′ ) (d+d') ( d + d ′ ) -core of G G G .
Proof. Let C C C be a connected component of G − ( A ∪ A ′ ) G - (A \cup A') G − ( A ∪ A ′ ) . By Lemma 3.1, A A A is a d d d -core of G − ( A ′ ∖ A ) G - (A' \setminus A) G − ( A ′ ∖ A ) , which implies ∣ N G ( V ( C ) ) ∩ A ∣ ≤ d \lvert N_G(V(C)) \cap A \rvert\leq d ∣ N G ( V ( C )) ∩ A ∣ ≤ d . For the same reason, ∣ N G ( V ( C ) ) ∩ A ′ ∣ ≤ d ′ \lvert N_G(V(C)) \cap A' \rvert\leq d' ∣ N G ( V ( C )) ∩ A ′ ∣ ≤ d ′ . Therefore, we have ∣ N G ( V ( C ) ) ∣ ≤ ∣ N G ( V ( C ) ) ∩ A ∣ + ∣ N G ( V ( C ) ) ∩ A ′ ∣ ≤ d + d ′ \lvert N_G(V(C)) \rvert\leq\lvert N_G(V(C)) \cap A \rvert+ \lvert N_G(V(C)) \cap A' \rvert\leq d+d' ∣ N G ( V ( C ))∣ ≤ ∣ N G ( V ( C )) ∩ A ∣ + ∣ N G ( V ( C )) ∩ A ′ ∣ ≤ d + d ′ . □ \square □
Tree decomposition and treewidth
In a rooted tree T T T , for a node x ∈ V ( T ) x \in V(T) x ∈ V ( T ) , we denote by T x T_x T x the subtree of T T T rooted at x x x . Let G G G be a graph. A tree decomposition of G G G is a pair T = ( T , β ) \mathcal{T} = (T,\beta) T = ( T , β ) where T T T is a rooted tree and β : V ( T ) → 2 V ( G ) \beta: V(T) \to2^{V(G)} β : V ( T ) → 2 V ( G ) is a map satisfying (i) ⋃ x ∈ V ( T ) β ( x ) = V ( G ) \bigcup_{x \in V(T)} \beta(x) = V(G) ⋃ x ∈ V ( T ) β ( x ) = V ( G ) , (ii) for every ( u , v ) ∈ E ( G ) (u,v) \in E(G) ( u , v ) ∈ E ( G ) , there exists x ∈ V ( T ) x \in V(T) x ∈ V ( T ) with u , v ∈ β ( x ) u,v \in\beta(x) u , v ∈ β ( x ) , and (iii) for every v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , T [ X v ] T[X_v] T [ X v ] is connected where X v = { x ∈ V ( T ) : v ∈ β ( x ) } X_v = \{x \in V(T) : v \in\beta(x)\} X v = { x ∈ V ( T ) : v ∈ β ( x )} . The width of T \mathcal{T} T is defined as ( max x ∈ V ( T ) ∣ β ( x ) ∣ ) − 1 (\max_{x \in V(T)} \lvert\beta(x) \rvert) - 1 ( max x ∈ V ( T ) ∣ β ( x )∣) − 1 . The treewidth of G G G is the minimum width of a tree decomposition of G G G .
Lemma 3.3. Given a connected graph G G G with n n n vertices, one can compute in 2 O ( tw ( G ) ) n 2^{O(\operatorname{tw}(G))}n 2 O ( tw ( G )) n time a tree decomposition T = ( T , β ) \mathcal{T} = (T,\beta) T = ( T , β ) of G G G with width O ( tw ( G ) ) O(\operatorname{tw}(G)) O ( tw ( G )) such that G [ γ ( x ) ] G[\gamma(x)] G [ γ ( x )] is connected for all x ∈ V ( T ) x \in V(T) x ∈ V ( T ) , where γ ( x ) = ⋃ y ∈ V ( T x ) β ( y ) \gamma(x) = \bigcup_{y \in V(T_x)} \beta(y) γ ( x ) = ⋃ y ∈ V ( T x ) β ( y ) .
Proof. Let k = tw ( G ) k = \operatorname{tw}(G) k = tw ( G ) . The case n = 1 n=1 n = 1 is immediate, so assume k ≥ 1 k \geq1 k ≥ 1 . Korhonen’s algorithm [40 ] , given an integer q q q , runs in time 2 O ( q ) n 2^{O(q)}n 2 O ( q ) n and either returns a tree decomposition of width at most 2 q + 1 2q+1 2 q + 1 or correctly reports that tw ( G ) > q \operatorname{tw}(G)>q tw ( G ) > q . Trying q = 0 , 1 , … q=0,1,\ldots q = 0 , 1 , … until a decomposition is returned therefore gives, in total time 2 O ( k ) n 2^{O(k)}n 2 O ( k ) n , a tree decomposition of width w ≤ 2 k + 1 = O ( k ) w \leq2k+1 = O(k) w ≤ 2 k + 1 = O ( k ) .
We convert this decomposition into an elimination ordering v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n of width at most w w w . Here, eliminating a vertex means making its remaining neighbors pairwise adjacent and then removing it; the width of the ordering is the maximum number of remaining neighbors at any elimination step. Root the decomposition arbitrarily. Repeatedly take a non-root leaf bag B B B with parent bag B ′ B' B ′ , eliminate the vertices of B ∖ B ′ B \setminus B' B ∖ B ′ in any order, and remove the leaf bag. Each such vertex occurs only in B B B in the current decomposition, so all its remaining neighbors lie in B B B . Thus each elimination has at most w w w remaining neighbors, and every fill edge is covered by B B B . After these eliminations, the surviving part of B B B is contained in B ′ B' B ′ , so removing the leaf bag preserves a tree decomposition of the remaining filled graph. When only the root bag remains, eliminate its vertices in any order. Using a decomposition with O ( n ) O(n) O ( n ) bags, this conversion and the construction of the filled elimination graph take O ( ( w + 1 ) 2 n ) O((w+1)^2n) O (( w + 1 ) 2 n ) time, which is absorbed by 2 O ( k ) n 2^{O(k)}n 2 O ( k ) n .
We construct a rooted tree T T T on V ( G ) V(G) V ( G ) recursively. Take v n v_n v n as the root. For each connected component D D D of G − v n G-v_n G − v n , choose as its root the vertex with largest elimination index in D D D , attach this root as a child of v n v_n v n , and apply the same construction to G [ D ] G[D] G [ D ] . For each vertex x = v i x=v_i x = v i , let C x C_x C x be the set consisting of x x x and its descendants in T T T . Equivalently, C x C_x C x is the connected component of G [ { v 1 , … , v i } ] G[\{v_1,\ldots,v_i\}] G [{ v 1 , … , v i }] containing v i v_i v i . In particular, G [ C x ] G[C_x] G [ C x ] is connected. Set
β ( x ) = { x } ∪ N G ( C x ) . \beta(x)=\{x\}\cup N_G(C_x). β ( x ) = { x } ∪ N G ( C x ) .
We first bound the bag sizes. Every vertex z ∈ N G ( C x ) z\in N_G(C_x) z ∈ N G ( C x ) has an elimination index larger than i i i . As G [ C x ] G[C_x] G [ C x ] is connected, there is an x x x –z z z path all of whose internal vertices have indices smaller than i i i . After eliminating v 1 , … , v i − 1 v_1,\ldots,v_{i-1} v 1 , … , v i − 1 , the fill edges therefore make x x x adjacent to z z z . Hence N G ( C x ) N_G(C_x) N G ( C x ) is contained in the set of remaining neighbors of x x x at its elimination step. We conclude that ∣ β ( x ) ∣ ≤ w + 1 |\beta(x)|\leq w+1 ∣ β ( x ) ∣ ≤ w + 1 .
We verify the tree-decomposition axioms. Each vertex x x x belongs to β ( x ) \beta(x) β ( x ) . For every edge v i v j ∈ E ( G ) v_iv_j\in E(G) v i v j ∈ E ( G ) with i < j i<j i < j , we have v j ∈ N G ( C v i ) v_j\in N_G(C_{v_i}) v j ∈ N G ( C v i ) ; thus both endpoints belong to β ( v i ) \beta(v_i) β ( v i ) . Finally, fix v ∈ V ( G ) v\in V(G) v ∈ V ( G ) . If v ∈ β ( x ) v\in\beta(x) v ∈ β ( x ) for x ≠ v x\neq v x = v , then v ∈ N G ( C x ) v\in N_G(C_x) v ∈ N G ( C x ) . The recursive construction implies that v v v is an ancestor of x x x . Furthermore, for any node y y y on the path from x x x to v v v other than v v v , the containment C x ⊆ C y C_x\subseteq C_y C x ⊆ C y gives v ∈ N G ( C y ) v\in N_G(C_y) v ∈ N G ( C y ) , and hence v ∈ β ( y ) v\in\beta(y) v ∈ β ( y ) . Thus the bags containing v v v induce a connected subtree of T T T . This proves that ( T , β ) (T,\beta) ( T , β ) is a tree decomposition of width at most w w w .
Let γ ( x ) \gamma(x) γ ( x ) be the union of all bags at descendants of x x x , including x x x itself. We claim that
γ ( x ) = C x ∪ N G ( C x ) . \gamma(x)=C_x\cup N_G(C_x). γ ( x ) = C x ∪ N G ( C x ) .
Indeed, every vertex of C x C_x C x appears in its own bag, while N G ( C x ) ⊆ β ( x ) N_G(C_x)\subseteq\beta(x) N G ( C x ) ⊆ β ( x ) . Conversely, if y y y is a descendant of x x x , then C y ⊆ C x C_y\subseteq C_x C y ⊆ C x , so β ( y ) ⊆ C x ∪ N G ( C x ) \beta(y)\subseteq C_x\cup N_G(C_x) β ( y ) ⊆ C x ∪ N G ( C x ) . As G [ C x ] G[C_x] G [ C x ] is connected and every vertex of N G ( C x ) N_G(C_x) N G ( C x ) has a neighbor in C x C_x C x , the induced graph G [ γ ( x ) ] G[\gamma(x)] G [ γ ( x )] is connected.
The tree T T T and its bags can be recovered from the filled elimination graph in O ( w 2 n ) O(w^2n) O ( w 2 n ) time: the parent of each non-root vertex is its smallest-indexed later neighbor, and the bag consists of that vertex and its later neighbors. Thus the total running time is 2 O ( k ) n 2^{O(k)}n 2 O ( k ) n , as claimed. □ \square □
Lemma 3.4. Let G G G be a graph and T = ( T , β ) T=(T,\beta) T = ( T , β ) be a tree decomposition of G G G . For any subset S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) and any number c ∈ N c\in\mathbb{N} c ∈ N , there exist r = O ( c ) r=O(c) r = O ( c ) nodes x 1 , … , x r ∈ V ( T ) x_1,\ldots,x_r\in V(T) x 1 , … , x r ∈ V ( T ) such that every connected component of G − ⋃ i = 1 r β ( x i ) G-\bigcup_{i=1}^{r}\beta(x_i) G − ⋃ i = 1 r β ( x i ) contains at most ∣ S ∣ c \frac{|S|}{c} c ∣ S ∣ vertices in S S S .
Proof. If S = ∅ S=\emptyset S = ∅ , take r = 0 r=0 r = 0 . Otherwise, let q = ∣ S ∣ / c q=|S|/c q = ∣ S ∣/ c . For each vertex v ∈ S v\in S v ∈ S , choose a node a ( v ) ∈ V ( T ) a(v)\in V(T) a ( v ) ∈ V ( T ) such that v ∈ β ( a ( v ) ) v\in\beta(a(v)) v ∈ β ( a ( v )) . Assign each node x ∈ V ( T ) x\in V(T) x ∈ V ( T ) the weight w ( x ) = ∣ { v ∈ S : a ( v ) = x } ∣ w(x)=|\{v\in S:a(v)=x\}| w ( x ) = ∣ { v ∈ S : a ( v ) = x } ∣ . Thus, the total weight of T T T is ∣ S ∣ |S| ∣ S ∣ .
We first construct a set X ⊆ V ( T ) X\subseteq V(T) X ⊆ V ( T ) of fewer than c c c nodes such that every connected component of T − X T-X T − X has weight at most q q q . Root T T T arbitrarily, and maintain a rooted tree T ′ T' T ′ , initially equal to T T T . While the total weight of T ′ T' T ′ exceeds q q q , choose a deepest node x x x whose subtree in T ′ T' T ′ has weight greater than q q q . Add x x x to X X X , and remove its entire subtree from T ′ T' T ′ . By the choice of x x x , each child subtree of x x x in the current tree has weight at most q q q .
The subtrees removed in different iterations are pairwise disjoint, and each has weight greater than q q q . Consequently, writing r = ∣ X ∣ r=|X| r = ∣ X ∣ , we obtain r q < ∣ S ∣ rq<|S| r q < ∣ S ∣ , and hence r < c r<c r < c . Moreover, every connected component of T − X T-X T − X is either a child subtree separated off in one of these iterations or the tree remaining at termination. Each such component has weight at most q q q .
Set U = ⋃ x ∈ X β ( x ) U=\bigcup_{x\in X}\beta(x) U = ⋃ x ∈ X β ( x ) . For each vertex v ∈ V ( G ) ∖ U v\in V(G)\setminus U v ∈ V ( G ) ∖ U , the nodes whose bags contain v v v induce a connected subtree of T T T disjoint from X X X , and therefore lie in a single connected component of T − X T-X T − X . If two vertices u , v ∉ U u,v \notin U u , v ∈ / U are adjacent in G G G , some bag contains both of them, so their corresponding subtrees lie in the same connected component of T − X T-X T − X . Thus, for every connected component C C C of G − U G-U G − U , there is a connected component D D D of T − X T-X T − X containing every node whose bag contains a vertex of C C C .
In particular, a ( v ) ∈ V ( D ) a(v) \in V(D) a ( v ) ∈ V ( D ) for every v ∈ S ∩ V ( C ) v \in S \cap V(C) v ∈ S ∩ V ( C ) . Hence ∣ S ∩ V ( C ) ∣ ≤ ∑ x ∈ V ( D ) w ( x ) ≤ q = ∣ S ∣ c |S \cap V(C)| \le\sum_{x \in V(D)} w(x) \le q = \frac{|S|}{c} ∣ S ∩ V ( C ) ∣ ≤ ∑ x ∈ V ( D ) w ( x ) ≤ q = c ∣ S ∣ . Enumerating X X X as x 1 , … , x r x_1,\ldots,x_r x 1 , … , x r proves the lemma.
Lemma 3.5. Let G G G be a graph with n n n vertices, M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) satisfying tw ( G − M ) ≤ t \operatorname{tw}(G-M) \le t tw ( G − M ) ≤ t , and d ∈ N d \in\mathbb{N} d ∈ N be a parameter. If G − M G-M G − M contains a connected component C C C with ∣ N G ( V ( C ) ) ∩ M ∣ > d |N_G(V(C)) \cap M| > d ∣ N G ( V ( C )) ∩ M ∣ > d , then one can compute in 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) time V , Z ⊆ V ( G ) ∖ M V,Z \subseteq V(G)\setminus M V , Z ⊆ V ( G ) ∖ M satisfying the following conditions:
(i) Z ⊆ V Z \subseteq V Z ⊆ V and N G − M ( V ∖ Z ) ⊆ Z N_{G-M}(V\setminus Z) \subseteq Z N G − M ( V ∖ Z ) ⊆ Z ,
(ii) G [ V ] G[V] G [ V ] is connected and ∣ N G ( V ) ∩ M ∣ > d |N_G(V) \cap M| > d ∣ N G ( V ) ∩ M ∣ > d ,
(iii) ∣ Z ∣ = O ( t ) |Z| = O(t) ∣ Z ∣ = O ( t ) ,
(iv) M M M is a d d d -core of G [ M ∪ V ] − Z G[M \cup V]-Z G [ M ∪ V ] − Z .
Proof. Let C C C be a connected component of G − M G-M G − M with ∣ N G ( V ( C ) ) ∩ M ∣ > d |N_G(V(C)) \cap M| > d ∣ N G ( V ( C )) ∩ M ∣ > d . Apply Lemma 3.3 to C C C to obtain a rooted tree decomposition ( T , β ) (T,\beta) ( T , β ) of width O ( t ) O(t) O ( t ) . Thus, for each node x x x , G [ γ ( x ) ] G[\gamma(x)] G [ γ ( x )] is connected.
Traverse T T T in postorder. At each node x x x , order its children arbitrarily as y 1 , … , y k y_1,\ldots,y_k y 1 , … , y k , and consider successively the sets W j = β ( x ) ∪ ⋃ i = 1 j γ ( y i ) W_j = \beta(x) \cup\bigcup_{i=1}^{j}\gamma(y_i) W j = β ( x ) ∪ ⋃ i = 1 j γ ( y i ) for j = 0 , … , k j=0,\ldots,k j = 0 , … , k . Stop at the first set W j W_j W j such that some connected component of G [ W j ] G[W_j] G [ W j ] has more than d d d neighbors in M M M . Let V V V be the vertex set of this component, and set Z = V ∩ β ( x ) Z = V \cap\beta(x) Z = V ∩ β ( x ) . The procedure must stop, because the last set considered at the root is V ( C ) V(C) V ( C ) .
By construction, Z ⊆ V ⊆ V ( G ) ∖ M Z \subseteq V \subseteq V(G)\setminus M Z ⊆ V ⊆ V ( G ) ∖ M , G [ V ] G[V] G [ V ] is connected, and ∣ N G ( V ) ∩ M ∣ > d |N_G(V) \cap M| > d ∣ N G ( V ) ∩ M ∣ > d . Furthermore, ∣ Z ∣ ≤ ∣ β ( x ) ∣ = O ( t ) |Z| \le|\beta(x)| = O(t) ∣ Z ∣ ≤ ∣ β ( x ) ∣ = O ( t ) . This proves (ii) and (iii).
For (i), the tree-decomposition axioms imply that the sets γ ( y i ) ∖ β ( x ) \gamma(y_i)\setminus\beta(x) γ ( y i ) ∖ β ( x ) are pairwise disjoint and satisfy N C ( γ ( y i ) ∖ β ( x ) ) ⊆ β ( x ) N_C(\gamma(y_i)\setminus\beta(x)) \subseteq\beta(x) N C ( γ ( y i ) ∖ β ( x )) ⊆ β ( x ) . Every vertex of V ∖ Z V\setminus Z V ∖ Z belongs to one of these sets with i ≤ j i \le j i ≤ j . Thus, all its neighbors in G − M G-M G − M belong to W j W_j W j . Since V V V is the vertex set of a connected component of G [ W j ] G[W_j] G [ W j ] , these neighbors belong to V V V . Consequently, N G − M ( V ∖ Z ) ⊆ Z N_{G-M}(V\setminus Z) \subseteq Z N G − M ( V ∖ Z ) ⊆ Z .
To prove (iv), observe that each child y i y_i y i was fully processed before x x x , including the set γ ( y i ) \gamma(y_i) γ ( y i ) . Since the procedure did not stop earlier and G [ γ ( y i ) ] G[\gamma(y_i)] G [ γ ( y i )] is connected, ∣ N G ( γ ( y i ) ) ∩ M ∣ ≤ d |N_G(\gamma(y_i)) \cap M| \le d ∣ N G ( γ ( y i )) ∩ M ∣ ≤ d . There are no edges between distinct sets γ ( y i ) ∖ β ( x ) \gamma(y_i)\setminus\beta(x) γ ( y i ) ∖ β ( x ) . Hence every connected component D D D of G [ V ∖ Z ] G[V\setminus Z] G [ V ∖ Z ] is contained in γ ( y i ) ∖ β ( x ) \gamma(y_i)\setminus\beta(x) γ ( y i ) ∖ β ( x ) for some i ≤ j i \le j i ≤ j . It follows that ∣ N G ( V ( D ) ) ∩ M ∣ ≤ ∣ N G ( γ ( y i ) ) ∩ M ∣ ≤ d |N_G(V(D)) \cap M| \le|N_G(\gamma(y_i)) \cap M| \le d ∣ N G ( V ( D )) ∩ M ∣ ≤ ∣ N G ( γ ( y i )) ∩ M ∣ ≤ d . Therefore, M M M is a d d d -core of G [ M ∪ V ] − Z G[M \cup V]-Z G [ M ∪ V ] − Z .
Finally, computing the decomposition takes 2 O ( t ) n 2^{O(t)}n 2 O ( t ) n time. The total number of sets W j W_j W j considered is O ( ∣ V ( T ) ∣ ) O(|V(T)|) O ( ∣ V ( T ) ∣ ) , since we consider only prefixes of the ordered children at each node. Computing their connected components and neighborhoods takes polynomial time per set. Thus, the total running time is 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) .
Corollary 3.6. Let G G G be a graph with n n n vertices, M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) satisfying tw ( G − M ) ≤ t \operatorname{tw}(G-M) \le t tw ( G − M ) ≤ t , and d ∈ N d \in\mathbb{N} d ∈ N be a parameter. Then one can compute in 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) time a collection P = { ( V 1 , Z 1 ) , … , ( V p , Z p ) } \mathcal{P} = \{(V_1,Z_1),\ldots,(V_p,Z_p)\} P = {( V 1 , Z 1 ) , … , ( V p , Z p )} where V 1 , … , V p , Z 1 , … , Z p ⊆ V ( G ) ∖ M V_1,\ldots,V_p,Z_1,\ldots,Z_p \subseteq V(G)\setminus M V 1 , … , V p , Z 1 , … , Z p ⊆ V ( G ) ∖ M satisfy the following conditions:
(i) V 1 , … , V p V_1,\ldots,V_p V 1 , … , V p are disjoint and Z i ⊆ V i Z_i \subseteq V_i Z i ⊆ V i for all i ∈ [ p ] i \in[p] i ∈ [ p ] ,
(ii) G [ V i ] G[V_i] G [ V i ] is connected and ∣ N G ( V i ) ∩ M ∣ > d |N_G(V_i) \cap M| > d ∣ N G ( V i ) ∩ M ∣ > d for all i ∈ [ p ] i \in[p] i ∈ [ p ] ,
(iii) ∣ Z i ∣ = O ( t ) |Z_i| = O(t) ∣ Z i ∣ = O ( t ) for all i ∈ [ p ] i \in[p] i ∈ [ p ] ,
(iv) M M M is a d d d -core of G − ( ⋃ i = 1 p Z i ) G - \left(\bigcup_{i=1}^{p} Z_i\right) G − ( ⋃ i = 1 p Z i ) .
Proof. We give a recursive algorithm, proving its correctness by induction on ∣ V ( G ) ∖ M ∣ |V(G)\setminus M| ∣ V ( G ) ∖ M ∣ . If M M M is already a d d d -core of G G G , return the empty collection, which satisfies all the required conditions. Otherwise, apply Lemma 3.5 to obtain sets V 1 , Z 1 V_1, Z_1 V 1 , Z 1 . Since V 1 ⊆ V ( G ) ∖ M V_1 \subseteq V(G)\setminus M V 1 ⊆ V ( G ) ∖ M is nonempty, the graph H : = G − V 1 H := G - V_1 H := G − V 1 satisfies M ⊆ V ( H ) M \subseteq V(H) M ⊆ V ( H ) , tw ( H − M ) ≤ t \operatorname{tw}(H-M) \le t tw ( H − M ) ≤ t , and ∣ V ( H ) ∖ M ∣ < ∣ V ( G ) ∖ M ∣ |V(H)\setminus M| < |V(G)\setminus M| ∣ V ( H ) ∖ M ∣ < ∣ V ( G ) ∖ M ∣ . Recursively apply the algorithm to H H H with the same set M M M and parameters d , t d,t d , t , obtaining a collection
P ′ = { ( V 2 , Z 2 ) , … , ( V p , Z p ) } . \mathcal{P}' = \{(V_2,Z_2),\ldots,(V_p,Z_p)\}. P ′ = {( V 2 , Z 2 ) , … , ( V p , Z p )} .
Return P : = { ( V 1 , Z 1 ) } ∪ P ′ \mathcal{P} := \{(V_1,Z_1)\} \cup\mathcal{P}' P := {( V 1 , Z 1 )} ∪ P ′ .
Conditions (i)–(iii) follow from Lemma 3.5 and the induction hypothesis. Indeed, all sets returned by the recursive call are disjoint from V 1 V_1 V 1 . Moreover, since H H H is an induced subgraph of G G G containing M M M , for every i ≥ 2 i \ge2 i ≥ 2 we have H [ V i ] = G [ V i ] H[V_i] = G[V_i] H [ V i ] = G [ V i ] and N H ( V i ) ∩ M = N G ( V i ) ∩ M N_H(V_i) \cap M = N_G(V_i) \cap M N H ( V i ) ∩ M = N G ( V i ) ∩ M .
It remains to prove (iv). Let
Z ∗ : = ⋃ i = 1 p Z i and H ′ : = H − ⋃ i = 2 p Z i . Z^* := \bigcup_{i=1}^{p} Z_i \qquad\text{and}\qquad H' := H - \bigcup_{i=2}^{p} Z_i. Z ∗ := i = 1 ⋃ p Z i and H ′ := H − i = 2 ⋃ p Z i .
By the induction hypothesis, M M M is a d d d -core of H ′ H' H ′ . Furthermore, Lemma 4 gives
N G − M ( V 1 ∖ Z 1 ) ⊆ Z 1 . N_{G-M}(V_1\setminus Z_1) \subseteq Z_1. N G − M ( V 1 ∖ Z 1 ) ⊆ Z 1 .
Consequently, there are no edges between V 1 ∖ Z 1 V_1\setminus Z_1 V 1 ∖ Z 1 and V ( H ′ ) ∖ M V(H')\setminus M V ( H ′ ) ∖ M . These two sets partition V ( G − Z ∗ ) ∖ M V(G-Z^*)\setminus M V ( G − Z ∗ ) ∖ M .
Thus, every connected component D D D of ( G − Z ∗ ) − M (G-Z^*)-M ( G − Z ∗ ) − M is either a connected component of G [ V 1 ∖ Z 1 ] G[V_1\setminus Z_1] G [ V 1 ∖ Z 1 ] or a connected component of H ′ − M H'-M H ′ − M . In the first case, D D D has at most d d d neighbors in M M M because Lemma 4 ensures that M M M is a d d d -core of G [ M ∪ V 1 ] − Z 1 G[M\cup V_1]-Z_1 G [ M ∪ V 1 ] − Z 1 . In the second case, the same bound follows from the induction hypothesis. Since all vertices of M M M are retained, their adjacencies to D D D are unchanged. Therefore, M M M is a d d d -core of G − Z ∗ G-Z^* G − Z ∗ , proving (iv).
Finally, each recursive step removes at least one vertex, so there are at most n n n applications of Lemma 4. Each application takes 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) time, and checking whether M M M is a d d d -core takes polynomial time. The total running time is therefore 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) .
The following lemma uses the standard LCA-closure argument; see Bodlaender et al. [13, Lemma 5.4] for a similar statement. We include a proof for completeness.
Lemma 3.7. Let G G G be a graph with n n n vertices. Given a subset Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) , one can compute in 2 O ( tw ( G ) ) n O ( 1 ) 2^{O(\operatorname{tw}(G))}n^{O(1)} 2 O ( tw ( G )) n O ( 1 ) time an O ( tw ( G ) ) O(\operatorname{tw}(G)) O ( tw ( G )) -core L ⊆ V ( G ) L \subseteq V(G) L ⊆ V ( G ) of G G G such that Z ⊆ L Z \subseteq L Z ⊆ L and ∣ L ∣ = O ( tw ( G ) ⋅ ∣ Z ∣ ) |L| = O(\operatorname{tw}(G)\cdot|Z|) ∣ L ∣ = O ( tw ( G ) ⋅ ∣ Z ∣ ) .
Proof. If Z = ∅ Z = \varnothing Z = ∅ , take L = ∅ L = \varnothing L = ∅ . Otherwise, put k = tw ( G ) k = \operatorname{tw}(G) k = tw ( G ) . Using Korhonen’s algorithm [40 ] , trying successive values of the width parameter as above, we compute a tree decomposition ( T , β ) (T,\beta) ( T , β ) of G G G of width w ≤ 2 k + 1 w \le2k+1 w ≤ 2 k + 1 in time 2 O ( k ) n O ( 1 ) 2^{O(k)}n^{O(1)} 2 O ( k ) n O ( 1 ) . Root T T T arbitrarily. For every z ∈ Z z \in Z z ∈ Z , choose a node a z a_z a z with z ∈ β ( a z ) z \in\beta(a_z) z ∈ β ( a z ) , and let A = { a z : z ∈ Z } A = \{a_z : z \in Z\} A = { a z : z ∈ Z } . Let Q Q Q consist of the root together with the closure of A A A under lowest common ancestors (LCAs). Then ∣ Q ∣ ≤ 2 ∣ A ∣ ≤ 2 ∣ Z ∣ |Q| \le2|A| \le2|Z| ∣ Q ∣ ≤ 2∣ A ∣ ≤ 2∣ Z ∣ : in the minimal subtree containing the root and A A A , every node added by LCA closure that is not already in A A A is a branching node, and there are at most ∣ A ∣ − 1 |A|-1 ∣ A ∣ − 1 such nodes; adding the root contributes at most one further node. Define
L = ⋃ q ∈ Q β ( q ) . L = \bigcup_{q\in Q} \beta(q). L = q ∈ Q ⋃ β ( q ) .
Clearly, Z ⊆ L Z \subseteq L Z ⊆ L and ∣ L ∣ ≤ 2 ( w + 1 ) ∣ Z ∣ = O ( ( k + 1 ) ∣ Z ∣ ) |L| \leq2(w+1)|Z| = O((k+1)|Z|) ∣ L ∣ ≤ 2 ( w + 1 ) ∣ Z ∣ = O (( k + 1 ) ∣ Z ∣ ) .
Every connected component R R R of T − Q T-Q T − Q has at most two neighbors in Q Q Q . Indeed, it has at most one neighbor towards the root. If it had two neighbors below it, their LCA would lie in R R R , contradicting the LCA closure of Q Q Q . Now let C C C be a connected component of G − L G-L G − L . For each vertex of C C C , the nodes whose bags contain it form a connected subtree disjoint from Q Q Q . Since adjacent vertices occur together in a bag and C C C is connected, the union of these subtrees is connected. Thus all bags meeting V ( C ) V(C) V ( C ) lie in a single component R R R of T − Q T-Q T − Q .
We claim that
N G ( V ( C ) ) ⊆ ⋃ q ∈ N T ( V ( R ) ) β ( q ) . N_G(V(C)) \subseteq\bigcup_{q \in N_T(V(R))} \beta(q). N G ( V ( C )) ⊆ q ∈ N T ( V ( R )) ⋃ β ( q ) .
To see this, let v ∈ N G ( V ( C ) ) v \in N_G(V(C)) v ∈ N G ( V ( C )) and choose a neighbor u ∈ V ( C ) u \in V(C) u ∈ V ( C ) . Some bag contains both u u u and v v v , and its node lies in R R R . Also, v ∈ L v \in L v ∈ L , so v v v belongs to a bag at a node of Q Q Q . The path between these two nodes crosses a node q ∈ N T ( V ( R ) ) q \in N_T(V(R)) q ∈ N T ( V ( R )) ; by the connectedness condition of a tree decomposition, v ∈ β ( q ) v \in\beta(q) v ∈ β ( q ) . This proves the claim. Consequently, ∣ N G ( V ( C ) ) ∣ ≤ 2 ( w + 1 ) = O ( k + 1 ) |N_G(V(C))| \leq2(w+1) = O(k+1) ∣ N G ( V ( C )) ∣ ≤ 2 ( w + 1 ) = O ( k + 1 ) , so L L L is an O ( k + 1 ) O(k+1) O ( k + 1 ) -core of G G G . The LCA closure and the union of the selected bags can be computed in polynomial time in the size of the decomposition, giving the stated running time.
Treewidth modulators. For a graph G G G and a number t ∈ N t \in\mathbb{N} t ∈ N , we say a subset S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) is a treewidth-t t t modulator of G G G if tw ( G − S ) ≤ t \operatorname{tw}(G-S) \leq t tw ( G − S ) ≤ t .
Lemma 3.8 ([37 ] ). Given a graph G G G with n n n vertices and a number t ∈ N t \in\mathbb{N} t ∈ N , one can compute in 2 t O ( 1 ) n O ( 1 ) 2^{t^{O(1)}}n^{O(1)} 2 t O ( 1 ) n O ( 1 ) time a treewidth-t t t modulator S S S of G G G satisfying ∣ S ∣ = O ( k log t ) |S| = O(k \log t) ∣ S ∣ = O ( k log t ) , where k k k is the minimum size of a treewidth-t t t modulator of G G G .
Torso operation. For a graph G G G and a set M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) , we define Torso ( G , M ) \operatorname{Torso}(G,M) Torso ( G , M ) as the graph obtained from G G G by adding edges ( u , v ) (u,v) ( u , v ) for all different u , v ∈ M u,v \in M u , v ∈ M satisfying that there exists a connected component C C C of G − M G-M G − M with u , v ∈ N G ( V ( C ) ) u,v \in N_G(V(C)) u , v ∈ N G ( V ( C )) . In other words, Torso ( G , M ) \operatorname{Torso}(G,M) Torso ( G , M ) is obtained from G G G by adding edges to make N G ( V ( C ) ) ∩ M N_G(V(C)) \cap M N G ( V ( C )) ∩ M a clique for each connected component C C C of G − M G-M G − M . We have the following simple observation.
Lemma 3.9. Let G G G be a graph and G + = Torso ( G , M ) G^+ = \operatorname{Torso}(G,M) G + = Torso ( G , M ) for some M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) . Then
tw ( G ) ≤ tw ( G + [ M ] ) + tw ( G − M ) + 1. \operatorname{tw}(G) \leq\operatorname{tw}(G^+[M]) + \operatorname{tw}(G-M) + 1. tw ( G ) ≤ tw ( G + [ M ]) + tw ( G − M ) + 1.
Proof. Write w = tw ( G + [ M ] ) w = \operatorname{tw}(G^+[M]) w = tw ( G + [ M ]) and t = tw ( G − M ) t = \operatorname{tw}(G-M) t = tw ( G − M ) . If either M M M or V ( G ) ∖ M V(G) \setminus M V ( G ) ∖ M is empty, the asserted inequality is immediate. Otherwise, take a tree decomposition ( T , β ) (T,\beta) ( T , β ) of G + [ M ] G^+[M] G + [ M ] of width w w w .
For each connected component C C C of G − M G-M G − M , put S C = N G ( C ) ∩ M S_C = N_G(C) \cap M S C = N G ( C ) ∩ M . By the definition of the torso, S C S_C S C is a clique in G + [ M ] G^+[M] G + [ M ] . Hence there is a node x C ∈ V ( T ) x_C \in V(T) x C ∈ V ( T ) such that S C ⊆ β ( x C ) S_C \subseteq\beta(x_C) S C ⊆ β ( x C ) . Take a tree decomposition ( T C , β C ) (T_C,\beta_C) ( T C , β C ) of G [ C ] G[C] G [ C ] of width at most t t t and enlarge each of its bags to β C ( y ) ∪ S C \beta_C(y) \cup S_C β C ( y ) ∪ S C . Finally, join an arbitrary node of T C T_C T C to x C x_C x C by an edge. Do this independently for every component C C C of G − M G-M G − M .
The resulting tree and bags form a tree decomposition of G G G . Edges within M M M and within each C C C remain covered; every edge between M M M and C C C has its endpoints in an enlarged bag of T C T_C T C . For a vertex of M M M , the bags containing it stay connected because each attached decomposition containing the vertex is joined at a bag that contains S C S_C S C . Connectivity for a vertex outside M M M follows from its original component decomposition. Every enlarged bag has size at most ( t + 1 ) + ( w + 1 ) (t+1)+(w+1) ( t + 1 ) + ( w + 1 ) , while the original bags have size at most w + 1 w+1 w + 1 . Therefore the new decomposition has width at most w + t + 1 w+t+1 w + t + 1 , proving the lemma.
Minor-free and induced-minor-free graphs. A graph H H H is an minor of G G G if H H H can be obtained from G G G by deleting vertices, deleting edges, and contracting edges. A graph H H H is an induced minor of G G G if H H H can be obtained from G G G by deleting vertices (but not edges) and contracting edges. A graph G G G is H H H -minor-free (resp., H H H -induced-minor-free ) if H H H is not a minor (resp., an induced minor) of G G G . We denote by G H \mathcal{G}_H G H the class of all H H H -induced-minor-free graphs.
The following treewidth bound uses the repaired separator theorem of Davies et al. [22 ] together with the separator-number characterization of treewidth due to Dvořák and Norin [29 ] . Indeed, a separator of an induced subgraph also separates every spanning subgraph of it, so the separator bound applies to all subgraphs as required by that characterization.
Lemma 3.10 ([41 , 22 ] ). Let H H H be a fixed graph. For any graph G ∈ G H G \in\mathcal{G}_H G ∈ G H , tw ( G ) = O ( ∣ E ( G ) ∣ ) \operatorname{tw}(G) = O\left(\sqrt{|E(G)|}\right) tw ( G ) = O ( ∣ E ( G ) ∣ ) .
We also need the following lemmas about induced-minor-free graphs in our proofs. For h ∈ N h \in\mathbb{N} h ∈ N , let K h K_h K h be the complete graph with h h h vertices and K h ∙ K_h^\bullet K h ∙ be the graph obtained from K h K_h K h by subdividing every edge (i.e., breaking the edge into two by inserting an intermediate vertex).
Lemma 3.11. Let H H H be a graph and h = ∣ V ( H ) ∣ h = |V(H)| h = ∣ V ( H ) ∣ . Then G H ⊆ G K h ∙ \mathcal{G}_H \subseteq\mathcal{G}_{K_h^\bullet} G H ⊆ G K h ∙ .
Proof. It suffices to show that K h ∙ K_h^\bullet K h ∙ contains H H H as an induced minor. Let X ⊆ V ( K h ∙ ) X \subseteq V(K_h^\bullet) X ⊆ V ( K h ∙ ) consist of the h h h original vertices of K h ∙ K_h^\bullet K h ∙ and Y ⊆ V ( K h ∙ ) Y \subseteq V(K_h^\bullet) Y ⊆ V ( K h ∙ ) consist of the ( h 2 ) \binom{h}{2} ( 2 h ) subdivision vertices of K h ∙ K_h^\bullet K h ∙ . Fix a bijection f : X → V ( H ) f : X \to V(H) f : X → V ( H ) . We consider every vertex y ∈ Y y \in Y y ∈ Y . There are two vertices u , v ∈ X u,v \in X u , v ∈ X neighboring to y y y in K h ∙ K_h^\bullet K h ∙ . If ( f ( u ) , f ( v ) ) ∉ E ( H ) (f(u), f(v)) \notin E(H) ( f ( u ) , f ( v )) ∈ / E ( H ) , we delete y y y from K h ∙ K_h^\bullet K h ∙ . Otherwise, we contract the edge ( u , y ) (u,y) ( u , y ) in K h ∙ K_h^\bullet K h ∙ . Clearly, the resulting graph is isomorphic to H H H . Thus, K h ∙ K_h^\bullet K h ∙ contains H H H as an induced minor. It follows that if a graph G G G contains K h ∙ K_h^\bullet K h ∙ as an induced minor, then it also contains H H H as an induced minor. □ \square □
Lemma 3.12. Let G ∈ G H G \in\mathcal{G}_H G ∈ G H for some graph H H H and I ⊆ V ( G ) I \subseteq V(G) I ⊆ V ( G ) be an independent set in G G G . Define G I G_I G I as the graph with V ( G I ) = I V(G_I) = I V ( G I ) = I in which two vertices u , v ∈ I u,v \in I u , v ∈ I are connected by an edge if there exists a connected component C C C of G − I G-I G − I such that N G ( V ( C ) ) = { u , v } N_G(V(C)) = \{u,v\} N G ( V ( C )) = { u , v } . Then G I G_I G I is H H H -minor-free.
Proof. Suppose for a contradiction that G I G_I G I contains H H H as an ordinary minor. By the branch-set characterization of graph minors, there is a subgraph F F F of G I G_I G I such that H H H can be obtained from F F F by contracting edges only (and suppressing parallel edges).
For each edge u v ∈ E ( F ) uv \in E(F) uv ∈ E ( F ) , choose a connected component C u v C_{uv} C uv of G − I G-I G − I with N G ( C u v ) = { u , v } N_G(C_{uv}) = \{u,v\} N G ( C uv ) = { u , v } . Different edges of F F F require different components, since the neighbourhood of each such component is a fixed pair of vertices. Consider the induced subgraph
G ′ = G [ V ( F ) ∪ ⋃ u v ∈ E ( F ) V ( C u v ) ] . G' = G\left[V(F) \cup\bigcup_{uv\in E(F)} V(C_{uv})\right]. G ′ = G V ( F ) ∪ uv ∈ E ( F ) ⋃ V ( C uv ) .
Since I I I is independent, there are no edges between distinct vertices of V ( F ) V(F) V ( F ) . Also, distinct chosen components have no edges between them, and each C u v C_{uv} C uv has neighbors in V ( F ) V(F) V ( F ) only at u u u and v v v .
For each u v ∈ E ( F ) uv \in E(F) uv ∈ E ( F ) , contract the connected subgraph C u v C_{uv} C uv together with u u u into the vertex u u u . These contractions are valid because C u v C_{uv} C uv is connected and adjacent to u u u ; they introduce the edge u v uv uv and no other edge among the vertices of V ( F ) V(F) V ( F ) . After doing this for every edge of F F F , the resulting graph is precisely F F F (up to parallel edges). Thus F F F is an induced minor of G G G . Contracting the edges that turn F F F into H H H shows that H H H is an induced minor of G G G , contradicting G ∈ G H G \in\mathcal{G}_H G ∈ G H . Hence G I G_I G I is H H H -minor-free. □ \square □
Sublinear-treewidth branching theorem
The main goal of this section is to prove the following theorem, which serves as the technical core of both our subexponential FPT algorithm and QPTAS. Roughly speaking, given an induced-minor-free graph G G G with an unknown treewidth modulator S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) of size at most k k k , the theorem allows us to guess in 2 O ~ ( k / d ) ⋅ ∣ V ( G ) ∣ O ( 1 ) 2^{\widetilde{O}(k/d)} \cdot|V(G)|^{O(1)} 2 O ( k / d ) ⋅ ∣ V ( G ) ∣ O ( 1 ) time a subset X X X of S S S satisfying tw ( G − X ) = O ( k d ) \operatorname{tw}(G-X) = O(\sqrt{kd}) tw ( G − X ) = O ( k d ) , via a branching algorithm. Setting d = k c d = k^c d = k c for a constant c ∈ ( 0 , 1 ) c \in(0,1) c ∈ ( 0 , 1 ) , the algorithm runs in subexponential time in k k k and the treewidth of G − X G-X G − X is sublinear in k k k .
Theorem 4.1. Let H H H be a fixed graph. Given a graph G ∈ C H G \in\mathcal{C}_H G ∈ C H with n n n vertices and three parameters k , d , t ∈ N k,d,t \in\mathbb{N} k , d , t ∈ N with d > 2 t d > 2t d > 2 t , one can compute in k t O ( 1 ) k / d n O ( 1 ) k^{t^{O(1)}k/d}n^{O(1)} k t O ( 1 ) k / d n O ( 1 ) time a collection X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } of r = k t O ( 1 ) k / d r = k^{t^{O(1)}k/d} r = k t O ( 1 ) k / d subsets of V ( G ) V(G) V ( G ) satisfying the following conditions:
(i) tw ( G − X i ) = t O ( 1 ) k d \operatorname{tw}(G-X_i) = t^{O(1)}\sqrt{kd} tw ( G − X i ) = t O ( 1 ) k d for all i ∈ [ r ] i \in[r] i ∈ [ r ] ,
(ii) for every treewidth-t t t modulator S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) of G G G satisfying ∣ S ∣ ≤ k |S| \leq k ∣ S ∣ ≤ k , there exists an index i ∈ [ r ] i \in[r] i ∈ [ r ] such that X i ⊆ S X_i \subseteq S X i ⊆ S .
The algorithm
In this section, we present the branching algorithm of Theorem 4.1. For convenience of analysis, instead of computing a collection X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } of subsets of V ( G ) V(G) V ( G ) as in Theorem 4.1, our actual algorithm will compute a collection Q = { ( X 1 , M 1 ) , … , ( X r , M r ) } \mathcal{Q} = \{(X_1,M_1),\ldots,(X_r,M_r)\} Q = {( X 1 , M 1 ) , … , ( X r , M r )} of pairs of subsets of V ( G ) V(G) V ( G ) . Specifically, the main goal of this section is to prove the following lemma.
Lemma 4.2. Given a graph G G G with n n n vertices and three parameters k , d , t ∈ N k,d,t \in\mathbb{N} k , d , t ∈ N with d > 2 t d > 2t d > 2 t , one can compute in k t O ( 1 ) k / d n O ( 1 ) k^{t^{O(1)}k/d}n^{O(1)} k t O ( 1 ) k / d n O ( 1 ) time a collection Q = { ( X 1 , M 1 ) , … , ( X r , M r ) } \mathcal{Q} = \{(X_1,M_1),\ldots,(X_r,M_r)\} Q = {( X 1 , M 1 ) , … , ( X r , M r )} where r = k t O ( 1 ) k / d r = k^{t^{O(1)}k/d} r = k t O ( 1 ) k / d and X 1 , … , X r , M 1 , … , M r ⊆ V ( G ) X_1,\ldots,X_r,M_1,\ldots,M_r \subseteq V(G) X 1 , … , X r , M 1 , … , M r ⊆ V ( G ) satisfy the following conditions:
(i) tw ( G − ( X i ∪ M i ) ) ≤ t \operatorname{tw}(G-(X_i \cup M_i)) \leq t tw ( G − ( X i ∪ M i )) ≤ t and ∣ M i ∣ = O ( t 2 log t ⋅ k ) |M_i| = O(t^2 \log t \cdot k) ∣ M i ∣ = O ( t 2 log t ⋅ k ) for all i ∈ [ r ] i \in[r] i ∈ [ r ] ,
(ii) M i M_i M i is an O ( d + t ) O(d+t) O ( d + t ) -core of G − X i G-X_i G − X i for all i ∈ [ r ] i \in[r] i ∈ [ r ] ,
(iii) G [ M i ] G[M_i] G [ M i ] is d d d -degenerate for i ∈ [ r ] i \in[r] i ∈ [ r ] ,
(iv) for every treewidth-t t t modulator S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) of G G G satisfying ∣ S ∣ ≤ k |S| \leq k ∣ S ∣ ≤ k , there exists an index i ∈ [ r ] i \in[r] i ∈ [ r ] such that X i ⊆ S X_i \subseteq S X i ⊆ S .
The algorithm of Theorem 4.1 is the same as the one in the above lemma, which returns X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } extracted from the collection Q = { ( X 1 , M 1 ) , … , ( X r , M r ) } \mathcal{Q} = \{(X_1,M_1),\ldots,(X_r,M_r)\} Q = {( X 1 , M 1 ) , … , ( X r , M r )} in the lemma. Note that (iv) of Lemma 4.2 directly implies (ii) of Theorem 4.1. However, the treewidth bound in (i) of Theorem 4.1 only holds when G ∈ C H G \in\mathcal{C}_H G ∈ C H for some fixed H H H , and proving this is way more difficult. To this end, we need to establish several new structural results for induced-minor-free graphs, and apply them together with (i), (ii), (iii) of Lemma 4.2.
To prove Lemma 4.2, we first discuss the sub-routines used in our algorithm. The first one we need is the approximation algorithm for minimum treewidth modulator in Lemma 3.8 ; we denote this algorithm by TwMod ( G , t ) \operatorname{TwMod}(G,t) TwMod ( G , t ) , whose output is a treewidth-t t t modulator of the graph G G G . The second one we need is the algorithm in Corollary 3.6 ; we denote this algorithm by Decompose ( G , M , d , t ) \operatorname{Decompose}(G,M,d,t) Decompose ( G , M , d , t ) , whose output is the collection P \mathcal{P} P in the corollary. Furthermore, we need the algorithm in Lemma 3.7; we denote this algorithm by Closure ( G , Z ) \operatorname{Closure}(G,Z) Closure ( G , Z ) , whose output is the set L ⊆ V ( G ) L \subseteq V(G) L ⊆ V ( G ) in the lemma. Finally, we also need the algorithm in the following lemma, which is a strengthening of a lemma by Korhonen and Lokshtanov [41 ] (see Lemma 5.1 in the arxiv version).
Lemma 4.3 [41 ] . Given a graph G G G with n n n vertices and parameters Δ , t ∈ N \Delta,t \in\mathbb{N} Δ , t ∈ N with Δ ≥ t \Delta\ge t Δ ≥ t , one can compute in n O ( t 2 ⋅ n / Δ ) n^{O(t^{2}\cdot n/\Delta)} n O ( t 2 ⋅ n /Δ ) time a collection A = { A 1 , … , A r } \mathcal{A}=\{A_{1},\ldots,A_{r}\} A = { A 1 , … , A r } where r = n O ( t 2 ⋅ n / Δ ) r=n^{O(t^{2}\cdot n/\Delta)} r = n O ( t 2 ⋅ n /Δ ) and A 1 , … , A r ⊆ V ( G ) A_{1},\ldots,A_{r}\subseteq V(G) A 1 , … , A r ⊆ V ( G ) satisfy the following conditions:
(i) for each i ∈ [ r ] i\in[r] i ∈ [ r ] , there exists B i ⊆ V ( G ) \ A i B_{i}\subseteq V(G)\backslash A_{i} B i ⊆ V ( G ) \ A i such that
G [ B i ] G[B_{i}] G [ B i ] is t t t -degenerate,
the degree of every vertex v ∈ V ( G ) \ ( A i ∪ B i ) v\in V(G)\backslash(A_{i}\cup B_{i}) v ∈ V ( G ) \ ( A i ∪ B i ) in G − A i G-A_{i} G − A i is at most Δ \Delta Δ ,
in particular, G − A i G-A_{i} G − A i is Δ \Delta Δ -degenerate,
(ii) for every subset S ⊆ V ( G ) S\subseteq V(G) S ⊆ V ( G ) satisfying that and G − S G-S G − S is t t t -degenerate, there exists an index i ∈ [ r ] i\in[r] i ∈ [ r ] such that A i ⊆ S A_{i}\subseteq S A i ⊆ S .
The lemma can be proved in very much the same way as [41 Lemma 5.1] ; for completeness, we give a proof in Appendix § 7 . We denote the algorithm in the lemma by Degen( G , Δ , t ) (G,\Delta,t) ( G , Δ , t ) , whose output is the collection A \mathcal{A} A in the lemma.
Now we are ready to discuss the branching algorithm of Lemma 4.2, which is presented in Algorithm 1. First, we apply Lemma 3.8 to compute a treewidth-t t t modulator M i n i t M_{\mathrm{init}} M init of the graph G G G . The desired collection Q Q Q is computed via a recursive procedure Branch, which is the technical core of our algorithm. Each call of Branch has two arguments, X X X and M M M , which are disjoint subsets of V ( G ) V(G) V ( G ) . We set Q = Branch ( X = ∅ , M = M i n i t ) Q=\operatorname{Branch}(X=\emptyset,M=M_{\mathrm{init}}) Q = Branch ( X = ∅ , M = M init ) .
Next, we explain how Branch ( X , M ) \operatorname{Branch}(X,M) Branch ( X , M ) works. If ∣ X ∣ > k |X|>k ∣ X ∣ > k , then it simply returns the empty collection ∅ \emptyset ∅ . Otherwise, we apply Corollary 3.6 to compute P = Decompose ( G − X , M , d , t ) P=\operatorname{Decompose}(G-X,M,d,t) P = Decompose ( G − X , M , d , t ) , which satisfies the four conditions in the corollary. Each element in P P P is a pair ( V , Z ) (V,Z) ( V , Z ) , where V , Z ⊆ V ( G ) \ M V,Z\subseteq V(G)\backslash M V , Z ⊆ V ( G ) \ M . The algorithm distinguishes two cases: ∣ P ∣ ≤ ∣ M ∣ + k |P|\le|M|+k ∣ P ∣ ≤ ∣ M ∣ + k and ∣ P ∣ > ∣ M ∣ + k |P|>|M|+k ∣ P ∣ > ∣ M ∣ + k . The former case corresponds to line 7-11 and the latter case corresponds to line 12-17 in Algorithm 1.
If ∣ P ∣ ≤ ∣ M ∣ + k |P|\le|M|+k ∣ P ∣ ≤ ∣ M ∣ + k , the procedure Branch will directly construct a collection Q Q Q and return it, as follows. First, we apply Lemma 3.7 to compute L = Closure ( G − ( X ∪ M ) , ⋃ ( V , Z ) ∈ P Z ) L=\operatorname{Closure}(G-(X\cup M),\bigcup_{(V,Z)\in P}Z) L = Closure ( G − ( X ∪ M ) , ⋃ ( V , Z ) ∈ P Z ) , which is a subset of V ( G ) \ ( X ∪ M ) V(G)\backslash(X\cup M) V ( G ) \ ( X ∪ M ) that contains ⋃ ( V , Z ) ∈ P Z \bigcup_{(V,Z)\in P}Z ⋃ ( V , Z ) ∈ P Z . Then Lemma 4.3 is applied to compute A = Degen ( G [ M ∪ L ] , d , t ) \mathcal{A}=\operatorname{Degen}(G[M\cup L],d,t) A = Degen ( G [ M ∪ L ] , d , t ) , which is a collection of subsets of M ∪ L M\cup L M ∪ L . The collection Q Q Q to be returned consists of pairs ( X ∪ A , ( M ∪ L ) \ A ) (X\cup A,(M\cup L)\backslash A) ( X ∪ A , ( M ∪ L ) \ A ) for all A ∈ A A\in\mathcal{A} A ∈ A .
On the other hand, if ∣ P ∣ > ∣ M ∣ + k |P|>|M|+k ∣ P ∣ > ∣ M ∣ + k , we need to recursively call Branch ( X ∪ X ′ , M \ X ′ ) \operatorname{Branch}(X\cup X',M\backslash X') Branch ( X ∪ X ′ , M \ X ′ ) for several subsets X ′ ⊆ M X'\subseteq M X ′ ⊆ M . Specifically, we take a sub-collection P ′ ⊆ P P'\subseteq P P ′ ⊆ P of size ∣ M ∣ + k |M|+k ∣ M ∣ + k . We consider all pairs ( V , Z ) ∈ P ′ (V,Z)\in P' ( V , Z ) ∈ P ′ . For each ( V , Z ) ∈ P ′ (V,Z)\in P' ( V , Z ) ∈ P ′ , we call Branch ( X ∪ X ′ , M \ X ′ ) \operatorname{Branch}(X\cup X',M\backslash X') Branch ( X ∪ X ′ , M \ X ′ ) for all subsets X ′ ⊆ N G ( V ) ∩ M X'\subseteq N_{G}(V)\cap M X ′ ⊆ N G ( V ) ∩ M satisfying ∣ ( N G ( V ) ∩ M ) \ X ′ ∣ ≤ 2 t |(N_{G}(V)\cap M)\backslash X'|\le2t ∣ ( N G ( V ) ∩ M ) \ X ′ ∣ ≤ 2 t . The collection Q Q Q to be returned is the union of the collections returned by these recursive calls.
To analyze Algorithm 1, let T r e c T_{\mathrm{rec}} T rec be the recurrence tree of the call Branch ( ∅ , M i n i t ) \operatorname{Branch}(\emptyset,M_{\mathrm{init}}) Branch ( ∅ , M init ) in line 2 of Algorithm 1. The root of T r e c T_{\mathrm{rec}} T rec corresponds to the initial call, and each non-root node of T r e c T_{\mathrm{rec}} T rec corresponds to a recursive call of Branch. For a node x ∈ V ( T r e c ) x\in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) , we denote by X x X_{x} X x and M x M_{x} M x the arguments X X X and M M M of the call corresponding to x x x , respectively. Thus, X r t = ∅ X_{\mathrm{rt}}=\emptyset X rt = ∅ and M r t = M i n i t M_{\mathrm{rt}}=M_{\mathrm{init}} M rt = M init for the root rt of T r e c T_{\mathrm{rec}} T rec . Also, let Q x Q_{x} Q x denote the collection returned by Branch ( X x , M x ) \operatorname{Branch}(X_{x},M_{x}) Branch ( X x , M x ) . Clearly, if x x x is a non-leaf node, then Q x = ⋃ y ∈ ch ( x ) Q y Q_{x}=\bigcup_{y\in\operatorname{ch}(x)}Q_{y} Q x = ⋃ y ∈ ch ( x ) Q y , where ch ( x ) \operatorname{ch}(x) ch ( x ) is the set of the children of x x x . As such, the final collection Q Q Q returned by Algorithm 1 is just Q = ⋃ x ∈ V ( T r e c ) Q x Q=\bigcup_{x\in V(T_{\mathrm{rec}})}Q_{x} Q = ⋃ x ∈ V ( T rec ) Q x .
Observation 4.4. X x ∩ M x = ∅ X_{x}\cap M_{x}=\emptyset X x ∩ M x = ∅ and X x ∪ M x = M i n i t X_{x}\cup M_{x}=M_{\mathrm{init}} X x ∪ M x = M init for all x ∈ V ( T r e c ) x\in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) .
Proof. Consider a call Branch ( X , M ) \operatorname{Branch}(X,M) Branch ( X , M ) . All its recursive calls are of the form Branch ( X ∪ X ′ , M \ X ′ ) \operatorname{Branch}(X\cup X',M\backslash X') Branch ( X ∪ X ′ , M \ X ′ ) , where X ′ ⊆ M X'\subseteq M X ′ ⊆ M . Thus, if X x ∩ M x = ∅ X_{x}\cap M_{x}=\emptyset X x ∩ M x = ∅ and X x ∪ M x = M i n i t X_{x}\cup M_{x}=M_{\mathrm{init}} X x ∪ M x = M init for a node x ∈ V ( T r e c ) x\in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) , then X y ∩ M y = ∅ X_{y}\cap M_{y}=\emptyset X y ∩ M y = ∅ and X y ∪ M y = M i n i t X_{y}\cup M_{y}=M_{\mathrm{init}} X y ∪ M y = M init for all children of x x x in T r e c T_{\mathrm{rec}} T rec . The root rt of T r e c T_{\mathrm{rec}} T rec clearly satisfies X r t ∩ M r t = ∅ X_{\mathrm{rt}}\cap M_{\mathrm{rt}}=\emptyset X rt ∩ M rt = ∅ and X r t ∪ M r t = M i n i t X_{\mathrm{rt}}\cup M_{\mathrm{rt}}=M_{\mathrm{init}} X rt ∪ M rt = M init . As such, we have the property for all x ∈ V ( T r e c ) x\in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) . □ \square □
Algorithm 1 Core(G , k , d , t G,k,d,t G , k , d , t )
1: M i n i t ← TwMod ( G , t ) M_{\mathrm{init}} \leftarrow\operatorname{TwMod}(G,t) M init ← TwMod ( G , t ) ▷ Lemma 3.8 2: Q ← Branch ( ∅ , M i n i t ) Q \leftarrow\operatorname{Branch}(\emptyset,M_{\mathrm{init}}) Q ← Branch ( ∅ , M init ) 3: return Q Q Q 4: function Branch ( X , M ) \operatorname{Branch}(X,M) Branch ( X , M ) 5: if ∣ X ∣ > k |X|>k ∣ X ∣ > k then return ∅ \emptyset ∅ 6: end if 7: P ← Decompose ( G − X , M , d , t ) \mathcal{P} \leftarrow\operatorname{Decompose}(G-X,M,d,t) P ← Decompose ( G − X , M , d , t ) ▷ Corollary 3.6 8: if ∣ P ∣ ≤ ∣ M ∣ + k |\mathcal{P}|\leq|M|+k ∣ P ∣ ≤ ∣ M ∣ + k then 9: L ← Closure ( G − ( X ∪ M ) , ⋃ ( V , Z ) ∈ P Z ) L \leftarrow\operatorname{Closure}\left(G-(X\cup M),\bigcup_{(V,Z)\in\mathcal{P}}Z\right) L ← Closure ( G − ( X ∪ M ) , ⋃ ( V , Z ) ∈ P Z ) ▷ Lemma 3.7 10: A ← Degen ( G [ M ∪ L ] , d , t ) \mathcal{A} \leftarrow\operatorname{Degen}(G[M\cup L],d,t) A ← Degen ( G [ M ∪ L ] , d , t ) ▷ Lemma 4.3 11: Q ← { ( X ∪ A , ( M ∪ L ) ∖ A ) : A ∈ A } Q \leftarrow\{(X\cup A,(M\cup L)\setminus A):A\in\mathcal{A}\} Q ← {( X ∪ A , ( M ∪ L ) ∖ A ) : A ∈ A } 12: return Q Q Q 13: else 14: P ′ ← \mathcal{P}' \leftarrow P ′ ← a sub-collection of P \mathcal{P} P with size ∣ M ∣ + k |M|+k ∣ M ∣ + k 15: Q ← ∅ Q \leftarrow\emptyset Q ← ∅ 16: for every ( V , Z ) ∈ P ′ (V,Z)\in\mathcal{P}' ( V , Z ) ∈ P ′ do 17: for every X ′ ⊆ N G ( V ) ∩ M X'\subseteq N_G(V)\cap M X ′ ⊆ N G ( V ) ∩ M satisfying ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t |(N_G(V)\cap M)\setminus X'|\leq2t ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t do 18: Q ← Q ∪ Branch ( X ∪ X ′ , M ∖ X ′ ) Q \leftarrow Q\cup\operatorname{Branch}(X\cup X',M\setminus X') Q ← Q ∪ Branch ( X ∪ X ′ , M ∖ X ′ ) 19: end for 20: end for 21: return Q Q Q 22: end if 23: end function
Observation 4.5. Let x x x be a node at the ℓ \ell ℓ -th level of T r e c T_{\mathrm{rec}} T rec . Then ∣ X x ∣ ≥ ℓ ( d − 2 t ) |X_x|\geq\ell(d-2t) ∣ X x ∣ ≥ ℓ ( d − 2 t ) .
Proof. We apply induction on ℓ \ell ℓ . When ℓ = 0 \ell=0 ℓ = 0 , the statement trivially holds. Assume that for all nodes x x x at the ( ℓ − 1 ) (\ell-1) ( ℓ − 1 ) -th level of T r e c T_{\mathrm{rec}} T rec , ∣ X x ∣ ≥ ( ℓ − 1 ) ( d − 2 t ) |X_x|\geq(\ell-1)(d-2t) ∣ X x ∣ ≥ ( ℓ − 1 ) ( d − 2 t ) . To prove the statement for the nodes at the ℓ \ell ℓ -th level, consider a node x x x at the ( ℓ − 1 ) (\ell-1) ( ℓ − 1 ) -th level and we need to show ∣ X y ∣ ≥ ℓ ( d − 2 t ) |X_y|\geq\ell(d-2t) ∣ X y ∣ ≥ ℓ ( d − 2 t ) for all children y y y of x x x . Note that for each child y y y of x x x , we have X y = X x ∪ X ′ X_y=X_x\cup X' X y = X x ∪ X ′ for some X ′ X' X ′ chosen in line 16 of the call the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) . So it suffices to show ∣ X ′ ∣ ≥ d − 2 t |X'|\geq d-2t ∣ X ′ ∣ ≥ d − 2 t for all X ′ X' X ′ chosen in line 16. By (ii) of Corollary 3.6 , ∣ N G ( V ) ∩ M ∣ > d |N_G(V)\cap M|>d ∣ N G ( V ) ∩ M ∣ > d for all ( V , Z ) ∈ P (V,Z)\in\mathcal{P} ( V , Z ) ∈ P where P \mathcal{P} P is the collection computed in line 6. Since X ′ X' X ′ is a subset of N G ( V ) ∩ M N_G(V)\cap M N G ( V ) ∩ M for some ( V , Z ) ∈ P ′ ⊆ P (V,Z)\in\mathcal{P}'\subseteq\mathcal{P} ( V , Z ) ∈ P ′ ⊆ P and ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t |(N_G(V)\cap M)\setminus X'|\leq2t ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t as required in line 16, we have ∣ X ′ ∣ ≥ d − 2 t |X'|\geq d-2t ∣ X ′ ∣ ≥ d − 2 t . Therefore, ∣ X y ∣ ≥ ℓ ( d − 2 t ) |X_y|\geq\ell(d-2t) ∣ X y ∣ ≥ ℓ ( d − 2 t ) for all children y y y of x x x .
To prove Lemma 4.2, we first show that the collection Q Q Q satisfy the four desired conditions in the lemma, and then bound the time complexity of the algorithm as well as the size of Q Q Q .
Correctness. To see Q Q Q satisfies the desired conditions, we observe that every element in Q Q Q is generated via line 10 of Algorithm 1 in some call corresponding to a leaf of T r e c T_{\mathrm{rec}} T rec .
To verify condition (i), we want to show tw ( G − ( X ∪ A ∪ M ∪ L ) ) ≤ t \operatorname{tw}(G-(X\cup A\cup M\cup L))\leq t tw ( G − ( X ∪ A ∪ M ∪ L )) ≤ t and ∣ ( M ∪ L ) ∖ A ∣ = O ( t 2 log t ⋅ k ) |(M\cup L)\setminus A|=O(t^{2}\log t\cdot k) ∣ ( M ∪ L ) ∖ A ∣ = O ( t 2 log t ⋅ k ) for all A ∈ A A\in\mathcal{A} A ∈ A whenever the algorithm executes line 10. It suffices to show tw ( G − ( X ∪ M ) ) ≤ t \operatorname{tw}(G-(X\cup M))\leq t tw ( G − ( X ∪ M )) ≤ t and ∣ M ∪ L ∣ = O ( t 2 log t ⋅ k ) |M\cup L|=O(t^{2}\log t\cdot k) ∣ M ∪ L ∣ = O ( t 2 log t ⋅ k ) . We have X ∪ M = M i n i t X\cup M=M_{\mathrm{init}} X ∪ M = M init by Observation 4.4, which implies tw ( G − ( X ∪ M ) ) ≤ t \operatorname{tw}(G-(X\cup M))\leq t tw ( G − ( X ∪ M )) ≤ t since M i n i t M_{\mathrm{init}} M init is a treewidth-t t t modulator of G G G . To bound the size of M ∪ L M\cup L M ∪ L , note that ∣ M ∣ ≤ ∣ M i n i t ∣ = O ( k log t ) |M|\leq|M_{\mathrm{init}}|=O(k\log t) ∣ M ∣ ≤ ∣ M init ∣ = O ( k log t ) by Observation 4.4 and Lemma 3.8 . By (iii) of Corollary 3.6 , the collection P \mathcal{P} P constructed in line 6 satisfies ∣ Z ∣ = O ( t ) |Z| = O(t) ∣ Z ∣ = O ( t ) for all ( V , Z ) ∈ P (V,Z) \in\mathcal{P} ( V , Z ) ∈ P . Since line 10 is only executed when ∣ P ∣ ≤ ∣ M ∣ + k |\mathcal{P}| \leq|\mathcal{M}| + k ∣ P ∣ ≤ ∣ M ∣ + k , we further have ∣ ⋃ ( V , Z ) ∈ P Z ∣ = O ( t ( ∣ M ∣ + k ) ) = O ( t log t ⋅ k ) \left|\bigcup_{(V,Z)\in\mathcal{P}} Z\right| = O(t(|\mathcal{M}| + k)) = O(t\log t \cdot k) ⋃ ( V , Z ) ∈ P Z = O ( t ( ∣ M ∣ + k )) = O ( t log t ⋅ k ) . Then by Lemma 3.7, ∣ L ∣ = O ( t ∣ ⋃ ( V , Z ) ∈ P Z ∣ ) = O ( t 2 log t ⋅ k ) |L| = O\left(t\left|\bigcup_{(V,Z)\in\mathcal{P}} Z\right|\right) = O(t^2\log t \cdot k) ∣ L ∣ = O ( t ⋃ ( V , Z ) ∈ P Z ) = O ( t 2 log t ⋅ k ) , because tw ( G − ( X ∪ M ) ) ≤ t \operatorname{tw}(G - (X \cup M)) \leq t tw ( G − ( X ∪ M )) ≤ t . Therefore, ∣ M ∪ L ∣ = O ( t 2 log t ⋅ k ) |M \cup L| = O(t^2\log t \cdot k) ∣ M ∪ L ∣ = O ( t 2 log t ⋅ k ) . Condition (i) holds.
To verify condition (ii), we need to show that ( M ∪ L ) ∖ A (M \cup L)\setminus A ( M ∪ L ) ∖ A is an O ( d + t ) O(d+t) O ( d + t ) -core of G − ( X ∪ A ) G - (X \cup A) G − ( X ∪ A ) for all A ∈ A A \in\mathcal{A} A ∈ A when executing line 10. Again, consider the collection P \mathcal{P} P constructed in line 6. By (iv) of Corollary 3.6 , M M M is a d d d -core of G − ( X ∪ ( ⋃ ( V , Z ) ∈ P Z ) ) G - \left(X \cup\left(\bigcup_{(V,Z)\in\mathcal{P}} Z\right)\right) G − ( X ∪ ( ⋃ ( V , Z ) ∈ P Z ) ) , and thus a d d d -core of G − ( X ∪ L ) G - (X \cup L) G − ( X ∪ L ) . Exploiting the fact tw ( G − ( X ∪ M ) ) ≤ t \operatorname{tw}(G - (X \cup M)) \leq t tw ( G − ( X ∪ M )) ≤ t , we see L L L is an O ( t ) O(t) O ( t ) -core of G − ( X ∪ M ) G - (X \cup M) G − ( X ∪ M ) by Lemma 3.7. Therefore, M ∪ L M \cup L M ∪ L is an O ( d + t ) O(d+t) O ( d + t ) -core of G − X G-X G − X by Lemma 3.2 . Now Lemma 3.1 further implies that ( M ∪ L ) ∖ A (M \cup L)\setminus A ( M ∪ L ) ∖ A is an O ( d + t ) O(d+t) O ( d + t ) -core of G − ( X ∪ A ) G - (X \cup A) G − ( X ∪ A ) for all A ∈ A A \in\mathcal{A} A ∈ A . So condition (ii) holds.
To verify condition (iii), we need to show that G [ ( M ∪ L ) ∖ A ] G[(M \cup L)\setminus A] G [( M ∪ L ) ∖ A ] is d d d -degenerate for all A ∈ A A \in\mathcal{A} A ∈ A when executing line 10. This directly follows from (i) of Lemma 4.3 , since A = Degen ( G [ M ∪ L ] , d , t ) \mathcal{A} = \operatorname{Degen}(G[M \cup L],d,t) A = Degen ( G [ M ∪ L ] , d , t ) , i.e., we apply the algorithm of Lemma 4.3 on the graph G [ M ∪ L ] G[M \cup L] G [ M ∪ L ] with Δ = d \Delta= d Δ = d .
Finally, we verify condition (iv). Let S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) be a treewidth-t t t modulator of G G G with ∣ S ∣ ≤ k |S| \leq k ∣ S ∣ ≤ k . We need to show there exists ( X , M ) ∈ Q (X,M) \in Q ( X , M ) ∈ Q such that X ⊆ S X \subseteq S X ⊆ S . We say a node x ∈ V ( T r e c ) x \in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) is S S S -good if X x ⊆ S X_x \subseteq S X x ⊆ S . The following observations for S S S -good nodes is crucial.
Observation 4.6. For an S S S -good node x ∈ V ( T r e c ) x \in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) , either the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) returns in line 11 or x x x has a child in T r e c T_{\mathrm{rec}} T rec that is also S S S -good.
Proof. Since x x x is S S S -good, we have ∣ X x ∣ ≤ ∣ S ∣ ≤ k |X_x| \leq|S| \leq k ∣ X x ∣ ≤ ∣ S ∣ ≤ k . Thus, Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) cannot return in line 5. Assume it does not return in line 11 either. We want to show that x x x has an S S S -good child. Consider the collection P \mathcal{P} P computed in line 6 in the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) . Since the call does not return in line 11, we have ∣ P ∣ > ∣ M ∣ + k |\mathcal{P}| > |M| + k ∣ P ∣ > ∣ M ∣ + k . In line 13, we construct the subset P ′ ⊆ P \mathcal{P}' \subseteq\mathcal{P} P ′ ⊆ P of size ∣ M ∣ + k |M| + k ∣ M ∣ + k . Write P ′ = { ( V 1 , Z 1 ) , … , ( V ∣ M ∣ + k , Z ∣ M ∣ + k ) } \mathcal{P}' = \{(V_1,Z_1),\ldots,(V_{|M|+k},Z_{|M|+k})\} P ′ = {( V 1 , Z 1 ) , … , ( V ∣ M ∣ + k , Z ∣ M ∣ + k )} . By (i) of Corollary 3.6 , V 1 , … , V ∣ M ∣ + k V_1,\ldots,V_{|M|+k} V 1 , … , V ∣ M ∣ + k are disjoint. Since ∣ S ∣ ≤ k |S| \leq k ∣ S ∣ ≤ k , S S S intersects at most k k k sets among V 1 , … , V ∣ M ∣ + k V_1,\ldots,V_{|M|+k} V 1 , … , V ∣ M ∣ + k . Without loss of generality, we can assume V i ∩ S = ∅ V_i \cap S = \varnothing V i ∩ S = ∅ for all i ∈ [ ∣ M ∣ ] i \in[|M|] i ∈ [ ∣ M ∣ ] . By (ii) of Corollary 3.6 , G [ V i ] G[V_i] G [ V i ] is connected for all i ∈ [ ∣ M ∣ ] i \in[|M|] i ∈ [ ∣ M ∣ ] . Let H H H be the graph obtained from G G G by contracting each V i V_i V i into a single vertex v i v_i v i for i ∈ [ ∣ M ∣ ] i \in[|M|] i ∈ [ ∣ M ∣ ] . Note that H − S H-S H − S is a minor of G − S G-S G − S , and thus tw ( H − S ) ≤ t \operatorname{tw}(H-S) \leq t tw ( H − S ) ≤ t . Define H ′ = H [ ( M ∖ S ) ∪ { v 1 , … , v ∣ M ∣ } ] H' = H[(M\setminus S) \cup\{v_1,\ldots,v_{|M|}\}] H ′ = H [( M ∖ S ) ∪ { v 1 , … , v ∣ M ∣ }] . We have ∣ V ( H ′ ) ∣ ≤ 2 ∣ M ∣ |V(H')| \leq2|M| ∣ V ( H ′ ) ∣ ≤ 2∣ M ∣ and tw ( H ′ ) ≤ t \operatorname{tw}(H') \leq t tw ( H ′ ) ≤ t . Therefore, ∣ E ( H ′ ) ∣ ≤ 2 t ∣ M ∣ |E(H')| \leq2t|M| ∣ E ( H ′ ) ∣ ≤ 2 t ∣ M ∣ . Observe that ∑ i = 1 ∣ M ∣ ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ = ∑ i = 1 ∣ M ∣ ∣ N H ′ ( v i ) ∩ ( M ∖ S ) ∣ ≤ ∣ E ( H ′ ) ∣ \sum_{i=1}^{|M|} |(N_{H'}(v_i) \cap M)\setminus S| = \sum_{i=1}^{|M|} |N_{H'}(v_i) \cap(M\setminus S)| \leq|E(H')| ∑ i = 1 ∣ M ∣ ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ = ∑ i = 1 ∣ M ∣ ∣ N H ′ ( v i ) ∩ ( M ∖ S ) ∣ ≤ ∣ E ( H ′ ) ∣ . As such, there exists i ∈ [ ∣ M ∣ ] i \in[|M|] i ∈ [ ∣ M ∣ ] such that ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ ≤ ∣ E ( H ′ ) ∣ / ∣ M ∣ ≤ 2 t |(N_{H'}(v_i) \cap M)\setminus S| \leq|E(H')|/|M| \leq2t ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ ≤ ∣ E ( H ′ ) ∣/∣ M ∣ ≤ 2 t . Note that N H ′ ( v i ) ∩ M = N G ( V i ) ∩ M N_{H'}(v_i) \cap M = N_G(V_i) \cap M N H ′ ( v i ) ∩ M = N G ( V i ) ∩ M . Let X ′ = N G ( V i ) ∩ M ∩ S X' = N_G(V_i) \cap M \cap S X ′ = N G ( V i ) ∩ M ∩ S . We then have
∣ ( N G ( V i ) ∩ M ) ∖ X ′ ∣ = ∣ ( N G ( V i ) ∩ M ) ∖ S ∣ = ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ ≤ 2 t . |(N_G(V_i) \cap M)\setminus X'| = |(N_G(V_i) \cap M)\setminus S| = |(N_{H'}(v_i) \cap M)\setminus S| \leq2t. ∣ ( N G ( V i ) ∩ M ) ∖ X ′ ∣ = ∣ ( N G ( V i ) ∩ M ) ∖ S ∣ = ∣ ( N H ′ ( v i ) ∩ M ) ∖ S ∣ ≤ 2 t . Hence, when we take ( V i , Z i ) ∈ P ′ (V_i,Z_i) \in\mathcal{P}' ( V i , Z i ) ∈ P ′ in line 15, the set X ′ X' X ′ is considered in line 16, which implies that there exists a child y y y of x x x in T r e c T_{\mathrm{rec}} T rec with X y = X x ∪ X ′ X_y = X_x \cup X' X y = X x ∪ X ′ . We have X x ⊆ S X_x \subseteq S X x ⊆ S and X ′ ⊆ S X' \subseteq S X ′ ⊆ S by construction. It follows that X y ⊆ S X_y \subseteq S X y ⊆ S and y y y is S S S -good.
Observation 4.7. If a leaf x x x of T r e c T_{\mathrm{rec}} T rec is S S S -good, then there exists ( X , M ) ∈ Q x (X,M) \in Q_x ( X , M ) ∈ Q x such that X ⊆ S X \subseteq S X ⊆ S .
Proof. Consider the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) . As a leaf, x x x does not have any children in T r e c T_{\mathrm{rec}} T rec . Observation 4.6 then implies that Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) returns in line 11. In line 8, we apply Lemma 3.7 on G − ( X x ∪ M x ) G-(X_x\cup M_x) G − ( X x ∪ M x ) , and the set L L L returned is a subset of V ( G ) ∖ ( X x ∪ M x ) V(G)\setminus(X_x\cup M_x) V ( G ) ∖ ( X x ∪ M x ) . Then in line 9, we apply Lemma 4.3 on the graph G [ M x ∪ L ] G[M_x\cup L] G [ M x ∪ L ] , and the collection A \mathcal{A} A returned consists of subsets of M x ∪ L M_x\cup L M x ∪ L . As S S S is a treewidth-t t t modulator of G G G , tw ( G − S ) ≤ t \operatorname{tw}(G-S) \leq t tw ( G − S ) ≤ t and thus G − S G-S G − S is t t t -degenerate. It follows that G [ M x ∪ L ] − ( S ∩ ( M x ∪ L ) ) G[M_x\cup L]-(S\cap(M_x\cup L)) G [ M x ∪ L ] − ( S ∩ ( M x ∪ L )) is also t t t -degenerate. Therefore, (ii) of Lemma 4.3 implies there exists A ∈ A A \in\mathcal{A} A ∈ A such that A ⊆ S ∩ ( M x ∪ L ) ⊆ S A \subseteq S\cap(M_x\cup L) \subseteq S A ⊆ S ∩ ( M x ∪ L ) ⊆ S . Since x x x is S S S -good, we have X x ⊆ S X_x \subseteq S X x ⊆ S and hence X x ∪ A ⊆ S X_x\cup A \subseteq S X x ∪ A ⊆ S . Note that ( X x ∪ A , ( M x ∪ L ) ∖ A ) ∈ Q x (X_x\cup A,(M_x\cup L)\setminus A) \in Q_x ( X x ∪ A , ( M x ∪ L ) ∖ A ) ∈ Q x by line 10, which completes the proof.
:::`
To see Q \mathcal{Q} Q consists of a pair ( X , M ) (X,M) ( X , M ) satisfying X ⊆ S X \subseteq S X ⊆ S , observe that T r e c T_{\mathrm{rec}} T rec contains at least one node that is S S S -good, simply because the root of T r e c T_{\mathrm{rec}} T rec is S S S -good. Let x x x be a lowest S S S -good node in T r e c T_{\mathrm{rec}} T rec . By definition, x x x does not have any S S S -good child. Observation 4.6 implies that the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) returns in line 9 and thus x x x is a leaf of T r e c T_{\mathrm{rec}} T rec . Then by Observation 4.7, there exists ( X , M ) ∈ Q x (X,M) \in\mathcal{Q}_x ( X , M ) ∈ Q x such that X ⊆ S X \subseteq S X ⊆ S . Since Q x ⊆ Q \mathcal{Q}_x \subseteq\mathcal{Q} Q x ⊆ Q , condition (iv) holds.
Time complexity. Next, we analyze the time complexity of Algorithm 1 and the size of the returned collection Q \mathcal{Q} Q . Line 1 takes 2 t O ( 1 ) n O ( 1 ) 2^{t^{O(1)}}n^{O(1)} 2 t O ( 1 ) n O ( 1 ) time by Lemma 3.8. Applying the algorithms of Corollary 3.6 and Lemma 3.7 in each call of Branch \operatorname{Branch} Branch takes 2 O ( t ) n O ( 1 ) 2^{O(t)}n^{O(1)} 2 O ( t ) n O ( 1 ) time. The size of the argument M M M is bounded by ∣ M i n i t ∣ = O ( k log t ) |M_{\mathrm{init}}| = O(k\log t) ∣ M init ∣ = O ( k log t ) . Furthermore, as observed before, the set L L L computed in line 8 is of size O ( t log t ⋅ k ) O(t\log t\cdot k) O ( t log t ⋅ k ) . Therefore, applying the algorithm of Lemma 4.3 in line 9 takes ( t log t ⋅ k ) O ( t 3 log t ⋅ k / d ) n O ( 1 ) (t\log t\cdot k)^{O(t^3\log t\cdot k/d)}n^{O(1)} ( t log t ⋅ k ) O ( t 3 l o g t ⋅ k / d ) n O ( 1 ) time, and the returned collection A \mathcal{A} A is of size ( t log t ⋅ k ) O ( t 3 log t ⋅ k / d ) (t\log t\cdot k)^{O(t^3\log t\cdot k/d)} ( t log t ⋅ k ) O ( t 3 l o g t ⋅ k / d ) . So the time cost of the call Branch ( ∅ , M i n i t ) \operatorname{Branch}(\varnothing,M_{\mathrm{init}}) Branch ( ∅ , M init ) in line 2 can be bounded by k t O ( 1 ) k / d n O ( 1 ) ⋅ ∣ V ( T r e c ) ∣ k^{t^{O(1)}k/d}n^{O(1)}\cdot|V(T_{\mathrm{rec}})| k t O ( 1 ) k / d n O ( 1 ) ⋅ ∣ V ( T rec ) ∣ . In addition, the size of Q x \mathcal{Q}_x Q x for each leaf x x x of T r e c T_{\mathrm{rec}} T rec is bounded by k t O ( 1 ) k / d k^{t^{O(1)}k/d} k t O ( 1 ) k / d , which then implies ∣ Q ∣ = k t O ( 1 ) k / d ⋅ ∣ V ( T r e c ) ∣ |\mathcal{Q}| = k^{t^{O(1)}k/d}\cdot|V(T_{\mathrm{rec}})| ∣ Q ∣ = k t O ( 1 ) k / d ⋅ ∣ V ( T rec ) ∣ . It now suffices to bound ∣ V ( T r e c ) ∣ |V(T_{\mathrm{rec}})| ∣ V ( T rec ) ∣ .
We first notice that the degree of T r e c T_{\mathrm{rec}} T rec is ( k log t ) O ( t ) (k\log t)^{O(t)} ( k log t ) O ( t ) . The collection P ′ \mathcal{P}' P ′ computed in line 13 is of size ∣ M ∣ + k = O ( k log t ) |M|+k = O(k\log t) ∣ M ∣ + k = O ( k log t ) . For each ( V , Z ) ∈ P ′ (V,Z) \in\mathcal{P}' ( V , Z ) ∈ P ′ , the number of X ′ ⊆ N G ( V ) ∩ M X' \subseteq N_G(V)\cap M X ′ ⊆ N G ( V ) ∩ M satisfying ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t |(N_G(V)\cap M)\setminus X'| \leq2t ∣ ( N G ( V ) ∩ M ) ∖ X ′ ∣ ≤ 2 t is bounded by ∣ N G ( V ) ∩ M ∣ O ( t ) ≤ ∣ M ∣ O ( t ) = ( k log t ) O ( t ) |N_G(V)\cap M|^{O(t)} \leq|M|^{O(t)} = (k\log t)^{O(t)} ∣ N G ( V ) ∩ M ∣ O ( t ) ≤ ∣ M ∣ O ( t ) = ( k log t ) O ( t ) . As such, line 17 is executed ( k log t ) O ( t ) (k\log t)^{O(t)} ( k log t ) O ( t ) time in each call of Branch \operatorname{Branch} Branch , and thus the degree of T r e c T_{\mathrm{rec}} T rec is ( k log t ) O ( t ) (k\log t)^{O(t)} ( k log t ) O ( t ) . Next, we show the depth of T r e c T_{\mathrm{rec}} T rec is at most k / ( d − 2 t ) + 1 k/(d-2t)+1 k / ( d − 2 t ) + 1 . If a node x ∈ V ( T r e c ) x \in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) satisfies ∣ X x ∣ > k |X_x|>k ∣ X x ∣ > k , then the call Branch ( X x , M x ) \operatorname{Branch}(X_x,M_x) Branch ( X x , M x ) returns in line 5 and hence x x x must be a leaf of T r e c T_{\mathrm{rec}} T rec . So we have ∣ X x ∣ ≤ k |X_x|\leq k ∣ X x ∣ ≤ k for all internal nodes x ∈ V ( T r e c ) x \in V(T_{\mathrm{rec}}) x ∈ V ( T rec ) . By Observation 4.5, this implies the depth of an internal node in T r e c T_{\mathrm{rec}} T rec is at most k / ( d − 2 t ) k/(d-2t) k / ( d − 2 t ) . Therefore, the depth of T r e c T_{\mathrm{rec}} T rec is at most k / ( d − 2 t ) + 1 = O ( t k / d ) k/(d-2t)+1 = O(tk/d) k / ( d − 2 t ) + 1 = O ( t k / d ) . It follows that ∣ V ( T r e c ) ∣ = k t O ( 1 ) k / d |V(T_{\mathrm{rec}})| = k^{t^{O(1)}k/d} ∣ V ( T rec ) ∣ = k t O ( 1 ) k / d , which completes the proof of Lemma 4.2.
Structural results
We first prove the following structural lemma, which states that when applying the Torso \operatorname{Torso} Torso operation to the complement of an independent set in an induced-minor-free graph, the resulting graph preserves the induced-minor-freeness.
Lemma 4.8. For every graph H H H , there exists a graph H ′ H' H ′ satisfying the following:
For any G ∈ G H G \in\mathcal{G}_H G ∈ G H and any independent set I ⊆ V ( G ) I \subseteq V(G) I ⊆ V ( G ) in G G G , we have Torso ( G , V ( G ) ∖ I ) ∈ G H ′ \operatorname{Torso}(G,V(G)\setminus I) \in\mathcal{G}_{H'} Torso ( G , V ( G ) ∖ I ) ∈ G H ′ .
Proof. Thanks to Lemma 3.11, it suffices to prove the lemma for the case H = K h p H=K_h^p H = K h p for some number h ∈ N h\in\mathbb{N} h ∈ N . Let G ∈ G H G\in\mathcal{G}_H G ∈ G H where H = K h p H=K_h^p H = K h p and I ⊆ V ( G ) I\subseteq V(G) I ⊆ V ( G ) be an independent set in G G G . Define G ′ = Torso ( G , V ( G ) ∖ I ) G'=\operatorname{Torso}(G,V(G)\setminus I) G ′ = Torso ( G , V ( G ) ∖ I ) . We shall show that G ′ ∈ G H G'\in\mathcal{G}_H G ′ ∈ G H . To this end, we define
Ext ( V ) = V ∪ { v ∈ I : N G [ v ] ∩ V ≠ ∅ } , \operatorname{Ext}(V)=V\cup\{v\in I:N_G[v]\cap V\ne\varnothing\}, Ext ( V ) = V ∪ { v ∈ I : N G [ v ] ∩ V = ∅ } ,
for V ⊆ V ( G ) V\subseteq V(G) V ⊆ V ( G ) . We say two sets U , V ⊆ V ( G ) U,V\subseteq V(G) U , V ⊆ V ( G ) touch in G G G (resp., G ′ G' G ′ ) if U ∩ V ≠ ∅ U\cap V\ne\varnothing U ∩ V = ∅ or U U U and V V V are adjacent in G G G (resp., G ′ G' G ′ ). We observe the following good properties of Ext \operatorname{Ext} Ext .
Claim 1. For any V ⊆ V ( G ) V\subseteq V(G) V ⊆ V ( G ) , if G ′ [ V ] G'[V] G ′ [ V ] is connected, then G [ Ext ( V ) ] G[\operatorname{Ext}(V)] G [ Ext ( V )] is connected as well.
Proof of the Claim. It suffices to show that for all u , v ∈ V u,v\in V u , v ∈ V with ( u , v ) ∈ E ( G ′ ) (u,v)\in E(G') ( u , v ) ∈ E ( G ′ ) , u u u and v v v belong to the same connected component of G [ Ext ( V ) ] G[\operatorname{Ext}(V)] G [ Ext ( V )] . If ( u , v ) ∈ E ( G ) (u,v)\in E(G) ( u , v ) ∈ E ( G ) , this is obvious. So suppose ( u , v ) ∉ E ( G ) (u,v)\notin E(G) ( u , v ) ∈ / E ( G ) . Since ( u , v ) ∈ E ( G ′ ) ∖ E ( G ) (u,v)\in E(G')\setminus E(G) ( u , v ) ∈ E ( G ′ ) ∖ E ( G ) and I I I is an independent set, there exists z ∈ I z\in I z ∈ I such that u , v ∈ N G ( z ) u,v\in N_G(z) u , v ∈ N G ( z ) . We have z ∈ Ext ( V ) z\in\operatorname{Ext}(V) z ∈ Ext ( V ) because u , v ∈ V u,v\in V u , v ∈ V . Thus, ( u , z ) (u,z) ( u , z ) and ( z , v ) (z,v) ( z , v ) are edges of G [ Ext ( V ) ] G[\operatorname{Ext}(V)] G [ Ext ( V )] , which implies that u u u and v v v belong to the same connected component of G [ Ext ( V ) ] G[\operatorname{Ext}(V)] G [ Ext ( V )] . ◁
:::
Claim 2. If U , V ⊆ V ( G ) U,V\subseteq V(G) U , V ⊆ V ( G ) do not touch in G ′ G' G ′ , then Ext ( U ) \operatorname{Ext}(U) Ext ( U ) and Ext ( V ) \operatorname{Ext}(V) Ext ( V ) do not touch in G G G .
Proof of the Claim. Assume Ext ( U ) \operatorname{Ext}(U) Ext ( U ) and Ext ( V ) \operatorname{Ext}(V) Ext ( V ) touch in G G G , and we shall show U U U and V V V touch in G ′ G' G ′ . By the assumption, there exist u ∈ Ext ( U ) u\in\operatorname{Ext}(U) u ∈ Ext ( U ) and v ∈ Ext ( v ) v\in\operatorname{Ext}(v) v ∈ Ext ( v ) such that u ∈ N G [ v ] u\in N_G[v] u ∈ N G [ v ] and v ∈ N G [ u ] v\in N_G[u] v ∈ N G [ u ] . If u ∈ U u\in U u ∈ U and v ∈ V v\in V v ∈ V , then U U U and V V V touch in G G G (and thus in G ′ G' G ′ ). Otherwise, at least one of u u u and v v v is in I I I . Without loss of generality, suppose u ∈ I u\in I u ∈ I . Since u ∈ Ext ( U ) u\in\operatorname{Ext}(U) u ∈ Ext ( U ) , we have N G [ u ] ∩ U ≠ ∅ N_G[u]\cap U\ne\varnothing N G [ u ] ∩ U = ∅ . Observe that N G [ u ] ∩ V ≠ ∅ N_G[u]\cap V\ne\varnothing N G [ u ] ∩ V = ∅ as well. Indeed, if v ∈ V v\in V v ∈ V , then v ∈ N G [ u ] ∩ V v\in N_G[u]\cap V v ∈ N G [ u ] ∩ V and thus N G [ u ] ∩ V ≠ ∅ N_G[u]\cap V\ne\varnothing N G [ u ] ∩ V = ∅ . If v ∉ V v\notin V v ∈ / V , then v ∈ I v\in I v ∈ I , which implies v = u v=u v = u , since I I I is an independent set in G G G . Thus, N G [ u ] ∩ V = N G [ v ] ∩ V ≠ ∅ N_G[u]\cap V=N_G[v]\cap V\ne\varnothing N G [ u ] ∩ V = N G [ v ] ∩ V = ∅ . Now N G [ u ] N_G[u] N G [ u ] intersects both U U U and V V V . But N G [ u ] N_G[u] N G [ u ] is a clique in G ′ G' G ′ , which implies U U U and V V V touch in G ′ G' G ′ . ◁
Now we are ready to prove G ′ ∈ G H G'\in\mathcal{G}_H G ′ ∈ G H . Recall that H = K h ∙ H=K_h^\bullet H = K h ∙ . Write X ⊆ V ( H ) X\subseteq V(H) X ⊆ V ( H ) as the set of the h h h clique vertices of H H H and Y ⊆ V ( H ) Y\subseteq V(H) Y ⊆ V ( H ) as the set of the ( h 2 ) \binom{h}{2} ( 2 h ) subdivision vertices of H H H . Assume G ′ G' G ′ contains H H H as an induced minor. We shall construct an H H H -induced-minor of G G G , which contradicts the fact G ∈ G H G\in\mathcal{G}_H G ∈ G H . For each vertex x ∈ V ( H ) x\in V(H) x ∈ V ( H ) , denote by G x ′ G'_x G x ′ as the connected subgraph of G ′ G' G ′ corresponding to x x x in the H H H -induced-minor of G ′ G' G ′ . Without loss of generality, we may assume that each G x ′ G'_x G x ′ is minimal in the sense that no vertex can be removed from G x ′ G'_x G x ′ while keeping the minor structure. With this minimality assumption, for each y ∈ Y y\in Y y ∈ Y with N H ( y ) = { a , b } ⊆ X N_H(y)=\{a,b\}\subseteq X N H ( y ) = { a , b } ⊆ X , G y ′ G'_y G y ′ has to be an induced path ( v 0 , v 1 , … , v r ) (v_0,v_1,\ldots,v_r) ( v 0 , v 1 , … , v r ) in G ′ G' G ′ such that v 0 v_0 v 0 (resp., v r v_r v r ) is adjacent to G a ′ G'_a G a ′ (resp., G b ′ G'_b G b ′ ) and v 1 , … , v r v_1,\ldots,v_r v 1 , … , v r (resp., v 0 , v 1 , … , v r − 1 v_0,v_1,\ldots,v_{r-1} v 0 , v 1 , … , v r − 1 ) are not adjacent to G a ′ G'_a G a ′ (resp., G b ′ G'_b G b ′ ), in G ′ G' G ′ . In particular, for every y ∈ Y y\in Y y ∈ Y and x ∈ X x\in X x ∈ X , at most one vertex of G y ′ G'_y G y ′ is adjacent to G x ′ G'_x G x ′ in G ′ G' G ′ .
Claim 3. V ( G y ′ ) ∩ I = ∅ V(G'_y)\cap I=\varnothing V ( G y ′ ) ∩ I = ∅ for all y ∈ Y y\in Y y ∈ Y .
Proof of the Claim. As observed above, G y ′ G'_y G y ′ is an induced path in G ′ G' G ′ . Assume V ( G y ′ ) ∩ I ≠ ∅ V(G'_y)\cap I\ne\varnothing V ( G y ′ ) ∩ I = ∅ and v ∈ V ( G y ′ ) ∩ I v\in V(G'_y)\cap I v ∈ V ( G y ′ ) ∩ I . Then v v v must be an endpoint of G y ′ G'_y G y ′ . Indeed, if v v v is an internal vertex of G y ′ G'_y G y ′ , then the two neighbors of v v v in G y ′ G'_y G y ′ are contained in N G ( v ) = N G ′ ( v ) N_G(v)=N_{G'}(v) N G ( v ) = N G ′ ( v ) . But N G ( v ) N_G(v) N G ( v ) is a clique in G ′ G' G ′ , which contradicts the fact that G y ′ G'_y G y ′ is an induced path in G ′ G' G ′ . Thus, v v v is an endpoint of G y ′ G'_y G y ′ . Let N H ( y ) = { a , b } ⊆ X N_H(y)=\{a,b\}\subseteq X N H ( y ) = { a , b } ⊆ X . Without loss of generality, assume v v v is adjacent to G a ′ G'_a G a ′ . If v v v is the only vertex of G y ′ G'_y G y ′ , then v v v is also adjacent to G b ′ G'_b G b ′ . As N G ( v ) N_G(v) N G ( v ) is a clique in G ′ G' G ′ , this would imply that G a ′ G'_a G a ′ and G b ′ G'_b G b ′ are adjacent in G ′ G' G ′ , which is impossible as ( a , b ) ∉ E ( H ) (a,b)\notin E(H) ( a , b ) ∈ / E ( H ) . Therefore, v v v has a neighbor v ′ v' v ′ in G y ′ G'_y G y ′ . Now V ( G a ′ ) ∩ N G ( v ) ≠ ∅ V(G'_a)\cap N_G(v)\ne\varnothing V ( G a ′ ) ∩ N G ( v ) = ∅ and v ′ ∈ N G ( v ) v'\in N_G(v) v ′ ∈ N G ( v ) , which implies v ′ v' v ′ is adjacent to G a ′ G'_a G a ′ in G ′ G' G ′ . However, this contradicts the fact that at most one vertex of G y ′ G'_y G y ′ is adjacent to G a ′ G'_a G a ′ . As a result, V ( G y ′ ) ∩ I = ∅ V(G'_y)\cap I=\varnothing V ( G y ′ ) ∩ I = ∅ . ◁
For each x ∈ X x\in X x ∈ X , define P x = Ext ( V ( G x ′ ) ) P_x=\operatorname{Ext}(V(G'_x)) P x = Ext ( V ( G x ′ )) . Since G x ′ G'_x G x ′ is connected for all x ∈ X x\in X x ∈ X , G [ P x ] G[P_x] G [ P x ] is connected for all x ∈ X x\in X x ∈ X by Claim 1. Then for each y ∈ Y y\in Y y ∈ Y , define P y = Ext ( V ( G y ′ ) ) ∖ ⋃ x ∈ X P x P_y=\operatorname{Ext}(V(G'_y))\setminus\bigcup_{x\in X}P_x P y = Ext ( V ( G y ′ )) ∖ ⋃ x ∈ X P x . We show that G [ P y ] G[P_y] G [ P y ] is connected for all y ∈ Y y\in Y y ∈ Y . Clearly, G ′ [ P y ] G'[P_y] G ′ [ P y ] is connected, since G y ′ G'_y G y ′ is connected and all vertices in P y ∖ V ( G y ′ ) P_y\setminus V(G'_y) P y ∖ V ( G y ′ ) are adjacent to V ( G y ′ ) V(G'_y) V ( G y ′ ) in G ′ G' G ′ . So it suffices to show for all u , v ∈ P y u,v\in P_y u , v ∈ P y such that u , v ∈ N G ( z ) u,v\in N_G(z) u , v ∈ N G ( z ) for some z ∈ I z\in I z ∈ I , u u u and v v v lie in the same connected component of G [ P y ] G[P_y] G [ P y ] . Let z ∈ I z\in I z ∈ I and u , v ∈ P y ∩ N G ( v ) u,v\in P_y\cap N_G(v) u , v ∈ P y ∩ N G ( v ) , where u ≠ v u\ne v u = v . Note that z ∈ Ext ( V ( G y ′ ) ) z\in\operatorname{Ext}(V(G'_y)) z ∈ Ext ( V ( G y ′ )) . Thus, if z ∉ ⋃ x ∈ X P x z\notin\bigcup_{x\in X}P_x z ∈ / ⋃ x ∈ X P x , then z ∈ P y z\in P_y z ∈ P y and we are done. Otherwise, z ∈ P x z\in P_x z ∈ P x for some x ∈ X x\in X x ∈ X . We observe that this is impossible. Indeed, if z ∈ P x z\in P_x z ∈ P x , then N G [ z ] ∩ V ( G x ′ ) ≠ ∅ N_{G}[z]\cap V(G'_x)\ne\varnothing N G [ z ] ∩ V ( G x ′ ) = ∅ . Since N G [ z ] N_G[z] N G [ z ] is a clique in G ′ G' G ′ and u , v ∈ N G [ z ] u,v\in N_G[z] u , v ∈ N G [ z ] , we see that both u u u and v v v are adjacent to G x ′ G'_x G x ′ in G ′ G' G ′ , which contradicts our previous observation that at most one vertex in G y ′ G'_y G y ′ is adjacent to G x ′ G'_x G x ′ . As a result, G [ P y ] G[P_y] G [ P y ] is connected for all y ∈ Y y\in Y y ∈ Y .
In the H H H -induced-minor of G G G we are going to construct, each vertex x ∈ V ( H ) x\in V(H) x ∈ V ( H ) just corresponds to the (connected) subgraph G [ P x ] G[P_x] G [ P x ] . To see this truly gives us an H H H -induced-minor, we need to show for any different vertices x , y ∈ V ( H ) x,y\in V(H) x , y ∈ V ( H ) ,
P x ∩ P y = ∅ P_x\cap P_y=\varnothing P x ∩ P y = ∅ ,
(ii) P x P_x P x and P y P_y P y are adjacent in G G G iff ( x , y ) ∈ E ( H ) (x,y) \in E(H) ( x , y ) ∈ E ( H ) .
If ( x , y ) ∉ E ( H ) (x,y) \notin E(H) ( x , y ) ∈ / E ( H ) , then V ( G x ′ ) V(G'_x) V ( G x ′ ) and V ( G y ′ ) V(G'_y) V ( G y ′ ) do not touch in G ′ G' G ′ . Claim 1 then directly implies P x P_x P x and P y P_y P y do not touch in G G G , because P x = Ext ( V ( G x ′ ) ) P_x = \operatorname{Ext}(V(G'_x)) P x = Ext ( V ( G x ′ )) and P y = Ext ( V ( G y ′ ) ) P_y = \operatorname{Ext}(V(G'_y)) P y = Ext ( V ( G y ′ )) . As such, conditions (i) and (ii) hold in this case. So assume ( x , y ) ∈ E ( H ) (x,y) \in E(H) ( x , y ) ∈ E ( H ) . Then one of x , y x,y x , y belongs to X X X and the other belongs to Y Y Y . Without loss of generality, suppose x ∈ X x \in X x ∈ X and y ∈ Y y \in Y y ∈ Y . Condition (i) directly follows from the construction of P y P_y P y . To see condition (ii), note that V ( G x ′ ) V(G'_x) V ( G x ′ ) and V ( G y ′ ) V(G'_y) V ( G y ′ ) are adjacent in G ′ G' G ′ . Thus, there exist u ∈ V ( G x ′ ) u \in V(G'_x) u ∈ V ( G x ′ ) and v ∈ V ( G y ′ ) v \in V(G'_y) v ∈ V ( G y ′ ) satisfying ( u , v ) ∈ E ( G ′ ) (u,v) \in E(G') ( u , v ) ∈ E ( G ′ ) . By Claim 3, v ∉ I v \notin I v ∈ / I . Since v ∈ V ( G y ′ ) ∖ I v \in V(G'_y) \setminus I v ∈ V ( G y ′ ) ∖ I , v ∉ Ext ( V ( G a ′ ) ) v \notin\operatorname{Ext}(V(G'_a)) v ∈ / Ext ( V ( G a ′ )) for any a ∈ X a \in X a ∈ X , which implies v ∈ P y v \in P_y v ∈ P y . Also, u ∈ V ( G x ′ ) ⊆ P x u \in V(G'_x) \subseteq P_x u ∈ V ( G x ′ ) ⊆ P x . Now if ( u , v ) ∈ E ( G ) (u,v) \in E(G) ( u , v ) ∈ E ( G ) , then P x P_x P x and P y P_y P y are adjacent in G G G . Otherwise, ( u , v ) ∈ E ( G ′ ) ∖ E ( G ) (u,v) \in E(G') \setminus E(G) ( u , v ) ∈ E ( G ′ ) ∖ E ( G ) and thus u , v ∈ N G ( z ) u,v \in N_G(z) u , v ∈ N G ( z ) for some z ∈ I z \in I z ∈ I . We then have z ∈ Ext ( V ( G x ′ ) ) = P x z \in\operatorname{Ext}(V(G'_x)) = P_x z ∈ Ext ( V ( G x ′ )) = P x . This implies P x P_x P x and P y P_y P y are adjacent in G G G , because ( z , v ) ∈ E ( G ) (z,v) \in E(G) ( z , v ) ∈ E ( G ) .
Based on the above discussion, we see that G G G contains H H H as an induced minor, where each vertex x ∈ V ( H ) x \in V(H) x ∈ V ( H ) corresponds to the (connected) subgraph G [ P x ] G[P_x] G [ P x ] . This contradicts the assumption G ∈ G H G \in\mathcal{G}_H G ∈ G H and completes the proof.
The second structural lemma we need is the following, which essentially states that when applying the Torso operation to a bounded-degeneracy core M M M of an induced-minor-free graph, the increase of the number of edges is linear in ∣ M ∣ |M| ∣ M ∣ .
Lemma 4.9. Let H H H be a fixed graph. For any graph G ∈ G H G \in\mathcal{G}_H G ∈ G H and any d d d -core M ⊆ V ( G ) M \subseteq V(G) M ⊆ V ( G ) of G G G such that G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate, we have
∣ E ( Torso ( G , M ) ) ∣ − ∣ E ( G ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . |E(\operatorname{Torso}(G,M))| - |E(G)| = O((d+\Delta)\cdot|M|). ∣ E ( Torso ( G , M )) ∣ − ∣ E ( G ) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) . The constant hidden in O ( ⋅ ) O(\cdot) O ( ⋅ ) only depends on H H H .
Proof. Write E ∗ = E ( Torso ( G , M ) ) ∖ E ( G ) E^* = E(\operatorname{Torso}(G,M)) \setminus E(G) E ∗ = E ( Torso ( G , M )) ∖ E ( G ) . Our goal is to show ∣ E ∗ ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*| = O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) . To this end, our main idea is to construct a random subset E 0 ⊆ E ∗ E_0 \subseteq E^* E 0 ⊆ E ∗ such that E [ ∣ E 0 ∣ ] = O ( ∣ M ∣ / ( d + Δ ) ) \mathbb{E}[|E_0|] = O(|M|/(d+\Delta)) E [ ∣ E 0 ∣ ] = O ( ∣ M ∣/ ( d + Δ )) and Pr [ e ∈ E 0 ] = Ω ( 1 ( d + Δ ) 2 ) \Pr[e \in E_0] = \Omega\left(\frac{1}{(d+\Delta)^2}\right) Pr [ e ∈ E 0 ] = Ω ( ( d + Δ ) 2 1 ) for each edge e ∈ E ∗ e \in E^* e ∈ E ∗ , which will imply ∣ E ∗ ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*| = O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Since G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate, we have an orientation of the edges of G [ M ] G[M] G [ M ] for which the out-degree of every vertex is at most Δ \Delta Δ in G [ M ] G[M] G [ M ] . We denote by Γ ( v ) \Gamma(v) Γ ( v ) the set of out-neighbors of a vertex v ∈ M v \in M v ∈ M in G [ M ] G[M] G [ M ] . Then ∣ Γ ( v ) ∣ ≤ Δ |\Gamma(v)| \leq\Delta ∣Γ ( v ) ∣ ≤ Δ for all v ∈ M v \in M v ∈ M .
Let R ⊆ M R \subseteq M R ⊆ M be a random subset obtained by sampling each vertex v ∈ M v \in M v ∈ M independently with probability p = 1 d + Δ p = \frac{1}{d+\Delta} p = d + Δ 1 . Define I = { v ∈ R : Γ ( v ) ∩ R = ∅ } I = \{v \in R : \Gamma(v) \cap R = \emptyset\} I = { v ∈ R : Γ ( v ) ∩ R = ∅ } . Note that I I I is an independent set in G [ M ] G[M] G [ M ] (and thus in G G G ), because for any u , v ∈ I u,v \in I u , v ∈ I , we have u ∉ Γ ( v ) u \notin\Gamma(v) u ∈ / Γ ( v ) and v ∉ Γ ( u ) v \notin\Gamma(u) v ∈ / Γ ( u ) . Furthermore, for each v ∈ M v \in M v ∈ M , Pr [ v ∈ I ] ≤ p ( 1 − p ) Δ = Θ ( p ) \Pr[v \in I] \leq p(1-p)^{\Delta} = \Theta(p) Pr [ v ∈ I ] ≤ p ( 1 − p ) Δ = Θ ( p ) , since ∣ Γ ( v ) ∣ ≤ Δ |\Gamma(v)| \leq\Delta ∣Γ ( v ) ∣ ≤ Δ . By the linearity of expectation, it follows that E [ ∣ I ∣ ] = Θ ( p ∣ M ∣ ) \mathbb{E}[|I|] = \Theta(p|M|) E [ ∣ I ∣ ] = Θ ( p ∣ M ∣ ) . Write G ′ = G − ( M ∖ I ) G' = G - (M \setminus I) G ′ = G − ( M ∖ I ) . Define G I ′ G'_I G I ′ as the graph with V ( G I ′ ) = I V(G'_I) = I V ( G I ′ ) = I in which two vertices u , v ∈ I u,v \in I u , v ∈ I are connected by an edge if there exists a connected component C C C of G ′ − I G' - I G ′ − I such that N G ( V ( C ) ) ∩ I = { u , v } N_G(V(C)) \cap I = \{u,v\} N G ( V ( C )) ∩ I = { u , v } . Also, define E 0 = E ( G I ′ ) E_0 = E(G'_I) E 0 = E ( G I ′ ) . Since G I ′ ∈ G H G'_I \in\mathcal{G}_H G I ′ ∈ G H , Lemma 3.12 implies that G I ′ G'_I G I ′ is H H H -minor-free and thus ∣ E 0 ∣ = O ( ∣ I ∣ ) |E_0| = O(|I|) ∣ E 0 ∣ = O ( ∣ I ∣ ) by the standard extremal bound for excluded minors [51 ] . Therefore, E [ ∣ E 0 ∣ ] = O ( E [ ∣ I ∣ ] ) = O ( p ∣ M ∣ ) \mathbb{E}[|E_0|] = O(\mathbb{E}[|I|]) = O(p|M|) E [ ∣ E 0 ∣ ] = O ( E [ ∣ I ∣ ]) = O ( p ∣ M ∣ ) .
Consider an edge e = ( u , v ) ∈ E ∗ e = (u,v) \in E^* e = ( u , v ) ∈ E ∗ . Since e ∈ E ( Torso ( G , M ) ) e \in E(\operatorname{Torso}(G,M)) e ∈ E ( Torso ( G , M )) and e ∉ E ( G ) e \notin E(G) e ∈ / E ( G ) , there exists a connected component C C C of G − M G - M G − M such that u , v ∈ N G ( V ( C ) ) u,v \in N_G(V(C)) u , v ∈ N G ( V ( C )) . Since M M M is a d d d -core of G G G , we have ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))| \leq d ∣ N G ( V ( C )) ∣ ≤ d . Note that e ∈ E 0 e \in E_0 e ∈ E 0 if both of the following events happen:
u , v ∈ R u,v \in R u , v ∈ R ,
z ∉ R z \notin R z ∈ / R for all z ∈ Γ ( u ) ∪ Γ ( v ) ∪ ( N G ( V ( C ) ) ∖ { u , v } ) z \in\Gamma(u) \cup\Gamma(v) \cup(N_G(V(C)) \setminus\{u,v\}) z ∈ Γ ( u ) ∪ Γ ( v ) ∪ ( N G ( V ( C )) ∖ { u , v }) .
Since ∣ Γ ( u ) ∪ Γ ( v ) ∣ ≤ 2 Δ |\Gamma(u) \cup\Gamma(v)| \le2\Delta ∣Γ ( u ) ∪ Γ ( v ) ∣ ≤ 2Δ and ∣ N G ( V ( C ) ) ∣ ≤ d |N_G(V(C))| \le d ∣ N G ( V ( C )) ∣ ≤ d , the probability that both events happen is at least p 2 ( 1 − p ) d + 2 Δ = Ω ( p 2 ) p^2(1-p)^{d+2\Delta} = \Omega(p^2) p 2 ( 1 − p ) d + 2Δ = Ω ( p 2 ) , which implies Pr [ e ∈ E 0 ] = Ω ( p 2 ) \Pr[e \in E_0] = \Omega(p^2) Pr [ e ∈ E 0 ] = Ω ( p 2 ) . Thus, ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = Ω ( p 2 ∣ E ∗ ∣ ) \sum_{e\in E^*} \Pr[e \in E_0] = \Omega(p^2|E^*|) ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = Ω ( p 2 ∣ E ∗ ∣ ) . On the other hand, we have ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) \sum_{e\in E^*} \Pr[e \in E_0] = \mathbb{E}[|E_0|] = O(p|M|) ∑ e ∈ E ∗ Pr [ e ∈ E 0 ] = E [ ∣ E 0 ∣ ] = O ( p ∣ M ∣ ) . As a result, it follows that ∣ E ∗ ∣ = O ( ∣ M ∣ / p ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E^*| = O(|M|/p) = O((d+\Delta)\cdot|M|) ∣ E ∗ ∣ = O ( ∣ M ∣/ p ) = O (( d + Δ ) ⋅ ∣ M ∣ ) .
As a consequence of the above two lemmas, we are able to prove the following structural result for induced-minor-free graphs.
Corollary 4.10. Let H H H be a fixed graph and G ∈ G H G \in\mathcal{G}_H G ∈ G H . If there exists a d d d -core M M M of G G G such that G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate and tw ( G − M ) ≤ t \operatorname{tw}(G-M) \le t tw ( G − M ) ≤ t , then tw ( G ) = O ( t + ( d + Δ ) ⋅ ∣ M ∣ ) \operatorname{tw}(G) = O(t+\sqrt{(d+\Delta)\cdot|M|}) tw ( G ) = O ( t + ( d + Δ ) ⋅ ∣ M ∣ ) .
Proof. Write G + = Torso ( G , M ) G^+ = \operatorname{Torso}(G,M) G + = Torso ( G , M ) for convenience. Thanks to Lemma 3.9 , it suffices to prove that tw ( G + [ M ] ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) \operatorname{tw}(G^+[M]) = O(\sqrt{(d+\Delta)\cdot|M|}) tw ( G + [ M ]) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . We first show that ∣ E ( G + [ M ] ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E(G^+[M])| = O((d+\Delta)\cdot|M|) ∣ E ( G + [ M ]) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) . Since G [ M ] G[M] G [ M ] is Δ \Delta Δ -degenerate, ∣ E ( G [ M ] ) ∣ = O ( Δ ∣ M ∣ ) |E(G[M])| = O(\Delta|M|) ∣ E ( G [ M ]) ∣ = O ( Δ∣ M ∣ ) . Furthermore, we have
∣ E ( G + [ M ] ) ∣ − ∣ E ( G [ M ] ) ∣ ≤ ∣ E ( G + ) ∣ − ∣ E ( G ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) , |E(G^+[M])| - |E(G[M])| \le|E(G^+)| - |E(G)| = O((d+\Delta)\cdot|M|), ∣ E ( G + [ M ]) ∣ − ∣ E ( G [ M ]) ∣ ≤ ∣ E ( G + ) ∣ − ∣ E ( G ) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) ,
which follows from Lemma 4.9 . Hence, ∣ E ( G + [ M ] ) ∣ = O ( ( d + Δ ) ⋅ ∣ M ∣ ) |E(G^+[M])| = O((d+\Delta)\cdot|M|) ∣ E ( G + [ M ]) ∣ = O (( d + Δ ) ⋅ ∣ M ∣ ) .
Next, we show that G + [ M ] ∈ G H ′ G^+[M] \in\mathcal{G}_{H'} G + [ M ] ∈ G H ′ for some graph H ′ H' H ′ depending on H H H . Let G ′ G' G ′ be the graph obtained from G G G by contracting each connected component of G − M G-M G − M to a single vertex. We have G ′ ∈ G H G' \in\mathcal{G}_H G ′ ∈ G H . Note that I = V ( G ′ ) ∖ M I = V(G')\setminus M I = V ( G ′ ) ∖ M is an independent set in G ′ G' G ′ . Therefore, Lemma 4.8 implies that Torso ( G ′ , M ) ∈ G H ′ \operatorname{Torso}(G',M) \in\mathcal{G}_{H'} Torso ( G ′ , M ) ∈ G H ′ for some H ′ H' H ′ depending on H H H . Note that Torso ( G ′ , M ) − I = G + [ M ] \operatorname{Torso}(G',M)-I = G^+[M] Torso ( G ′ , M ) − I = G + [ M ] . As such, G + [ M ] ∈ G H ′ G^+[M] \in\mathcal{G}_{H'} G + [ M ] ∈ G H ′ . Lemma 3.10 then implies tw ( G + [ M ] ) = O ( ∣ E ( G + [ M ] ) ∣ ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) \operatorname{tw}(G^+[M]) = O(\sqrt{|E(G^+[M])|}) = O(\sqrt{(d+\Delta)\cdot|M|}) tw ( G + [ M ]) = O ( ∣ E ( G + [ M ]) ∣ ) = O ( ( d + Δ ) ⋅ ∣ M ∣ ) . As a result, tw ( G ) = O ( t + ( d + Δ ) ⋅ ∣ M ∣ ) \operatorname{tw}(G) = O(t+\sqrt{(d+\Delta)\cdot|M|}) tw ( G ) = O ( t + ( d + Δ ) ⋅ ∣ M ∣ ) by Lemma 3.9 .
Putting everything together
With the help of the results obtained in the previous sections, we are now ready to complete the proof of Theorem 4.1.
Theorem 4.1. Let H H H be a fixed graph. Given a graph G ∈ G H G \in\mathcal{G}_H G ∈ G H with n n n vertices and three parameters k , d , t ∈ N k,d,t \in\mathbb{N} k , d , t ∈ N with d > 2 t d > 2t d > 2 t , one can compute in k t O ( 1 ) k / d n O ( 1 ) k^{t^{O(1)}k/d}n^{O(1)} k t O ( 1 ) k / d n O ( 1 ) time a collection X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } of r = k t O ( 1 ) k / d r = k^{t^{O(1)}k/d} r = k t O ( 1 ) k / d subsets of V ( G ) V(G) V ( G ) satisfying the following conditions:
(i) tw ( G − X i ) = t O ( 1 ) k d \operatorname{tw}(G-X_i) = t^{O(1)}\sqrt{kd} tw ( G − X i ) = t O ( 1 ) k d for all i ∈ [ r ] i \in[r] i ∈ [ r ] ,
(ii) for every treewidth-t t t modulator S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) of G G G satisfying ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k , there exists an index i ∈ [ r ] i \in[r] i ∈ [ r ] such that X i ⊆ S X_i \subseteq S X i ⊆ S .
Proof. As mentioned in § 5.1 , our final algorithm simply applies the algorithm of Lemma 4.2 to compute Q = { ( X 1 , M 1 ) , … , ( X r , M r ) } Q = \{(X_1,M_1),\ldots,(X_r,M_r)\} Q = {( X 1 , M 1 ) , … , ( X r , M r )} and returns the collection X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } . By Lemma 4.2, the time complexity is k t O ( 1 ) k / d n O ( 1 ) k^{t^{O(1)}k/d}n^{O(1)} k t O ( 1 ) k / d n O ( 1 ) and r = k t O ( 1 ) k / d r = k^{t^{O(1)}k/d} r = k t O ( 1 ) k / d . Also, condition (ii) of the theorem follows directly from (iv) of Lemma 4.2. Therefore, it suffices to prove condition (i), i.e., tw ( G − X i ) = t O ( 1 ) k d \operatorname{tw}(G-X_i) = t^{O(1)}\sqrt{kd} tw ( G − X i ) = t O ( 1 ) k d for all i ∈ [ r ] i \in[r] i ∈ [ r ] .
Write G i = G − X i G_i = G-X_i G i = G − X i . By (i) of Lemma 4.2, tw ( G i − M i ) ≤ t \operatorname{tw}(G_i-M_i) \le t tw ( G i − M i ) ≤ t and ∣ M i ∣ = O ( t 2 log t ⋅ k ) |M_i| = O(t^2\log t\cdot k) ∣ M i ∣ = O ( t 2 log t ⋅ k ) . Also, M i M_i M i is an O ( d + t ) O(d+t) O ( d + t ) -core of G − X i G-X_i G − X i and G i [ M i ] G_i[M_i] G i [ M i ] is d d d -degenerate, by (ii) and (iii) of Lemma 4.2, respectively. Therefore, Corollary 4.10 implies tw ( G i ) = O ( t + ( d + t ) ⋅ t 2 log t ⋅ k ) = t O ( 1 ) k d \operatorname{tw}(G_i) = O(t+\sqrt{(d+t)\cdot t^2\log t\cdot k}) = t^{O(1)}\sqrt{kd} tw ( G i ) = O ( t + ( d + t ) ⋅ t 2 log t ⋅ k ) = t O ( 1 ) k d .
:::
Dynamic programming
In this section, we consider ( t , ϕ ) (t,\phi) ( t , ϕ ) -DELETION parameterized by the treewidth w = tw ( G ) w = \operatorname{tw}(G) w = tw ( G ) . We introduce an FPT algorithm with running time w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) by standard dynamic programming on a tree decomposition. Combining this algorithm with Theorem 4.1 can already result in the subexponential FPT algorithm in Theorem 1.1. To obtain the QPTAS in Theorem 1.2, however, we need the algorithm to solve a slightly more general version of the problem, which asks for not only an optimal solution of the instance but also the entire DP table.
To present the more general problem, we need to introduce the notion of boundaried graphs and MSO-types . For a set L L L , an L L L -boundaried graph is a pair ( G , η ) (G,\eta) ( G , η ) where G G G is a graph and η : L → V ( G ) \eta: L \to V(G) η : L → V ( G ) is an injective map. We call L L L the boundary label set of G G G . If ( G , η ) (G,\eta) ( G , η ) and ( G ′ , η ′ ) (G',\eta') ( G ′ , η ′ ) are two L L L -boundaried graphs, then we use ( G , η ) ⊕ L ( H , τ ) (G,\eta) \oplus_L (H,\tau) ( G , η ) ⊕ L ( H , τ ) to denote the graph (without boundary) obtained by gluing ( G , η ) (G,\eta) ( G , η ) and ( G ′ , η ′ ) (G',\eta') ( G ′ , η ′ ) as follows. We first take the disjoint union G ⊔ G ′ G \sqcup G' G ⊔ G ′ , and then for each ℓ ∈ L \ell\in L ℓ ∈ L , add an edge e ℓ = ( η ( ℓ ) , η ′ ( ℓ ) ) e_\ell= (\eta(\ell),\eta'(\ell)) e ℓ = ( η ( ℓ ) , η ′ ( ℓ )) to G ⊔ G ′ G \sqcup G' G ⊔ G ′ . After this, we contract all edges e ℓ e_\ell e ℓ for ℓ ∈ L \ell\in L ℓ ∈ L , and the resulting graph is ( G , η ) ⊕ L ( H , τ ) (G,\eta) \oplus_L (H,\tau) ( G , η ) ⊕ L ( H , τ ) .
Let ϕ \phi ϕ be an MSO formula. We define an equivalence relation ∼ ϕ \sim_\phi ∼ ϕ among boundaried graphs as follows: ( G , η ) ∼ ϕ ( G ′ , η ′ ) (G,\eta) \sim_\phi(G',\eta') ( G , η ) ∼ ϕ ( G ′ , η ′ ) if the following conditions hold:
( G , η ) (G,\eta) ( G , η ) and ( G ′ , η ′ ) (G',\eta') ( G ′ , η ′ ) have the same boundary label set L L L ,
for all L L L -boundaried graphs, ( G , η ) ⊕ L ( H , τ ) (G,\eta) \oplus_L (H,\tau) ( G , η ) ⊕ L ( H , τ ) satisfies ϕ \phi ϕ iff ( G ′ , η ′ ) ⊕ L ( H , τ ) (G',\eta') \oplus_L (H,\tau) ( G ′ , η ′ ) ⊕ L ( H , τ ) satisfies ϕ \phi ϕ .
It is easy to verify that ∼ ϕ \sim_\phi ∼ ϕ is an equivalence relation. The ϕ \phi ϕ -type of a boundaried graph is the equivalence class of ∼ ϕ \sim_\phi ∼ ϕ containing the graph. For convenience, graphs without boundary are viewed as ∅ \emptyset ∅ -boundaried graphs, and therefore also have their ϕ \phi ϕ -types.
A ( t , ϕ ) (t,\phi) ( t , ϕ ) -table of a graph G G G is a collection S \mathcal{S} S of subsets of V ( G ) V(G) V ( G ) satisfying that
tw ( G − S ) ≤ t \operatorname{tw}(G-S) \le t tw ( G − S ) ≤ t and G − S G-S G − S satisfies ϕ \phi ϕ for all S ∈ S S \in\mathcal{S} S ∈ S ,
for every R ⊆ V ( G ) R \subseteq V(G) R ⊆ V ( G ) such that tw ( G − R ) ≤ t \operatorname{tw}(G-R) \le t tw ( G − R ) ≤ t and G − R G-R G − R satisfies ϕ \phi ϕ , there exists S ∈ S S \in\mathcal{S} S ∈ S with ∣ S ∣ ≤ ∣ R ∣ |S| \le|R| ∣ S ∣ ≤ ∣ R ∣ satisfying that G − S G-S G − S is of the same ϕ \phi ϕ -type as G − R G-R G − R .
It is easy to see that if S \mathcal{S} S is a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table of a graph G G G , then the smallest set S ∈ S S \in\mathcal{S} S ∈ S is an optimal solution for ( t , ϕ ) (t,\phi) ( t , ϕ ) -DELETION on G G G . In the more general version of the problem, we require the algorithm th return a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table of the input graph G G G . In the following lemma, we show this can be done in w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) time. While the proof is a bit involved, the basic idea is similar to that used in MSO-checking on bounded-treewidth graphs [20 , 47 ] .
Lemma 5.1. Let t ∈ N t \in\mathbb{N} t ∈ N be a fixed number and ϕ \phi ϕ be a fixed MSO formula. Given a graph G G G with n n n vertices, one can compute a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table of G G G in w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) time, where w = tw ( G ) w = \operatorname{tw}(G) w = tw ( G ) .
Proof. All constants in the proof may depend on t t t and ϕ \phi ϕ . Let θ t \theta_t θ t be a fixed MSO sentence expressing that a graph has treewidth at most t t t . Such a sentence exists because, for fixed t t t , this property is characterized by excluding finitely many minors [50 ] , and containment of a fixed minor is MSO-expressible [21 ] . We first show how to summarize a residual graph of treewidth at most t t t by a small representative. We then use these representatives in a dynamic program that retains a cheapest witness for every relevant type.
Equivalence under extensions. We identify boundary labels with the vertices carrying them and suppress the boundary maps from the notation. For two L L L -boundaried graphs H 1 , H 2 H_1,H_2 H 1 , H 2 , write H 1 ≡ L H 2 H_1 \equiv_L H_2 H 1 ≡ L H 2 if the graphs induced by their boundaries coincide under the label correspondence and, for every L L L -boundaried graph F F F (with no restriction on its treewidth) and each ψ ∈ { θ t , ϕ } \psi\in\{\theta_t,\phi\} ψ ∈ { θ t , ϕ } , the graph H 1 ⊕ L F H_1 \oplus_L F H 1 ⊕ L F satisfies ψ \psi ψ if and only if H 2 ⊕ L F H_2 \oplus_L F H 2 ⊕ L F does. Thus ≡ L \equiv_L ≡ L refines ∼ ϕ \sim_\phi ∼ ϕ . Taking F F F to consist only of isolated boundary vertices shows that equivalent graphs themselves agree on both θ t \theta_t θ t and ϕ \phi ϕ . When L = ∅ L = \emptyset L = ∅ , gluing is disjoint union, so equivalence still records the behavior under every disjoint-union extension.
This equivalence is preserved by gluing along the boundary, forgetting boundary labels, and introducing a new boundary vertex with a prescribed neighborhood in the old boundary. For gluing, combine the graph being glued with any subsequent extension and apply the defining equivalence. For forgetting labels, augment an extension along the smaller boundary with isolated vertices carrying the forgotten labels. For introducing a vertex v v v , take an extension along the enlarged boundary, add the prescribed edges from v v v to the old boundary, and regard v v v as internal to this extension. In each case this gives an extension along the old boundary, to which the equivalence applies. Moreover, corresponding outputs have identical labeled boundary graphs whenever the inputs do. In particular, replacing either input of a gluing operation by an equivalent graph preserves the equivalence of the result.
We use the following standard consequence of the MSO composition theorem and the finite-state form of Courcelle’s theorem [20 , 21 ] . For a fixed number s s s of boundary labels, there is a finite refinement of ≡ L \equiv_L ≡ L whose classes can be computed on graphs of fixed treewidth. Such a refinement is given by MSO types of sufficiently large fixed quantifier rank, with the boundary vertices named. Here a type records which sentences up to that rank hold, including adjacency between named boundary vertices; there are only finitely many such types up to logical equivalence. The composition theorem ensures that equality of types implies agreement on θ t \theta_t θ t and ϕ \phi ϕ after every gluing.
These types also yield an effective choice of representatives. First relabel the boundary by [ s ] [s] [ s ] , so the preprocessing does not depend on the particular labels. Adding the s s s boundary vertices to every bag of a width-t t t decomposition gives a decomposition of width at most t + s t+s t + s in which all boundary vertices are present throughout. On such decompositions, a finite tree automaton computes the type and checks θ t \theta_t θ t . By enumerating its reachable states and retaining a witnessing decomposition for each state, we can precompute a representative of every type realized by a graph of treewidth at most t t t . Retain only witnesses satisfying θ t \theta_t θ t , so the representatives also have treewidth at most t t t . The automaton is fixed, hence this preprocessing and the representative sizes depend only on s , t , ϕ s,t,\phi s , t , ϕ . Given a graph of treewidth at most t t t , compute its type, choose the corresponding representative, and restore the original boundary labels. This takes polynomial time. We use this construction only for s ≤ 2 ( t + 1 ) s \le2(t+1) s ≤ 2 ( t + 1 ) .
Small representatives for larger boundaries. We next show that any L L L -boundaried graph H H H of treewidth at most t t t , where b = ∣ L ∣ b = |L| b = ∣ L ∣ , can be replaced in polynomial time by an equivalent L L L -boundaried graph J J J with tw ( J ) ≤ t \operatorname{tw}(J) \le t tw ( J ) ≤ t and ∣ V ( J ) ∣ ≤ c ( b + 1 ) |V(J)| \le c(b+1) ∣ V ( J ) ∣ ≤ c ( b + 1 ) , for a constant c c c depending only on t t t and ϕ \phi ϕ . The additive term allows a nonempty representative when the boundary is empty.
The empty graph requires no replacement. Otherwise, compute a tree decomposition of H H H of width at most t t t in polynomial time [12 ] , and make it rooted and binary by duplicating bags as needed. Denote the resulting decomposition by ( T , β ) (T,\beta) ( T , β ) . Mark the root and, for each boundary vertex, one node whose bag contains it. Let Q Q Q be the closure of these nodes under lowest common ancestors, and put Y = ⋃ x ∈ Q β ( x ) Y = \bigcup_{x\in Q}\beta(x) Y = ⋃ x ∈ Q β ( x ) . The subtree connecting the marked nodes has at most b b b branching nodes, so ∣ Q ∣ = O ( b + 1 ) |Q| = O(b+1) ∣ Q ∣ = O ( b + 1 ) and ∣ Y ∣ = O ( b + 1 ) |Y| = O(b+1) ∣ Y ∣ = O ( b + 1 ) . Moreover, Y Y Y contains every boundary vertex.
Each component K K K of T − Q T-Q T − Q has at most two neighbors in Q Q Q . Indeed, it has at most one neighbor above it, and two distinct neighbors below it would have their lowest common ancestor in K K K , contradicting the closure of Q Q Q . Every component of T − Q T-Q T − Q has a neighbor in the nonempty set Q Q Q , and each node of Q Q Q has degree at most three because T T T is binary. Thus there are O ( ∣ Q ∣ ) = O ( b + 1 ) O(|Q|) = O(b+1) O ( ∣ Q ∣ ) = O ( b + 1 ) such components. For each such component, let A K = ( ⋃ x ∈ V ( K ) β ( x ) ) ∖ Y A_K = \left(\bigcup_{x\in V(K)} \beta(x)\right) \setminus Y A K = ( ⋃ x ∈ V ( K ) β ( x ) ) ∖ Y and C K = N H ( A K ) C_K = N_H(A_K) C K = N H ( A K ) .
The nonempty sets A K A_K A K partition V ( H ) ∖ Y V(H) \setminus Y V ( H ) ∖ Y , and no edge joins two distinct such sets. This follows because the bags containing a vertex outside Y Y Y form a connected subtree disjoint from Q Q Q , and the endpoints of every edge occur together in a bag. Also, C K C_K C K is contained in the union of the bags at the neighbors of K K K in Q Q Q . To see this, a vertex of Y Y Y adjacent to A K A_K A K occurs in a bag of K K K and a bag of Q Q Q . The connected subtree of bags containing it must therefore meet one of those neighboring bags. Consequently, C K ⊆ Y C_K \subseteq Y C K ⊆ Y and ∣ C K ∣ ≤ 2 ( t + 1 ) |C_K| \leq2(t+1) ∣ C K ∣ ≤ 2 ( t + 1 ) .
Keep H [ Y ] H[Y] H [ Y ] and replace each H [ A K ∪ C K ] H[A_K \cup C_K] H [ A K ∪ C K ] with A K ≠ ∅ A_K \ne\varnothing A K = ∅ , viewed as a C K C_K C K -boundaried graph, by a constant-size equivalent representative. Give different representatives disjoint sets of fresh internal vertices, and identify their boundary vertices with the corresponding vertices of Y Y Y . The resulting graph J J J has O ( b + 1 ) O(b+1) O ( b + 1 ) vertices and the same labeled boundary graph as H H H . Each replacement preserves the truth of θ t \theta_t θ t and ϕ \phi ϕ even after any extension along L L L : the rest of the graph, together with that extension, is a context attached along C K C_K C K . All original boundary vertices lie in Y Y Y , so no replacement removes one. Replacing the pieces one at a time therefore proves H ≡ L J H \equiv_L J H ≡ L J . Taking the extension consisting of isolated boundary vertices shows that J ⊨ θ t J \models\theta_t J ⊨ θ t , and hence tw ( J ) ≤ t \operatorname{tw}(J) \leq t tw ( J ) ≤ t . All pieces have treewidth at most t t t and constant-size boundaries, so the construction takes polynomial time. In particular, we compute logical types only at these constant-size interfaces.
For a fixed label set L L L , there are at most 2 O ( ( b + 1 ) log ( b + 2 ) ) 2^{O((b+1)\log(b+2))} 2 O (( b + 1 ) l o g ( b + 2 )) encodings of the resulting representatives. Each has O ( b + 1 ) O(b+1) O ( b + 1 ) vertices and O ( b + 1 ) O(b+1) O ( b + 1 ) edges, since its treewidth is at most the fixed constant t t t . Fix an order on the boundary labels and number the internal vertices consecutively. The vertex count and edge list then give the asserted bound. We use these graph encodings as states; different encodings may describe equivalent graphs, and we do not need to test this equivalence.
Dynamic programming. Using the treewidth approximation algorithm of Korhonen [40 ] , and trying increasing width bounds until it succeeds, compute a tree decomposition of G G G of width W = O ( w + 1 ) W = O(w+1) W = O ( w + 1 ) in 2 O ( w ) n O ( 1 ) 2^{O(w)}n^{O(1)} 2 O ( w ) n O ( 1 ) time. Convert it into a nice tree decomposition with empty root and leaf bags and polynomially many nodes. For each node x x x , let B x B_x B x be its bag, let V x V_x V x be the union of the bags in its subtree, and put G x = G [ V x ] G_x = G[V_x] G x = G [ V x ] .
A state at x x x is a pair ( D , J ) (D,J) ( D , J ) , where D ⊆ B x D \subseteq B_x D ⊆ B x is the set of deleted bag vertices and J J J is a representative with boundary B x ∖ D B_x \setminus D B x ∖ D . At every state a cost a a a and a witnessing set S x ⊆ V x S_x \subseteq V_x S x ⊆ V x of size a a a . We require S x ∩ B x = D S_x \cap B_x = D S x ∩ B x = D , tw ( G x − S x ) ≤ t \operatorname{tw}(G_x-S_x) \leq t tw ( G x − S x ) ≤ t , and G x − S x ≡ B x ∖ D J G_x-S_x \equiv_{B_x \setminus D} J G x − S x ≡ B x ∖ D J . Whenever several candidates have the same state encoding, keep one of minimum cost together with its witness. Witnesses may instead be stored implicitly using backpointers.
The transitions are as follows.
At an introduce node x x x with child y y y , where B x = B y ∪ { v } B_x = B_y \cup\{v\} B x = B y ∪ { v } , extend each child state in two ways. Deleting v v v replaces D D D by D ∪ { v } D \cup\{v\} D ∪ { v } , leaves J J J unchanged, adds v v v to the witness, and increases the cost by one. Retaining v v v leaves D D D , the witness, and the cost unchanged, and adds a new boundary vertex v v v to J J J , adjacent precisely to N G ( v ) ∩ ( B y ∖ D ) N_G(v) \cap(B_y \setminus D) N G ( v ) ∩ ( B y ∖ D ) . These are all its neighbors in the retained part of G y G_y G y , because the tree-decomposition axioms imply that an introduced vertex has no neighbor in V y ∖ B y V_y \setminus B_y V y ∖ B y .
At a forget node x x x with child y y y , where B x = B y ∖ { v } B_x = B_y \setminus\{v\} B x = B y ∖ { v } , replace D D D by D ∖ { v } D \setminus\{v\} D ∖ { v } . If v v v was retained in the child state, forget its boundary label in J J J but retain the vertex itself. The cost and
witness are unchanged; in particular, a deleted vertex remains in the witness after it leaves the bag.
At a join node x x x with children y , z y,z y , z , we have B x = B y = B z B_x = B_y = B_z B x = B y = B z . Combine every pair of child states with the same deleted set D D D . Glue their representatives along B x ∖ D B_x \setminus D B x ∖ D , using disjoint copies of their internal vertices, and take the union of their witnesses. If the child costs are a y , a z a_y,a_z a y , a z , the new cost is a y + a z − ∣ D ∣ a_y + a_z - |D| a y + a z − ∣ D ∣ . Indeed, V y ∩ V z = B x V_y \cap V_z = B_x V y ∩ V z = B x , so the deleted bag vertices are exactly the vertices counted twice. There are no edges between V y ∖ B x V_y \setminus B_x V y ∖ B x and V z ∖ B x V_z \setminus B_x V z ∖ B x , so gluing also gives exactly the residual graph of the combined witness, up to equivalence.
After each transition, test whether the resulting graph has treewidth at most t t t . Discard the candidate if it does not. Otherwise, apply the replacement procedure with its current boundary and store the resulting state and cost, retaining a cheapest witness when encodings coincide. Partial graphs need not satisfy ϕ \phi ϕ , so we test that property only at the root.
Correctness and extraction of the table. We prove two statements simultaneously by induction over the decomposition. First, every stored entry has a witness satisfying the requirements above. Second, for every Z ⊆ V x Z \subseteq V_x Z ⊆ V x with tw ( G x − Z ) ≤ t \operatorname{tw}(G_x - Z) \le t tw ( G x − Z ) ≤ t , there is a stored state ( D , J ) (D,J) ( D , J ) with D = Z ∩ B x D = Z \cap B_x D = Z ∩ B x , cost at most ∣ Z ∣ |Z| ∣ Z ∣ , and G x − Z ≡ B x ∖ D J G_x - Z \equiv_{B_x \setminus D} J G x − Z ≡ B x ∖ D J .
Both statements hold at an empty leaf. For the first statement, each transition constructs the specified union or extension of child witnesses. The corresponding operation on their residual graphs agrees, up to equivalence, with the operation on their representatives. The extension properties of ≡ L \equiv_L ≡ L and the replacement procedure preserve this equivalence. Agreement on θ t \theta_t θ t makes the treewidth test valid for the actual residual graph as well. Retaining a cheapest witness for an encoding preserves all these requirements.
For the second statement, restrict Z Z Z to each child vertex set. The resulting child residual graphs are induced subgraphs of G x − Z G_x - Z G x − Z , so their treewidth is at most t t t . Apply the induction hypothesis to these restrictions and use the corresponding transition. At an introduce node choose whether to delete v v v according to Z Z Z ; at a forget node use the forget transition; at a join node the chosen child states have the same deleted boundary Z ∩ B x Z \cap B_x Z ∩ B x . The resulting graph is equivalent to G x − Z G_x - Z G x − Z , and its cost is at most ∣ Z ∣ |Z| ∣ Z ∣ . At a join, the cost bound follows from ∣ Z ∩ V y ∣ + ∣ Z ∩ V z ∣ − ∣ Z ∩ B x ∣ = ∣ Z ∣ |Z \cap V_y| + |Z \cap V_z| - |Z \cap B_x| = |Z| ∣ Z ∩ V y ∣ + ∣ Z ∩ V z ∣ − ∣ Z ∩ B x ∣ = ∣ Z ∣ . The candidate passes the treewidth test because equivalence preserves θ t \theta_t θ t . Replacement preserves its equivalence. If another candidate with the same encoding has lower cost, its representative is identical and its witness remains suitable. Thus every partial deletion set is represented by an equivalent state of no greater cost; the induction does not require a particular encoding to survive.
At the empty root r r r , output the collection S \mathcal{S} S of witnesses of all stored states whose representatives satisfy ϕ \phi ϕ . The first induction statement gives tw ( G − S ) ≤ t \operatorname{tw}(G - S) \le t tw ( G − S ) ≤ t and G − S ⊨ ϕ G - S \models\phi G − S ⊨ ϕ for every S ∈ S S \in\mathcal{S} S ∈ S . Conversely, take any Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) with tw ( G − Z ) ≤ t \operatorname{tw}(G - Z) \le t tw ( G − Z ) ≤ t and G − Z ⊨ ϕ G - Z \models\phi G − Z ⊨ ϕ . The second statement gives a root state of cost at most ∣ Z ∣ |Z| ∣ Z ∣ whose representative is equivalent to G − Z G - Z G − Z . This representative satisfies ϕ \phi ϕ , so its witness S S S is output. Both G − S G - S G − S and G − Z G - Z G − Z are equivalent to that representative under ≡ ∅ \equiv_{\emptyset} ≡ ∅ , and hence have the same ϕ \phi ϕ -type. Therefore S \mathcal{S} S satisfies both requirements of a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table. We need not determine which accepted states have the same ϕ \phi ϕ -type, since the definition permits redundant witnesses. If no state is accepted, there is no feasible deletion set, and the empty collection is a valid table.
Running time. There are 2 O ( ( W + 1 ) log ( W + 2 ) ) 2^{O((W+1)\log(W+2))} 2 O (( W + 1 ) l o g ( W + 2 )) states per node, including the choice of D D D . Each transition handles graphs with O ( W + 1 ) O(W+1) O ( W + 1 ) vertices. Testing treewidth against the fixed bound t t t , computing the needed decompositions, and replacing the pieces all take polynomial time. Enumerating all pairs of child states at a join only squares the number of states and preserves this asymptotic bound. At the root, representatives have constant size, so testing ϕ \phi ϕ takes constant time per state. Keeping or recovering witnesses adds a polynomial factor. The total running time is 2 O ( ( w + 1 ) log ( w + 2 ) ) n O ( 1 ) 2^{O((w+1)\log(w+2))}n^{O(1)} 2 O (( w + 1 ) l o g ( w + 2 )) n O ( 1 ) , which is w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) for w ≥ 2 w \ge2 w ≥ 2 ; bounded values of w w w are handled in polynomial time.
Corollary 5.2. Let t ∈ N t \in\mathbb{N} t ∈ N be a fixed number and ϕ \phi ϕ be a fixed MSO formula. Then ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion admits an algorithm with running time w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) , where w = tw ( G ) w = \operatorname{tw}(G) w = tw ( G ) .
Proof. We simply apply Lemma 5.1 to compute a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table S \mathcal{S} S of G G G in w O ( w ) n O ( 1 ) w^{O(w)}n^{O(1)} w O ( w ) n O ( 1 ) time and then output the smallest set S 0 ∈ S S_0 \in\mathcal{S} S 0 ∈ S . By property (i) of a ( t , ϕ ) (t,\phi) ( t , ϕ ) -table, S 0 S_0 S 0 is a feasible solution. To see it is optimal, consider an optimal solution S ∗ ⊆ V ( G ) S^* \subseteq V(G) S ∗ ⊆ V ( G ) for ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on G G G . By property (ii) of ( t , ϕ ) (t,\phi) ( t , ϕ ) -table, there exists S ∈ S S \in\mathcal{S} S ∈ S such that ∣ S ∣ ≤ ∣ S ∗ ∣ |S| \le|S^*| ∣ S ∣ ≤ ∣ S ∗ ∣ . Therefore, ∣ S 0 ∣ ≤ ∣ S ∣ ≤ ∣ S ∗ ∣ |S_0| \le|S| \le|S^*| ∣ S 0 ∣ ≤ ∣ S ∣ ≤ ∣ S ∗ ∣ .
Subexponential FPT algorithms
In this section, we combine Theorem 4.1 and Corollary 5.2 to prove Theorem 1.1, which gives subexponential FPT algorithms for ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion.
Theorem 1.1. Let H H H be a fixed graph, t ∈ N t \in\mathbb{N} t ∈ N be a fixed number, and ϕ \phi ϕ be a fixed MSO formula. Then ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on G H \mathcal{G}_H G H admits an algorithm that runs in 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) time.
Proof. We first apply Theorem 4.1 with d = k 1 / 3 d = k^{1/3} d = k 1/3 to compute the collection X = { X 1 , … , X r } \mathcal{X} = \{X_1,\ldots,X_r\} X = { X 1 , … , X r } in 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) time, where r = 2 O ~ ( k 2 / 3 ) r = 2^{\widetilde{O}(k^{2/3})} r = 2 O ( k 2/3 ) . For each i ∈ [ r ] i \in[r] i ∈ [ r ] , we apply Corollary 5.2 on the graph G − X i G-X_i G − X i , which gives us a minimum subset S i ⊆ V ( G ) ∖ X i S_i \subseteq V(G)\setminus X_i S i ⊆ V ( G ) ∖ X i such that tw ( G − ( X i ∪ S i ) ) ≤ t \operatorname{tw}(G-(X_i \cup S_i)) \le t tw ( G − ( X i ∪ S i )) ≤ t and G − ( X i ∪ S i ) G-(X_i \cup S_i) G − ( X i ∪ S i ) satisfies ϕ \phi ϕ . By (i) of Theorem 4.1, tw ( G − X i ) = O ( k d ) = O ( k 2 / 3 ) \operatorname{tw}(G-X_i) = O(\sqrt{kd}) = O(k^{2/3}) tw ( G − X i ) = O ( k d ) = O ( k 2/3 ) for all i ∈ [ r ] i \in[r] i ∈ [ r ] . Therefore, computing each S i S_i S i can be done in 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) time. Since r = 2 O ~ ( k 2 / 3 ) r = 2^{\widetilde{O}(k^{2/3})} r = 2 O ( k 2/3 ) , the overall time cost is also 2 O ~ ( k 2 / 3 ) n O ( 1 ) 2^{\widetilde{O}(k^{2/3})}n^{O(1)} 2 O ( k 2/3 ) n O ( 1 ) . Define i ∗ = arg min i ∈ [ r ] ∣ X i ∪ S i ∣ i^* = \arg\min_{i \in[r]} |X_i \cup S_i| i ∗ = arg min i ∈ [ r ] ∣ X i ∪ S i ∣ . If ∣ X i ∗ ∪ S i ∗ ∣ ≤ k |X_{i^*} \cup S_{i^*}| \le k ∣ X i ∗ ∪ S i ∗ ∣ ≤ k , then we return X i ∗ ∪ S i ∗ X_{i^*} \cup S_{i^*} X i ∗ ∪ S i ∗ as the output, otherwise we return Fail.
To see the correctness of the algorithm, observe that if the algorithm returns a subset of V ( G ) V(G) V ( G ) , then it is a feasible solution for the instance. So it suffices to show that if there exists a solution S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) for ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on G G G with ∣ S ∣ ≤ k |S| \le k ∣ S ∣ ≤ k , then the algorithm does not fail. Note that S S S is a treewidth-t t t modulator of G G G . Thus, by (ii) of Theorem 4.1, there exists i ∈ [ r ] i \in[r] i ∈ [ r ] such that X i ⊆ S X_i \subseteq S X i ⊆ S . Now S ∖ X i S\setminus X_i S ∖ X i is a feasible solution on G − X i G-X_i G − X i , and thus ∣ S i ∣ ≤ ∣ S ∖ X i ∣ |S_i| \le|S\setminus X_i| ∣ S i ∣ ≤ ∣ S ∖ X i ∣ . It follows that
∣ X i ∗ ∪ S i ∗ ∣ ≤ ∣ X i ∪ S i ∣ = ∣ X i ∣ + ∣ S i ∣ ≤ ∣ X i ∣ + ∣ S ∖ X i ∣ ≤ ∣ S ∣ ≤ k . |X_{i^*} \cup S_{i^*}| \le|X_i \cup S_i| = |X_i| + |S_i| \le|X_i| + |S\setminus X_i| \le|S| \le k. ∣ X i ∗ ∪ S i ∗ ∣ ≤ ∣ X i ∪ S i ∣ = ∣ X i ∣ + ∣ S i ∣ ≤ ∣ X i ∣ + ∣ S ∖ X i ∣ ≤ ∣ S ∣ ≤ k .
Thus, the algorithm returns X i ∗ ∪ S i ∗ X_{i^*} \cup S_{i^*} X i ∗ ∪ S i ∗ rather than Fail.
Quasipolynomial-time approximation schemes
In this section, we use Theorem 4.1 to obtain a QPTAS for ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion. The approximation scheme is proved by repeatedly applying Theorem 4.1 to instances reduced using balance separator (Lemma 3.4 ). For every graph G ′ G' G ′ , define
OPT t , ϕ ( G ′ ) = min { ∣ S ∣ : S ⊆ V ( G ′ ) , tw ( G ′ − S ) ≤ t and G ′ − S ⊨ ϕ } . \operatorname{OPT}_{t,\phi}(G') = \min\{|S| : S \subseteq V(G'),\ \operatorname{tw}(G' - S) \le t\ \text{and}\ G' - S \models\phi\}. OPT t , ϕ ( G ′ ) = min { ∣ S ∣ : S ⊆ V ( G ′ ) , tw ( G ′ − S ) ≤ t and G ′ − S ⊨ ϕ } .
Throughout this section, G G G denotes the input graph of ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion where G ∈ G H G \in\mathcal{G}_H G ∈ G H , and we assume that k = OPT t , ϕ ( G ) k = \operatorname{OPT}_{t,\phi}(G) k = OPT t , ϕ ( G ) and this value is known to the algorithm. The high-level idea is to apply Theorem 4.1, which guarantees that, for an optimum solution S ∗ S^* S ∗ , there exists a set $X in the collection output by the algorithm such that G − X G-X G − X has treewidth sublinear in k k k . We then aim to divide the problem into two subinstances, each with an optimum solution size smaller by a constant factor. To achieve this, we fix an approximate solution and apply Lemma 3.4 to find a separator that partitions the approximate solution in a balanced manner. We recursively solve the resulting subinstances and combine their ( t , ϕ ) (t,\phi) ( t , ϕ ) -tables to obtain ( t , ϕ ) (t,\phi) ( t , ϕ ) -table of the graph obtained after deleting X X X and the separator. We will show that the resulting ( t , ϕ ) (t,\phi) ( t , ϕ ) -table and is enough to extract a good approximate solution to the original instance.
Our algorithm is a branching algorithm and each local branching step is an application of Theorem 4.1 and Lemma 3.4.
Lemma 7.1 (Local branching). Let 0 < δ ≤ 1 / 2 0<\delta\le1/2 0 < δ ≤ 1/2 . There are constants c 1 , c 2 , c 3 > 0 c_1,c_2,c_3>0 c 1 , c 2 , c 3 > 0 , depending only on H , t H,t H , t , with the following property. For every sufficiently large q q q , where the threshold depends only on H , t , δ H,t,\delta H , t , δ , given a graph G ′ ∈ G H G'\in\mathcal{G}_H G ′ ∈ G H and a set W ⊆ V ( G ′ ) W\subseteq V(G') W ⊆ V ( G ′ ) of size q q q , one can compute a family Y \mathcal{Y} Y of size 2 c 2 δ − 3 log 9 q 2^{c_2\delta^{-3}\log^9q} 2 c 2 δ − 3 l o g 9 q in time 2 c 2 δ − 3 log 9 q ∣ V ( G ′ ) ∣ O ( 1 ) 2^{c_2\delta^{-3}\log^9q}|V(G')|^{O(1)} 2 c 2 δ − 3 l o g 9 q ∣ V ( G ′ ) ∣ O ( 1 ) and for each Y ∈ Y Y\in\mathcal{Y} Y ∈ Y , a set Z Y ⊆ V ( G ′ ) ∖ Y Z_Y\subseteq V(G')\setminus Y Z Y ⊆ V ( G ′ ) ∖ Y and two vertex-disjoint induced subgraphs G Y , 1 ′ , G Y , 2 ′ G'_{Y,1},G'_{Y,2} G Y , 1 ′ , G Y , 2 ′ such that:
(i) G ′ − ( Y ∪ Z Y ) G'-(Y\cup Z_Y) G ′ − ( Y ∪ Z Y ) is the disjoint union of G Y , 1 ′ G'_{Y,1} G Y , 1 ′ and G Y , 2 ′ G'_{Y,2} G Y , 2 ′ ;
(ii) ∣ W ∩ V ( G Y , j ′ ) ∣ ≤ 2 q / 3 |W\cap V(G'_{Y,j})|\le2q/3 ∣ W ∩ V ( G Y , j ′ ) ∣ ≤ 2 q /3 for j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } ;
(iii) ∣ Z Y ∣ ≤ c 1 q / log 3 q |Z_Y|\le c_1q/\log^3q ∣ Z Y ∣ ≤ c 1 q / log 3 q ;
(iv) tw ( G Y , j ′ ) ≤ c 3 q / log 4 q \operatorname{tw}(G'_{Y,j})\le c_3q/\log^4q tw ( G Y , j ′ ) ≤ c 3 q / log 4 q for j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } ;
(v) For every treewidth-t t t modulator S ⊆ V ( G ′ ) S\subseteq V(G') S ⊆ V ( G ′ ) satisfying ∣ S ∣ ≤ q / δ |S|\le q/\delta ∣ S ∣ ≤ q / δ , there exists some Y ∈ Y Y\in\mathcal{Y} Y ∈ Y such that Y ⊆ S Y\subseteq S Y ⊆ S .
Proof. Set
b = ⌈ q δ ⌉ , d = ⌊ δ q log 8 q ⌋ . b=\left\lceil\frac{q}{\delta}\right\rceil,\qquad d=\left\lfloor\frac{\delta q}{\log^8q}\right\rfloor. b = ⌈ δ q ⌉ , d = ⌊ log 8 q δ q ⌋ .
Choose the threshold sufficiently large so that q ≥ 1 / δ q\ge1/\delta q ≥ 1/ δ and δ q / log 8 q ≥ 1 \delta q/\log^8q\ge1 δ q / log 8 q ≥ 1 . Then
b ≤ 2 q δ , δ q log 8 q ≤ d ≤ 2 δ q log 8 q , b d ≤ 2 log 8 q δ 2 . b\le\frac{2q}{\delta},\qquad
\frac{\delta q}{\log^8q}\le d\le\frac{2\delta q}{\log^8q},\qquad
\frac{b}{d}\le\frac{2\log^8q}{\delta^2}. b ≤ δ 2 q , log 8 q δ q ≤ d ≤ log 8 q 2 δ q , d b ≤ δ 2 2 log 8 q .
Apply Theorem 4.1 to G ′ G' G ′ with parameters k = b , d k=b,d k = b , d , and t t t . Let Y \mathcal{Y} Y denote the resulting family. Its cardinality is at most
b O ( t 2 b / d ) ≤ 2 c 2 δ − 3 log 9 q , b^{O(t^2b/d)}\le2^{c_2\delta^{-3}\log^9q}, b O ( t 2 b / d ) ≤ 2 c 2 δ − 3 l o g 9 q ,
where the inequality follows from log b ≤ log q ⋅ log ( 1 / δ ) \log b\le\log q\cdot\log(1/\delta) log b ≤ log q ⋅ log ( 1/ δ ) , and c 2 c_2 c 2 is a sufficiently large constant depending only on H , t H,t H , t . The containment guarantee (condition (ii)) of Theorem 4.1 implies property (v). Moreover, for every Y ∈ Y Y\in\mathcal{Y} Y ∈ Y , we have
tw ( G ′ − Y ) ≤ C H , t b d ≤ 2 C H , t q log 4 q , \operatorname{tw}(G'-Y)\le C_{H,t}\sqrt{bd}\le2C_{H,t}\frac{q}{\log^4q}, tw ( G ′ − Y ) ≤ C H , t b d ≤ 2 C H , t log 4 q q ,
where C H , t C_{H,t} C H , t is a constant. Thus, the condition (iv) follows. We next construct the set Z Y Z_Y Z Y and the two subgraphs G Y , 1 ′ G'_{Y,1} G Y , 1 ′ and G Y , 2 ′ G'_{Y,2} G Y , 2 ′ for each Y ∈ Y Y\in\mathcal{Y} Y ∈ Y . Fix Y ∈ Y Y\in\mathcal{Y} Y ∈ Y . By the polynomial-time treewidth approximation algorithm of Feige, Hajiaghayi, and Lee [31 ] , we can compute a tree decomposition of G ′ − Y G'-Y G ′ − Y of width O ( w log w ) O(w\sqrt{\log w}) O ( w log w ) , where w = tw ( G ′ − Y ) w=\operatorname{tw}(G'-Y) w = tw ( G ′ − Y ) . Thus, we can obtain a tree decomposition T = ( T , β ) \mathcal{T}=(T,\beta) T = ( T , β ) of G ′ − Y G'-Y G ′ − Y of width at most O ( q log 3 q ) O\left(\frac{q}{\log^3q}\right) O ( l o g 3 q q ) . Now we apply Lemma 3.4 with S = W S=W S = W and $c=2 to get O ( 1 ) O(1) O ( 1 ) nodes x 1 , … , x r ∈ T x_1,\ldots,x_r \in T x 1 , … , x r ∈ T such that each connected component of G ′ − ( Y ∪ ( ⋃ i = 1 r β ( x i ) ) ) G'-(Y\cup(\bigcup_{i=1}^r\beta(x_i))) G ′ − ( Y ∪ ( ⋃ i = 1 r β ( x i ))) has size at most ∣ W ∣ / 2 |W|/2 ∣ W ∣/2 vertices from W W W . We set Z Y = ⋃ i = 1 r β ( x i ) Z_Y=\bigcup_{i=1}^r\beta(x_i) Z Y = ⋃ i = 1 r β ( x i ) . Notice that ∣ Z Y ∣ ≤ c 1 q log 3 q |Z_Y|\le c_1\frac{q}{\log^3 q} ∣ Z Y ∣ ≤ c 1 l o g 3 q q where c 1 c_1 c 1 is a constant. This establishes property (iii).
It remains to construct the two subgraphs. Consider the connected components of G ′ − ( Y ∪ Z Y ) G'-(Y\cup Z_Y) G ′ − ( Y ∪ Z Y ) , and assign to each component C C C the weight ∣ W ∩ V ( C ) ∣ |W\cap V(C)| ∣ W ∩ V ( C ) ∣ . The total weight is at most q q q , and each component has weight at most q / 2 q/2 q /2 . If some component has weight in [ q / 3 , 2 q / 3 ] [q/3,2q/3] [ q /3 , 2 q /3 ] , place it in the first group and all remaining components in the second group. Otherwise, every component has weight less than q / 3 q/3 q /3 . If the total weight is at least q / 3 q/3 q /3 , greedily add components to the first group until its weight first reaches q / 3 q/3 q /3 . The resulting weight is less than 2 q / 3 2q/3 2 q /3 , and the weight of the remaining components is at most 2 q / 3 2q/3 2 q /3 . If the total weight is less than q / 3 q/3 q /3 , place all components in the first group and leave the second group empty. Components of weight zero can be assigned arbitrarily.
Let G Y , 1 ′ G'_{Y,1} G Y , 1 ′ and G Y , 2 ′ G'_{Y,2} G Y , 2 ′ be the subgraphs induced by the vertices in the two groups, respectively. By construction, they are vertex-disjoint, there are no edges between them, and
G ′ − ( Y ∪ Z Y ) = G Y , 1 ′ ∪ ˙ G Y , 2 ′ . G'-(Y\cup Z_Y)=G'_{Y,1}\mathbin{\dot\cup}G'_{Y,2}. G ′ − ( Y ∪ Z Y ) = G Y , 1 ′ ∪ ˙ G Y , 2 ′ .
Furthermore,
∣ W ∩ V ( G Y , j ′ ) ∣ ≤ 2 q 3 for j ∈ { 1 , 2 } . |W\cap V(G'_{Y,j})|\le\frac{2q}{3}\qquad\text{for }j\in\{1,2\}. ∣ W ∩ V ( G Y , j ′ ) ∣ ≤ 3 2 q for j ∈ { 1 , 2 } .
Hence properties (i) and (ii) hold. All computations following the application of Theorem 4.1 take polynomial time for each Y ∈ Y Y\in\mathcal{Y} Y ∈ Y . So, the total running time is at most 2 c 2 δ − 3 log 9 q ∣ V ( G ′ ) ∣ O ( 1 ) 2^{c_2\delta^{-3}\log^9q}|V(G')|^{O(1)} 2 c 2 δ − 3 l o g 9 q ∣ V ( G ′ ) ∣ O ( 1 ) , for some contant c 2 c_2 c 2 . □
Now we are ready to give the QPTAS.
Theorem 1.2. Let H H H be a fixed graph, t ∈ N t\in\mathbb{N} t ∈ N be a fixed number, and ϕ \phi ϕ be a fixed hereditary MSO formula. Then ( t , ϕ ) (t,\phi) ( t , ϕ ) -Deletion on G H G_H G H admits a quasipolynomial-time approximation scheme.
Proof. Fix 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 , and set δ = ε / 2 \delta=\varepsilon/2 δ = ε /2 . All constants below may depend on H , t , ϕ , ε H,t,\phi,\varepsilon H , t , ϕ , ε . We first describe the type information used by the algorithm. Let T \mathcal{T} T be the finite set of ϕ \phi ϕ -types of graphs with empty boundary, and write tp ( F ) \operatorname{tp}(F) tp ( F ) for the type of a graph F F F . Since the type equivalence is preserved by disjoint union, there is a well-defined operation ⊕ \oplus ⊕ on T \mathcal{T} T such that
tp ( F 1 ∪ ˙ F 2 ) = tp ( F 1 ) ⊕ tp ( F 2 ) . \operatorname{tp}(F_1\mathbin{\dot\cup}F_2)=\operatorname{tp}(F_1)\oplus\operatorname{tp}(F_2). tp ( F 1 ∪ ˙ F 2 ) = tp ( F 1 ) ⊕ tp ( F 2 ) .
Define a relation on T \mathcal{T} T by putting σ ⪯ 0 τ \sigma\preceq_0\tau σ ⪯ 0 τ if there exist graphs F σ , F τ F_\sigma,F_\tau F σ , F τ of types σ , τ \sigma,\tau σ , τ , respectively, such that F σ F_\sigma F σ is an induced subgraph of F τ F_\tau F τ . Let ⪯ \preceq ⪯ be its reflexive transitive closure of ⪯ 0 \preceq_0 ⪯ 0 . In particular, deleting vertices can only decrease the type with respect to ⪯ \preceq ⪯ . The preorder ⪯ \preceq ⪯ (i.e., the relation is reflexive and transitive) is compatible with disjoint union:
σ 1 ⪯ τ 1 , σ 2 ⪯ τ 2 ⟹ σ 1 ⊕ σ 2 ⪯ τ 1 ⊕ τ 2 . \sigma_1\preceq\tau_1,\ \sigma_2\preceq\tau_2\quad\Longrightarrow\quad\sigma_1\oplus\sigma_2\preceq\tau_1\oplus\tau_2. σ 1 ⪯ τ 1 , σ 2 ⪯ τ 2 ⟹ σ 1 ⊕ σ 2 ⪯ τ 1 ⊕ τ 2 .
Indeed, for a generating relation σ ⪯ 0 τ \sigma\preceq_0\tau σ ⪯ 0 τ , take witnessing graphs F σ ⊆ i n d F τ F_\sigma\subseteq_{\mathrm{ind}}F_\tau F σ ⊆ ind F τ and any graph K K K of type κ \kappa κ . Then F σ ∪ ˙ K F_\sigma\mathbin{\dot\cup}K F σ ∪ ˙ K is an induced subgraph of F τ ∪ ˙ K F_\tau\mathbin{\dot\cup}K F τ ∪ ˙ K , proving σ ⊕ κ ⪯ 0 τ ⊕ κ \sigma\oplus\kappa\preceq_0\tau\oplus\kappa σ ⊕ κ ⪯ 0 τ ⊕ κ . The claim follows by transitivity and by applying this observation to each coordinate. For each τ ∈ T \tau\in\mathcal{T} τ ∈ T , let χ τ \chi_\tau χ τ be the fixed MSO property
F ⊨ χ τ ⟺ tp ( F ) ⪯ τ . F\models\chi_\tau\quad\Longleftrightarrow\quad\operatorname{tp}(F)\preceq\tau. F ⊨ χ τ ⟺ tp ( F ) ⪯ τ .
This property is hereditary. Moreover, if graphs of type τ \tau τ satisfy ϕ \phi ϕ , then every graph satisfying χ τ \chi_\tau χ τ also satisfies ϕ \phi ϕ : this follows from the heredity of ϕ \phi ϕ along each generating relation ⪯ 0 \preceq_0 ⪯ 0 of ⪯ \preceq ⪯ . All type information, the operation ⊕ \oplus ⊕ , and the preorder ⪯ \preceq ⪯ are fixed independently of the input.
Let G ∈ G H G \in\mathcal{G}_{H} G ∈ G H be the input graph, and put n = ∣ V ( G ) ∣ n = |V(G)| n = ∣ V ( G ) ∣ and k = OPT t , ϕ ( G ) k = \operatorname{OPT}_{t,\phi}(G) k = OPT t , ϕ ( G ) . Using Lemma 3.8 , compute a treewidth-t t t modulator M M M whose size is at most a constant multiple of k k k . On the bounded-treewidth graph G − M G - M G − M , use Lemma 5.1 to compute a minimum deletion set P ⊆ V ( G ) ∖ M P \subseteq V(G) \setminus M P ⊆ V ( G ) ∖ M such that G − ( M ∪ P ) ⊨ ϕ G - (M \cup P) \models\phi G − ( M ∪ P ) ⊨ ϕ . If S ∗ S^* S ∗ is an optimum solution, then G − ( M ∪ S ∗ ) G - (M \cup S^*) G − ( M ∪ S ∗ ) is an induced subgraph of G − S ∗ G - S^* G − S ∗ and therefore satisfies ϕ \phi ϕ . Consequently,
∣ P ∣ ≤ ∣ S ∗ ∖ M ∣ ≤ k . |P| \leq|S^* \setminus M| \leq k. ∣ P ∣ ≤ ∣ S ∗ ∖ M ∣ ≤ k .
Let W = M ∪ P W = M \cup P W = M ∪ P and q = ∣ W ∣ ≤ a t k q = |W| \leq a_t k q = ∣ W ∣ ≤ a t k for a constant a t a_t a t . Notice that tw ( G − W ) ≤ t \operatorname{tw}(G - W) \leq t tw ( G − W ) ≤ t and G − W ⊨ ϕ G - W \models\phi G − W ⊨ ϕ . We call the vertices of W W W marked. We maintain the marked set by restriction: a recursive call has input
G ′ ⊆ i n d G , W ′ = W ∩ V ( G ′ ) , q ′ = ∣ W ′ ∣ . G' \subseteq_{\mathrm{ind}} G,\qquad W' = W \cap V(G'),\qquad q' = |W'|. G ′ ⊆ ind G , W ′ = W ∩ V ( G ′ ) , q ′ = ∣ W ′ ∣.
In particular, W ′ W' W ′ is a treewidth-t t t modulator of G ′ G' G ′ . The output of a call consists of at most one deletion set S τ S_\tau S τ for each τ ∈ T \tau\in\mathcal{T} τ ∈ T . Every stored set must satisfy
tw ( G ′ − S τ ) ≤ t , tp ( G ′ − S τ ) ⪯ τ . \operatorname{tw}(G' - S_\tau) \leq t,\qquad\operatorname{tp}(G' - S_\tau) \preceq\tau. tw ( G ′ − S τ ) ≤ t , tp ( G ′ − S τ ) ⪯ τ .
If several candidates are available for an entry, retain one of minimum cardinality. An entry is absent if no candidate has been obtained. Choose a sufficiently large integer s 0 ≥ 2 s_0 \geq2 s 0 ≥ 2 , specified below, and put B = t + s 0 B = t + s_0 B = t + s 0 . If tw ( G ′ ) ≤ B \operatorname{tw}(G') \leq B tw ( G ′ ) ≤ B , compute every entry exactly using Lemma 5.1, applied to the fixed hereditary properties χ τ \chi_\tau χ τ . This takes polynomial time because B B B is a constant. Suppose now that tw ( G ′ ) > B \operatorname{tw}(G') > B tw ( G ′ ) > B . Since tw ( G ′ ) ≤ t + ∣ W ′ ∣ \operatorname{tw}(G') \leq t + |W'| tw ( G ′ ) ≤ t + ∣ W ′ ∣ , we have q ′ > s 0 q' > s_0 q ′ > s 0 . Choose s 0 s_0 s 0 large enough that Lemma 7.1 is applicable with the fixed value δ = ε / 2 \delta= \varepsilon/2 δ = ε /2 .
First, for every τ ∈ T \tau\in\mathcal{T} τ ∈ T , compute a minimum set P τ ⊆ V ( G ′ ) ∖ W ′ P_\tau\subseteq V(G') \setminus W' P τ ⊆ V ( G ′ ) ∖ W ′ such that G ′ − ( W ′ ∪ P τ ) ⊨ χ τ G' - (W' \cup P_\tau) \models\chi_\tau G ′ − ( W ′ ∪ P τ ) ⊨ χ τ . This is a bounded-treewidth computation on G ′ − W ′ G' - W' G ′ − W ′ , using Lemma 5.1. Whenever such a set exists, include W ′ ∪ P τ W' \cup P_\tau W ′ ∪ P τ as a candidate for entry τ \tau τ . Next, apply Lemma 7.1 to ( G ′ , W ′ ) (G', W') ( G ′ , W ′ ) . For every returned set Y Y Y , let Z Y Z_Y Z Y , G Y , 1 ′ G'_{Y,1} G Y , 1 ′ , G Y , 2 ′ G'_{Y,2} G Y , 2 ′ be the associated separator and two induced subgraphs. Recursively process
( G Y , j ′ , W ′ ∩ V ( G Y , j ′ ) ) , j ∈ { 1 , 2 } . \left(G'_{Y,j}, W' \cap V(G'_{Y,j})\right),\qquad j \in\{1,2\}. ( G Y , j ′ , W ′ ∩ V ( G Y , j ′ ) ) , j ∈ { 1 , 2 } .
For every pair of available child entries S 1 , τ 1 , S 2 , τ 2 S_{1,\tau_1}, S_{2,\tau_2} S 1 , τ 1 , S 2 , τ 2 , form
D = Y ∪ Z Y ∪ S 1 , τ 1 ∪ S 2 , τ 2 . D = Y \cup Z_Y \cup S_{1,\tau_1} \cup S_{2,\tau_2}. D = Y ∪ Z Y ∪ S 1 , τ 1 ∪ S 2 , τ 2 .
For every τ \tau τ satisfying τ 1 ⊕ τ 2 ⪯ τ \tau_1 \oplus\tau_2 \preceq\tau τ 1 ⊕ τ 2 ⪯ τ , include D D D as a candidate for entry τ \tau τ . These candidates are feasible. Indeed,
G ′ − D = ( G Y , 1 ′ − S 1 , τ 1 ) ∪ ( G Y , 2 ′ − S 2 , τ 2 ) , G' - D = (G'_{Y,1} - S_{1,\tau_1}) \cup(G'_{Y,2} - S_{2,\tau_2}), G ′ − D = ( G Y , 1 ′ − S 1 , τ 1 ) ∪ ( G Y , 2 ′ − S 2 , τ 2 ) ,
so its treewidth is at most t t t . Compatibility of ⪯ \preceq ⪯ with disjoint union gives
tp ( G ′ − D ) ⪯ τ 1 ⊕ τ 2 ⪯ τ . \operatorname{tp}(G' - D) \preceq\tau_1 \oplus\tau_2 \preceq\tau. tp ( G ′ − D ) ⪯ τ 1 ⊕ τ 2 ⪯ τ .
We next bound the separator cost. Consider any binary recursion tree obtained by choosing one set Y Y Y at each internal call. If a node has m m m marked vertices and its children have m 1 , m 2 m_1,m_2 m 1 , m 2 marked vertices, then m 1 + m 2 ≤ m m_1 + m_2 \leq m m 1 + m 2 ≤ m and m j ≤ 2 m 3 m_j \leq\frac{2m}{3} m j ≤ 3 2 m . Every internal node has m > s 0 m > s_0 m > s 0 , and its separator has size at most c 1 m log 3 m \frac{c_1m}{\log^3 m} l o g 3 m c 1 m . Charge its separator cost equally to its m m m marked vertices. Each marked vertex receives a charge of at most c 1 / log 3 m c_1/\log^3 m c 1 / log 3 m at that node.
Along a root-to-leaf path, the positive marked-set sizes decrease by a factor of at least 3 / 2 3/2 3/2 . Reading the internal nodes in the reverse order, their sizes are therefore at least s 0 , ( 3 / 2 ) s 0 , ( 3 / 2 ) 2 s 0 , … s_0, (3/2)s_0, (3/2)^2s_0, \ldots s 0 , ( 3/2 ) s 0 , ( 3/2 ) 2 s 0 , … . Hence the total charge to any marked vertex is at most
c 1 ∑ i ≥ 0 1 log 3 ( s 0 ( 3 / 2 ) i ) ≤ C log 2 s 0 . c_1 \sum_{i \geq0} \frac{1}{\log^3\left(s_0(3/2)^i\right)} \leq\frac{C}{\log^2 s_0}. c 1 i ≥ 0 ∑ log 3 ( s 0 ( 3/2 ) i ) 1 ≤ log 2 s 0 C .
for a constant C C C . Thus, any such recursion tree starting with m m m marked vertices has total separator cost at most
C ⋅ m log 2 s 0 . \frac{C \cdot m}{\log^2 s_0}. log 2 s 0 C ⋅ m .
Equivalently, the total separator cost can be bounded by analysing the recurrence in which a subproblem of size m m m incurs a separator cost of at most c 1 m / log 3 m c_1m/\log^3 m c 1 m / log 3 m , child sizes satisfying the two inequalities above, and zero cost at leaves. We prove the approximation guarantee by induction on the recursion. Fix a state τ \tau τ and any set R ⊆ V ( G ′ ) R \subseteq V(G') R ⊆ V ( G ′ ) satisfying
tw ( G ′ − R ) ≤ t , tp ( G ′ − R ) ⪯ τ . \operatorname{tw}(G' - R) \leq t,\qquad\operatorname{tp}(G' - R) \preceq\tau. tw ( G ′ − R ) ≤ t , tp ( G ′ − R ) ⪯ τ .
We show that the algorithm obtains a feasible entry of cost at most ( 1 + δ ) ∣ R ∣ (1+\delta)|R| ( 1 + δ ) ∣ R ∣ plus the separator costs in a suitable binary recursion tree. At a bounded-treewidth leaf, the entry is computed exactly, so its cost is at most ∣ R ∣ |R| ∣ R ∣ .
At an internal call, suppose first that ∣ R ∣ > q ′ / δ |R| > q'/\delta ∣ R ∣ > q ′ / δ . The graph G ′ − ( W ′ ∪ R ) G' - (W' \cup R) G ′ − ( W ′ ∪ R ) is an induced subgraph of G ′ − R G' - R G ′ − R , and therefore satisfies χ τ \chi_\tau χ τ . By the optimality of P τ P_\tau P τ , ∣ P τ ∣ ≤ ∣ R ∖ W ′ ∣ |P_\tau| \leq|R\setminus W'| ∣ P τ ∣ ≤ ∣ R ∖ W ′ ∣ . The fallback candidate consequently satisfies
∣ W ′ ∪ P τ ∣ ≤ q ′ + ∣ R ∖ W ′ ∣ ≤ q ′ + ∣ R ∣ < ( 1 + δ ) ∣ R ∣ . |W' \cup P_\tau| \leq q' + |R\setminus W'| \leq q' + |R| < (1+\delta)|R|. ∣ W ′ ∪ P τ ∣ ≤ q ′ + ∣ R ∖ W ′ ∣ ≤ q ′ + ∣ R ∣ < ( 1 + δ ) ∣ R ∣.
In this case, the comparison tree terminates at this call and incurs no separator cost. Otherwise, ∣ R ∣ ≤ q ′ / δ |R| \leq q'/\delta ∣ R ∣ ≤ q ′ / δ . Since R R R is a treewidth-t t t modulator of G ′ G' G ′ , Lemma 7.1 guarantees a branch with Y ⊆ R Y \subseteq R Y ⊆ R . Fix this branch and, for j ∈ { 1 , 2 } j \in\{1,2\} j ∈ { 1 , 2 } , put
R j = R ∩ V ( G Y , j ′ ) , τ j = tp ( G Y , j ′ − R j ) . R_j = R \cap V(G'_{Y,j}),\qquad\tau_j = \operatorname{tp}(G'_{Y,j} - R_j). R j = R ∩ V ( G Y , j ′ ) , τ j = tp ( G Y , j ′ − R j ) .
Each graph G Y , j ′ − R j G'_{Y,j} - R_j G Y , j ′ − R j is an induced subgraph of G ′ − R G' - R G ′ − R , so it has treewidth at most t t t . Moreover, since Y ⊆ R Y \subseteq R Y ⊆ R ,
( G Y , 1 ′ − R 1 ) ∪ ˙ ( G Y , 2 ′ − R 2 ) = G ′ − ( R ∪ Z Y ) . (G'_{Y,1} - R_1) \mathbin{\dot\cup} (G'_{Y,2} - R_2) = G' - (R \cup Z_Y). ( G Y , 1 ′ − R 1 ) ∪ ˙ ( G Y , 2 ′ − R 2 ) = G ′ − ( R ∪ Z Y ) .
The latter graph is an induced subgraph of G ′ − R G' - R G ′ − R . Consequently,
τ 1 ⊕ τ 2 = tp ( G ′ − ( R ∪ Z Y ) ) ⪯ tp ( G ′ − R ) ⪯ τ . \tau_1 \oplus\tau_2 = \operatorname{tp}(G' - (R \cup Z_Y)) \preceq\operatorname{tp}(G' - R) \preceq\tau. τ 1 ⊕ τ 2 = tp ( G ′ − ( R ∪ Z Y )) ⪯ tp ( G ′ − R ) ⪯ τ .
Thus, the algorithm considers the combination of the child entries indexed by τ 1 \tau_1 τ 1 and τ 2 \tau_2 τ 2 as a candidate for the parent entry indexed by τ \tau τ . By the induction hypothesis, these child entries exist and satisfy
∣ S 1 , τ 1 ∣ + ∣ S 2 , τ 2 ∣ ≤ ( 1 + δ ) ( ∣ R 1 ∣ + ∣ R 2 ∣ ) + E 1 + E 2 , |S_{1,\tau_1}| + |S_{2,\tau_2}| \leq(1+\delta)(|R_1|+|R_2|) + E_1 + E_2, ∣ S 1 , τ 1 ∣ + ∣ S 2 , τ 2 ∣ ≤ ( 1 + δ ) ( ∣ R 1 ∣ + ∣ R 2 ∣ ) + E 1 + E 2 ,
where E j E_j E j is the total separator cost in the comparison tree witnessing the guarantee for the j j j th child. The corresponding candidate at the current call is
D = Y ∪ Z Y ∪ S 1 , τ 1 ∪ S 2 , τ 2 . D = Y \cup Z_Y \cup S_{1,\tau_1} \cup S_{2,\tau_2}. D = Y ∪ Z Y ∪ S 1 , τ 1 ∪ S 2 , τ 2 .
As established above, D D D is feasible for the parent entry. Its cardinality satisfies
∣ D ∣ ≤ ∣ Y ∣ + ∣ Z Y ∣ + ∣ S 1 , τ 1 ∣ + ∣ S 2 , τ 2 ∣ ≤ ∣ Y ∣ + ( 1 + δ ) ( ∣ R 1 ∣ + ∣ R 2 ∣ ) + ∣ Z Y ∣ + E 1 + E 2 ≤ ( 1 + δ ) ∣ R ∣ + ∣ Z Y ∣ + E 1 + E 2 . \begin{aligned}
|D| &\leq|Y| + |Z_Y| + |S_{1,\tau_1}| + |S_{2,\tau_2}| \\
&\leq|Y| + (1+\delta)(|R_1|+|R_2|) + |Z_Y| + E_1 + E_2 \\
&\leq(1+\delta)|R| + |Z_Y| + E_1 + E_2.
\end{aligned} ∣ D ∣ ≤ ∣ Y ∣ + ∣ Z Y ∣ + ∣ S 1 , τ 1 ∣ + ∣ S 2 , τ 2 ∣ ≤ ∣ Y ∣ + ( 1 + δ ) ( ∣ R 1 ∣ + ∣ R 2 ∣ ) + ∣ Z Y ∣ + E 1 + E 2 ≤ ( 1 + δ ) ∣ R ∣ + ∣ Z Y ∣ + E 1 + E 2 .
The last inequality follows because Y Y Y , R 1 R_1 R 1 , R 2 R_2 R 2 are pairwise disjoint subsets of R R R . The comparison tree for the current call consists of its root and the two child comparison trees, and hence its total separator cost is E = ∣ Z Y ∣ + E 1 + E 2 E = |Z_Y| + E_1 + E_2 E = ∣ Z Y ∣ + E 1 + E 2 . Since the algorithm retains a minimum-cardinality candidate for each entry, its returned entry satisfies ∣ S τ ∣ ≤ ∣ D ∣ ≤ ( 1 + δ ) ∣ R ∣ + E |S_\tau| \le|D| \le(1+\delta)|R|+E ∣ S τ ∣ ≤ ∣ D ∣ ≤ ( 1 + δ ) ∣ R ∣ + E . This completes the induction.
Now apply the guarantee at the root with R = S ⋆ R = S^\star R = S ⋆ and τ ⋆ = tp ( G − S ⋆ ) \tau^\star= \operatorname{tp}(G-S^\star) τ ⋆ = tp ( G − S ⋆ ) , where S ⋆ S^\star S ⋆ is an optimum solution. Using the separator-cost bound and q ≤ a t k q \le at k q ≤ a t k , we obtain
∣ S τ ⋆ ∣ ≤ ( 1 + δ ) k + C q log 2 s 0 ≤ ( 1 + δ + C a t log 2 s 0 ) k . |S_{\tau^\star}| \le(1+\delta)k + \frac{Cq}{\log^2 s_0} \le\left(1+\delta+\frac{Cat}{\log^2 s_0}\right)k. ∣ S τ ⋆ ∣ ≤ ( 1 + δ ) k + log 2 s 0 C q ≤ ( 1 + δ + log 2 s 0 C a t ) k .
Choose s 0 s_0 s 0 sufficiently large that all earlier requirements hold and C a t log 2 s 0 ≤ ε 2 \frac{Cat}{\log^2 s_0} \le\frac{\varepsilon}{2} l o g 2 s 0 C a t ≤ 2 ε . Since δ = ε / 2 \delta=\varepsilon/2 δ = ε /2 , it follows that ∣ S τ ⋆ ∣ ≤ ( 1 + ε ) k |S_{\tau^\star}| \le(1+\varepsilon)k ∣ S τ ⋆ ∣ ≤ ( 1 + ε ) k . Furthermore, tw ( G − S τ ⋆ ) ≤ t \operatorname{tw}(G-S_{\tau^\star}) \le t tw ( G − S τ ⋆ ) ≤ t and tp ( G − S τ ⋆ ) ⪯ τ ⋆ \operatorname{tp}(G-S_{\tau^\star}) \preceq\tau^\star tp ( G − S τ ⋆ ) ⪯ τ ⋆ . Because G − S ⋆ ⊨ ϕ G-S^\star\models\phi G − S ⋆ ⊨ ϕ and ϕ \phi ϕ is hereditary, every type below τ ⋆ \tau^\star τ ⋆ satisfies ϕ \phi ϕ . Thus, S τ ⋆ S_{\tau^\star} S τ ⋆ is a feasible solution to the original instance. Returning the smallest stored deletion set whose remainder satisfies ϕ \phi ϕ therefore yields a feasible solution of size at most ( 1 + ε ) k (1+\varepsilon)k ( 1 + ε ) k .
Now we bound the running time. The number of states is constant. At a call with q ′ q' q ′ marked vertices, Lemma 7.1 produces at most 2 c 2 δ − 3 log 9 q ′ 2^{c2^{\delta-3}\log^9 q'} 2 c 2 δ − 3 l o g 9 q ′ branches, each with two recursive children. The number of marked vertices decreases by a factor of 2 / 3 2/3 2/3 along every recursive edge, so the recursion depth is O ( log n ) O(\log n) O ( log n ) . Consequently, the total number of recursive calls is at most 2 O H , t , ε ( log 10 n ) 2^{O_{H,t,\varepsilon}(\log^{10} n)} 2 O H , t , ε ( l o g 10 n ) . All remaining work at each call, including the bounded-treewidth computations and the constant-size table combinations, takes polynomial time for fixed H , t , ϕ , ε H,t,\phi,\varepsilon H , t , ϕ , ε . The total running time is therefore 2 O H , t , ϕ , ε ( log 10 n ) 2^{O_{H,t,\phi,\varepsilon}(\log^{10} n)} 2 O H , t , ϕ , ε ( l o g 10 n ) , which is quasipolynomial.
Proof of Lemma 4.3
We mainly follow the proof of [41 Lemma 5.1] The branching algorithm will maintain a partition { A , B , U } \{A,B,U\} { A , B , U } of the vertex set V ( G ) V(G) V ( G ) , and a “potential function” ϕ : V ( G ) → [ − 1 , δ ] \phi: V(G) \to[-1,\delta] ϕ : V ( G ) → [ − 1 , δ ] on vertices. Each element of the collection A A A returned by the algorithm will be the set A A A in (some of) the leaves of this branching. Besides, the set B B B consists of the vertices that we decide to not include in A A A , and the set U U U consists of the “undecided” vertices. At the beginning, U = V ( G ) U = V(G) U = V ( G ) and ϕ ( v ) = t \phi(v) = t ϕ ( v ) = t for all vertices v ∈ V ( G ) v \in V(G) v ∈ V ( G ) . The intuition will be that the function ϕ ( v ) \phi(v) ϕ ( v ) counts how many more out-neighbors the vertex v v v is allowed to have in the set B B B . The algorithm maintains the invariants that G [ B ] G[B] G [ B ] is t t t -degenerate and ϕ ( u ) ≥ 0 \phi(u) \ge0 ϕ ( u ) ≥ 0 for all u ∈ B ∪ U u \in B \cup U u ∈ B ∪ U ; whenever one of them is violated, the current branch is terminated without output.
Next we describe the branching. First, if every vertex of U U U already has degree at most Δ \Delta Δ in G [ B ∪ U ] G[B \cup U] G [ B ∪ U ] , then we add A A A to the collection A A A (and terminate the branch). Otherwise, there exists v ∈ U v \in U v ∈ U so that v v v has degree more than Δ \Delta Δ in G [ B ∪ U ] G[B \cup U] G [ B ∪ U ] . We arbitrarily select such a vertex v v v , and branch on it in the following sense. In the first branch, we simply move v v v from U U U to A A A . In the second branch, we move v v v from U U U to B B B and further branch on all possibilities of a subset N o u t ( v ) ⊆ N G ( v ) ∩ ( B ∪ U ) N_{\mathrm{out}}(v) \subseteq N_G(v) \cap(B \cup U) N out ( v ) ⊆ N G ( v ) ∩ ( B ∪ U ) with ∣ N o u t ∣ ≤ t |N_{\mathrm{out}}| \le t ∣ N out ∣ ≤ t , and in each of these branches, decrease ϕ ( u ) \phi(u) ϕ ( u ) by one for all vertices u ∈ ( N G ( v ) ∩ ( B ∪ U ) ) ∖ N o u t ( v ) u \in(N_G(v) \cap(B \cup U)) \setminus N_{\mathrm{out}}(v) u ∈ ( N G ( v ) ∩ ( B ∪ U )) ∖ N out ( v ) . After that, if G [ B ] G[B] G [ B ] is not t t t -degenerate or ϕ ( u ) = − 1 \phi(u) = -1 ϕ ( u ) = − 1 for some u ∈ B u \in B u ∈ B , we terminate the branch without output. Otherwise, we move all vertices u ∈ U u \in U u ∈ U with ϕ ( u ) = − 1 \phi(u) = -1 ϕ ( u ) = − 1 to the set A A A . Note that the ϕ \phi ϕ -value of each vertex is decreased at most once per step, so ϕ ( u ) ≥ − 1 \phi(u) \ge-1 ϕ ( u ) ≥ − 1 always holds.
To see the correctness of the above branching algorithm, we first show the collection A A A returned satisfies condition (i). Let A ∈ A A \in\mathcal{A} A ∈ A and consider the leaf of the branching tree at which A A A is added to A \mathcal{A} A . By the invariant, at this point, G [ B ] G[B] G [ B ] is t t t -degenerate, and every vertex of U = V ( G ) ∖ ( A ∪ B ) U = V(G) \setminus(A \cup B) U = V ( G ) ∖ ( A ∪ B ) has degree at most Δ \Delta Δ in G [ B ∪ U ] = G − A G[B \cup U] = G - A G [ B ∪ U ] = G − A . It remains to bound ∣ B ∣ |B| ∣ B ∣ . To this end, we consider the function ϕ + : V ( G ) → [ 0 , t + 1 ] \phi^+ : V(G) \to[0,t+1] ϕ + : V ( G ) → [ 0 , t + 1 ] defined as ϕ + ( v ) = ϕ ( v ) + 1 \phi^+(v) = \phi(v)+1 ϕ + ( v ) = ϕ ( v ) + 1 for all v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , and let ϕ + ( B ∪ U ) = ∑ v ∈ B ∪ U ϕ + ( v ) \phi^+(B \cup U) = \sum_{v \in B \cup U} \phi^+(v) ϕ + ( B ∪ U ) = ∑ v ∈ B ∪ U ϕ + ( v ) . Observe that at the beginning, the value of ϕ + ( U ∪ U ) \phi^+(U \cup U) ϕ + ( U ∪ U ) is ( t + 1 ) ⋅ n (t+1) \cdot n ( t + 1 ) ⋅ n , that it is always non-negative, and that moving vertices from U U U to A A A does not increase it. In all branches of the second type, the vertex v v v stays in B ∪ U B \cup U B ∪ U , and ϕ + ( u ) \phi^+(u) ϕ + ( u ) decreases by one for all u ∈ ( N G ( v ) ∩ ( B ∪ U ) ) ∖ N o u t ( v ) u \in(N_G(v) \cap(B \cup U)) \setminus N_{\mathrm{out}}(v) u ∈ ( N G ( v ) ∩ ( B ∪ U )) ∖ N out ( v ) , so the value ϕ + ( B ∪ U ) \phi^+(B \cup U) ϕ + ( B ∪ U ) decreases by at least Δ + 1 − t \Delta+ 1 - t Δ + 1 − t . Therefore, in any root-leaf path of the branching tree, there can be at most ( t + 1 ) n / ( Δ − t + 1 ) (t+1)n/(\Delta- t + 1) ( t + 1 ) n / ( Δ − t + 1 ) branches of the second type. This implies that in each leaf, the set B B B is of size at most ( t + 1 ) n / ( Δ − t + 1 ) (t+1)n/(\Delta- t + 1) ( t + 1 ) n / ( Δ − t + 1 ) . Then we show that A \mathcal{A} A satisfies condition (ii). Consider a subset S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) such that G − S G-S G − S is t t t -degenerate. We need to show the existence of A ∈ A A \in\mathcal{A} A ∈ A with A ⊆ S A \subseteq S A ⊆ S . Let σ \sigma σ be a fixed t t t -degeneracy ordering of G − S G-S G − S . For v ∈ V ( G ) ∖ S v \in V(G)\setminus S v ∈ V ( G ) ∖ S , denote by Γ ( v ) \Gamma(v) Γ ( v ) the set of (at most t t t ) out-neighbors of v v v in G − S G-S G − S under σ \sigma σ . We say a node of the branching tree is good if at the node we have A ⊆ S A \subseteq S A ⊆ S , B ∩ S = ∅ B \cap S = \emptyset B ∩ S = ∅ , and ϕ ( v ) ≥ ∣ Γ ( v ) ∩ U ∣ \phi(v) \geq|\Gamma(v) \cap U| ϕ ( v ) ≥ ∣Γ ( v ) ∩ U ∣ for all v ∈ V ( G ) ∖ S v \in V(G)\setminus S v ∈ V ( G ) ∖ S . Note that the root of the branching tree is good. Furthermore, we define the notion of correct and wrong branches as follows. During the algorithm, when branching on a vertex v ∈ U v \in U v ∈ U ,
Observe that at a good node of the branching tree, exactly one of its branches is correct, because ∣ Γ ( v ) ∖ S ∣ ≤ t |\Gamma(v)\setminus S| \leq t ∣Γ ( v ) ∖ S ∣ ≤ t and for a good node we have Γ ( v ) ∖ S ⊆ N G ( v ) ∖ A = N G ( v ) ∩ ( B ∪ U ) \Gamma(v)\setminus S \subseteq N_G(v)\setminus A=N_G(v)\cap(B\cup U) Γ ( v ) ∖ S ⊆ N G ( v ) ∖ A = N G ( v ) ∩ ( B ∪ U ) . Furthermore, one can easily verify that if y y y is a child of a good node x x x and the branch x → y x \to y x → y is correct, then y y y is also good. Therefore, if we go from the root of the branching tree and follow the correct branches, we will reach a leaf that is good. At this leaf, the set A A A is added to A \mathcal{A} A and it holds that A ⊆ S A \subseteq S A ⊆ S .
Finally, it suffices to bound the time complexity and the size of A \mathcal{A} A . At each node of the branching tree, at most one branch is of the first type and n O ( t ) n^{O(t)} n O ( t ) branches are of the second type. Furthermore, as observed before, along any root-leaf path, there can be at most ( t + 1 ) n / ( Δ − t + 1 ) = O ( t n / Δ ) (t+1)n/(\Delta-t+1)=O(tn/\Delta) ( t + 1 ) n / ( Δ − t + 1 ) = O ( t n /Δ ) branches of the second type. Since the height of the branching tree is at most n n n , the number of root-leaf paths is at most
n O ( t n / Δ ) ⋅ n O ( t 2 n / Δ ) = n O ( t 2 n / Δ ) . n^{O(tn/\Delta)} \cdot n^{O(t^2n/\Delta)} = n^{O(t^2n/\Delta)}. n O ( t n /Δ ) ⋅ n O ( t 2 n /Δ ) = n O ( t 2 n /Δ ) .
This directly bounds the number of nodes in the branching tree. Since we add at most one set to A \mathcal{A} A at each leaf and the time cost at each node is n O ( 1 ) n^{O(1)} n O ( 1 ) , we see that ∣ A ∣ = n O ( t 2 n / Δ ) |\mathcal{A}|=n^{O(t^2n/\Delta)} ∣ A ∣ = n O ( t 2 n /Δ ) and the time complexity of the algorithm is also n O ( t 2 n / Δ ) n^{O(t^2n/\Delta)} n O ( t 2 n /Δ ) .