Introduction
Graph decompositions are a general set of tools that allow us to break graphs into smaller pieces, connected to each other in somewhat restricted way. One of the motivations behind this line of study is algorithmic: many computational problems can often be solved using some kind of dynamic programming over a decomposition, and the “complexity” (usually referred to as width ) of the decompositions restricts the number of states one needs to consider.
Arguably, the best known type of graph decompositions are tree decompositions, discovered independently by several groups of authors with different motivations [4 , 6 , 38 , 47 ] . Intuitively, a tree decomposition of a graph G G G is a tree T T T whose vertices (typically called nodes ) are equipped with subsets of the vertex set of G G G , called bags , so that the general structure of G G G is reflected by the structure of T T T . If each bag is “simple,” then the whole graph is considered “simple.” Perhaps the most straightforward notion of simplicity is constant size. This leads to the definition of treewidth : a graph has treewidth k k k if it admits a tree decomposition whose every bag is of size less than k k k . Consequently, if a graph has small treewidth, then it “resembles a tree.”
The drawback of treewidth is that its boundedness implies that the graph is sparse, i.e., it has a linear number of edges. Thus, this parameter is not suitable for studying classes of “well-structured” dense graphs, like chordal graphs. As a remedy, in recent years there is a growing interest in structured tree decompositions where we do not aim to obtain small bags, but rather bags of “simple structure.” A motivating example is the class of chordal graphs mentioned above: they are precisely graphs that admit tree decompositions whose every bag is a clique. Such cliques can be arbitrarily large, but their structure is indeed rather simple.
A generalization of this idea is the tree-independence number (denoted by tree-α ( G ) \alpha(G) α ( G ) ), introduced independently by Yolov [50 ] and by Dallard, Milanič, and Štorgel [27 ] . Here, for every bag of a tree decomposition, we measure the size of a largest independent set in the graph induced by the bag. In particular, chordal graphs are precisely graphs of tree-independence number 1. We remark that tree-independence number is always upper-bounded by treewidth (plus 1).
As already observed by Yolov [50 ] , tree-independence number might still be large on graphs of simple structure, like complete bipartite graphs. Thus, he introduced another parameter, minor-matching hypertreewidth , which is now usually called induced matching treewidth and denoted by tree-μ ( G ) \mu(G) μ ( G ) . This time, for every bag of a tree decomposition, we measure the size of a largest induced matching whose every edge intersects the bag (note that the matching might not be contained in the bag). It is not hard to observe that induced matching treewidth never exceeds tree-independence number, but can be much smaller. In particular, bicliques have induced matching treewidth 1.
When introducing a new graph parameter, there are three important questions to have in mind:
(Q1) If the parameter is bounded, can we solve some interesting computational problems efficiently?
(Q2) If the parameter is bounded, can we compute a corresponding decomposition efficiently?
(Q3) Are there any interesting classes of graphs in which the parameter is bounded?
Let us briefly discuss the state of art concerning these three questions for tree-independence number and induced matching treewidth.
Concerning (Q1), Yolov [50 ] showed that some classic problems including Max Weight Independent Set (MWIS) and k k k -Coloring are solvable in polynomial time for graphs given with a tree decomposition witnessing that tree-independence number or induced matching treewidth is bounded. Another family of problems that are tractable in the discussed setting concern packing induced subgraphs, possibly with distance constraints [27 , 28 ] . Lima, Milanič, Murišić, Okrasa, Rzążewski, and Štorgel [28 ] showed that ( tw ≤ r , ψ ) (\operatorname{tw} \le r,\psi) ( tw ≤ r , ψ ) -MWIS, a wide generalization of MWIS (see § 10 for the definition) can be solved efficiently in classes of bounded tree-independence number (see also the refined version of this result [41 ] ). The authors conjectured that the same holds for induced matching treewidth, supporting this with several partial results. The conjecture was recently confirmed by Bodlaender, Fomin, and Korhonen [8 ] .
Concerning (Q2), already in the first paper introducing both parameters, Yolov [50 ] showed that both tree-independence number and induced matching treewidth admit XP-approximation algorithm with respect to the value of the parameter. More precisely, given an n n n -vertex graph G G G and an integer k k k , in time n O ( k 3 ) n^{O(k^3)} n O ( k 3 ) one can compute a tree decomposition witnessing that tree - α ( G ) = O ( k 3 ) \operatorname{tree}\text{-}\alpha(G)=O(k^3) tree - α ( G ) = O ( k 3 ) (resp., tree - μ ( G ) = O ( k 3 ) \operatorname{tree}\text{-}\mu(G)=O(k^3) tree - μ ( G ) = O ( k 3 ) ) or conclude that the corresponding parameter is larger than k k k . Later, Dallard, Fomin, Golovach, Korhonen, and Milanič [25 ] proposed a refined algorithm that runs in time 2 O ( k 2 ) n O ( k ) 2^{O(k^2)}n^{O(k)} 2 O ( k 2 ) n O ( k ) and returns a tree decomposition showing that tree - α ( G ) ≤ 8 k \operatorname{tree}\text{-}\alpha(G)\le8k tree - α ( G ) ≤ 8 k or concludes tree - α ( G ) > k \operatorname{tree}\text{-}\alpha(G)>k tree - α ( G ) > k . Using a structural observation of Yolov [50 ] one can use this algorithm to obtain analogous results for induced matching treewidth [28 ] .
Interestingly, this approach is essentially optimal (up to improving the constant 8 8 8 and the 2 O ( k 2 ) 2^{O(k^2)} 2 O ( k 2 ) -factor). In particular, known reductions [25 ] exclude an exact algorithm even for k = 4 k=4 k = 4 , as well as any FPT-approximation algorithm, under standard assumptions in complexity theory.
Classes considered in (Q3) are typically defined by excluding some graphs under one of the standard containment relations: as a subgraph, a topological minor, and a minor, as well as their induced counterparts, see § 2 for formal definitions of these relations. For a relation ⋆ \star ⋆ and a graph H H H , we say that a graph G G G is H H H -⋆ \star ⋆ -free if it does not contain H H H with respect to ⋆ \star ⋆ .
Dallard, Milanič, and Štorgel [26 ] studied tree-independence number in classes defined by forbidding a single graph under the relations mentioned above. For each of the six considered relations, they fully characterized graphs H H H whose exclusion bounds tree-independence number, see Table 1 . Since then, the classes of small tree-independence number have been a topic of investigation [1 , 14 , 15 , 17 ] .
Table 1. Maximal (w.r.t. a given containment relation) graphs whose exclusion (w.r.t. that relation) implies boundedness of tree-independence number or induced matching treewidth. In the last column we additionally assume that graphs have no vertices of degree at most 1.
On the other hand, very little is known about which classes have bounded induced matching treewidth. Let us mention that Abrishami, Briański, Czyżewska, McCarty, Rzążewski, and Walczak [2 ] showed that induced matching treewidth and tree-independence number are functionally equivalent for graphs that exclude some fixed biclique as an induced subgraph. However, for classes that contain arbitrarily large bicliques, we are not aware of any results.
Our results.
In this paper we initiate a systematic study of classes of graphs that have bounded induced matching treewidth, see Table 1 . The definitions of the graphs listed throughout this section can be found in § 2 .
Dichotomy theorems. First, we show results analogous to ones obtained for tree-independence number by Dallard, Milanič, and Štorgel [26 ] : for each of the six basic containment relations, we fully characterize which classes defined by excluding a single graph have bounded induced matching treewidth.
For subgraphs, induced subgraphs, minors, and topological minors, the dichotomies almost coincide with the ones for tree-independence number. Note that graphs with no large induced matching have trivially bounded induced matching treewidth, just like graphs with no large independent set have trivially bounded tree-independence number.
Theorem 1.1. Let H H H be a graph with at least 2 2 2 vertices. The following hold.
(1.) The class of H H H -subgraph-free graphs has bounded induced matching treewidth if and only if H H H every component of H H H is a subcubic tree with at most one vertex of degree $3.
(2.) The class of H H H -free graphs has bounded induced matching treewidth if and only if H H H is P 3 P_3 P 3 or a graph with maximum degree 1.
(3.) The class of H H H -minor-free graphs has bounded induced matching treewidth if and only if H H H is planar.
(4.) The class of H H H -topological-minor-free graphs has bounded induced matching treewidth if and only if H H H is subcubic and planar.
All unbounded cases remain so, even when restricted to 2-connected graphs.
The landscape gets a bit richer when we exclude a graph as an induced topological minor: here we get a new bounded case: 1-tipi, also known as the paw, see Figure 1 .
Figure 1. The q q q -tipi (left), q q q -windmill (middle), and K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) (right).
Theorem 1.2. Let H H H be a graph with at least 2 vertices. The class of H H H -topological-minor-free graphs has bounded induced matching treewidth if and only if H H H is not contained in one of the following graphs: C 4 C_4 C 4 , K 4 − K_4^- K 4 − , 1-tipi, or a matching as an induced topological minor. All unbounded cases remain so, even when restricted to 2-connected graphs.
For H H H -induced-minor-free graphs, we actually get an infinite family of bounded cases: it turns out that excluding any tipi (i.e., the q q q -tipi for any q q q ) bounds the induced matching treewidth.
Theorem 1.3. Let H H H be a graph with at least 2 vertices. The class of H H H -induced-minor-free graphs has bounded induced matching treewidth if and only if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q for some q ∈ N q \in\mathbb{N} q ∈ N , W 4 W_4 W 4 , K 5 − K_5^- K 5 − , a tipi, or a matching.
Restricting to graphs of minimum degree 2. Recall that the motivation to consider induced matching treewidth was that tree-independence number is unbounded in some very simple classes of graphs, like bicliques. Admittedly, induced matching treewidth has similar drawback. Consider for example the graph obtained from the biclique with each part of size n n n by adding a private neighbor to every vertex. As noted by Yolov [50 ] this graph has induced matching treewidth n n n .
However, instead of defining a new parameter, we can take another route. If our motivation is algorithmic, perhaps degree-1 vertices do not play a crucial role and can be removed by some preprocessing rule. In general, we can try to apply various (problem-dependent) preprocessing rules to the considered graph and only then ask if the considered parameter is bounded. This idea is not new, but previously it was applied to other (not tree-decomposition-based) graph parameters, like clique-width [24 , 35 ] and mim-width [13 ] .
We investigate this direction for tree-independence number and induced matching treewidth in classes excluding a fixed substructure. First, let us restrict our attention to graphs with minimum degree 2 as for most classic computational problems we can indeed easily handle vertices of degree at most 1. It turns out that for tree-independence number this change in the setting does not alter the dichotomies for any of the six consider containment relations. Similarly, for induced matching treewidth and (induced) subgraph, (induced) topological minors, and minors, the classification remains the same as before.
However, for H H H -induced-minor-free graphs, we get new family of bounded cases: if H H H is a windmill , i.e., the q q q -windmill for any q q q ; see Figure 1 .
Theorem 1.4. Let H H H be a graph. The class of H H H -induced-minor-free graphs, restricted to graphs with minimum degree at least 2, has bounded induced matching treewidth if and only if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q for some q ∈ N q \in\mathbb{N} q ∈ N , W 4 W_4 W 4 , K 5 − K_5^{-} K 5 − , or a windmill.
Graphs that exclude a fixed windmill as an induced minor were considered by Bonnet, Duron, Geniet, Thomassé, and Wesolek [11 ] ; we will get back to this soon.
Restricting to 2-connected graphs. We can further generalize the idea of removing vertices of degree 1: we can assume that the input graph is 2-connected. Indeed, for many problems such an assumption is justified (see e.g. § 10 ). Note that this setting generalizes the one considered before, as every 2-connected graph has no vertices of degree at most 1. Again, it turns out that for two parameters and six containment relations studied in this paper, only the case of induced matching treewidth of H H H -induced-minor-free graphs differs from the basic dichotomies without any further restrictions imposed on the graph.
In this setting, we get one more bounded case: K ^ 4 ( 1 ) \widehat{K}_4^{(1)} K 4 ( 1 ) , for simplicity denoted as K ^ 4 \widehat{K}_4 K 4 , see Figure 1 .
Theorem 1.5. Let H H H be a graph. The class of H H H -induced-minor-free graphs, restricted to 2-connected graphs, has bounded induced matching treewidth if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q for some q q q , W 4 W_4 W 4 , K 5 − K_5^{-} K 5 − , a windmill, a matching, or K ^ 4 \widehat{K}_4 K 4 . If H H H is not one of these graphs, nor K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) for some fixed q q q , then 2-connected H H H -induced-minor-free graphs have unbounded induced matching treewidth.
Our Theorem 1.5 leaves one family of open cases: H = K ^ 4 ( q ) H = \widehat{K}_4^{(q)} H = K 4 ( q ) for some q ≥ 2 q \ge2 q ≥ 2 . For them, we were not able to prove either boundedness nor unboundedness of induced matching treewidth for 2-connected H H H -induced-minor-free graphs. We believe in the former outcome and we state the following conjecture.
Conjecture 1.6. For every fixed q ≥ 1 q \ge1 q ≥ 1 , the class of 2-connected K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) -induced-minor-free graphs has bounded induced matching treewidth.
Algorithmic consequences. Now, let us turn our attention to algorithmic implications of our results. We consider two general families of problems: ( tw ≤ r , ψ ) (\operatorname{tw} \le r,\psi) ( tw ≤ r , ψ ) -MWIS and Max Induced H H H -Colorable Subgraph. The first one asks for a maximum-weight induced subgraph of treewidth at most r r r , satisfying given CMSO2 _2 2 formula, while the second one asks for a maximum-weight induced subgraph homomorphic to a fixed simple graph H H H ; see § 10 for precise definitions. Let us mention that the first family captures, e.g., MWIS, Feedback Vertex Set, and Even Cycle Transversal, while the second family captures, e.g., MWIS (again), Odd Cycle Transversal, and List k k k -Coloring for any fixed k k k .
We show that for all problems described by the formalisms above, it is indeed enough to solve instances that are 2-connected. Thus, combining this with known algorithms for graphs of bounded induced matching treewidth [8 , 50 ] and our Theorem 1.5, we obtain the following algorithmic corollary. (The first column follows from bounded tree-independence number and thus, it was known before, while the second column contains new results.)
Corollary 1.7. Every problem that can be described as Max Induced H H H -Colorable Subgraph for some fixed simple graph H H H or ( tw ≤ r , ψ ) (\operatorname{tw} \le r,\psi) ( tw ≤ r , ψ ) -MWIS for fixed r r r and a formula ψ \psi ψ , can be solved in polynomial time when restricted to graphs from the following classes:
K 2 , q K_{2,q} K 2 , q -induced-minor-free for any fixed q q q ,
W 4 W_4 W 4 -induced-minor-free,
K 5 − K_5^{-} K 5 − -induced-minor-free,
q q q -windmill-induced-minor-free for any fixed q q q ,
K ^ 4 \widehat{K}_4 K 4 -induced-minor-free.
Let us mention some context of these results. First, as already mentioned, Bonnet, Duron, Geniet, Thomassé, and Wesolek [11 ] considered graphs that exclude a fixed windmill as an induced minor, and showed that MWIS can be solved in polynomial time in every such class. Our Corollary 1.7 not only heavily generalizes this result, but also shows the underlying reason why this class admits algorithms for classic problems.
Second, our results confirm special cases of the following conjecture of Gartland and Lokshtanov [32 ] .
Conjecture 1.8 (Gartland and Lokshtanov). For any fixed planar graph H H H , integer r r r , and a formula ψ \psi ψ , ( tw ≤ r , ψ ) (\operatorname{tw} \le r,\psi) ( tw ≤ r , ψ ) -MWIS and List 3-Coloring can be solved in polynomial time in H H H -induced-minor-free graphs.
Very recently, Conjecture 1.8 was disproved by Bonnet and Chang [51 ] for H H H being the 5 × 5 5 \times5 5 × 5 grid. However, the statement was confirmed for some families of simple planar graphs H H H [3 , 12 , 18 , 19 , 31 , 36 , 39 , 40 , 42 ] and it remains a very interesting open problem to understand for which graphs H H H the conjecture actually holds. Even its relaxed variants, asking for quasipolynomial-time algorithms, or at least a quasipolynomial-time approximation scheme (QPTAS) for MWIS, remain very challenging and are shown only in restricted cases [9 , 10 , 11 , 16 , 23 , 33 , 34 , 44 , 46 ] .
Dominated balanced separators. Finally, we show one more consequence of our results. For a constant t t t , a class of graphs is said to admit t t t -dominated balanced separator if every graph from the class a set of at most t t t vertices, such that removing these vertices along with their neighbors breaks the graph into small pieces; see § 11 for precise definitions. We show that boundedness of induced matching treewidth, even for just 2-connected members of the considered class, yields O ( 1 ) O(1) O ( 1 ) -dominated balanced separators. Thus we obtain the following.
Corollary 1.9. The following classes of graphs admit t t t -dominated balanced separators, where t t t is a constant depending only on the class.
K 2 , q K_{2,q} K 2 , q -induced-minor-free for any fixed q q q ,
W 4 W_4 W 4 -induced-minor-free,
K ‾ 5 \overline{K}_5 K 5 -induced-minor-free,
q q q -windmill-induced-minor-free for any fixed q q q ,
K ‾ 4 \overline{K}_4 K 4 -induced-minor-free.
Corollary 1.9 confirms special cases of another conjecture by Gartland and Lokshtanov [32 ] .
Conjecture 1.10 (Gartland and Lokshtanov). For any fixed planar graph H H H there exists t t t such that H H H -induced-minor-free graphs admit t t t -dominated balanced separators.
Conjecture 1.10 is also very challenging and, despite interest in the community, was only confirmed for very restricted graphs H H H [5 , 16 , 20 , 23 ] .
Organization of the paper. In § 2 we define main notions used in the paper and show some basic results. In § 3 we construct some families of graphs with unbounded induced matching treewidth. In § 6 we discuss graphs that exclude a tipi as an induced minor. In § 7 we show Theorems 1.1 , 1.2 and 1.3, i.e., dichotomy theorems for classes that exclude one fixed graph. In § 8 we dicuss the problem where we additionally assume that th graphs considered have minimum degree 2, and prove Theorem 1.4. In § 9 we restrict ourselves to 2-connected graphs wne show Theorem 1.5. In § 10 we discuss algorithmic consequences of our results and show Corollary 1.7. In § 11 we discuss dominated balanced separators an show Corollary 1.9. Finally, in § 12 , we point out some directions for further research.
Definitions and basic tools
For an integer n n n , by [ n ] [n] [ n ] we denote the set { 1 , 2 , … , n } \{1,2,\ldots,n\} { 1 , 2 , … , n } . For a set X X X , by 2 X 2^{X} 2 X we denote the family of all subsets of X X X .
Graph theory. All graphs in the paper are undirected and simple, i.e., without loops or parallel edges. Let G G G be a graph and consider X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) . By G [ X ] G[X] G [ X ] we denote the subgraph of G G G induced by X X X and by G − X G-X G − X we denote G [ V ( G ) ∖ X ] G[V(G) \setminus X] G [ V ( G ) ∖ X ] . We use N [ X ] N[X] N [ X ] for the closed neighborhood of X X X , i.e., the set consisting of X X X and all vertices adjacent to a vertex of X X X . If it does not lead to confusion, sometimes we identify induced subgraphs with their vertex sets.
We say that a graph is biconnected if it is 2-connected or isomorphic to K 2 K_2 K 2 . A block is an inclusion-wise biconnected (induced) subgraph of a graph. A block-cut tree of a connected graph G G G is the bipartite graph whose vertices are blocks and cutvertices of G G G , and a cutvertex v v v and a block b b b are adjacent if and only if v ∈ b v \in b v ∈ b . It is well-known that the block-cut tree is indeed a tree. Note that all leaves of this tree are blocks. We treat block-cut trees as rooted trees, where the root r r r is an arbitrarily chosen leaf and which defines a parent-child relation between adjacent nodes. For a block node b ≠ r b \ne r b = r , if v b v_b v b is the cutvertex that is the parent of b b b in T T T , then the parent of v b v_b v b in T T T is called the parent block . Analogously we define children blocks and leaf blocks .
A matching in a graph is a set of pairwise disjoint edges. For a matching M M M , by V ( M ) V(M) V ( M ) we denote the set of vertices of edges in M M M . A matching M M M in a graph G G G is induced if the edge set of G [ V ( M ) ] G[V(M)] G [ V ( M )] is M M M , i.e., there are no edges joining vertices belonging to two distinct edges in M M M . Given a graph G G G and two vertex subsets A , B ⊆ V ( G ) A,B \subseteq V(G) A , B ⊆ V ( G ) , an induced ( A , B ) (A,B) ( A , B ) -matching of G G G is an induced matching M M M of G G G whose edges have one endpoint in A A A and one endpoint in B B B .
Graph containment relations. For a graph G G G and an edge x y xy x y , contracting x y xy x y is the operation of introducing a new vertex adjacent to every vertex adjacent to x x x or y y y , and then removing x x x and y y y . A contraction is topological if one of the vertices x , y x,y x , y is of degree 2 in G G G . For a graph G G G and an edge x y xy x y , subdividing x y xy x y is the operation of adding a new vertex adjacent to x x x and y y y .
For a containment relation ⋆ \star ⋆ , we say that a graph G G G contains a graph H H H as ⋆ \star ⋆ , if H H H can be obtained from G G G by a sequence of allowed elementary operations , according to the following table:
Table 2.
We will interchangeably use terms induced topological minor and induced subdivision . Note that all relations discussed above are transitive, i.e., if G G G contains H H H and H H H contains F F F , then G G G contains F F F (with respect to the considered relation). Furthermore, the relations between these relations are depicted in Figure 2 .
Figure 2. The considered containment relations as a poset. A relation ⋆ \star ⋆ is greater than (above) a relation ∗ \ast ∗ if every graph G G G that contains H H H as ∗ \ast ∗ also contains H H H as ⋆ \star ⋆ . In other words, H H H -⋆ \star ⋆ -free graphs form a subclass of H H H -∗ \ast ∗ -free graphs.
A class is hereditary if it is closed under vertex deletion (i.e., taking induced subgraphs). Note that if ⋆ \star ⋆ is any of the relations discussed above and H H H is any graph, then H H H -⋆ \star ⋆ -free graphs form a hereditary class.
Some special graphs. For graphs H 1 H_1 H 1 , H 2 H_2 H 2 , by H 1 + H 2 H_1 + H_2 H 1 + H 2 we denote the graph obtained as a disjoint union of H 1 H_1 H 1 and H 2 H_2 H 2 .
By P k P_k P k (resp., C k C_k C k ) we denote the path (resp., the cycle) with k k k vertices. We say that a graph is a linear forest if it is isomorphic to a disjoint union of paths. If it does not lead to confusion, a linear forest with every component having at most two vertices will be called a matching .
A wheel is a graph obtained from a cycle by adding a universal vertex. The 4 4 4 -wheel , denoted by W 4 W_4 W 4 , is the wheel obtained from C 4 C_4 C 4 .
For k ∈ N k \in\mathbb{N} k ∈ N , the k k k -tipi is the graph that is obtained from K 3 K_3 K 3 after attaching k k k vertices of degree one to a single vertex of K 3 K_3 K 3 ; see Figure 1 . For k ∈ N k \in\mathbb{N} k ∈ N , the k k k -windmill is the graph that is obtained from a matching with k k k edges by adding a universal vertex, see Figure 1 . Note that the k k k -tipi is an induced subgraph of the ( k + 1 ) (k+1) ( k + 1 ) -windmill. We say that G G G is a tipi (resp., a windmill ) if it is a k k k -tipi (resp. k k k -windmill) for some k ∈ N k \in\mathbb{N} k ∈ N .
The bull is the graph obtained from K 3 K_3 K 3 by adding two degree-1 vertices, each adjacent to a different vertex of the triangle. The house is the graph obtained from C 4 C_4 C 4 by adding a new vertex, adjacent to two consecutive vertices of the cycle.
By K k K_k K k we denote the complete graph on k k k vertices. By K k − K_k^{-} K k − we denote the graph obtained from K k K_k K k by deleting a single edge. For integers k 1 , k 2 , … , k ℓ k_1, k_2, \ldots, k_\ell k 1 , k 2 , … , k ℓ , by K k 1 , k 2 , … , k ℓ K_{k_1,k_2,\ldots,k_\ell} K k 1 , k 2 , … , k ℓ we denote the complete ℓ \ell ℓ -partite graph with parts of size, respectively, k 1 , k 2 , … , k ℓ k_1, k_2, \ldots, k_\ell k 1 , k 2 , … , k ℓ .
For q ≥ 1 q \ge1 q ≥ 1 , by K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) we denote the graph obtained from K 4 K_4 K 4 by adding q q q new, pairwise nonadjacent vertices, all adjacent with the same pair of vertices of the K 4 K_4 K 4 . We shortly write K ^ 4 : = K ^ 4 ( 1 ) \widehat{K}_4 := \widehat{K}_4^{(1)} K 4 := K 4 ( 1 ) .
A k k k -wall is the k × k k \times k k × k hexagonal grid. A subdivided k k k -wall is any graph obtained from the k k k -wall by repeatedly subdividing edges. A properly subdivided k k k -wall is obtained from the k k k -wall by subdividing each edge at least once. Note that every (subdivided) wall is subcubic, and so is the line graph of each properly subdivided wall.
For graphs G G G and H H H , let G ⊙ H G \odot H G ⊙ H denote the graph obtained from G G G by adding ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ copies of H H H , one for each vertex v v v of G G G , and adding all edges between v v v and the vertices of its copy of H H H .
Treewidth, tree-independence number, and induced matching treewidth. 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 tree and β : V ( T ) → 2 V ( G ) \beta: V(T) \to2^{V(G)} β : V ( T ) → 2 V ( G ) is a bag function that satisfies the following two properties:
for each vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , the set { t ∈ V ( T ) ∣ v ∈ β ( t ) } \{t \in V(T) \mid v \in\beta(t)\} { t ∈ V ( T ) ∣ v ∈ β ( t )} is nonempty and induces a subtree of T T T ,
for each edge e ∈ E ( G ) e \in E(G) e ∈ E ( G ) there is t ∈ V ( T ) t \in V(T) t ∈ V ( T ) such that e ⊆ β ( t ) e \subseteq\beta(t) e ⊆ β ( t ) .
A tree decomposition ( T , β ) (T,\beta) ( T , β ) , where T T T is a path, is called a path decomposition .
Let T = ( T , β ) \mathcal{T}=(T,\beta) T = ( T , β ) be a tree decomposition of a graph G G G . The width of T \mathcal{T} T is defined as max t ∈ V ( T ) ∣ β ( t ) ∣ − 1 \max_{t\in V(T)}|\beta(t)|-1 max t ∈ V ( T ) ∣ β ( t ) ∣ − 1 . The independence number of T \mathcal{T} T is the size of a largest independent set in G [ β ( t ) ] G[\beta(t)] G [ β ( t )] , over all t ∈ V ( T ) t \in V(T) t ∈ V ( T ) . The induced matching width of T \mathcal{T} T is the largest size of an induced ( β ( t ) , V ( G ) ) (\beta(t),V(G)) ( β ( t ) , V ( G )) -matching, over all t ∈ V ( T ) t \in V(T) t ∈ V ( T ) .
The treewidth (resp. tree-independence number , induced matching treewidth ) of G G G , denoted by tw ( G ) \operatorname{tw}(G) tw ( G ) (resp., tree - α ( G ) \operatorname{tree}\text{-}\alpha(G) tree - α ( G ) , tree - μ ( G ) \operatorname{tree}\text{-}\mu(G) tree - μ ( G ) ) is the minimum width (resp., independence number, induced matching width) of a tree decomposition of G G G .
The following proposition summarizes some known relations between these three parameters, see [2 , 28 , 50 ] .
Proposition 2.1. The following hold for every graph G G G .
(1.) tree - μ ( G ) ≤ tree - α ( G ) ≤ tw ( G ) + 1 , \operatorname{tree}\text{-}\mu(G) \le\operatorname{tree}\text{-}\alpha(G) \le\operatorname{tw}(G)+1, tree - μ ( G ) ≤ tree - α ( G ) ≤ tw ( G ) + 1 ,
(2.) tree - α ( G ) = tree - μ ( G ⊙ K 1 ) , \operatorname{tree}\text{-}\alpha(G)=\operatorname{tree}\text{-}\mu(G\mathbin{\odot}K_1), tree - α ( G ) = tree - μ ( G ⊙ K 1 ) ,
(3.) tw ( G ) ≤ 2 tree - μ ( G ) ⋅ Δ ( G ) 2 ( Δ ( G ) + 1 ) \operatorname{tw}(G)\le2\operatorname{tree}\text{-}\mu(G)\cdot\Delta(G)^2(\Delta(G)+1) tw ( G ) ≤ 2 tree - μ ( G ) ⋅ Δ ( G ) 2 ( Δ ( G ) + 1 ) , where Δ ( G ) \Delta(G) Δ ( G ) is the maximum vertex degree in G G G .
Let us also show one simple property of tree-independence number.
Lemma 2.2. Let G \mathcal{G} G be a hereditary class, and let G 2 -conn \mathcal{G}_{2\text{-conn}} G 2 -conn consist of the 2-connected graphs in G \mathcal{G} G . Then G \mathcal{G} G has bounded tree-independence number if and only if G 2 -conn \mathcal{G}_{2\text{-conn}} G 2 -conn has bounded tree-independence number.
Proof. The forward implication is immediate. Conversely, suppose that every graph in G 2 -conn \mathcal{G}_{2\text{-conn}} G 2 -conn has tree-independence number at most k ≥ 1 k \ge1 k ≥ 1 .
Pick any G ∈ G G \in\mathcal{G} G ∈ G . We may assume that G G G is connected, as otherwise we can easily obtain a tree decomposition of G G G by combining tree decompositions of its components. Every block of G G G is either 2-connected or isomorphic to K 2 K_2 K 2 ; hence, since G \mathcal{G} G is hereditary, it has a tree decomposition of independence number at most k k k .
Fix such a tree decomposition T B \mathcal{T}_B T B of each block b b b of G G G . For each cutvertex v v v of G G G , we create a node t v t_v t v whose bag is { v } \{v\} { v } . Now we combine these decompositions along the block-cut tree of G G G . More precisely, if a block b b b contains a cutvertex v v v , we join the node t v t_v t v to an arbitrary node of T b \mathcal{T}_b T b whose bag contains v v v . It is straightforward to verify that this way we obtain a tree decomposition of G G G of independence number at most k k k .
:::
BFS-layerings. For a connected graph G G G and a vertex r r r , the BFS-layering of G G G rooted at r r r is the partition ( L 0 , … , L q ) (L_0,\ldots,L_q) ( L 0 , … , L q ) of V ( G ) V(G) V ( G ) , where L 0 = { r } L_0=\{r\} L 0 = { r } and for i ≥ 1 i\ge1 i ≥ 1 , the layer L i L_i L i consists of all neighbors of vertices in L i − 1 L_{i-1} L i − 1 that do not belong to ⋃ j < i L j \bigcup_{j<i}L_j ⋃ j < i L j . For a vertex v v v in layer L i L_i L i , for some i ∈ [ 0 , q ] i\in[0,q] i ∈ [ 0 , q ] , a root path is an r r r -v v v -path visiting each layer 0 , 1 , … , i 0,1,\ldots,i 0 , 1 , … , i exactly once; clearly such a path exists for any vertex v v v .
The following lemma shows how to turn BFS-layerings into tree decompositions of small induced matching width.
Lemma 2.3. Let G G G be a connected graph, and consider its BFS layering ( L 0 , L 1 , … , L q ) (L_0,L_1,\ldots,L_q) ( L 0 , L 1 , … , L q ) rooted at some vertex. If, for each i ≥ 1 i\ge1 i ≥ 1 , it holds that:
a largest induced matching in G [ L i ] G[L_i] G [ L i ] has at most a a a edges and
a largest induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching has at most b b b edges,
then tree - μ ( G ) ≤ 2 a + 3 b \operatorname{tree}\text{-}\mu(G)\le2a+3b tree - μ ( G ) ≤ 2 a + 3 b .
Proof. Consider a path decomposition with bags of consecutive vertices
L 0 ∪ L 1 , L 1 ∪ L 2 , … , L q − 1 ∪ L q . L_0 \cup L_1, L_1 \cup L_2, \ldots, L_{q-1} \cup L_q. L 0 ∪ L 1 , L 1 ∪ L 2 , … , L q − 1 ∪ L q .
It is straightforward to verify that it is indeed a path decomposition. Fix any bag X = L i − 1 ∪ L i X = L_{i-1} \cup L_i X = L i − 1 ∪ L i and let M M M be an induced matching whose every edge intersects X X X . We can partition the edges of M M M into five groups: edges between L i − 2 L_{i-2} L i − 2 and L i − 1 L_{i-1} L i − 1 (if L i − 2 L_{i-2} L i − 2 exists), edges in L i − 1 L_{i-1} L i − 1 , edges between L i − 1 L_{i-1} L i − 1 and L i L_i L i , edges in L i L_i L i , and edges between L i L_i L i and L i + 1 L_{i+1} L i + 1 (if L i + 1 L_{i+1} L i + 1 exists). The bound follows from upper-bounding the number of edges of each type independently.
Induced minors. Let G G G and H H H be graphs. An induced minor model of H H H in G G G is a function φ : V ( H ) → 2 V ( G ) \varphi: V(H) \to2^{V(G)} φ : V ( H ) → 2 V ( G ) such that for every v ∈ V ( H ) v \in V(H) v ∈ V ( H ) the subgraph G [ φ ( v ) ] G[\varphi(v)] G [ φ ( v )] is connected and also u v ∈ E ( H ) uv \in E(H) uv ∈ E ( H ) if and only if there is at least one edge in G G G between φ ( u ) \varphi(u) φ ( u ) and φ ( v ) \varphi(v) φ ( v ) . The sets φ ( v ) \varphi(v) φ ( v ) for v ∈ V ( H ) v \in V(H) v ∈ V ( H ) are called branch sets .
A walk W = v 1 , … , v ℓ W = v_1, \ldots, v_\ell W = v 1 , … , v ℓ in a graph G G G is a thin walk if all its vertices are pairwise distinct, except possibly from v 1 v_1 v 1 v ℓ v_\ell v ℓ , and all vertices are of degree 2 2 2 in H H H . Vertices v 2 , … , v ℓ − 1 v_2, \ldots, v_{\ell-1} v 2 , … , v ℓ − 1 are called internal vertices of the walk.
The following lemma is a slight generalization of the observation of Milanič, Pivač [43 3.2] that is given by the same proof.
Lemma 2.4. Let H H H be a graph, W W W be a set of edge-disjoint thin walks in H H H , and U U U be the set consisting of all internal vertices of walks in W W W and all vertices of degree at most 1 1 1 in H H H . Let H H H be an induced minor of a graph G G G . Then, there exists an induced minor model φ : V ( H ) → 2 V ( G ) \varphi: V(H) \to2^{V(G)} φ : V ( H ) → 2 V ( G ) of H H H in G G G such that ∣ φ ( u ) ∣ = 1 |\varphi(u)| = 1 ∣ φ ( u ) ∣ = 1 for all u ∈ U u \in U u ∈ U .
Corollary 2.5. If H H H is a linear forest , then the class of H H H -free graphs coincides with the class of H H H -induced-minor-free graphs.
Families of unbounded induced matching treewidth
We start this section by listing a few families of graphs with unbounded induced matching treewidth; the definitions of the considered graphs were introduced in § 2 .
Lemma 3.1. The following graphs have induced matching treewidth at least k k k :
(1.) any subdivided 72 k 72k 72 k -wall,
(2.) the line graph of any properly subdivided 72 k 72k 72 k -wall,
(3.) the graph M k M_k M k constructed from two k k k -edge matchings, by adding all edges between one matching and another,
(4.) the graph K k , k ∘ K^\circ_{k,k} K k , k ∘ obtained from K k , k K_{k,k} K k , k by fixing a perfect matching and, for each matching edge x y xy x y , adding a new 5-vertex path with endpoints x x x and y y y ,
(5.) K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 ,
(6.) K k , k ⊙ K 1 K_{k,k} \odot K_1 K k , k ⊙ K 1 .
Furthermore, for k ≥ 2 k \ge2 k ≥ 2 , the graphs constructed in items (1.)–(4.) of Lemma 3.1 are 2-connected, while graphs constructed in item (5.) have minimum degree 2.
Proof. The first two items follow from recalling that (subdivided) k k k -walls and their line graphs have treewidth k k k . Since they are subcubic graphs, the bound on induced matching treewidth follows immediately from Proposition 2.1 (3.).
For the third item, recall a well-known property of tree decompositions that for every tree decomposition T T T there exists a vertex whose whole closed neighborhood is contained in a single bag. The neighborhood of every vertex in M k M_k M k contains a k k k -edge induced matching, proving that tree - μ ( M k ) ≥ k \operatorname{tree}\text{-}\mu(M_k) \ge k tree - μ ( M k ) ≥ k .
For the last three items, note that all these graphs contain K k , k ⊙ K 1 K_{k,k} \odot K_1 K k , k ⊙ K 1 as an induced subgraph. Thus, the claim follows from Proposition 2.1 (2.) and the facts that tree - α ( K k , k ) ≥ k \operatorname{tree}\text{-}\alpha(K_{k,k}) \ge k tree - α ( K k , k ) ≥ k [27 ] and that induced matching treewidth does not increase when deleting vertices.
Let us show one more property of induced minors of K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 .
Lemma 3.2. Let H H H be a 2-connected graph with at least 4 vertices. Then H H H is an induced minor of K k , k K_{k,k} K k , k if an only if it is an induced minor of K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 .
Proof. The forward implication is obvious, as K k , k K_{k,k} K k , k is an induced subgraph of K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 . Now, suppose that K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 contains H H H as an induced minor and consider an induced minor model
φ : V ( H ) → 2 V ( K k , k ⊙ K 2 ) \varphi: V(H) \to2^{V(K_{k,k} \odot K_2)} φ : V ( H ) → 2 V ( K k , k ⊙ K 2 )
Denote the vertex set of the biclique K k , k K_{k,k} K k , k in K k , k ⊙ K 2 K_{k,k} \odot K_2 K k , k ⊙ K 2 by B B B and let Z = V ( K k , k ⊙ K 2 ) ∖ B Z = V(K_{k,k} \odot K_2) \setminus B Z = V ( K k , k ⊙ K 2 ) ∖ B .
Claim 3.2.1. Let z ∈ Z z \in Z z ∈ Z be such that z ∈ φ ( v ) z \in\varphi(v) z ∈ φ ( v ) for some v ∈ V ( H ) v \in V(H) v ∈ V ( H ) . Let x x x be the neighbor of z z z in B B B , and let z ′ ∈ Z z' \in Z z ′ ∈ Z be the common neighbor of z z z and x x x . Then x ∈ φ ( v ) x \in\varphi(v) x ∈ φ ( v ) .
Proof of Claim. Suppose not. Since H H H is 2-connected, v v v has at least two neighbors, say u , w u,w u , w . Consequently, we must have z ′ ∈ φ ( u ) z' \in\varphi(u) z ′ ∈ φ ( u ) and x ∈ φ ( w ) x \in\varphi(w) x ∈ φ ( w ) (or vice versa, the other case is symmetric). As H H H has at least four vertices, there is q ∈ V ( H ) ∖ { u , v , w } q \in V(H) \setminus\{u,v,w\} q ∈ V ( H ) ∖ { u , v , w } . However, removing φ ( w ) \varphi(w) φ ( w ) separates φ ( v ) \varphi(v) φ ( v ) from φ ( q ) \varphi(q) φ ( q ) , so w w w is a cutvertex in H H H , a contradiction.
By the claim above we conclude that whenever some z ∈ Z z \in Z z ∈ Z appears in a branch set of the induced minor model, the same branch set contains the neighbor of z z z in B B B . Consequently, we can modify the model into an equivalent one, by removing all vertices from Z Z Z from all branch sets. Note that this preserves all (non-)adjacencies. Thus, H H H is an induced minor of K k , k ⊙ K 2 − Z K_{k,k} \odot K_2 - Z K k , k ⊙ K 2 − Z , i.e., of K k , k K_{k,k} K k , k .
Induced matching treewidth and forbidden substructures. Now let us analyze what substructures do not appear in graphs listed in Lemma 3.1 . We aim to detect maximal unbounded families, also keeping in mind the comparison of containment (and exclusion) relations; recall Figure 2 . Finally, whenever possible, we try to use constructions that are 2-connected, or at least of minimum degree 2.
Lemma 3.3. The following classes of graphs have unbounded induced matching treewidth:
subcubic graphs of girth at least t t t , for any fixed t t t ,
claw-free graphs,
H H H -minor-free, where H H H is not planar,
P 4 P_4 P 4 -induced-minor-free graphs, ( P 3 + P 1 ) (P_3 + P_1) ( P 3 + P 1 ) -induced-minor-free graphs, ( K 3 + P 1 ) (K_3 + P_1) ( K 3 + P 1 ) -induced-minor-free graphs,
bull-induced-subdivision-free graphs,
house-induced-subdivision-free graphs,
K 4 K_4 K 4 -induced-subdivision-free and K 4 ′ K'_4 K 4 ′ -induced-minor-free graphs, where K 4 ′ K'_4 K 4 ′ is obtained from K 4 K_4 K 4 by subdividing one edge once,
K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 -induced-minor-free graphs,
H H H -induced-minor-free graphs, where H H H is any graph containing three vertices, each of degree at least 3, inducing P 2 + P 1 P_2 + P_1 P 2 + P 1 ,
H H H -induced-minor-free graphs, where H H H is any 2-connected graph containing P 2 + P 1 P_2 + P_1 P 2 + P 1 ,
2-windmill-induced-minor-free graphs.
Furthermore, items (1.)–(10.) hold even restricted to graphs of minimum at least degree 2, and items (1.)–(9.) hold even restricted to 2-connected graphs.
Proof. We will use constructions provided in Lemma 3.1 .
Walls and their line graphs
Let us start with subdivided walls and their line graphs, as in Lemma 3.1 (1.) and (2.).
(1.) Subdividing each edge of a large wall t t t times we obtain a subcubic graph with girth at least t t t and large induced matching treewidth.
(2.) Line graphs of subdivided walls are claw-free.
(3.) Note that every planar graph excludes any non-planar graph as a minor. Thus, (subdivided) walls are H H H -minor-free for any non-planar graph H H H .
Graphs M k M_k M k
Fix k ≥ 2 k \ge2 k ≥ 2 and consider the graph M k M_k M k defined in Lemma 3.1 (3.). Let X , Y X,Y X , Y be two sets that are complete to each other and induce k k k -edge matchings in M k M_k M k .
(4.) It is straightforward to verify that for every k ∈ N k \in\mathbb{N} k ∈ N , the graph M k M_k M k is P 4 P_4 P 4 -free (i.e., a cograph) so, equivalently (see Corollary 2.5 ), P 4 P_4 P 4 -induced-minor-free. Furthermore, as removing the neighborhood of any vertex leaves a matching, we observe that M k M_k M k is ( P 3 + P 1 ) (P_3 + P_1) ( P 3 + P 1 ) -induced-minor-free and ( K 3 + P 1 ) (K_3 + P_1) ( K 3 + P 1 ) -induced-minor-free.
(5.) Suppose that for some k k k , the graph M k M_k M k contains a copy of the bull as an induced subdivision. Denote the vertices of the bull by a , b , c , u , v a,b,c,u,v a , b , c , u , v , where a , b , c a,b,c a , b , c form a triangle, b b b is adjacent to u u u , and c c c is adjacent to v v v . Since u u u and v v v are non-adjacent, we may assume by symmetry that their images u ′ , v ′ u',v' u ′ , v ′ are both in X X X , and they belong to distinct matching edges in M k [ X ] M_k[X] M k [ X ] . Thus, the image a ′ a' a ′ of a a a must also be in X X X , belonging to yet another edge in M k [ X ] M_k[X] M k [ X ] . Since each of u ′ , v ′ u',v' u ′ , v ′ is complete to Y Y Y , we observe that the images b ′ , c ′ b',c' b ′ , c ′ of b b b and c c c are also in X X X . Among edges a b , a c ab,ac ab , a c there is at least one, say a b ab ab , whose image is not contained in X X X and thus, must be a three-vertex path a ′ y b ′ a' y b' a ′ y b ′ for some y ∈ Y y \in Y y ∈ Y . However, y y y is adjacent to a ′ a' a ′ and b ′ b' b ′ , a contradiction.
(6.) Suppose that for some k k k , the graph M k M_k M k contains a copy of the house as an induced subdivision. Let a , b , c , d a,b,c,d a , b , c , d be consecutive vertices of the 4-cycle in the bull, and let z z z be the last vertex, adjacent to a a a and b b b . As M k M_k M k is P 4 P_4 P 4 -free, it has no cycles with more than 4 vertices. Thus, the image of the cycle with vertices a , b , c , d a,b,c,d a , b , c , d must be a 4-cycle in M k M_k M k . The only such cycles are obtained by taking two pairs of non-adjacent vertices, one from X X X and the other from Y Y Y . However, there is no way to place the image of z z z to make it non-adjacent both to the image of c c c and d d d , a contradiction.
Graphs K k , k ∘ K^\circ_{k,k} K k , k ∘ . Next, we will consider the graph K k , k ∘ K^\circ_{k,k} K k , k ∘ defined in Lemma 3.1 (4.). Let X X X and Y Y Y denote, respectively, the sides of the copy of K k , k K_{k,k} K k , k in K k , k ∘ K^\circ_{k,k} K k , k ∘ .
(7.) Note that for any k ∈ N k \in\mathbb{N} k ∈ N , the graph K k , k ∘ K^\circ_{k,k} K k , k ∘ does not contain K 4 K_4 K 4 . Thus, in order to show that it is K 4 K_4 K 4 -induced-subdivision-free, it is sufficient to show that it is K 4 ′ K'_4 K 4 ′ -induced-minor-free. For contradiction, suppose that there is k ≥ 2 k \ge2 k ≥ 2 such that K k , k ∘ K^\circ_{k,k} K k , k ∘ contains K 4 ′ K'_4 K 4 ′ as an induced minor. Denote the degree-3 vertices of K 4 ′ K'_4 K 4 ′ by a , b , c , d a,b,c,d a , b , c , d , and let the degree-2 vertex z z z be adjacent to a a a and b b b . Consider an induced minor model φ : { a , b , c , d , z } → 2 V ( K k , k ∘ ) \varphi:\{a,b,c,d,z\}\to2^{V(K^\circ_{k,k})} φ : { a , b , c , d , z } → 2 V ( K k , k ∘ ) .
As a a a has degree 3 in K 4 ′ K'_4 K 4 ′ , we observe that φ ( a ) \varphi(a) φ ( a ) must intersect X ∪ Y X\cup Y X ∪ Y . By symmetry, suppose that X ∩ φ ( a ) ≠ ∅ X\cap\varphi(a)\ne\varnothing X ∩ φ ( a ) = ∅ . Similarly, we have that φ ( b ) \varphi(b) φ ( b ) must intersect X ∪ Y X\cup Y X ∪ Y . As a a a and b b b are non-adjacent, we observe that φ ( a ) ∩ ( X ∪ Y ) ⊆ X \varphi(a)\cap(X\cup Y)\subseteq X φ ( a ) ∩ ( X ∪ Y ) ⊆ X and φ ( b ) ∩ ( X ∪ Y ) ⊆ X \varphi(b)\cap(X\cup Y)\subseteq X φ ( b ) ∩ ( X ∪ Y ) ⊆ X . Now, since z z z is adjacent to both a a a and b b b , we must have φ ( z ) ∩ Y ≠ ∅ \varphi(z)\cap Y\ne\varnothing φ ( z ) ∩ Y = ∅ . Consequently, φ ( c ) \varphi(c) φ ( c ) and φ ( d ) \varphi(d) φ ( d ) cannot intersect X X X . However, there is no way to place φ ( c ) \varphi(c) φ ( c ) and φ ( d ) \varphi(d) φ ( d ) so that they are adjacent to each other, and also to φ ( a ) \varphi(a) φ ( a ) and φ ( b ) \varphi(b) φ ( b ) , a contradiction.
(8.) For contradiction, suppose that there is k ∈ N k\in\mathbb{N} k ∈ N such that K k , k ∘ K^\circ_{k,k} K k , k ∘ contains K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 as an induced minor. Denote the vertices of K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 by { a , a ′ , b , b ′ , c , c ′ } \{a,a',b,b',c,c'\} { a , a ′ , b , b ′ , c , c ′ } , where a a ′ aa' a a ′ , b b ′ bb' b b ′ , c c ′ cc' c c ′ are non-edges. Consider an induced minor model φ : { a , a ′ , b , b ′ , c , c ′ } → 2 V ( K k , k ∘ ) \varphi:\{a,a',b,b',c,c'\}\to2^{V(K^\circ_{k,k})} φ : { a , a ′ , b , b ′ , c , c ′ } → 2 V ( K k , k ∘ ) .
Let u , u ′ u,u' u , u ′ be a pair of non-adjacent vertices of K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 . Note that it cannot hold that φ ( u ) ∩ ( X ∪ Y ) = ∅ \varphi(u)\cap(X\cup Y)=\varnothing φ ( u ) ∩ ( X ∪ Y ) = ∅ , as u u u is of degree 4 in K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 . By symmetry, suppose that φ ( u ) ∩ X ≠ ∅ \varphi(u)\cap X\ne\varnothing φ ( u ) ∩ X = ∅ . Note that since u u u and u ′ u' u ′ are non-adjacent in K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 , we must have φ ( u ′ ) ∩ ( X ∪ Y ) ⊆ X \varphi(u')\cap(X\cup Y)\subseteq X φ ( u ′ ) ∩ ( X ∪ Y ) ⊆ X and thus, symmetrically, φ ( u ) ∩ ( X ∪ Y ) ⊆ X \varphi(u)\cap(X\cup Y)\subseteq X φ ( u ) ∩ ( X ∪ Y ) ⊆ X .
Suppose by symmetry that φ ( a ) ∩ ( X ∪ Y ) ⊆ X \varphi(a)\cap(X\cup Y)\subseteq X φ ( a ) ∩ ( X ∪ Y ) ⊆ X and φ ( a ′ ) ∩ ( X ∪ Y ) ⊆ X \varphi(a')\cap(X\cup Y)\subseteq X φ ( a ′ ) ∩ ( X ∪ Y ) ⊆ X . Note that since b b b is adjacent to both a a a and a ′ a' a ′ , we must have φ ( b ) ∩ Y ≠ ∅ \varphi(b)\cap Y\ne\varnothing φ ( b ) ∩ Y = ∅ , which means that φ ( b ) ∩ ( X ∪ Y ) ⊆ Y \varphi(b)\cap(X\cup Y)\subseteq Y φ ( b ) ∩ ( X ∪ Y ) ⊆ Y and φ ( b ′ ) ∩ ( X ∪ Y ) ⊆ Y \varphi(b')\cap(X\cup Y)\subseteq Y φ ( b ′ ) ∩ ( X ∪ Y ) ⊆ Y . However, now there is no way to place φ ( c ) \varphi(c) φ ( c ) and φ ( c ′ ) \varphi(c') φ ( c ′ ) , a contradiction.
(9.) Now let H H H be a graph as in item (9.), and denote the vertices of the induced P 1 + P 2 P_1+P_2 P 1 + P 2 by a , b , c a,b,c a , b , c , where b c bc b c is an edge. For contradiction, suppose that there is k ∈ N k\in\mathbb{N} k ∈ N such that K k , k ∘ K^\circ_{k,k} K k , k ∘ contains H H H as an induced minor and consider an induced minor model φ : V ( H ) → 2 V ( K k , k ∘ ) \varphi:V(H)\to2^{V(K^\circ_{k,k})} φ : V ( H ) → 2 V ( K k , k ∘ ) .
As each of a , b , c a,b,c a , b , c is of degree at least 3, the image of each of them must intersect X ∪ Y X\cup Y X ∪ Y . By symmetry, assume that φ ( a ) ∩ X ≠ ∅ \varphi(a)\cap X\ne\varnothing φ ( a ) ∩ X = ∅ . As a a a is not adjacent to both b b b and c c c , it must hold that each of φ ( b ) ∩ ( X ∪ Y ) \varphi(b)\cap(X\cup Y) φ ( b ) ∩ ( X ∪ Y ) and φ ( c ) ∩ ( X ∪ Y ) \varphi(c)\cap(X\cup Y) φ ( c ) ∩ ( X ∪ Y ) is a nonempty subset of X X X . Since b b b and c c c are adjacent, there must be an edge between φ ( a ) \varphi(a) φ ( a ) and φ ( a ′ ) \varphi(a') φ ( a ′ ) , but this is impossible, a contradiction.
Graphs K k , k ⊙ K p K_{k,k}\odot K_p K k , k ⊙ K p . In the next two items we will consider graphs K k , k ⊙ K p K_{k,k}\odot K_p K k , k ⊙ K p for p ∈ { 1 , 2 } p\in\{1,2\} p ∈ { 1 , 2 } , defined in Lemma 3.1 (6.) and (5.). By X , Y X,Y X , Y we denote the sides of the copy of K k , k K_{k,k} K k , k in K k , k ⊙ K p K_{k,k}\odot K_p K k , k ⊙ K p , for k ≥ 2 k\ge2 k ≥ 2 and p ∈ { 1 , 2 } p\in\{1,2\} p ∈ { 1 , 2 } .
(10.) Let H H H be a graph as in item (10.), and denote the vertices of the induced P 1 + P 2 P_1+P_2 P 1 + P 2 by a , b , c a,b,c a , b , c , where b c bc b c is an edge. Consider p = 2 p=2 p = 2 , i.e., the family of graphs K k , k ⊙ K 2 K_{k,k}\odot K_2 K k , k ⊙ K 2 . Note that since H H H is 2-connected and has at least 4 vertices, by Lemma 3.2 , it is sufficient to show that H H H is not an induced minor of K k , k K_{k,k} K k , k . So, for contradiction, suppose that there is an induced minor model φ : V ( H ) → 2 X ∪ Y \varphi:V(H)\to2^{X\cup Y} φ : V ( H ) → 2 X ∪ Y of H H H in K k , k K_{k,k} K k , k . By symmetry, suppose that there is x ∈ X x \in X x ∈ X such that x ∈ φ ( a ) x \in\varphi(a) x ∈ φ ( a ) . Since both b b b and c c c are non-adjacent to a a a , both sets φ ( b ) \varphi(b) φ ( b ) and φ ( c ) \varphi(c) φ ( c ) are contained in X X X . However, this means there are no edges between them, as X X X is independent – a contradiction with b c bc b c being an edge.
(11.) We claim that K k , k ⊙ K 1 K_{k,k} \odot K_1 K k , k ⊙ K 1 is 2-windmill-induced-minor-free. Define Z = V ( K k , k ⊙ K 1 ) ∖ ( X ∪ Y ) Z = V(K_{k,k} \odot K_1) \setminus(X \cup Y) Z = V ( K k , k ⊙ K 1 ) ∖ ( X ∪ Y ) . Thus, Z Z Z is a 2 k 2k 2 k -element independent set and every vertex from Z Z Z has a unique neighbor in X ∪ Y X \cup Y X ∪ Y .
Consider a 2-windmill, and denote its central vertex by c c c , and the two edges obtained by removing c c c by a a ′ aa' a a ′ and b b ′ bb' b b ′ . For contradiction, suppose there is an induced minor model φ : { c , a , a ′ , b , b ′ } → 2 X ∪ Y ∪ Z \varphi: \{c, a, a', b, b'\} \to2^{X \cup Y \cup Z} φ : { c , a , a ′ , b , b ′ } → 2 X ∪ Y ∪ Z .
Similarly as in Claim 3.2.1 , we observe that whenever some z ∈ Z z \in Z z ∈ Z belongs to some φ ( u ) \varphi(u) φ ( u ) for u ∈ { c , a , a ′ , b , b ′ } u \in\{c, a, a', b, b'\} u ∈ { c , a , a ′ , b , b ′ } , then also z ′ z' z ′ , the unique neighbor of z z z , belongs to φ ( u ) \varphi(u) φ ( u ) . Consequently, we can modify the minor model into an equivalent one by removing all vertices from Z Z Z from all branch sets. Thus, the 2-windmill is an induced minor of K k , k K_{k,k} K k , k . In particular, K k , k K_{k,k} K k , k contains 2 K 2 2K_2 2 K 2 (the subgraph of the 2-windmill induced by { a , a ′ , b , b ′ } \{a, a', b, b'\} { a , a ′ , b , b ′ } ) as an induced minor, so, by Corollary 2.5 , also as an induced subgraph. This is a contradiction.
Finally, we state the following straightforward consequence of the transitivity of all considered containment relations. We will often use it implicitly.
Observation 3.4. Let ⋆ \star ⋆ be one of the considered relations, i.e., (induced) subgraph, (induced) topological minor, or (induced) minor. Let F F F be contained in H H H as ⋆ \star ⋆ , and let G \mathcal{G} G be a class of graphs. If induced matching treewidth is unbounded in the class of F F F -⋆ \star ⋆ -free graphs from G \mathcal{G} G , then it is unbounded in the class of H H H -⋆ \star ⋆ -free graphs from G \mathcal{G} G .
Tipi-induced-minor-free graphs
Let us start with the following structural observation concerning graphs that exclude 1-tipi as an induced minor.
Lemma 4.1. A graph G G G is 1-tipi-induced-minor-free if and only if it is 1-tipi-induced-subdivision-free.
Proof. As every induced subdivision of any graph H H H is in particular an induced minor model of H H H (see Figure 2 ), the forward implication is obvious. Thus suppose that G G G has 1-tipi as an induced minor. We will exhibit an induced subdivision of 1-tipi in G G G . Denote the vertices of 1-tipi by x x x , y y y , z z z , and p p p , where x x x , y y y , z z z form a triangle and p p p is adjacent to x x x . Consider an induced minor model φ : { x , y , z , p } → 2 V ( G ) \varphi: \{x,y,z,p\} \to2^{V(G)} φ : { x , y , z , p } → 2 V ( G ) of 1-tipi. By Lemma 2.4 , we can assume that φ ( p ) \varphi(p) φ ( p ) is a singleton, say, φ ( p ) = { v } \varphi(p)=\{v\} φ ( p ) = { v } .
Let C C C be a shortest cycle that satisfies the following conditions:
V ( C ) V(C) V ( C ) consists of three consecutive non-empty subpaths, each contained in, respectively, φ ( x ) \varphi(x) φ ( x ) , φ ( y ) \varphi(y) φ ( y ) , and φ ( z ) \varphi(z) φ ( z ) ,
V ( C ) V(C) V ( C ) contains a neighbor of v v v .
Such a cycle exists since φ \varphi φ is an induced minor model of 1-tipi. For convenience, fix the ordering of the cycle from φ ( y ) \varphi(y) φ ( y ) to φ ( x ) \varphi(x) φ ( x ) , and then to φ ( z ) \varphi(z) φ ( z ) .
First, suppose that v v v is adjacent to at least two vertices of C C C . Let a a a , b b b be two consecutive vertices of C C C such that v v v is non-adjacent to a a a and adjacent to b b b , and b b b is later than a a a along the cycle. Such vertices exist as v v v has a neighbor in φ ( x ) \varphi(x) φ ( x ) and has no neighbor in φ ( y ) \varphi(y) φ ( y ) . Let c c c be the first neighbor of v v v that appears on C C C after b b b . Note that a c ∉ E ( G ) ac \notin E(G) a c ∈ / E ( G ) , as the neighborhood of v v v in C C C is contained in φ ( x ) \varphi(x) φ ( x ) and C C C intersects both φ ( y ) \varphi(y) φ ( y ) and φ ( z ) \varphi(z) φ ( z ) . Now, vertices a a a , b b b , c c c , v v v and the subpath of C C C joining b b b and c c c (and avoiding a a a ) form an induced subdivision of 1-tipi.
So suppose that v v v has exactly one neighbor on C C C , say u u u . Since C C C is shortest possible, we observe that either C C C is an induced cycle or there is an edge between the neighbors of u u u on C C C . In both outcomes we obtain an induced subdivision of 1-tipi.
We also give the following easy observation that will be used in this section but also in the proof of Theorem 6.1 .
Observation 4.2. Let G G G be a graph that contains a matching M M M of size k ≥ 1 k \ge1 k ≥ 1 as an induced subgraph. Also, let Z Z Z be a connected subset of V ( G ) ∖ V ( M ) V(G) \setminus V(M) V ( G ) ∖ V ( M ) . If every vertex of V ( M ) V(M) V ( M ) is adjacent to some vertex of Z Z Z , then G G G contains the k k k -windmill as an induced minor. In particular, G G G contains the ( k − 1 ) (k-1) ( k − 1 ) -tipi as an induced minor.
Lemma 4.3. Let k ≥ 1 k \ge1 k ≥ 1 , let G G G be a graph, and let Z ⊆ V ( G ) Z \subseteq V(G) Z ⊆ V ( G ) such that G [ Z ] G[Z] G [ Z ] is connected and contains a cycle C C C as a subgraph. Also, suppose that G G G contains a matching M M M of at least 3 k 3k 3 k edges as an induced subgraph so that for every edge e e e of M M M one of the following holds:
both endpoints of e e e are disjoint from Z Z Z and at least one of them is adjacent to a vertex in Z Z Z , or
e e e has exactly one endpoint in Z Z Z , which is also in V ( C ) V(C) V ( C ) .
Then, G G G contains the k k k -tipi as an induced minor.
Proof. An edge of M M M can satisfy exactly one of the conditions in the statement. Let E 1 E_1 E 1 be the edges in M M M that satisfy the first condition and let E 2 E_2 E 2 be the edges that satisfy the second one.
First, suppose there is an edge e ∈ E 1 e \in E_1 e ∈ E 1 whose both endpoints are adjacent to vertices in Z Z Z . In that case, from each edge in E 1 ∖ { e } E_1 \setminus\{e\} E 1 ∖ { e } we delete one endpoint, leaving one that has a neighbor in Z Z Z , and then we contract Z Z Z to a single vertex. This way we obtain a ( ∣ M ∣ − 1 ) (|M|-1) ( ∣ M ∣ − 1 ) -tipi (and thus, a k k k -tipi) as an induced minor of $G. So from now on, assume that every edge e ∈ E 1 e \in E_1 e ∈ E 1 has exactly one endpoint that is adjacent to a vertex in Z Z Z . We denote such endpoint by u e u_e u e .
For each edge e ∈ E 1 e \in E_1 e ∈ E 1 , we fix a shortest path P e P_e P e in G G G joining u e u_e u e to some vertex in V ( C ) V(C) V ( C ) . Note that V ( P e ) ∖ { u e } ⊆ Z V(P_e) \setminus\{u_e\} \subseteq Z V ( P e ) ∖ { u e } ⊆ Z . By w e w_e w e we denote the endpoint of P e P_e P e in V ( C ) V(C) V ( C ) . For edges e ∈ E 2 e \in E_2 e ∈ E 2 , we set w e w_e w e be their endpoint in C C C . Note that the paths P e P_e P e do not contain any edge from E 2 E_2 E 2 .
Next, we fix two consecutive vertices z 1 z_1 z 1 and z 2 z_2 z 2 in C C C and we partition V ( C ) V(C) V ( C ) to the sets B 1 = { z 1 } B_1 = \{z_1\} B 1 = { z 1 } , B 2 = { z 2 } B_2 = \{z_2\} B 2 = { z 2 } , and B 3 = V ( C ) ∖ { z 1 , z 2 } B_3 = V(C) \setminus\{z_1,z_2\} B 3 = V ( C ) ∖ { z 1 , z 2 } . Fix j ∈ { 1 , 2 , 3 } j \in\{1,2,3\} j ∈ { 1 , 2 , 3 } so that the number of edges e ∈ M e \in M e ∈ M with w e ∈ B j w_e \in B_j w e ∈ B j is maximized. Since ∣ M ∣ ≥ 3 k |M| \geq3k ∣ M ∣ ≥ 3 k , B j B_j B j contains the vertices w e w_e w e of at least k k k edges in M M M . Thus, by contracting the paths P e P_e P e for each e ∈ E 1 e \in E_1 e ∈ E 1 with w e ∈ B j w_e \in B_j w e ∈ B j to single edges, contracting V ( C ) ∖ { z 1 , z 2 } V(C) \setminus\{z_1,z_2\} V ( C ) ∖ { z 1 , z 2 } to a single vertex, and removing all remaining vertices, we obtain the k ′ k' k ′ -tipi for k ′ ≥ k k' \geq k k ′ ≥ k (and thus, also the k k k -tipi) as an induced minor.
As the main result of this section, we show excluding a tipi as an induced minor yields a class of bounded induced matching treewidth.
Theorem 4.4. For every integer k ≥ 1 k \geq1 k ≥ 1 , every graph G G G that does not contain the k k k -tipi as an induced minor satisfies tree - μ ( G ) ≤ 11 k + 5 \operatorname{tree}\text{-}\mu(G) \leq11k + 5 tree - μ ( G ) ≤ 11 k + 5 .
Proof. Without loss of generality, assume that G G G is connected, as otherwise we can process each component separately and obtain a tree decomposition of G G G by combining the tree decompositions of components. If G G G is a tree, then tw ( G ) ≤ 1 \operatorname{tw}(G) \leq1 tw ( G ) ≤ 1 and thus, due Proposition 2.1 (1.), we have tree - μ ( G ) ≤ 2 \operatorname{tree}\text{-}\mu(G) \leq2 tree - μ ( G ) ≤ 2 . So, assume hat G G G has a cycle.
Pick any vertex r r r of G G G and consider the BFS-layering ( L 0 , … , L q ) (L_0,\ldots,L_q) ( L 0 , … , L q ) of G G G rooted at this vertex.
Claim 4.4.1. For every i ≥ 0 i \geq0 i ≥ 0 , every induced matching in G [ L i ] G[L_i] G [ L i ] has at most k k k edges.
Proof of Claim. The statement is trivial for i = 0 i = 0 i = 0 , so assume that i ≥ 1 i \geq1 i ≥ 1 . For contradiction, suppose there is an induced matching M M M on k + 1 k+1 k + 1 edges contained in L i L_i L i . Note that the set Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j is connected and disjoint from L i L_i L i . Furthermore, every vertex in L i L_i L i has a neighbor in Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j . Thus, by Observation 4.2 , G G G contains the k k k -tipi as an induced minor, a contradiction. ◁
We next bound the size of an induced matching between layers.
Claim 4.4.2. For every i ∈ [ q ] i \in[q] i ∈ [ q ] , every induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching of G G G has at most 3 k + 1 3k+1 3 k + 1 edges.
Proof of Claim. We assume that i ≥ 2 i \geq2 i ≥ 2 since in the case i = 1 i = 1 i = 1 we have ∣ L 0 ∣ = 1 |L_0| = 1 ∣ L 0 ∣ = 1 . Suppose that G G G contains an induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching M M M of at least 3 k + 2 3k+2 3 k + 2 edges. Recall that we assumed that G G G contains a cycle as a subgraph. Let C C C be a shortest such cycle; in particular, it is induced. We distinguish two cases depending whether C C C uses some edge from M M M . In both cases, we use Lemma 4.3 to arrive at a contradiction.
Case A: E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ . Let j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j ≠ ∅ } j_0 = \min\{j \in[q] \mid V(C) \cap L_j \neq\varnothing\} j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j = ∅ } and let z ∈ V ( C ) ∩ L j 0 z \in V(C) \cap L_{j_0} z ∈ V ( C ) ∩ L j 0 . Let P z P_z P z be a root path for z z z . Note that there is at most one edge e ′ ∈ M e' \in M e ′ ∈ M that has an endpoint in V ( P z ) V(P_z) V ( P z ) , as P z P_z P z contains at most one vertex from L i − 1 L_{i-1} L i − 1 and at most one vertex from L i L_i L i , and these two vertices are adjacent. Let M ′ = M ∖ { e ′ } M' = M \setminus\{e'\} M ′ = M ∖ { e ′ } (or M ′ = M M' = M M ′ = M if e ′ e' e ′ does not exist), note that ∣ M ′ ∣ ≥ 3 k |M'| \geq3k ∣ M ′ ∣ ≥ 3 k . For every edge in M ′ M' M ′ we have that both endpoints are disjoint from V ( P z ) V(P_z) V ( P z ) .
Let Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) Z = \bigcup_{j<i-1} L_j \cup V(C) \cup V(P_z) Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) and note that G [ Z ] G[Z] G [ Z ] is connected and contains the cycle C C C . Our goal is to apply Lemma 4.3 for Z Z Z and M ′ M' M ′ . Since E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ and C C C is induced, every edge in M ′ M' M ′ has at most one endpoint in V ( C ) V(C) V ( C ) . Let E 1 = { u v ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } E_1 = \{uv \in M' \mid\{u,v\} \cap V(C) = \varnothing\} E 1 = { uv ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } and E 2 = M ′ ∖ E 1 E_2 = M' \setminus E_1 E 2 = M ′ ∖ E 1 . Note that for every edge e ∈ E 1 e \in E_1 e ∈ E 1 , both endpoints are disjoint from Z Z Z and the endpoint in L i − 1 L_{i-1} L i − 1 is adjacent
@page 18/43 starts_mid=1 ends_mid=1 So from now on, assume that every edge e ∈ E 1 e \in E_1 e ∈ E 1 has exactly one endpoint that is adjacent to a vertex in Z Z Z . We denote such endpoint by u e u_e u e .
For each edge e ∈ E 1 e \in E_1 e ∈ E 1 , we fix a shortest path P e P_e P e in G G G joining u e u_e u e to some vertex in V ( C ) V(C) V ( C ) . Note that V ( P e ) ∖ { u e } ⊆ Z V(P_e) \setminus\{u_e\} \subseteq Z V ( P e ) ∖ { u e } ⊆ Z . By w e w_e w e we denote the endpoint of P e P_e P e in V ( C ) V(C) V ( C ) . For edges e ∈ E 2 e \in E_2 e ∈ E 2 , we set w e w_e w e be their endpoint in C C C . Note that the paths P e P_e P e do not contain any edge from E 2 E_2 E 2 .
Next, we fix two consecutive vertices z 1 z_1 z 1 and z 2 z_2 z 2 in C C C and we partition V ( C ) V(C) V ( C ) to the sets B 1 = { z 1 } B_1 = \{z_1\} B 1 = { z 1 } , B 2 = { z 2 } B_2 = \{z_2\} B 2 = { z 2 } , and B 3 = V ( C ) ∖ { z 1 , z 2 } B_3 = V(C) \setminus\{z_1,z_2\} B 3 = V ( C ) ∖ { z 1 , z 2 } . Fix j ∈ { 1 , 2 , 3 } j \in\{1,2,3\} j ∈ { 1 , 2 , 3 } so that the number of edges e ∈ M e \in M e ∈ M with w e ∈ B j w_e \in B_j w e ∈ B j is maximized. Since ∣ M ∣ ≥ 3 k |M| \geq3k ∣ M ∣ ≥ 3 k , B j B_j B j contains the vertices w e w_e w e of at least k k k edges in M M M . Thus, by contracting the paths P e P_e P e for each e ∈ E 1 e \in E_1 e ∈ E 1 with w e ∈ B j w_e \in B_j w e ∈ B j to single edges, contracting V ( C ) ∖ { z 1 , z 2 } V(C) \setminus\{z_1,z_2\} V ( C ) ∖ { z 1 , z 2 } to a single vertex, and removing all remaining vertices, we obtain the k ′ k' k ′ -tipi for k ′ ≥ k k' \geq k k ′ ≥ k (and thus, also the k k k -tipi) as an induced minor.
As the main result of this section, we show excluding a tipi as an induced minor yields a class of bounded induced matching treewidth.
Theorem 4.4. For every integer k ≥ 1 k \geq1 k ≥ 1 , every graph G G G that does not contain the k k k -tipi as an induced minor satisfies tree - μ ( G ) ≤ 11 k + 5 \operatorname{tree}\text{-}\mu(G) \leq11k + 5 tree - μ ( G ) ≤ 11 k + 5 .
Proof. Without loss of generality, assume that G G G is connected, as otherwise we can process each component separately and obtain a tree decomposition of G G G by combining the tree decompositions of components. If G G G is a tree, then tw ( G ) ≤ 1 \operatorname{tw}(G) \leq1 tw ( G ) ≤ 1 and thus, due Proposition 2.1 (1.), we have tree - μ ( G ) ≤ 2 \operatorname{tree}\text{-}\mu(G) \leq2 tree - μ ( G ) ≤ 2 . So, assume hat G G G has a cycle.
Pick any vertex r r r of G G G and consider the BFS-layering ( L 0 , … , L q ) (L_0,\ldots,L_q) ( L 0 , … , L q ) of G G G rooted at this vertex.
Claim 4.4.1. For every i ≥ 0 i \geq0 i ≥ 0 , every induced matching in G [ L i ] G[L_i] G [ L i ] has at most k k k edges.
Proof of Claim. The statement is trivial for i = 0 i = 0 i = 0 , so assume that i ≥ 1 i \geq1 i ≥ 1 . For contradiction, suppose there is an induced matching M M M on k + 1 k+1 k + 1 edges contained in L i L_i L i . Note that the set Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j is connected and disjoint from L i L_i L i . Furthermore, every vertex in L i L_i L i has a neighbor in Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j . Thus, by Observation 4.2 , G G G contains the k k k -tipi as an induced minor, a contradiction. ◁
We next bound the size of an induced matching between layers.
Claim 4.4.2. For every i ∈ [ q ] i \in[q] i ∈ [ q ] , every induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching of G G G has at most 3 k + 1 3k+1 3 k + 1 edges.
Proof of Claim. We assume that i ≥ 2 i \geq2 i ≥ 2 since in the case i = 1 i = 1 i = 1 we have ∣ L 0 ∣ = 1 |L_0| = 1 ∣ L 0 ∣ = 1 . Suppose that G G G contains an induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching M M M of at least 3 k + 2 3k+2 3 k + 2 edges. Recall that we assumed that G G G contains a cycle as a subgraph. Let C C C be a shortest such cycle; in particular, it is induced. We distinguish two cases depending whether C C C uses some edge from M M M . In both cases, we use Lemma 4.3 to arrive at a contradiction.
Case A: E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ . Let j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j ≠ ∅ } j_0 = \min\{j \in[q] \mid V(C) \cap L_j \neq\varnothing\} j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j = ∅ } and let z ∈ V ( C ) ∩ L j 0 z \in V(C) \cap L_{j_0} z ∈ V ( C ) ∩ L j 0 . Let P z P_z P z be a root path for z z z . Note that there is at most one edge e ′ ∈ M e' \in M e ′ ∈ M that has an endpoint in V ( P z ) V(P_z) V ( P z ) , as P z P_z P z contains at most one vertex from L i − 1 L_{i-1} L i − 1 and at most one vertex from L i L_i L i , and these two vertices are adjacent. Let M ′ = M ∖ { e ′ } M' = M \setminus\{e'\} M ′ = M ∖ { e ′ } (or M ′ = M M' = M M ′ = M if e ′ e' e ′ does not exist), note that ∣ M ′ ∣ ≥ 3 k |M'| \geq3k ∣ M ′ ∣ ≥ 3 k . For every edge in M ′ M' M ′ we have that both endpoints are disjoint from V ( P z ) V(P_z) V ( P z ) .
Let Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) Z = \bigcup_{j<i-1} L_j \cup V(C) \cup V(P_z) Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) and note that G [ Z ] G[Z] G [ Z ] is connected and contains the cycle C C C . Our goal is to apply Lemma 4.3 for Z Z Z and M ′ M' M ′ . Since E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ and C C C is induced, every edge in M ′ M' M ′ has at most one endpoint in V ( C ) V(C) V ( C ) . Let E 1 = { u v ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } E_1 = \{uv \in M' \mid\{u,v\} \cap V(C) = \varnothing\} E 1 = { uv ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } and E 2 = M ′ ∖ E 1 E_2 = M' \setminus E_1 E 2 = M ′ ∖ E 1 . Note that for every edge e ∈ E 1 e \in E_1 e ∈ E 1 , both endpoints are disjoint from Z Z Z and the endpoint in L i − 1 L_{i-1} L i − 1 is adjacent
@page 18/43 starts_mid=1 ends_mid=1 So from now on, assume that every edge e ∈ E 1 e \in E_1 e ∈ E 1 has exactly one endpoint that is adjacent to a vertex in Z Z Z . We denote such endpoint by u e u_e u e .
For each edge e ∈ E 1 e \in E_1 e ∈ E 1 , we fix a shortest path P e P_e P e in G G G joining u e u_e u e to some vertex in V ( C ) V(C) V ( C ) . Note that V ( P e ) ∖ { u e } ⊆ Z V(P_e) \setminus\{u_e\} \subseteq Z V ( P e ) ∖ { u e } ⊆ Z . By w e w_e w e we denote the endpoint of P e P_e P e in V ( C ) V(C) V ( C ) . For edges e ∈ E 2 e \in E_2 e ∈ E 2 , we set w e w_e w e be their endpoint in C C C . Note that the paths P e P_e P e do not contain any edge from E 2 E_2 E 2 .
Next, we fix two consecutive vertices z 1 z_1 z 1 and z 2 z_2 z 2 in C C C and we partition V ( C ) V(C) V ( C ) to the sets B 1 = { z 1 } B_1 = \{z_1\} B 1 = { z 1 } , B 2 = { z 2 } B_2 = \{z_2\} B 2 = { z 2 } , and B 3 = V ( C ) ∖ { z 1 , z 2 } B_3 = V(C) \setminus\{z_1,z_2\} B 3 = V ( C ) ∖ { z 1 , z 2 } . Fix j ∈ { 1 , 2 , 3 } j \in\{1,2,3\} j ∈ { 1 , 2 , 3 } so that the number of edges e ∈ M e \in M e ∈ M with w e ∈ B j w_e \in B_j w e ∈ B j is maximized. Since ∣ M ∣ ≥ 3 k |M| \geq3k ∣ M ∣ ≥ 3 k , B j B_j B j contains the vertices w e w_e w e of at least k k k edges in M M M . Thus, by contracting the paths P e P_e P e for each e ∈ E 1 e \in E_1 e ∈ E 1 with w e ∈ B j w_e \in B_j w e ∈ B j to single edges, contracting V ( C ) ∖ { z 1 , z 2 } V(C) \setminus\{z_1,z_2\} V ( C ) ∖ { z 1 , z 2 } to a single vertex, and removing all remaining vertices, we obtain the k ′ k' k ′ -tipi for k ′ ≥ k k' \geq k k ′ ≥ k (and thus, also the k k k -tipi) as an induced minor.
As the main result of this section, we show excluding a tipi as an induced minor yields a class of bounded induced matching treewidth.
Theorem 4.4. For every integer k ≥ 1 k \geq1 k ≥ 1 , every graph G G G that does not contain the k k k -tipi as an induced minor satisfies tree - μ ( G ) ≤ 11 k + 5 \operatorname{tree}\text{-}\mu(G) \leq11k + 5 tree - μ ( G ) ≤ 11 k + 5 .
Proof. Without loss of generality, assume that G G G is connected, as otherwise we can process each component separately and obtain a tree decomposition of G G G by combining the tree decompositions of components. If G G G is a tree, then tw ( G ) ≤ 1 \operatorname{tw}(G) \leq1 tw ( G ) ≤ 1 and thus, due Proposition 2.1 (1.), we have tree - μ ( G ) ≤ 2 \operatorname{tree}\text{-}\mu(G) \leq2 tree - μ ( G ) ≤ 2 . So, assume hat G G G has a cycle.
Pick any vertex r r r of G G G and consider the BFS-layering ( L 0 , … , L q ) (L_0,\ldots,L_q) ( L 0 , … , L q ) of G G G rooted at this vertex.
Claim 4.4.1. For every i ≥ 0 i \geq0 i ≥ 0 , every induced matching in G [ L i ] G[L_i] G [ L i ] has at most k k k edges.
Proof of Claim. The statement is trivial for i = 0 i = 0 i = 0 , so assume that i ≥ 1 i \geq1 i ≥ 1 . For contradiction, suppose there is an induced matching M M M on k + 1 k+1 k + 1 edges contained in L i L_i L i . Note that the set Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j is connected and disjoint from L i L_i L i . Furthermore, every vertex in L i L_i L i has a neighbor in Z = ⋃ j < i L j Z = \bigcup_{j<i} L_j Z = ⋃ j < i L j . Thus, by Observation 4.2 , G G G contains the k k k -tipi as an induced minor, a contradiction. ◁
We next bound the size of an induced matching between layers.
Claim 4.4.2. For every i ∈ [ q ] i \in[q] i ∈ [ q ] , every induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching of G G G has at most 3 k + 1 3k+1 3 k + 1 edges.
Proof of Claim. We assume that i ≥ 2 i \geq2 i ≥ 2 since in the case i = 1 i = 1 i = 1 we have ∣ L 0 ∣ = 1 |L_0| = 1 ∣ L 0 ∣ = 1 . Suppose that G G G contains an induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching M M M of at least 3 k + 2 3k+2 3 k + 2 edges. Recall that we assumed that G G G contains a cycle as a subgraph. Let C C C be a shortest such cycle; in particular, it is induced. We distinguish two cases depending whether C C C uses some edge from M M M . In both cases, we use Lemma 4.3 to arrive at a contradiction.
Case A: E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ . Let j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j ≠ ∅ } j_0 = \min\{j \in[q] \mid V(C) \cap L_j \neq\varnothing\} j 0 = min { j ∈ [ q ] ∣ V ( C ) ∩ L j = ∅ } and let z ∈ V ( C ) ∩ L j 0 z \in V(C) \cap L_{j_0} z ∈ V ( C ) ∩ L j 0 . Let P z P_z P z be a root path for z z z . Note that there is at most one edge e ′ ∈ M e' \in M e ′ ∈ M that has an endpoint in V ( P z ) V(P_z) V ( P z ) , as P z P_z P z contains at most one vertex from L i − 1 L_{i-1} L i − 1 and at most one vertex from L i L_i L i , and these two vertices are adjacent. Let M ′ = M ∖ { e ′ } M' = M \setminus\{e'\} M ′ = M ∖ { e ′ } (or M ′ = M M' = M M ′ = M if e ′ e' e ′ does not exist), note that ∣ M ′ ∣ ≥ 3 k |M'| \geq3k ∣ M ′ ∣ ≥ 3 k . For every edge in M ′ M' M ′ we have that both endpoints are disjoint from V ( P z ) V(P_z) V ( P z ) .
Let Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) Z = \bigcup_{j<i-1} L_j \cup V(C) \cup V(P_z) Z = ⋃ j < i − 1 L j ∪ V ( C ) ∪ V ( P z ) and note that G [ Z ] G[Z] G [ Z ] is connected and contains the cycle C C C . Our goal is to apply Lemma 4.3 for Z Z Z and M ′ M' M ′ . Since E ( C ) ∩ M = ∅ E(C) \cap M = \varnothing E ( C ) ∩ M = ∅ and C C C is induced, every edge in M ′ M' M ′ has at most one endpoint in V ( C ) V(C) V ( C ) . Let E 1 = { u v ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } E_1 = \{uv \in M' \mid\{u,v\} \cap V(C) = \varnothing\} E 1 = { uv ∈ M ′ ∣ { u , v } ∩ V ( C ) = ∅ } and E 2 = M ′ ∖ E 1 E_2 = M' \setminus E_1 E 2 = M ′ ∖ E 1 . Note that for every edge e ∈ E 1 e \in E_1 e ∈ E 1 , both endpoints are disjoint from Z Z Z and the endpoint in L i − 1 L_{i-1} L i − 1 is adjacent to Z Z Z . For every edge in E 2 E_2 E 2 , only one of its endpoints is in V ( C ) V(C) V ( C ) and none is in Z ∖ V ( C ) Z \setminus V(C) Z ∖ V ( C ) . Therefore, by applying Lemma 4.3 for Z Z Z and M ′ M' M ′ , we get that G G G contains the k k k -tipi as an induced minor, a contradiction.
Case B: E ( C ) ∩ M ≠ ∅ E(C) \cap M \ne\emptyset E ( C ) ∩ M = ∅ . Note that in this case there are at least two edges between vertices in L i − 1 L_{i-1} L i − 1 and L i L_i L i that belong to E ( C ) E(C) E ( C ) .
Consider an inclusion-wise minimal subpath Q Q Q of C ∩ ⋃ j > i − 1 L j C \cap\bigcup_{j>i-1} L_j C ∩ ⋃ j > i − 1 L j with both endpoints in L i L_i L i and all internal vertices in ⋃ j > i L j \bigcup_{j>i} L_j ⋃ j > i L j . Let v 1 , v 2 v_1,v_2 v 1 , v 2 be the endpoints of Q Q Q and let u 1 u_1 u 1 and u 2 u_2 u 2 be the neighbors of v 1 v_1 v 1 and v 2 v_2 v 2 respectively in C C C which belong to L i − 1 L_{i-1} L i − 1 ; if v 1 = v 2 v_1=v_2 v 1 = v 2 , pick u 1 u_1 u 1 and u 2 u_2 u 2 be distinct vertices. Then, let P 1 P_1 P 1 and P 2 P_2 P 2 be, respectively, root paths of u 1 u_1 u 1 and u 2 u_2 u 2 . Now set Z = ⋃ j < i − 1 L j ∪ V ( Q ) ∪ V ( P 1 ) ∪ V ( P 2 ) Z = \bigcup_{j<i-1} L_j \cup V(Q) \cup V(P_1) \cup V(P_2) Z = ⋃ j < i − 1 L j ∪ V ( Q ) ∪ V ( P 1 ) ∪ V ( P 2 ) and note that G [ Z ] G[Z] G [ Z ] is connected and contains a cycle. Also note that by construction there are at most two edges in M M M that have some endpoint in Z Z Z . Let M ′ M' M ′ be obtained from M M M by removing these two edges (if they exist); note that ∣ M ′ ∣ ≥ 3 k |M'| \ge3k ∣ M ′ ∣ ≥ 3 k . Furthermore, for every edge from M ′ M' M ′ , its endpoint in L i − 1 L_{i-1} L i − 1 has a neighbor in L i − 2 ⊆ Z L_{i-2} \subseteq Z L i − 2 ⊆ Z . Therefore, by applying Lemma 4.3 to Z Z Z and M ′ M' M ′ we get that G G G contains a k k k -tipi as an induced minor, a contradiction. ◃ \triangleleft ◃
Thus, by Lemma 2.3 for a = k a=k a = k and b = 3 k + 1 b=3k+1 b = 3 k + 1 , we obtain that tree - μ ( G ) ≤ 2 k + 3 ( 3 k + 1 ) = 11 k + 3 \operatorname{tree}\text{-}\mu(G) \le2k+3(3k+1)=11k+3 tree - μ ( G ) ≤ 2 k + 3 ( 3 k + 1 ) = 11 k + 3 . This completes the proof. □ \square □
Dichotomies for one excluded graph
In this section we prove dichotomies for boundedness of induced matching treewidth in classes that exclude a fixed substructure. For exclusion as a subgraph, as an induced subgraph, as a minor, or as a topological minor, the dichotomies almost coincide with their counterparts for tree-independence number.
... as a subgraph or an induced subgraph
Theorem 5.1 (Theorem 1.1 (1.) restated). The class of H H H -subgraph-free graphs has bounded induced matching treewidth if and only if every component of H H H is a subcubic tree with at most one vertex of degree 3. All unbounded cases remain so, even when restricted to 2-connected graphs.
Proof. If every component of H H H is a subcubic tree with at most one vertex of degree 3, then H H H -subgraph-free graphs have bounded tree-independence number (see Table 1 ), and thus also induced matching treewidth.
Otherwise H H H contains a cycle or a vertex of degree at least 4. In this case, subcubic graphs of girth at least ∣ V ( H ) ∣ + 1 |V(H)|+1 ∣ V ( H ) ∣ + 1 are H H H -subgraph-free and have unbounded induced matching treewidth by Lemma 3.3 (1.).
Theorem 5.2 (Theorem 1.1 (2.) restated). The class of H H H -free graphs has bounded induced matching treewidth if and only if H = P 3 H=P_3 H = P 3 or H H H has maximum degree at most 1 (i.e., is a subgraph of a matching). All unbounded cases remain so, even when restricted to 2-connected graphs.
Proof. Recall that P 3 P_3 P 3 -free graphs are precisely graphs whose every component is a clique; clearly they have bounded induced matching treewidth. If H H H is a subgraph of a matching, then H H H -free graphs do not contain large induced matchings at all, so in particular induced matching treewidth is bounded.
Now, let us assume that H H H is neither P 3 P_3 P 3 nor a graph with maximum degree at most 1. Each such H H H contains one of the following graphs as an induced subgraph: K 3 K_3 K 3 , P 3 + P 1 P_3+P_1 P 3 + P 1 , P 4 P_4 P 4 , K 1 , 3 K_{1,3} K 1 , 3 , C 4 C_4 C 4 . Each of them can be excluded by Lemma 3.3 (1.), (2.), and (4.).
... as a minor or a topological minor
Theorem 5.3 (Theorem 1.1 (3.) restated). The class of H H H -minor-free graphs has bounded induced matching treewidth if and only if H H H is planar. All unbounded cases remain so, even when restricted to 2-connected graphs.
Proof. If H H H is planar, then H H H -minor-free graphs have bounded treewidth [48 ] and thus also induced matching treewidth. Otherwise, induced matching treewidth is unbounded by Lemma 3.3 (3.).
Theorem 5.4 (Theorem 1.1 (4.) restated). The class of H H H -topological-minor-free graphs has bounded induced matching treewidth if and only if H H H is subcubic and planar. All unbounded cases remain so, even when restricted to 2-connected graphs.
Proof. It is well-known that if H H H is subcubic, then classes of H H H -minor-free graphs and H H H -topological-minor-free graphs coincide (see, e.g., Diestel [29 ] ). Thus, if H H H is subcubic and planar, then H H H -topological-minor-free (equivalently, H H H -minor-free graphs) graphs have bounded treewidth [48 ] and thus also induced matching treewidth. Otherwise, induced matching treewidth is unbounded by Lemma 3.3 (1.) and Lemma 3.3 (3.).
... as an induced subdivision
Now let us consider H H H -induced-subdivision-free graphs, for any fixed H H H .
Theorem 1.2. Let H H H be a graph with at least 2 vertices. The class of H H H -topological-minor-free graphs has bounded induced matching treewidth if and only if H H H is not contained in one of the following graphs: C 4 C_4 C 4 , K 4 − K_4^{-} K 4 − , 1 1 1 -tipi, or a matching as an induced topological minor. All unbounded cases remain so, even when restricted to 2-connected graphs.
Proof. If H H H is an induced subdivision of C 4 C_4 C 4 or K 4 − K_4^{-} K 4 − , then H H H -induced-subdivision-free graphs have bounded tree-independence number (see Table 1 ), and thus also induced matching treewidth. If H H H is 1 1 1 -tipi, then the claim follows from combining Lemma 4.1 and Theorem 4.4. If H H H is a graph of maximum degree 1, then, by Corollary 2.5 , H H H -induced-subdivision-free graphs coincide with H H H -free graphs. Such graphs do not have a large induced matching at all, so in particular they have bounded induced matching treewidth.
Thus, let us argue that all remaining cases define a class with unbounded induced matching treewidth. We employ a small case analysis. We remark that in all subsequent claims we assume that H H H satisfies all properties established so far. Let us start with a few simple observations.
Claim 1.2.1. Induced matching treewidth of H H H -induced-subdivision-free graphs is unbounded if:
H H H contains K 1 , 3 K_{1,3} K 1 , 3 as an induced subgraph,
H H H contains P 3 + P 1 P_3 + P_1 P 3 + P 1 or P 4 P_4 P 4 or K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced subdivision,
H H H is non-planar,
H H H has a vertex of degree at least 4.
Proof of Claim. First, if H H H contains K 1 , 3 K_{1,3} K 1 , 3 as an induced subgraph, then claw-free graphs are H H H -induced-subdivision-free and thus induced matching treewidth is unbounded by Lemma 3.3 (2.). Second, if H H H contains ( P 3 + P 1 ) (P_3 + P_1) ( P 3 + P 1 ) or P 4 P_4 P 4 or ( K 3 + P 1 ) (K_3 + P_1) ( K 3 + P 1 ) as an induced subdivision, then it also contains one of these graphs as an induced minor, so Lemma 3.3 (4.) yields that induced matching treewidth is unbounded in H H H -induced-subdivision-free graphs. Third, every H H H -minor-free graph is H H H -topological-minor-free, and every H H H -topological-minor-free graph is H H H -induced-subdivision-free. If H H H is non-planar, then the former class has unbounded induced matching treewidth by Lemma 3.3 (3.). If H H H has a vertex of degree at least 4, then every subcubic graph is H H H -topological-minor-free, so the latter class has unbounded induced matching treewidth by Lemma 3.3 (1.). ◁
So suppose that H H H is a subcubic planar graph that does not contain K 1 , 3 K_{1,3} K 1 , 3 as an induced subgraph nor P 4 P_4 P 4 , P 3 + P 1 P_3 + P_1 P 3 + P 1 , K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced subdivision. If H H H is a forest, then these conditions imply that H H H is either P 3 P_3 P 3 (and thus, contained in C 4 C_4 C 4 as an induced subdivision) or has maximum degree 1 – in both cases we have one of bounded cases considered above. Thus, H H H is not a forest. Furthermore, since H H H excludes K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced subdivision, every cycle in H H H is dominating.
Claim 1.2.2. If H H H has an induced cycle on at least four vertices, then induced matching treewidth of H H H -induced-subdivision-free graphs is unbounded.
Proof of Claim. If H H H has an induced cycle on at least 5 vertices, then it also contains P 3 + P 1 P_3 + P_1 P 3 + P 1 , so again we have unbounded case. Suppose that H H H has an induced cycle on four vertices { a , b , c , d } \{a,b,c,d\} { a , b , c , d } . Since H H H is not isomorphic to C 4 C_4 C 4 , there must be a vertex x ∈ V ( H ) ∖ { a , b , c , d } x \in V(H) \setminus\{a,b,c,d\} x ∈ V ( H ) ∖ { a , b , c , d } . Since every cycle is dominating, x x x must have neighbors in { a , b , c , d } \{a,b,c,d\} { a , b , c , d } . If x x x has one neighbor in { a , b , c , d } \{a,b,c,d\} { a , b , c , d } , then H H H contains P 3 + P 1 P_3 + P_1 P 3 + P 1 , a contradiction. Similarly, if x x x has two neighbors on { a , b , c , d } \{a,b,c,d\} { a , b , c , d } and they are non-adjacent, then H H H contains an induced K 1 , 3 K_{1,3} K 1 , 3 .
::: If the neighborhood of x x x in { a , b , c , d } \{a,b,c,d\} { a , b , c , d } consists of two adjacent vertices, then H H H contains a house as an induced subdivision, and thus induced matching treewidth is unbounded by Lemma 3.3 (6.). If the neighborhood of x x x in { a , b , c , d } \{a,b,c,d\} { a , b , c , d } consists of three vertices, then H H H contains K 4 K_4 K 4 as an induced subdivision and induced matching treewidth is unbounded by Lemma 3.3 (7.). As H H H is subcubic, this covers all cases if H H H contains an induced C 4 C_4 C 4 .
Thus, assume that H H H is not a forest and all induced cycles in H H H are triangles, i.e., H H H is chordal. If H H H contains K 4 K_4 K 4 as an induced subdivision, then H H H -induced-subdivision-free graphs have unbounded induced matching treewidth by Lemma 3.3 (7.). We observe that every such graph that does not contain previously excluded substructures contains either a K 4 − K_4^{-} K 4 − or a 1-tipi (as an induced subgraph). We know that H H H must contain at least one more vertex v v v , as both these structures were considered in the first part of the proof and now we assume that H H H is not one of such graphs.
Claim 1.2.3. If H H H contains a K 4 − K_4^{-} K 4 − , then induced matching treewidth of H H H -induced-subdivision-free graphs is unbounded.
Proof of Claim. Fix one copy of K 4 − K_4^{-} K 4 − in H H H . Since H H H is ( K 3 + P 1 ) (K_3+P_1) ( K 3 + P 1 ) -free, v v v is adjacent to both triangles in K 4 − K_4^{-} K 4 − . Since H H H is subcubic, the neighborhood of v v v in the considered copy of K 4 − K_4^{-} K 4 − consists of both degree-2 vertices. However, this means that H H H contains an induced C 4 C_4 C 4 , a contradiction.
Claim 1.2.4. If H H H contains a 1-tipi, then induced matching treewidth of H H H -induced-subdivision-free graphs is unbounded.
Proof of Claim. Fix one copy of 1-tipi in H H H . Since H H H is ( K 3 + P 1 ) (K_3+P_1) ( K 3 + P 1 ) -free and subcubic, v v v is adjacent to at least one of degree-2 vertices of the 1-tipi. If v v v is also adjacent to the degree-1 vertex of the 1-tipi, H H H has an induced C 4 C_4 C 4 , a contradiction. If v v v is adjacent to both degree-2 vertices of the 1-tipi, then H H H is not ( K 3 + P 1 ) (K_3+P_1) ( K 3 + P 1 ) -free, a contradiction. Thus, the neighborhood of v v v in the considered copy of 1-tipi consists of exactly one of degree-2 vertices. Then the vertices of the copy of 1-tipi, together with v v v , induce in H H H a copy of the bull. and we get an unbounded case by Lemma 3.3 (5.).
Summing up, for every graph H H H not listed in the first part of the statement, induced matching treewidth of H H H -induced-subdivision-free graphs is unbounded. As we only used constructions from Lemma 3.3 (1.)–(8.), the statement holds even when we restrict attention to 2-connected graphs. This completes the proof.
... as an induced minor
Finally, we consider the last containment relation, i.e., induced minors.
Theorem 1.3. Let H H H be a graph with at least 2 vertices. The class of H H H -induced-minor-free graphs has bounded induced matching treewidth if and only if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q , for some q ∈ N q \in\mathbb{N} q ∈ N , W 4 W_4 W 4 , K 5 − K_5^{-} K 5 − , a tipi, or a matching.
Proof. If H H H is an induced minor of K 2 , q K_{2,q} K 2 , q for some fixed q q q or W 4 W_4 W 4 , or K 5 − K_5^{-} K 5 − , then H H H -induced-minor-free graphs have bounded tree-independence number (see Table 1 ), and thus also induced matching treewidth. If H H H is a tipi, then the claim follows from Theorem 4.4. If H H H is a graph of maximum degree 1, then, by Corollary 2.5 , classes of H H H -free graphs and H H H -induced-minor-free graphs coincide and such graphs do not have large induced matchings at all.
Now we need to show that all remaining graphs H H H define classes of unbounded induced matching treewidth. Thus, assume that H H H is not one of the graphs listed above.
Claim 1.3.1. If H H H is disconnected, then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. Suppose H H H is disconnected. Since H H H is not a subgraph of a matching, at least one of components of H H H , say C C C , must have at least three vertices. Thus, C C C contains either P 3 P_3 P 3 or K 3 K_3 K 3 as an induced subgraph. Consequently, H H H contains either P 3 + P 1 P_3 + P_1 P 3 + P 1 or K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced minor, so the conclusion follows from Lemma 3.3 (4).
Next, we consider two cases, depending whether H H H is 2-connected or not.
Case A. H H H is not 2-connected. Let B \mathcal{B} B and C \mathcal{C} C denote, respectively, the set of blocks and the set of cutvertices of G G G . Let T T T be the block-cut tree of G G G .
Claim 1.3.2. If H H H has at least two cutvertices, then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. If H H H has at least two cutvertices, T T T contains a 5-vertex path with three vertices from B \mathcal{B} B (and two from C \mathcal{C} C ) – recall that every leaf of T T T is in B \mathcal{B} B . Denote the consecutive vertices of this path by x x x , a a a , y y y , b b b , z z z . Let v x v_x v x (resp., v z v_z v z ) be a neighbor of a a a (resp., b b b ) in the block x x x (resp., z z z ). Let P P P be a shortest a a a -b b b -path contained in y y y . Note that v x v_x v x , a a a , P P P , b b b , v z v_z v z is an induced path with at least four vertices. Thus, P 4 P_4 P 4 is an induced minor of H H H , and the conclusion follows from Lemma 3.3 (4).
So, assume that H H H has exactly one cutvertex, denote it by c c c . Consequently, T T T is a star with c c c as the central vertex.
Claim 1.3.3. If H H H has a block with at least four vertices, then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. Let b b b be a block of G G G with at least four vertices and let b ′ b' b ′ be some block other than b b b ; it exists since G G G is not 2-connected. As b − c b-c b − c is a connected graph on at least three vertices, it contains an induced P 3 P_3 P 3 or K 3 K_3 K 3 . This subgraph, together with any vertex from b ′ − c b'-c b ′ − c , forms an induced P 3 + P 1 P_3 + P_1 P 3 + P 1 or induced K 3 + P 1 K_3 + P_1 K 3 + P 1 in H H H . In both cases, the conclusion follows from Lemma 3.3 (4).
Thus, every block of G G G has either two or three vertices, i.e., is either a K 2 K_2 K 2 or K 3 K_3 K 3 .
Claim 1.3.4. If H H H has two blocks with three vertices, then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. If H H H has two blocks with three vertices, then it contains a 2-windmill as an induced subgraph. The conclusion follows from Lemma 3.3 (11).
Consequently, H H H has at most one block with three vertices. This means that H H H is an induced subgraph of a tipi – a graph whose exclusion defines a class of bounded induced matching treewidth. This completes the proof in Case A.
Case B. H H H is 2-connected. First, we observe the following.
Claim 1.3.5. If H H H contains induced P 2 + P 1 P_2 + P_1 P 2 + P 1 , then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. The claim follows from Lemma 3.3 (10).
So from now on let us assume that H H H is ( P 2 + P 1 ) (P_2 + P_1) ( P 2 + P 1 ) -free, i.e., is a complete multipartite graph. Let k k k be the number of parts (i.e., inclusion-wise maximal independent sets) in H H H . A part is large if it has at least two vertices.
Claim 1.3.6. If H H H has at least 3 large parts, then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. If H H H has at least three large parts, then it contains K 2 , 2 , 2 K_{2,2,2} K 2 , 2 , 2 as an induced subgraph. The claim follows from Lemma 3.3 (8.). ◁
Claim 1.3.7. If k ≥ 5 k \ge5 k ≥ 5 , then induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. If k ≥ 5 k \ge5 k ≥ 5 , then H H H contains K 5 K_5 K 5 and thus, is non-planar. The claim follows from Lemma 3.3 (3.). ◁
So, H H H has two, three, or four parts. Let us consider these cases separately.
Claim 1.3.8. If k = 2 k = 2 k = 2 , then either H H H is an induced minor of K 2 , q K_{2,q} K 2 , q for some q q q , or induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. If each part has at least three vertices, then H H H contains K 3 , 3 K_{3,3} K 3 , 3 and thus, is non-planar, so we are done by Lemma 3.3 (3.). Otherwise H H H is an induced minor of K 2 , q K_{2,q} K 2 , q for some q ≥ 2 q \ge2 q ≥ 2 , which is one of the cases that imply bounded induced matching treewidth. ◁
Claim 1.3.9. If k = 3 k = 3 k = 3 , then either H H H is an induced minor of K 2 , q K_{2,q} K 2 , q for some q q q or isomorphic to W 4 W_4 W 4 , or induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. By Claim 1.3.6 we know that at least one part is just a singleton. Let H = K a , b , 1 H = K_{a,b,1} H = K a , b , 1 , where a ≥ b a \ge b a ≥ b .
If b = 1 b = 1 b = 1 , then H H H is an induced minor of K a + 1 , 2 K_{a+1,2} K a + 1 , 2 , i.e., is one of the graphs that defines a class of bounded induced matching treewidth. If a ≥ 3 a \ge3 a ≥ 3 , then H H H contains K 3 , 3 K_{3,3} K 3 , 3 as a subgraph and thus is non-planar, so we are done by Lemma 3.3 (3.). So, we are left with the case that H = K 2 , 2 , 1 ≃ W 4 H = K_{2,2,1} \simeq W_4 H = K 2 , 2 , 1 ≃ W 4 . In this case, we obtain a class of bounded induced matching treewidth. ◁
Claim 1.3.10. If k = 4 k = 4 k = 4 , then either H H H is isomorphic to K 5 − K_5^{-} K 5 − , or induced matching treewidth of H H H -induced-minor-free graphs is unbounded.
Proof of Claim. By Claim 1.3.6 we know that two parts are singletons. Let H = K a , b , 1 , 1 H = K_{a,b,1,1} H = K a , b , 1 , 1 , where a ≥ b a \ge b a ≥ b . If a ≥ 3 a \ge3 a ≥ 3 or a = b = 2 a = b = 2 a = b = 2 , then H H H contains K 3 , 3 K_{3,3} K 3 , 3 as a subgraph and again we are done since H H H is non-planar. So, we are left with the case that H = K 2 , 1 , 1 , 1 ≃ K 5 − H = K_{2,1,1,1} \simeq K_5^{-} H = K 2 , 1 , 1 , 1 ≃ K 5 − . In this case, we obtain a class of bounded induced matching treewidth. ◁
This completes the proof. □
Let us remark that the case that Claim 1.3.4 and Claim 1.3.5 are the only cases in the proof of Theorem 1.3 where we use constructions that are not 2-connected, i.e., Lemma 3.3 (10.) and (11.). Furthermore, Claim 1.3.4 is the only place where we use Lemma 3.3 (11.), i.e., graphs that contain vertices of degree 1. This gives the following observation.
Observation 5.5. Let H H H be a graph for which H H H -induced-minor-free graphs have unbounded induced matching treewidth.
Induced matching treewidth in H H H -induced-minor-free graphs remains unbounded, even restricted to graphs of minimum degree at least 2, unless H H H contains a 2-windmill as an induced subgraph.
Induced matching treewidth in H H H -induced-minor-free graphs remains unbounded, even restricted to 2-connected graphs, unless H H H contains a 2-windmill as an induced subgraph or H H H is 2-connected and contains P 2 + P 1 P_2 + P_1 P 2 + P 1 as an induced subgraph.
Observation 5.5 will be a starting point to further discussion in § 8 and § 9 .
Restricting to graphs of minimum degree at least 2
Now, let us discuss the (un)boundedness of the considered parameters when we additionally assume that graphs have no vertices of degree 1. By Lemma 2.2 , this restriction does not make any difference for tree-independence number. Furthermore, recall that this is also the case for induced matching treewidth and graphs that excluding a fixed graph H H H as an (induced) subgraph, (induced) topological minor, or a minor. However, it turns out that for H H H -induced-minor-free graphs, the situation changes.
Windmill-induced-minor-free graphs of minimum degree 2
We show that if we assume that no vertices have degree at most 1, then we get one more family of graphs that define classes of bounded induced matching treewidth.
Theorem 6.1. There is a function f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N such that for every integer k ≥ 0 k\ge0 k ≥ 0 , every graph G G G of minimum degree at least 2 that does not contain the k k k -windmill as an induced minor satisfies tree-μ ( G ) ≤ 36 k 3 + 2 k \mu(G)\le36k^3+2k μ ( G ) ≤ 36 k 3 + 2 k .
Proof. Without loss of generality we may assume that G G G is connected. As in the proof of Theorem 4.4, consider the BFS-layering ( L 0 , … , L q ) (L_0,\ldots,L_q) ( L 0 , … , L q ) of G G G rooted at an arbitrary vertex r r r . We aim to bound the size of a largest induced matching within each layer and between any two consecutive layers, and then apply Lemma 2.3 .
Claim 6.1.1. For every i ≥ 0 i\ge0 i ≥ 0 , every induced matching of G G G between vertices of L i L_i L i has at most k − 1 k-1 k − 1 edges.
Proof of Claim. For i = 0 i=0 i = 0 the statement is trivial, and for i ≥ 1 i\ge1 i ≥ 1 , as in the proof of Theorem 4.4, the claim follows by applying Observation 4.2 for Z = ⋃ j < i L j Z=\bigcup_{j<i}L_j Z = ⋃ j < i L j .
We next bound the size of an induced matching between consecutive layers.
Claim 6.1.2. For every i ∈ [ q ] i\in[q] i ∈ [ q ] , every induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching of G G G has at most 12 k 3 − 1 12k^3-1 12 k 3 − 1 edges.
Proof of Claim. We assume that i ≥ 2 i\ge2 i ≥ 2 since in the case i = 1 i=1 i = 1 we have ∣ L 0 ∣ = 1 |L_0|=1 ∣ L 0 ∣ = 1 . We fix i ∈ [ 2 , q ] i\in[2,q] i ∈ [ 2 , q ] and suppose that G G G contains an induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching M M M with at least 12 k 3 12k^3 12 k 3 edges. We denote by M u p M^{\mathrm{up}} M up (resp. M d o w n M^{\mathrm{down}} M down ) the set of endpoints of M M M in L i − 1 L_{i-1} L i − 1 (resp. L i L_i L i ) and by G ′ G' G ′ the graph G [ ⋃ j ≥ i L j ] G[\bigcup_{j\ge i}L_j] G [ ⋃ j ≥ i L j ] — see Figure 3 for an illustration.
Figure 3. An illustration of the sets M u p M^{\mathrm{up}} M up and M d o w n M^{\mathrm{down}} M down and the graph G ′ G' G ′ .
We distinguish cases:
Case A: There is a component C C C of G ′ G' G ′ containing at least 4 k 2 4k^2 4 k 2 vertices of M d o w n M^{\mathrm{down}} M down . In this case, consider an inclusion-wise minimal (with respect to the vertex set) tree T T T in C C C which satisfies the following properties:
Note that every leaf of T T T is in M d o w n M^{\mathrm{down}} M down and therefore the leaves of T T T are pairwise non-adjacent in G G G . We distinguish two subcases depending on the number of leaves of T T T .
Subcase A.1: T T T has at least k + 1 k+1 k + 1 leaves. Let L ( T ) ⊆ M d o w n L(T) \subseteq M^{\mathrm{down}} L ( T ) ⊆ M down be the set of leaves of T T T and let I ( T ) ⊆ V ( G ) I(T) \subseteq V(G) I ( T ) ⊆ V ( G ) be the set of all internal vertices of T T T , i.e., I ( T ) = V ( T ) ∖ L ( T ) I(T) = V(T) \setminus L(T) I ( T ) = V ( T ) ∖ L ( T ) . Pick arbitrary w d o w n ∈ L ( T ) w^{\mathrm{down}} \in L(T) w down ∈ L ( T ) and let w u p w^{\mathrm{up}} w up be the neighbor of w d o w n w^{\mathrm{down}} w down in M M M . Let M ′ M' M ′ be the set of edges of M M M that are incident to L ( T ) ∖ { w d o w n } L(T) \setminus\{w^{\mathrm{down}}\} L ( T ) ∖ { w down } . Note that ∣ M ′ ∣ ≥ k |M'| \ge k ∣ M ′ ∣ ≥ k . Finally, let Z = I ( T ) ∪ { w d o w n , w u p } ∪ ⋃ j < i − 1 L j Z = I(T) \cup\{w^{\mathrm{down}}, w^{\mathrm{up}}\} \cup\bigcup_{j<i-1} L_j Z = I ( T ) ∪ { w down , w up } ∪ ⋃ j < i − 1 L j . We observe that Z Z Z is connected and every vertex in V ( M ′ ) V(M') V ( M ′ ) has a neighbor in Z Z Z : for vertices of L i − 1 L_{i-1} L i − 1 such neighbor is in L i − 2 L_{i-2} L i − 2 and for vertices in L i L_i L i such neighbor is in I ( T ) I(T) I ( T ) . Thus, by Observation 4.2 , G G G contains the k k k -windmill as an induced minor, a contradiction.
Subcase A.2: T T T has at most k k k leaves. We argue that in this case there is a path P P P in T T T with all internal vertices of degree 2 (in T T T ) containing at least 2 k 2k 2 k vertices of M d o w n M^{\mathrm{down}} M down . To see why this holds, consider the tree T ~ \widetilde{T} T obtained from T T T by contracting all vertices of degree two (in T T T ). Since T ~ \widetilde{T} T has at most k k k leaves and no degree-two vertices, it has at most 2 k 2k 2 k vertices and therefore at most 2 k − 1 2k-1 2 k − 1 edges. Since T T T spans at least 4 k 2 4k^2 4 k 2 vertices of M d o w n M^{\mathrm{down}} M down , there is an edge of T ~ \widetilde{T} T corresponding to the claimed path P P P in T T T .
Claim 6.1.3. P P P is an induced path in G G G .
Proof of Claim. Let the consecutive vertices of P P P be v 1 , v 2 , … , v p v_1, v_2, \ldots, v_p v 1 , v 2 , … , v p and suppose there are indices j , j ′ j,j' j , j ′ where j + 1 < j ′ j+1<j' j + 1 < j ′ , such that v j v j ′ v_jv_{j'} v j v j ′ is an edge of G G G . If v j + 1 , … , v j ′ − 1 ∉ M d o w n v_{j+1},\ldots,v_{j'-1} \notin M^{\mathrm{down}} v j + 1 , … , v j ′ − 1 ∈ / M down , then replacing P P P in T T T by v 1 , … , v j , v j ′ , … , v p v_1,\ldots,v_j,v_{j'},\ldots,v_p v 1 , … , v j , v j ′ , … , v p we obtain a smaller tree that spans M d o w n M^{\mathrm{down}} M down and has the same set of leaves as T T T , contradicting the minimality of T T T . So let j ′ ′ ∈ [ j + 1 , j ′ − 1 ] j'' \in[j+1,j'-1] j ′′ ∈ [ j + 1 , j ′ − 1 ] be the smallest index for which v j ′ ′ ∈ M d o w n v_{j''} \in M^{\mathrm{down}} v j ′′ ∈ M down . Removing the edge v j ′ ′ v j ′ ′ + 1 v_{j''}v_{j''+1} v j ′′ v j ′′ + 1 from T T T and adding the edge v j v j ′ v_jv_{j'} v j v j ′ instead, we obtain a tree with the same vertex set as T T T , but more leaves in M d o w n M^{\mathrm{down}} M down , contradicting the choice of T T T . ◁
Since P P P contains at least 2 k 2k 2 k vertices of M d o w n M^{\mathrm{down}} M down and these vertices are pairwise nonadjacent, we can find a collection Q Q Q of k k k pairwise vertex-disjoint and anticomplete subpaths of P P P , each having two vertices of M d o w n M^{\mathrm{down}} M down as endpoints – see Figure 4 for an illustration.
Figure 4. An illustration of Case A.
Therefore, by removing all vertices of G ′ G' G ′ that are not in a path from Q Q Q , contracting each path in Q Q Q to a single edge, and contracting all edges in ⋃ j < i L j \bigcup_{j<i} L_j ⋃ j < i L j , we get the k ′ k' k ′ -windmill for k ′ ≥ k k' \ge k k ′ ≥ k (and thus, also the k k k -windmill) as an induced minor, a contradiction.
This concludes Case A.
Case B: Every component of G ′ G' G ′ has fewer than 4 k 2 4k^2 4 k 2 vertices of M d o w n M^{\mathrm{down}} M down . Let C \mathcal{C} C be the set of components of G ′ G' G ′ that intersect M d o w n M^{\mathrm{down}} M down . As M M M has size at least 12 k 3 12k^3 12 k 3 , we have ∣ C ∣ ≥ 3 k |\mathcal{C}| \ge3k ∣ C ∣ ≥ 3 k .
Our plan, towards finding a k k k -windmill as an induced minor and therefore contradicting our assumption for the existence of M M M , is the following. We will find a subset C ′ ⊆ C \mathcal{C}' \subseteq\mathcal{C} C ′ ⊆ C of size k k k , and for every component C ∈ C ′ C \in\mathcal{C}' C ∈ C ′ we will find an edge e C = x y e_C=xy e C = x y and two paths P x , P y P_x,P_y P x , P y in G G G such that:
paths P x , P y P_x,P_y P x , P y connect, respectively, x x x and y y y to the root r r r and y ∉ V ( P x ) , x ∉ V ( P y ) y \notin V(P_x), x \notin V(P_y) y ∈ / V ( P x ) , x ∈ / V ( P y ) , and
for C ′ ∈ C ′ ∖ { C } C' \in\mathcal{C}' \setminus\{C\} C ′ ∈ C ′ ∖ { C } , the edge e C ′ e_{C'} e C ′ is vertex-disjoint with both P x P_x P x and P y P_y P y ,
the set { e C ∣ C ∈ C ′ } \{e_C \mid C \in\mathcal{C}'\} { e C ∣ C ∈ C ′ } is an induced matching.
Note that this is sufficient to get the k k k -windmill as an induced minor. Indeed, we first remove from G G G all vertices that do not belong to any of the chosen paths. Second, we contract all edges in the chosen paths, except for the edges incident to the vertices of the induced matching { e C ∣ C ∈ C ′ } \{e_C \mid C \in\mathcal{C}'\} { e C ∣ C ∈ C ′ } . This way we obtain a k k k -windmill as an induced minor in G G G , a contradiction.
It remains to define C ′ \mathcal{C}' C ′ and the special edge and paths for every component in C ′ \mathcal{C}' C ′ .
We distinguish three types of component in C \mathcal{C} C :
(I) a single-vertex component,
(II) a tree with at least two vertices,
(III) not a tree.
As ∣ C ∣ ≥ 3 k |\mathcal{C}| \ge3k ∣ C ∣ ≥ 3 k , there is a set C ′ ⊆ C \mathcal{C}' \subseteq\mathcal{C} C ′ ⊆ C of size k k k such that all components in C ′ \mathcal{C}' C ′ have the same type. We will consider three subcases, depending on the type of components in C ′ \mathcal{C}' C ′ .
Subcase B.1: Type (I). Let v v v be the unique vertex in C C C , clearly v ∈ M d o w n v \in M^{\mathrm{down}} v ∈ M down . Let u ∈ M t o p u \in M^{\mathrm{top}} u ∈ M top be such that v u ∈ M vu \in M v u ∈ M .
As v v v has minimum degree 2 in v v v , there is w ≠ u w \ne u w = u such that v w ∈ E ( G ) vw \in E(G) v w ∈ E ( G ) . Note that w ∈ L i − 1 w \in L_{i-1} w ∈ L i − 1 . We pick e C = v u e_C=vu e C = v u . The path P u P_u P u is a root path for u u u , and the path P v P_v P v is obtained by first following the edge v w vw v w and then a root path of P w P_w P w . See Figure 5 .
Figure 5. An edge e C e_C e C for a component of type (I).
Now let us argue that such choice of e C e_C e C and paths satisfies all required properties. The first property is obvious. The second and the third property follow from the fact that { e C ∣ C ∈ C ′ } ⊆ M \{e_C \mid C \in\mathcal{C}'\} \subseteq M { e C ∣ C ∈ C ′ } ⊆ M and M M M is an induced ( L i − 1 , L i ) (L_{i-1},L_i) ( L i − 1 , L i ) -matching.
Subcase B.2: Type (II). Consider any component C ∈ C ′ C \in\mathcal{C}' C ∈ C ′ . Let v v v be any vertex in V ( C ) ∩ M d o w n V(C) \cap M^{\mathrm{down}} V ( C ) ∩ M down and u u u be the unique neighbor of v v v in M t o p M^{\mathrm{top}} M top . Let z z z be a leaf of C C C that is distinct from v v v ; it exists as C C C is a tree on at least two vertices. Since z z z has degree one in C C C and degree at least two in G G G , it has a neighbor z ′ z' z ′ in L i − 1 L_{i-1} L i − 1 .
Let e C = v v ′ e_C=vv' e C = v v ′ be the first edge on the unique v v v -z z z -path in C C C . We also set P v P_v P v to be the path obtained by first following the edge v u vu v u and then a root path of u u u , and P v ′ P_{v'} P v ′ to be the path obtained by first following the v ′ v' v ′ -z z z -path in C C C , then the edge z z ′ zz' z z ′ , and then a root path of z ′ z' z ′ . See Figure 6 .
Figure 6. An edge e C e_C e C for a component of type (II).
As e C e_C e C is contained in C C C , all required properties are clearly satisfied.
Subcase B.3: Type (III). Consider any component C ∈ C ′ C \in\mathcal{C}' C ∈ C ′ . Again, let v v v be any vertex in V ( C ) ∩ M d o w n V(C) \cap M^{\mathrm{down}} V ( C ) ∩ M down and u u u be the unique neighbor of v v v in M t o p M^{\mathrm{top}} M top .
Fix an induced cycle contained in C C C . Let Q Q Q be a shortest path in C C C joining v v v with a vertex of the cycle; call this vertex z z z . We set e C e_C e C to be any edge x y xy x y of the cycle that does not contain z z z . The paths P x P_x P x and P y P_y P y are obtained by first taking two internally vertex-disjoint paths along the cycle connecting x x x and y y y to z z z , then following the path Q Q Q to v v v , then the edge v u vu v u , and then a root path of u u u . See Figure 7 .
Figure 7. An edge e C e_C e C for a component of type (III).
Similarly as in the previous case, e C e_C e C is contained in C C C , so all required properties are satisfied.
This completes the case analysis and the proof of the claim.
Now, the statement of the theorem follows from Lemma 2.3 .
Dichotomy for induced minors
Equipped with Theorem 6.1 , we can present the following dichotomy result.
Theorem 1.4. Let H H H be a graph. The class of H H H -induced-minor-free graphs, restricted to graphs with minimum degree at least 2, has bounded induced matching treewidth if and only if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q for some q ∈ N q \in\mathbb{N} q ∈ N , W 4 W_4 W 4 , K 5 − K_5^{-} K 5 − , or a windmill.
Proof. The cases that define classes of bounded induced matching treewidth follow directly from combining Theorem 1.3 and Theorem 6.1 . Thus, let us assume that H H H is not one of these graphs. By Theorem 1.3 and Observation 5.5 , we may assume that H H H contains a k k k -windmill as an induced subgraph for some $k \ge 2.
Fix an induced copy W W W of a k k k -windmill with k k k largest possible. Let x x x be the central vertex, and all other vertices are referred to as satellites . Each triangle of this windmill is called a sail , i.e., each sail contains two adjacent satellites and x x x .
Since H H H is not a windmill, there is a vertex not in W W W . Let us consider two cases.
Case A. There is a vertex v v v non-adjacent to x x x . If there is a sail of W W W that is non-adjacent to v v v , then H H H contains K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced minor, and the conclusion follows from Lemma 3.3 (4.).
Thus, v v v is adjacent to all sails of W W W . Let H ′ H' H ′ be the subgraph of H H H induced by the vertices of W W W and v v v . Note that H ′ H' H ′ is 2-connected and contains an induced P 2 + P 1 P_2 + P_1 P 2 + P 1 , consisting of two satellites from one sail and one satellite from another sail. Thus, by Lemma 3.3 (10.), induced matching treewidth is unbounded in H H H -induced-minor-free graphs, even restricted to graphs of minimum degree at least 2.
Case B. Every vertex of H H H is adjacent to x x x . If H − x H-x H − x is connected, then H H H is 2-connected, and since it contains an induced P 2 + P 1 P_2 + P_1 P 2 + P 1 , the conclusion follows from Lemma 3.3 (10.). Thus, H − x H-x H − x has at least two components. Furthermore, as H H H is not an induced minor of a windmill, there is a component of H − x H-x H − x that has at least three vertices, i.e., it contains either P 3 P_3 P 3 or K 3 K_3 K 3 . Summing up, H H H contains P 3 + P 1 P_3 + P_1 P 3 + P 1 or K 3 + P 1 K_3 + P_1 K 3 + P 1 as an induced minor, and the conclusion follows from Lemma 3.3 (4.). This completes the proof.
Similarly to Observation 5.5 we note that the only case where the graphs in our construction are not 2-connected, i.e., where we use Lemma 3.3 (10.), is the case that H H H contains a 2-connected induced subgraph that contains P 2 + P 1 P_2 + P_1 P 2 + P 1 as an induced subgraph. Thus, we obtain the following refinement of Observation 5.5 .
Observation 6.2. Let H H H be a graph for which H H H -induced-minor-free graphs have unbounded induced matching treewidth. Induced matching treewidth in H H H -induced-minor-free graphs remains unbounded, even restricted to 2-connected graphs, unless H H H contains a 2-connected induced subgraph that contains P 2 + P 1 P_2 + P_1 P 2 + P 1 as an induced subgraph.
Restricting to 2-connected graphs
In this section we restrict the considered graphs even more, by assuming that they are 2-connected. Recall that this assumption does not change anything for tree-independence number (Lemma 2.2 ), nor for induced matching treewidth of graphs that exclude a fixed graph H H H as a subgraph, induced subgraph, a minor, a topological minor, or an induced subdivision. Again it appears that the remaining case, i.e., H H H -induced-minor-free graphs, behaves differently.
New bounded case
Figure 8. The graph K ^ 4 \widehat{K}_4 K 4 .
First, we exhibit one new graph whose exclusion bounds induced matching treewidth.
Theorem 7.1. Let G G G be a 2-connected graph that excludes K ^ 4 \widehat{K}_4 K 4 as an induced minor. Then tree-μ ( G ) ≤ 4 \mu(G) \leq4 μ ( G ) ≤ 4 .
To prove Theorem 7.1 , we use the following result of Błasiok, Kamiński, Raymond, and Trunck [7 Theorem 2] . Here, a prism is the complement of C 6 C_6 C 6 , i.e., two disjoint triangles joined with a perfect matching.
Theorem 7.2 (Błasiok, Kamiński, Raymond, and Trunck [7 ] ). Let G G G be a 2-connected graph that excludes K ^ 4 \widehat{K}_4 K 4 as an induced minor. Then one of the following holds:
G G G is K 4 K_4 K 4 -minor-free;
G G G is a subdivision of K 4 K_4 K 4 , of K 3 , 3 K_{3,3} K 3 , 3 , or of the prism;
V ( G ) V(G) V ( G ) can be partitioned to sets W , M ⊆ V ( G ) W, M \subseteq V(G) W , M ⊆ V ( G ) such that G [ W ] G[W] G [ W ] is a wheel on at most five vertices and G [ M ] G[M] G [ M ] is a complete multipartite graph;
V ( G ) V(G) V ( G ) can be partitioned to sets C , I ⊆ V ( G ) C, I \subseteq V(G) C , I ⊆ V ( G ) such that G [ C ] G[C] G [ C ] is a cycle, G [ I ] G[I] G [ I ] is edgeless, and every vertex of I I I has the same neighborhood on C C C .
Now let us proceed to the proof of Theorem 7.1
Proof of Theorem 7.1. We examine all cases given by Lemma 7.2.
Case 1. If G G G is K 4 K_4 K 4 -minor-free, then tw ( G ) ≤ 2 \operatorname{tw}(G) \leq2 tw ( G ) ≤ 2 [30 ] , and thus, tree-μ ( G ) ≤ 3 \mu(G) \leq3 μ ( G ) ≤ 3 .
Case 2. It is easy to verify that the treewidth of K 4 K_4 K 4 , K 3 , 3 K_{3,3} K 3 , 3 , or a prism is 3. Since subdividing edges does not increase treewidth, we conclude that tw ( G ) ≤ 3 \operatorname{tw}(G) \leq3 tw ( G ) ≤ 3 and thus, tree-μ ( G ) ≤ 4 \mu(G) \leq4 μ ( G ) ≤ 4 .
Case 3. Let F F F be an maximum-size induced matching in G G G . At most one edge of F F F might be contained in W W W and at most one edge might be contained in M M M . Moreover, there might be at most 2 edges of F F F with one endvertex in M M M and the other in W W W , as W W W does not contain a tree-element independent set. Consequently, ∣ F ∣ ≤ 4 |F| \leq4 ∣ F ∣ ≤ 4 , and thus, tree-μ ( G ) ≤ 4 \mu(G) \leq4 μ ( G ) ≤ 4 .
Case 4. Let T \mathcal{T} T be a tree decomposition of G [ C ] G[C] G [ C ] with width 2, and modify it by adding every vertex from I I I to every bag. It is straightforward to verify that this way we obtain a tree decomposition of G G G . Consider any bag X u X_u X u of this decomposition. Note that ∣ X u ∩ C ∣ ≤ 3 |X_u \cap C| \leq3 ∣ X u ∩ C ∣ ≤ 3 and since I I I is independent, the size of a largest induced matching touching X u X_u X u is at most 3. Consequently, tree-μ ( G ) ≤ 3 \mu(G) \leq3 μ ( G ) ≤ 3 .
This completes the proof.
Towards the dichotomy for 2-connected graphs
While we are not able to provide a full dichotomy in this case, we show the following almost dichotomy theorem.
Theorem 1.5. Let H H H be a graph. The class of H H H -induced-minor-free graphs, restricted to 2 2 2 -connected graphs, has bounded induced matching treewidth if H H H is an induced minor of one of the following graphs: K 2 , q K_{2,q} K 2 , q for some q q q , W 4 W_4 W 4 , K 5 − K_5^{-} K 5 − , a windmill, a matching, or K ^ 4 \widehat{K}_4 K 4 . If H H H is not one of these graphs, nor K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) for some fixed q q q , then 2 2 2 -connected H H H -induced-minor-free graphs have unbounded induced matching treewidth.
Proof. The bounded cases follow from the combination of Theorem 1.4 and Theorem 7.1 . So let us consider a graph H H H that is not one of these cases, nor K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) for some fixed q q q .
By Observation 6.2 we may assume that some 2 2 2 -connected induced subgraph of H H H contains P 1 + P 2 P_1 + P_2 P 1 + P 2 as an induced subgraph. Fix one copy of such subgraph H ′ H' H ′ and an induced copy of P 1 + P 2 P_1 + P_2 P 1 + P 2 in H ′ H' H ′ . Let a , b , c a,b,c a , b , c be the vertices of this copy, where b c ∈ E ( H ) bc \in E(H) b c ∈ E ( H ) .
As H H H is not a subgraph of a matching, there are vertices in V ( H ) ∖ { a , b , c } V(H) \setminus\{a,b,c\} V ( H ) ∖ { a , b , c } . Note that if there is v ∈ V ( G ) ∖ { a , b , c } v \in V(G) \setminus\{a,b,c\} v ∈ V ( G ) ∖ { a , b , c } that is adjacent to { b , c } \{b,c\} { b , c } but non-adjacent to a a a , then H H H contains either K 3 + P 1 K_3 + P_1 K 3 + P 1 or P 3 + P 1 P_3 + P_1 P 3 + P 1 and we are done by Lemma 3.3 (4.). Thus, every vertex in V ( H ) ∖ { a , b , c } V(H) \setminus\{a,b,c\} V ( H ) ∖ { a , b , c } that is adjacent to { b , c } \{b,c\} { b , c } is also adjacent to a a a .
Next, if there is v v v adjacent to, say b b b (and thus to a a a ), but not c c c , then H H H contains an induced P 4 P_4 P 4 and again we are done by Lemma 3.3 (4.).
Since H ′ H' H ′ is 2 2 2 -connected, there are two internally disjoint paths from a a a to { b , c } \{b,c\} { b , c } in H ′ H' H ′ and thus in H H H . Pick one such path, without loss of generality we can assume that it is induced. If the path has more than one internal vertex, then H H H contains an induced P 4 P_4 P 4 and we are done. So each of the two paths has exactly one internal vertex. Thus, there are two vertices x , y x,y x , y , both adjacent to all { a , b , c } \{a,b,c\} { a , b , c } .
If x y ∉ E ( H ) xy \notin E(H) x y ∈ / E ( H ) , then H [ { a , b , c , x , y } ] H[\{a,b,c,x,y\}] H [{ a , b , c , x , y }] is isomorphic to K 4 ′ K'_4 K 4 ′ , the graph obtained from K 4 K_4 K 4 by once subdividing an edge. Unboundedness of induced matching treewidth in H H H -induced-minor-free graphs follows from Lemma 3.3 (7.).
So, let us assume that x y ∈ E ( H ) xy \in E(H) x y ∈ E ( H ) . This means that the set { a , b , c , x , y } \{a,b,c,x,y\} { a , b , c , x , y } induces a copy of K ^ 4 \widehat{K}_4 K 4 in H H H .
If there is a vertex in V ( H ) ∖ { a , b , c , x , y } V(H) \setminus\{a,b,c,x,y\} V ( H ) ∖ { a , b , c , x , y } adjacent to a a a , then a , b , c a,b,c a , b , c are of degree at least 3 3 3 and they induce P 2 + P 1 P_2 + P_1 P 2 + P 1 in H H H , so we are done by Lemma 3.3 (9.).
So suppose that every vertex v ∈ V ( H ) ∖ { a , b , c , x , y } v \in V(H) \setminus\{a,b,c,x,y\} v ∈ V ( H ) ∖ { a , b , c , x , y } is non-adjacent to a a a . If there is v ∈ V ( H ) ∖ { a , b , c , x , y } v \in V(H) \setminus\{a,b,c,x,y\} v ∈ V ( H ) ∖ { a , b , c , x , y } that is adjacent to at least one of { b , c } \{b,c\} { b , c } , then H [ { v , b , c , a } ] H[\{v,b,c,a\}] H [{ v , b , c , a }] is either K 3 + K 1 K_3 + K_1 K 3 + K 1 or P 3 + K 1 P_3 + K_1 P 3 + K 1 ; in both cases we are done by Lemma 3.3 (4.).
Suppose there is a vertex v v v whose neighborhood in { b , c , a , x , y } \{b,c,a,x,y\} { b , c , a , x , y } is not { x , y } \{x,y\} { x , y } . As v v v is non-adjacent to a , b , c a,b,c a , b , c , by symmetry let us assume that either v v v has no neighbors in { b , c , a , x , y } \{b,c,a,x,y\} { b , c , a , x , y } , or its only neighbor in this set is x x x . But then, H [ { v , b , c , y } ] H[\{v,b,c,y\}] H [{ v , b , c , y }] is isomorphic to K 3 + K 1 K_3 + K_1 K 3 + K 1 and we are done by Lemma 3.3 (4.).
Consequently, every vertex v ∈ V ( H ) ∖ { a , b , c , x , y } v \in V(H) \setminus\{a,b,c,x,y\} v ∈ V ( H ) ∖ { a , b , c , x , y } is adjacent to both { x , y } \{x,y\} { x , y } and none of { b , c , a } \{b,c,a\} { b , c , a } . Finally, suppose that V ( H ) ∖ { a , b , c , x , y } V(H) \setminus\{a,b,c,x,y\} V ( H ) ∖ { a , b , c , x , y } is not independent, i.e., it contains two adjacent vertices v , v ′ v,v' v , v ′ . Then H [ { v , v ′ , x , a } ] H[\{v,v',x,a\}] H [{ v , v ′ , x , a }] is K 3 + K 1 K_3 + K_1 K 3 + K 1 and we are done by Lemma 3.3 (4.).
This means that H H H is isomorphic to K ^ 4 ( q ) \widehat{K}_4^{(q)} K 4 ( q ) for some q q q . This contradiction completes the proof. □
Algorithmic consequences
Boundedness of induced matching treewidth in a certain class of graphs allows us to solve numerous computational problems in polynomial time. Furthermore, for many problems we can reduce solving them to blocks of the input graph. Thus, we can make use of the positive statement in Theorem 1.5.
Finding large induced sparse subgraphs.
For a fixed integer w w w and fixed C M S O 2 \mathrm{CMSO}_2 CMSO 2 sentence1 ^{1} 1 ψ \psi ψ , by ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS we denote the problem where we are given a graph G G G with vertex-weights, and we want to find a maximum-weight subset X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) such that the graph induced by X X X has treewidth at most w w w and satisfies the sentence ψ \psi ψ , or report that no such set exists.
This formalism captures many classic computational problems, like Maximum Weight Independent Set (for w = 0 w=0 w = 0 and ψ \psi ψ being a sentence satisfied by all graphs), Feedback Vertex Set (by complementation, for w = 1 w=1 w = 1 and ψ \psi ψ being a sentence satisfied by all graphs).
By ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS∗ ^* ∗ we denote the generalization of ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS where vertices of the input graph might be colored using constant-size set of colors the formula ψ \psi ψ uses these colors. The following result was shown by Bodlaender, Fomin, Korhonen [8 ] (see the discussion in the conclusion).
Theorem 8.1 (Bodlaender, Fomin, Korhonen [8 ] ). For every w w w and ψ \psi ψ , the ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS∗ ^* ∗ problem can be solved in polynomial time on graphs of bounded induced matching treewidth.
Next, we show that in order to solve ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS∗ ^* ∗ in some hereditary class of graphs, it is sufficient to focus on 2-connected graphs from this class. The proof is a standard dynamic-programming process along block-cut trees.
Lemma 8.2. Let G \mathcal{G} G be a hereditary class of graphs (whose vertices are colored with a fixed number of colors) and let G 2 -conn \mathcal{G}_{2\text{-conn}} G 2 -conn be the family of 2-connected members of G \mathcal{G} G . If, for every fixed r r r and ψ \psi ψ , and every graph in G 2 -conn \mathcal{G}_{2\text{-conn}} G 2 -conn , the ( tw ≤ w , ψ ) (\operatorname{tw} \le w,\psi) ( tw ≤ w , ψ ) -MWIS∗ ^* ∗ problem can be solved in polynomial time, then it can also be solved in polynomial time for every graph in G \mathcal{G} G .
Proof. Let ℓ \ell ℓ denote the (fixed) number of colors appearing in graphs from C \mathcal{C} C . The algorithm will treat graphs with one distinguished vertex, which we will mark by an extra fresh color. Let q q q be the quantifier rank of ψ \psi ψ , i.e., the maximum number of nested quantifiers in it. It is well-known that there are only finitely many syntactically non-equivalent C M S O 2 \mathrm{CMSO}_2 CMSO 2 sentences over graphs (colored with ℓ + 1 \ell+1 ℓ + 1 colors) and of quantifier rank at most q q q . We denote this set of formulas by Φ q , ℓ + 1 \Phi_{q,\ell+1} Φ q , ℓ + 1 and note that there is a sentence ψ ′ \psi' ψ ′ in Φ q , ℓ + 1 \Phi_{q,\ell+1} Φ q , ℓ + 1 that is equivalent to ψ \psi ψ , in the sense that for every colored graph G G G , G G G satisfies ψ \psi ψ if and only if it satisfies ψ ′ \psi' ψ ′ . Since ψ \psi ψ is fixed, we may assume that Φ q , ℓ \Phi_{q,\ell} Φ q , ℓ and ψ ′ \psi' ψ ′ are also available to our algorithm.
Given a graph G ∈ G G \in\mathcal{G} G ∈ G colored with ℓ \ell ℓ colors, we assume that an arbitrary vertex is marked with an extra ( ℓ + 1 ) (\ell+1) ( ℓ + 1 ) -th color. Our goal is to prove the statement of the lemma for every sentence in Φ q , ℓ + 1 \Phi_{q,\ell+1} Φ q , ℓ + 1 , i.e., for each φ ∈ Φ q , ℓ + 1 \varphi\in\Phi_{q,\ell+1} φ ∈ Φ q , ℓ + 1 , find a maximum-weight subset X ⊆ V ( G ) X \subseteq V(G) X ⊆ V ( G ) such that the graph induced by X X X has treewidth at most w w w and satisfies φ \varphi φ , or report that no such set exists. We call such a set a maximum-weight solution for φ \varphi φ in G G G .
We first show how to deal with the case where G G G is connected and then we lift the argument to disconnected graphs. If G G G is 2-connected, we are done by the assumption. Thus, suppose otherwise and let T T T be the block-cut tree of G G G . For every non-root block b b b of T T T , we use c b c_b c b to denote the cutvertex between b b b and its parent block. We proceed by dynamic programming, using the structure of T T T in a bottom-up fashion.
Let us first establish some notation. For a node u u u of T T T , we denote by G u G_u G u the subgraph of G G G induced by the blocks/cutvertices in the subtree of T T T rooted at u u u . The distinguished vertex (colored by the extra color) of G u G_u G u is u u u if u u u is a cutvertex, or the cutvertex c b c_b c b , in case u u u is a block (in case b b b is the root block, we set c b c_b c b be an arbitrarily chosen vertex in b b b ).
For each node u u u of the block-cut tree and each formula φ ∈ Φ q , ℓ \varphi\in\Phi_{q,\ell} φ ∈ Φ q , ℓ , we will store an entry D φ ( u ) D_\varphi(u) D φ ( u ) consisting of a number p p p , corresponding to the weight of a maximum-weight solution S S S for φ \varphi φ in G u G_u G u , as well as the part of the set S S S in the block/cutvertex u u u and pointers to entries of the form D φ ′ ( u ′ ) D_{\varphi'}(u') D φ ′ ( u ′ ) , where φ ′ ∈ Φ q , ℓ \varphi' \in\Phi_{q,\ell} φ ′ ∈ Φ q , ℓ and u ′ u' u ′ is a child of u u u . The latter information will be used so as to recursively recover the maximum-weight solution for G u G_u G u . If a solution does not exist for certain φ \varphi φ , we set D φ ( u ) = ⊥ D_\varphi(u)=\bot D φ ( u ) = ⊥ .
We start from leaf blocks. Note that a leaf block b b b either consists of two vertices or it is 2-connected. Therefore, for each φ ∈ Φ q , ℓ \varphi\in\Phi_{q,\ell} φ ∈ Φ q , ℓ , we find a maximum-weight solution for φ \varphi φ in G b G_b G b (if such exists) by either using brute-force (in the former case), or calling the algorithm for 2-connected instances (in the latter case). In both cases, we store the corresponding information in D φ ( b ) D_\varphi(b) D φ ( b ) .
For a non-leaf block b b b for which we have already D φ ′ ( b ′ ) D_{\varphi'}(b') D φ ′ ( b ′ ) for every φ ′ ∈ Φ q , ℓ \varphi' \in\Phi_{q,\ell} φ ′ ∈ Φ q , ℓ and every child block b ′ b' b ′ of b b b , we proceed as follows. We use the following fact about CMSO2 _2 2 , following from the well-known “Feferman-Vaught” compositionality of types of CMSO2 _2 2 (see [21 ] ).
Fact: Let φ ∈ Φ q , ℓ + 1 \varphi\in\Phi_{q,\ell+1} φ ∈ Φ q , ℓ + 1 . There is a collection of pairs of sentences ( ψ 1 j , ψ 2 j ) j ∈ { 1 , … , p } ⊆ Φ q , ℓ + 1 × Φ q , ℓ + 1 (\psi^j_1,\psi^j_2)_{j\in\{1,\ldots,p\}} \subseteq\Phi_{q,\ell+1}\times\Phi_{q,\ell+1} ( ψ 1 j , ψ 2 j ) j ∈ { 1 , … , p } ⊆ Φ q , ℓ + 1 × Φ q , ℓ + 1 for a p ∈ N p \in\mathbb{N} p ∈ N depending only on q q q and ℓ \ell ℓ , such that the following holds. Let G 1 , G 2 G_1,G_2 G 1 , G 2 be two graphs (colored with ℓ \ell ℓ colors) with a distinguished vertex v 1 v_1 v 1 and v 2 v_2 v 2 in each of them respectively (colored with an ( ℓ + 1 ) (\ell+1) ( ℓ + 1 ) -th color). Also let G ^ \widehat{G} G be the graph obtained by taking the disjoint union of G 1 G_1 G 1 and G 2 G_2 G 2 and identifying v 1 v_1 v 1 with v 2 v_2 v 2 . Then for every set S ⊆ V ( G ^ ) S \subseteq V(\widehat{G}) S ⊆ V ( G ) , G ^ [ S ] \widehat{G}[S] G [ S ] satisfies φ \varphi φ if and only if there is a j ∈ { 1 , … , p } j \in\{1,\ldots,p\} j ∈ { 1 , … , p } and sets S 1 ⊆ V ( G 1 ) S_1 \subseteq V(G_1) S 1 ⊆ V ( G 1 ) and S 2 ⊆ V ( G 2 ) S_2 \subseteq V(G_2) S 2 ⊆ V ( G 2 ) such that for each i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } , G i [ S i ] G_i[S_i] G i [ S i ] satisfies ψ i j \psi^j_i ψ i j and S = S 1 ∪ S 2 S=S_1\cup S_2 S = S 1 ∪ S 2 . We call such a pair of formulas admissible for φ \varphi φ .
In the above fact, it is easy to observe that the treewidth of G ^ [ S ] \widehat{G}[S] G [ S ] is the maximum of the treewidth of G 1 [ S 1 ] G_1[S_1] G 1 [ S 1 ] and G 2 [ S 2 ] G_2[S_2] G 2 [ S 2 ] (since these two graphs have at most one vertex in common) and that every maximal-weight set S S S as above is the union of two maximal-weight sets S 1 S_1 S 1 and S 2 S_2 S 2 as above and vice versa.
We now apply the following intermediate step: we combine solutions of children blocks with a common cutvertex. Let c c c be a cutvertex of G G G that belongs to b b b and is not c b c_b c b and let b 1 , … , b m b_1,\ldots,b_m b 1 , … , b m be the children blocks of b b b that share the cutvertex c c c with b b b . We can compute D φ ( c ) D_\varphi(c) D φ ( c ) for every sentence φ ∈ Φ q , ℓ \varphi\in\Phi_{q,\ell} φ ∈ Φ q , ℓ , by iteratively applying the above fact and computing (in time O ( m ) O(m) O ( m ) ) a collection of m m m -tuples of admissible formulas ( φ 1 j , … , φ m j ) j ∈ { 1 , … , z } (\varphi^j_1,\ldots,\varphi^j_m)_{j\in\{1,\ldots,z\}} ( φ 1 j , … , φ m j ) j ∈ { 1 , … , z } , where z z z is a constant depending only on ℓ \ell ℓ and q q q , such that D φ ( c ) D_\varphi(c) D φ ( c ) is determined by D φ i j ( b i ) D_{\varphi^j_i}(b_i) D φ i j ( b i ) for i ∈ { 1 , … , m − 1 } i \in\{1,\ldots,m-1\} i ∈ { 1 , … , m − 1 } , for some choice of j ∈ { 1 , … , z } j \in\{1,\ldots,z\} j ∈ { 1 , … , z } maximizing the total weight of a solution.
We next proceed to compute D φ ( b ) D_\varphi(b) D φ ( b ) for every φ ∈ Φ q , ℓ + 1 \varphi\in\Phi_{q,\ell+1} φ ∈ Φ q , ℓ + 1 . Let c 1 , … , c m c_1,\ldots,c_m c 1 , … , c m be the cutvertices of G G G belonging to b b b that are not c b c_b c b . In the subgraph B B B of G G G induced by the vertices in the block b b b , we assign a fresh color to each cutvertex c i c_i c i , corresponding to the formulas φ ′ ∈ Φ q , ℓ \varphi' \in\Phi_{q,\ell} φ ′ ∈ Φ q , ℓ for which D φ ′ ( c i ) ≠ ⊥ D_{\varphi'}(c_i)\ne\bot D φ ′ ( c i ) = ⊥ . Note that the number of colors in this new colored (2-connected) graph, denoted by B ^ \widehat{B} B , is some constant ℓ ′ \ell' ℓ ′ depending only on q q q and ℓ \ell ℓ . Also, the iterative application of the above fact implies that there is
a sentence φ ~ \widetilde{\varphi} φ with quantifier rank at most q q q , on the vocabulary of ℓ ′ \ell' ℓ ′ colored graphs (which can be computed from φ \varphi φ in constant time) and
a collection of m m m -tuples of admissible formulas ( τ 1 j , … , τ m j ) j ∈ { 1 , … , z ′ } (\tau^j_1,\ldots,\tau^j_m)_{j\in\{1,\ldots,z'\}} ( τ 1 j , … , τ m j ) j ∈ { 1 , … , z ′ } , where z ′ z' z ′ is a constant depending only on ℓ \ell ℓ and q q q (which can be computed in O ( m ) O(m) O ( m ) time),
such that a maximum-weight solution for φ \varphi φ in G b G_b G b is obtained by the maximum-weight solution for φ ~ \tilde{\varphi} φ ~ in B ~ \tilde{B} B ~ expanded by the recovered solution from D τ 1 j ( c 1 ) , … , D τ m j ( c m ) D_{\tau_1^j}(c_1),\ldots,D_{\tau_m^j}(c_m) D τ 1 j ( c 1 ) , … , D τ m j ( c m ) for the tuple ( τ 1 j , … , τ m j ) (\tau_1^j,\ldots,\tau_m^j) ( τ 1 j , … , τ m j ) that maximizes the total weight. This concludes the description of recursive steps along the block-cut tree.
In case the input graph G G G is disconnected, we first solve the problem in each connected component by applying the above procedure to compute maximum-weight solutions for every formula in Φ q , ℓ + 1 \Phi_{q,\ell+1} Φ q , ℓ + 1 in every connected component. Then, by the (standard) analogue of the above fact applied for disjoint unions, this gives a maximum-weight solution in G G G for every formula in Φ q , ℓ + 1 \Phi_{q,\ell+1} Φ q , ℓ + 1 .
The overall running time is polynomial, provided that the algorithm for 2-connected instances runs in polynomial time.
Combining Theorem 8.1 , Lemma 8.2 , and Theorem 1.5, we obtain the following.
Corollary 8.3. For every r r r and ψ \psi ψ , the ( tw ≤ r , ψ ) (\operatorname{tw} \le r,\psi) ( tw ≤ r , ψ ) -MWIS* problem can be solved in polynomial time when restricted to graphs from the following classes:
K 2 , q K_{2,q} K 2 , q -induced-minor-free for any fixed q q q ,
W 4 W_4 W 4 -induced-minor-free,
K 5 − K_5^- K 5 − -induced-minor-free,
q q q -windmill-induced-minor-free for any fixed q q q ,
K 4 − K_4^- K 4 − -induced-minor-free.
Finding large induced H H H -colorable subgraphs.
A homomorphism from a graph G G G to a graph H H H is an edge-preserving mapping from V ( G ) V(G) V ( G ) to V ( H ) V(H) V ( H ) . For a fixed simple graph H H H , in the Max Induced H H H -Colorable Subgraph problem, the input consists of a triple ( G , L , rev ) (G,L,\operatorname{rev}) ( G , L , rev ) , where G G G is a graph, L : V ( G ) → 2 V ( H ) L:V(G)\to2^{V(H)} L : V ( G ) → 2 V ( H ) is a list function, and rev : V ( G ) × V ( H ) → Q \operatorname{rev}:V(G)\times V(H)\to\mathbb{Q} rev : V ( G ) × V ( H ) → Q is a revenue function. A feasible solution for such an instance is a pair ( X , φ ) (X,\varphi) ( X , φ ) , where X ⊆ V ( G ) X\subseteq V(G) X ⊆ V ( G ) and φ \varphi φ is a homomorphism from G [ X ] G[X] G [ X ] to H H H , respecting lists L L L . The revenue of such a solution is given by ∑ v ∈ X rev ( v , φ ( v ) ) \sum_{v\in X}\operatorname{rev}(v,\varphi(v)) ∑ v ∈ X rev ( v , φ ( v )) . Our goal is to find a solution of maximum possible revenue.
This formalism captures many classic problems line MWIS, Odd Cycle Transversal, or (List) k k k -Coloring. We remark that the lists L L L in the definition of the problem are somewhat redundant, as they can be modeled by adjusting the revenue function. However, we keep them as they make the description of the algorithm simpler. We emphasize that the list of a vertex might be empty, then it cannot be included in any feasible solution at all.
The work of Yolov [50 ] yields the following result.
Theorem 8.4 (Yolov [50 ] ). For every fixed simple graph H H H and every fixed integer k k k , Max Induced H H H -Colorable Subgraph can be solved in polynomial time when restricted to graphs of induced matching treewidth at most k k k .
The following lemma shows that, while solving Max Induced H H H -Colorable Subgraph, it is sufficient to focus on 2-connected graphs.
Lemma 8.5. Let G \mathcal{G} G be a hereditary class of graphs such that and let G 2 -con \mathcal{G}_{2\text{-con}} G 2 -con be the family of 2-connected members of G \mathcal{G} G . If, for every graph in G 2 -con \mathcal{G}_{2\text{-con}} G 2 -con , the Max Induced H H H -Colorable Subgraph problem can be solved in polynomial time, then it can also be solved in polynomial time for every graph in G \mathcal{G} G .
Proof. Consider an instance ( G , L , rev ) (G,L,\operatorname{rev}) ( G , L , rev ) of Max Induced H H H -Colorable Subgraph, where G ∈ G G\in\mathcal{G} G ∈ G . Note that without loss of generality we may assume that G G G is connected. If G G G is 2-connected, we are done by the assumption. Thus, suppose otherwise and let T T T be the block-cut tree of G G G . Let r r r be an arbitrary leaf; recall that r r r is a block. We treat T T T as rooted at r r r ; this defines parent-child relation between adjacent nodes. Let v r v_r v r be any vertex of r r r that does not belong to any other block (i.e., it is not the unique cutvertex that belongs to r r r ).
For a block node b ≠ r b \ne r b = r , let v b v_b v b be the cutvertex that is the parent of b b b in T T T , and the parent block is the parent of v b v_b v b in T T T . Analogously we define children blocks .
We proceed by dynamic programming, using the structure of T T T in a bottom-up fashion. For each block b b b , and each c ∈ L ( v b ) ∪ { ⊥ } c \in L(v_b) \cup\{\perp\} c ∈ L ( v b ) ∪ { ⊥ } , we will compute the maximum possible revenue Opt ( b , c ) \operatorname{Opt}(b,c) Opt ( b , c ) of a solution ( X , φ ) (X,\varphi) ( X , φ ) in the subgraph induced by the blocks in the subtree of T T T rooted at b b b such that
{ v b ∈ X and φ ( v b ) = c if c ∈ L ( v b ) , v b ∉ X if c = ⊥ . \begin{cases}
v_b \in X \text{ and } \varphi(v_b)=c & \text{if } c \in L(v_b),\\
v_b \notin X & \text{if } c=\perp.
\end{cases} { v b ∈ X and φ ( v b ) = c v b ∈ / X if c ∈ L ( v b ) , if c =⊥ .
Clearly, the optimum revenue is max c ∈ L ( v r ) ∪ { ⊥ } Opt ( r , c ) \max_{c \in L(v_r) \cup\{\perp\}} \operatorname{Opt}(r,c) max c ∈ L ( v r ) ∪ { ⊥ } Opt ( r , c ) .
Thus, fix some block b b b and some c ∈ L ( v b ) ∪ { ⊥ } c \in L(v_b) \cup\{\perp\} c ∈ L ( v b ) ∪ { ⊥ } . Suppose first that b b b is a leaf block. If b b b has two vertices, then Opt ( b , c ) \operatorname{Opt}(b,c) Opt ( b , c ) can be computed by brute force. Otherwise, the b b b is 2-connected and Opt ( b , c ) \operatorname{Opt}(b,c) Opt ( b , c ) can be computed by calling the algorithm for 2-connected instances with the list of v b v_b v b set to { c } \{c\} { c } if c ∈ L ( v b ) c \in L(v_b) c ∈ L ( v b ) or to ∅ \varnothing ∅ if c = ⊥ c=\perp c =⊥ .
Thus, suppose that b b b is not a leaf block and Opt ( b ′ , c ′ ) \operatorname{Opt}(b',c') Opt ( b ′ , c ′ ) is computed for every child block b ′ b' b ′ of b b b and every c ′ ∈ L ( v b ′ ) ∪ { ⊥ } c' \in L(v_{b'}) \cup\{\perp\} c ′ ∈ L ( v b ′ ) ∪ { ⊥ } . First, we restrict the list of v b v_b v b to c c c or set it to ∅ \varnothing ∅ , as before. Next, for every child block b ′ b' b ′ of b b b and every c ′ ∈ L ( v b ′ ) c' \in L(v_{b'}) c ′ ∈ L ( v b ′ ) , we set the revenue of the pair ( v b ′ , c ′ ) (v_{b'},c') ( v b ′ , c ′ ) to Opt ( b ′ , c ′ ) − Opt ( b ′ , ⊥ ) \operatorname{Opt}(b',c')-\operatorname{Opt}(b',\perp) Opt ( b ′ , c ′ ) − Opt ( b ′ , ⊥ ) . It is straightforward to verify that Opt ( b , c ) \operatorname{Opt}(b,c) Opt ( b , c ) is equal to the revenue of the optimum solution to this instance plus ∑ b ′ : child of b Opt ( b ′ , ⊥ ) \sum_{b':\ \text{child of }b} \operatorname{Opt}(b',\perp) ∑ b ′ : child of b Opt ( b ′ , ⊥ ) . The overall running time is polynomial, provided that the algorithm for 2-connected instances runs in polynomial time.
Combining Theorem 8.4 , Lemma 8.5 , and Theorem 1.5, we obtain the following.
Corollary 8.6. For every fixed graph H H H , the Max Induced H H H -Colorable Subgraph problem can be solved in polynomial time when restricted to graphs from the following classes:
K 2 , q K_{2,q} K 2 , q -induced-minor-free for any fixed q q q ,
W 4 W_4 W 4 -induced-minor-free,
K ^ 5 \widehat{K}_5 K 5 -induced-minor-free,
q q q -windmill-induced-minor-free for any fixed q q q ,
K ^ 4 \widehat{K}_4 K 4 -induced-minor-free.
Dominated balanced separators
Let G \mathcal{G} G be a graph class. We say that G \mathcal{G} G has k k k -dominated balanced separators if for every G ∈ G G \in\mathcal{G} G ∈ G and every weight function w : V ( G ) → R ≥ 0 w : V(G) \to\mathbb{R}_{\geq0} w : V ( G ) → R ≥ 0 , there is S ⊆ V ( G ) S \subseteq V(G) S ⊆ V ( G ) such that ∣ S ∣ ≤ k |S| \leq k ∣ S ∣ ≤ k and every component of G − N [ S ] G-N[S] G − N [ S ] has weight at most 1 2 w ( V ( G ) ) \frac{1}{2}w(V(G)) 2 1 w ( V ( G )) .
First, we show that graphs of bounded induced matching treewidth admit O ( 1 ) O(1) O ( 1 ) -dominated balanced separators.
Lemma 9.1. The class of graphs of induced matching treewidth at most t t t has 2 t 2t 2 t -dominated balanced separators.
Proof. Let G G G be a graph from G \mathcal{G} G , w : V ( G ) → R ≥ 0 w : V(G) \to\mathbb{R}_{\geq0} w : V ( G ) → R ≥ 0 be any weight function, and let T = ( T , { X u } u ∈ V ( T ) ) \mathcal{T} = (T, \{X_u\}_{u \in V(T)}) T = ( T , { X u } u ∈ V ( T ) ) be its tree decomposition with μ ( T , G ) ≤ t \mu(\mathcal{T},G) \leq t μ ( T , G ) ≤ t . We aim to find a set S S S with at most 2 t 2t 2 t vertices such that every component of G − N [ S ] G-N[S] G − N [ S ] has weight at most 1 2 w ( V ( G ) ) \frac{1}{2}w(V(G)) 2 1 w ( V ( G )) .
From the properties of tree decompositions it follows that there exists u ∈ V ( T ) u \in V(T) u ∈ V ( T ) such that every component of G − X u G-X_u G − X u has weight at most 1 2 w ( V ( G ) ) \frac{1}{2}w(V(G)) 2 1 w ( V ( G )) . Let M M M be a largest induced matching in G G G touching X u X_u X u ; clearly ∣ M ∣ ≤ t |M| \leq t ∣ M ∣ ≤ t and thus, ∣ V ( M ) ∣ ≤ 2 t |V(M)| \leq2t ∣ V ( M ) ∣ ≤ 2 t . Notice that in G − N [ V ( M ) ] G-N[V(M)] G − N [ V ( M )] there is no edge with at least one endpoint in X u X_u X u , as the existence of such an edge contradicts the maximality of M M M .
Thus, in G − N [ V ( M ) ] G-N[V(M)] G − N [ V ( M )] , there are components of two types: (i) components of G − X u G-X_u G − X u , and (ii) isolated vertices, all contained in X t X_t X t . Each component of type (i) has weight at most 1 2 w ( V ( G ) ) \frac{1}{2}w(V(G)) 2 1 w ( V ( G )) by the choice of X u X_u X u . If every component of type (ii) has weight at most 1 2 w ( V ( G ) ) \frac{1}{2}w(V(G)) 2 1 w ( V ( G )) , we can set S = V ( M ) S=V(M) S = V ( M ) . If this is not the case, there is a unique vertex v ∈ X t ∖ N [ V ( M ) ] v \in X_t \setminus N[V(M)] v ∈ X t ∖ N [ V ( M )] such that w ( v ) > 1 2 w ( V ( G ) ) w(v) > \frac{1}{2}w(V(G)) w ( v ) > 2 1 w ( V ( G )) . Now it is sufficient to choose S = { v } S=\{v\} S = { v } .
Next, we show that in order to obtain O ( 1 ) O(1) O ( 1 ) -dominated balanced separators in a hereditary class of graphs, it is actually sufficient that its 2 2 2 -connected members admit such separators.
Lemma 9.2. Let G \mathcal{G} G be a hereditary class of graphs such that, for every G ∈ G G \in\mathcal{G} G ∈ G , if G G G is 2 2 2 -connected, then it admits t t t -dominated balanced separators. Then G \mathcal{G} G has t t t -dominated balanced separators.
Proof. Let G ∈ G G \in\mathcal{G} G ∈ G and let w : V ( G ) → R ≥ 0 w : V(G) \to\mathbb{R}_{\geq0} w : V ( G ) → R ≥ 0 be any weight function. Note that we can also assume that G G G is connected – otherwise we can focus on finding the balanced separator in the component of largest weight.
Let B \mathcal{B} B be the set of blocks of G G G and C \mathcal{C} C be the set of cutvertices. Consider the block-cut-tree T B T_B T B of G G G : the vertex set of T B T_B T B is B ∪ C \mathcal{B} \cup\mathcal{C} B ∪ C and v b vb v b is an edge if b ∈ B b \in\mathcal{B} b ∈ B and v ∈ C v \in\mathcal{C} v ∈ C and v v v belongs to b b b .
Define the weight w B : V ( T B ) → R ≥ 0 w_B : V(T_B) \to\mathbb{R}_{\geq0} w B : V ( T B ) → R ≥ 0 as follows: for v ∈ C v \in\mathcal{C} v ∈ C , we set w B ( v ) = w ( v ) w_B(v)=w(v) w B ( v ) = w ( v ) , and for b ∈ B b \in\mathcal{B} b ∈ B we set w B ( b ) = ∑ v ∈ b ∖ C w ( v ) w_B(b)=\sum_{v \in b \setminus\mathcal{C}} w(v) w B ( b ) = ∑ v ∈ b ∖ C w ( v ) . Note that w ( V ( G ) ) = w B ( V ( T B ) ) w(V(G))=w_B(V(T_B)) w ( V ( G )) = w B ( V ( T B )) .
Since T B T_B T B is a tree, it has a node such that, once we remove it, every component has weight at most 1 2 w B ( V ( T B ) ) \frac{1}{2}w_B(V(T_B)) 2 1 w B ( V ( T B )) . If the separating node is a cutvertex or an edge, we pick these at most two vertices as a balanced separator in G G G . So assume that the separating node is a non-edge block, i.e., a maximal 2 2 2 -connected subgraph of G G G , call it G ′ G' G ′ . Clearly, G ′ G' G ′ is an induced subgraph of G G G , so in particular it belongs to G \mathcal{G} G .
Consider components of G − V ( G ′ ) G-V(G') G − V ( G ′ ) . Each of them is adjacent to exactly one vertex of G ′ G' G ′ (these vertices are cutvertices of G G G ). For a vertex v ∈ V ( G ′ ) v \in V(G') v ∈ V ( G ′ ) , let V v V_v V v denote the union of the vertex sets of all components of G − V ( G ′ ) G-V(G') G − V ( G ′ ) that are adjacent to v v v . Clearly, if v ∉ C v \notin\mathcal{C} v ∈ / C , then V v = ∅ V_v=\varnothing V v = ∅ .
Define a new weight function w ′ w' w ′ on G ′ G' G ′ as follows: for each v ∈ V ( G ′ ) v \in V(G') v ∈ V ( G ′ ) , we set w ′ ( v ) = w ( v ) + ∑ u ∈ V v w ( u ) w'(v)=w(v)+\sum_{u \in V_v}w(u) w ′ ( v ) = w ( v ) + ∑ u ∈ V v w ( u ) . Note that w ( V ( G ) ) = w ′ ( V ( G ′ ) ) w(V(G))=w'(V(G')) w ( V ( G )) = w ′ ( V ( G ′ )) .
By the assumption, there is S ⊆ V ( G ′ ) S \subseteq V(G') S ⊆ V ( G ′ ) such that ∣ S ∣ ≤ t |S| \leq t ∣ S ∣ ≤ t and every component of G ′ − N G ′ [ S ] G'-N_{G'}[S] G ′ − N G ′ [ S ] has weight (according to w ′ w' w ′ ) at most 1 2 w ′ ( V ( G ′ ) ) \frac{1}{2}w'(V(G')) 2 1 w ′ ( V ( G ′ )) .
We claim that N [ S ] N[S] N [ S ] is a balanced separator in G G G with respect to w w w . Consider a component C C C of G − N [ S ] G-N[S] G − N [ S ] . If C C C intersects V ( G ′ ) V(G') V ( G ′ ) , then w ( V ( C ) ) = w ′ ( V ( C ) ∩ V ( G ′ ) ) ≤ 1 2 w ( V ( G ′ ) ) = 1 2 w ( V ( G ) ) w(V(C))=w'(V(C)\cap V(G'))\le\frac{1}{2}w(V(G'))=\frac{1}{2}w(V(G)) w ( V ( C )) = w ′ ( V ( C ) ∩ V ( G ′ )) ≤ 2 1 w ( V ( G ′ )) = 2 1 w ( V ( G )) as the weight of vertices of V ( G ) ∖ V ( G ′ ) V(G)\setminus V(G') V ( G ) ∖ V ( G ′ ) was transferred to the vertices in V ( G ′ ) ∩ C V(G')\cap C V ( G ′ ) ∩ C .
If C C C does not intersect V ( G ′ ) V(G') V ( G ′ ) , then it is contained in one of the components of G − V ( G ′ ) G-V(G') G − V ( G ′ ) and, by the choice of G ′ G' G ′ , we have w ( V ( C ) ) ≤ 1 2 w ( V ( G ) ) w(V(C))\le\frac{1}{2}w(V(G)) w ( V ( C )) ≤ 2 1 w ( V ( G )) .
This completes the proof.
Combining Theorem 1.5 with Lemmas 9.1 and 9.2 yields the following corollary.
Corollary 1.9. The following classes of graphs admit t t t -dominated balanced separators, where t t t is a constant depending only on the class.
K 2 , q K_{2,q} K 2 , q -induced-minor-free for any fixed q q q ,
W 4 W_4 W 4 -induced-minor-free,
K 5 − K_5^{-} K 5 − -induced-minor-free,
q q q -windmill-induced-minor-free for any fixed q q q ,
K ‾ 4 \overline{K}_4 K 4 -induced-minor-free.
Conclusion
Let us summarize the paper with pointing out some directions for further research. First, we recall Conjecture 1.6 .
Conjecture 1.6. For every fixed q ≥ 1 q \ge1 q ≥ 1 , the class of 2 2 2 -connected K ^ 4 ( q ) \widehat{\mathcal{K}}_4^{(q)} K 4 ( q ) -induced-minor-free graphs has bounded induced matching treewidth.
Furthermore, we believe that the approach of preprocessing the graph and then asking for boundedness of some parameter is promising and not much explored [13 , 24 , 35 ] . Possible preprocessing steps might include decomposing on clique cutsets [49 ] , applying modular decomposition [37 ] or contracting degree-2 2 2 vertices.
Finally, let us mention some further generalization of induced matching treewidth, introduced recently by Nikabadi and Rzążewski [45 ] , who were in turn inspired by a question of Bodlaender, Fomin, and Korhonen [8 ] . For a family H \mathcal{H} H of graphs, the induced H \mathcal{H} H -packing treewidth is a tree-decomposition-based parameter where, for each bag of the decomposition, we measure the number of disjoint and pairwise nonadjacent copies of graphs from H \mathcal{H} H , each intersecting the bag. Note that induced { P 1 } \{P_1\} { P 1 } -packing treewidth is equivalent to tree-independence number, while induced { P 2 } \{P_2\} { P 2 } -packing treewidth is equivalent to induced matching treewidth. Let us look at this family of parameters through the lens of questions (Q1), (Q2), and (Q3) stated in the introduction. We focus on the first open case, i.e., H = { P 3 } \mathcal{H} = \{P_3\} H = { P 3 } .
Question (Q1) was partially answered as boundedness of induced packing yields quasipolynomial-time algorithms for some problems including MWIS, List 3-Coloring, and Odd Cycle Transversal [45 ] . Question (Q2) is answered as a simple argument allows us to reduce the problem to computing a tree decomposition of small independence number in an auxiliary graph, which yields an XP-approximation algorithm for induced { P 3 } \{P_3\} { P 3 } -packing treewidth. However, (Q3) is wide open. In particular, it would be interesting to investigate which classes (say, defined by a forbidding a single graph) have bounded induced { P 3 } \{P_3\} { P 3 } -packing treewidth.