# Treewidth versus clique number. III. Tree-independence number of graphs with
a forbidden structure

Clément Dallard1, Martin Milanič2,3, Kenny Štorgel2,4 1 LIP, École Normale
Supérieure de Lyon, France
2 FAMNIT, University of Primorska, Koper, Slovenia
3 IAM, University of Primorska, Koper, Slovenia
4 Faculty of Information Studies in Novo mesto, Slovenia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We continue the study of $(\mathrm{tw},\omega)$-bounded graph classes, that
is, hereditary graph classes in which the treewidth can only be large due to
the presence of a large clique, with the goal of understanding the extent to
which this property has useful algorithmic implications for the Maximum
Independent Set and related problems.

In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth
versus clique number. II. Tree-independence number], we introduced the _tree-
independence number_ , a min-max graph invariant related to tree
decompositions. Bounded tree-independence number implies both
$(\mathrm{tw},\omega)$-boundedness and the existence of a polynomial-time
algorithm for the Maximum Weight Independent Packing problem, provided that
the input graph is given together with a tree decomposition with bounded
independence number. In particular, this implies polynomial-time solvability
of the Maximum Weight Independent Set problem.

In this paper, we consider six graph containment relations—the subgraph,
topological minor, and minor relations, as well as their induced variants—and
for each of them characterize the graphs $H$ for which any graph excluding $H$
with respect to the relation admits a tree decomposition with bounded
independence number. The induced minor relation is of particular interest: we
show that excluding either a $K_{5}$ minus an edge or the $4$-wheel implies
the existence of a tree decomposition in which every bag is a clique plus at
most $3$ vertices, while excluding a complete bipartite graph $K_{2,q}$
implies the existence of a tree decomposition with independence number at most
$2(q-1)$.

These results are obtained using a variety of tools, including $\ell$-refined
tree decompositions, SPQR trees, and potential maximal cliques, and actually
show that in the bounded cases identified in this work, one can also compute
tree decompositions with bounded independence number efficiently. Applying the
algorithmic framework provided by the previous paper in the series leads to
polynomial-time algorithms for the Maximum Weight Independent Set problem in
an infinite family of graph classes, each of which properly contains the class
of chordal graphs. In particular, these results apply to the class of
$1$-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky,
Gurvich, Milanič, and Servatius from 2019.

###### Contents

  1. 1 Introduction
    1. 1.1 Background
    2. 1.2 Our results
      1. 1.2.1 Bounding the tree-independence number
      2. 1.2.2 Algorithmic implications
    3. 1.3 Overview of our methodology
    4. 1.4 Organization of the paper
  2. 2 Preliminaries
    1. 2.1 General notations and definitions
    2. 2.2 On the tree-independence number
  3. 3 $K_{2,q}$-induced-minor-free graphs
  4. 4 Tree-independence number and SPQR trees
    1. 4.1 Reducing the problem to blocks
    2. 4.2 Preliminaries on SPQR trees
    3. 4.3 Reducing the problem to triconnected components
  5. 5 $W_{4}$-induced-minor-free graphs
  6. 6 $K_{5}^{-}$-induced-minor-free graphs
  7. 7 The dichotomies
  8. 8 Concluding remarks

##  1 Introduction

###  1.1 Background

Treewidth is an important and well-studied graph invariant, with both
structural and algorithmic applications. The presence of a large clique
implies large treewidth and it is an interesting question for which graph
classes this sufficient condition is also necessary. A graph class
$\mathcal{G}$ is said to be _$(\mathrm{tw},\omega)$ -bounded_ if it admits a
_$(\mathrm{tw},\omega)$ -binding function_, that is, a function $f$ such that
the treewidth of any graph $G\in\mathcal{G}$ is at most $f(\omega(G))$, where
$\omega(G)$ is the clique number of $G$, and the same holds for all induced
subgraphs of $G$. The chromatic number of any graph is bounded from above by
its treewidth plus one, and hence every $(\mathrm{tw},\omega)$-bounded graph
class is $\chi$-bounded, that is, the chromatic number of the graphs in the
class and all their induced subgraphs is bounded from above by some function
of the clique number (see, e.g., [55]). Similarly as $\chi$-boundedness
generalizes perfection, $(\mathrm{tw},\omega)$-boundedness generalizes
chordality. Besides the class of chordal graphs, further examples of
$(\mathrm{tw},\omega)$-bounded graph classes include the class of circular-arc
graphs, as well as several more general families of graph classes studied in
the literature (see [78, 15, 13, 28, 25, 26, 46, 27, 79]). This is the third
paper of a series of papers on $(\mathrm{tw},\omega)$-bounded graph classes,
initiated in [37] (see also [35]) and continued in [36].

It is known that $(\mathrm{tw},\omega)$-bounded graph classes enjoy good
algorithmic properties related to clique and coloring problems, in some cases
under the mere assumption that the class admits a computable
$(\mathrm{tw},\omega)$-binding function (see [28, 27, 35, 37, 36]). This
motivates the question of whether $(\mathrm{tw},\omega)$-boundedness has any
other algorithmic implications, in particular, for problems related to
independent sets. A partial answer to this question was given in the second
paper of the series [36] where we identified a sufficient condition for
$(\mathrm{tw},\omega)$-bounded graph classes to admit a polynomial-time
algorithm for the Max Weight Independent Packing problem and, as a
consequence, for the weighted variants of the Independent Set and Induced
Matching problems. (We refer to Section 2 for precise definitions.) These
results were obtained using the notion of tree-independence number, a newly
introduced graph invariant related to tree decompositions.

The _independence number_ of a tree decomposition of a graph $G$ is defined as
the maximum independence number of a subgraph of $G$ induced by a bag of the
decomposition. The _tree-independence number_ of a graph $G$ is the minimum
independence number over all tree decompositions of $G$. It follows from
Ramsey’s theorem that every graph class with bounded tree-independence number
is $(\mathrm{tw},\omega)$-bounded, even with a polynomial binding function; in
particular, every graph class with bounded tree-independence number is
polynomially $\chi$-bounded. It was shown in [36] that the Max Weight
Independent Packing problem can be solved in polynomial time provided that the
input graph is given along with a tree decomposition with bounded independence
number. Thus, boundedness of the tree-independence number is an
algorithmically useful refinement of $(\mathrm{tw},\omega)$-boundedness that
still captures a wide variety of families of graph classes, including graph
classes of bounded treewidth, graph classes of bounded independence number,
intersection graphs of connected subgraphs of graphs with bounded treewidth,
and graphs in which all minimal separators are of bounded size (see [36] for
details).

###  1.2 Our results

In this paper, we identify new graph classes with bounded tree-independence
number and show that in each of these cases the general algorithmic result
from [36] can be applied.

####  1.2.1 Bounding the tree-independence number

We consider six graph containment relations—the subgraph, topological minor,
and minor relations, as well as their induced variants—and for each of them
characterize the graphs $H$ for which any graph excluding $H$ with respect to
the relation admits a tree decomposition with bounded independence number.
These results build on and refine the analogous characterizations for
$(\mathrm{tw},\omega)$-boundedness from [37], and show that in all these
cases, $(\mathrm{tw},\omega)$-boundedness is actually equivalent to bounded
tree-independence number.

Instead of stating the exact characterizations here (they can be found in
Theorem 7.3), let us summarize their main features. Because of the Grid-Minor
Theorem, for any graph class closed under subgraphs (and hence also for any
graph class closed under topological minors or minors), bounded tree-
independence number is equivalent to bounded treewidth. When a single graph is
excluded as an induced subgraph or as an induced topological minor, bounded
tree-independence number is equivalent to bounded independence number, except
for a small number of well-structured graph classes, such as disjoint unions
of complete graphs, chordal graphs, or block-cactus graphs. The most
interesting case is when a single graph is excluded as an induced minor. Given
two graphs $G$ and $H$, we say that $G$ is _$H$ -induced-minor-free_ if it is
not possible to obtain from $G$ a graph isomorphic to $H$ by a sequence of
vertex deletions and edge contractions. We show that the class of $H$-induced-
minor-free graphs has bounded tree-independence number if and only if $H$ is
an induced minor of $W_{4}$ (a wheel with four spokes, that is, the graph
obtained from the $4$-vertex cycle by adding to it a universal vertex), of
$K_{5}^{-}$ (the complete $5$-vertex graph minus an edge), or of some complete
bipartite graph $K_{2,q}$. In fact, we not only prove that these graph classes
have bounded tree-independence number, but also show that, given a graph in
such a class, we can compute a tree decomposition with bounded independence
number in polynomial time.

As a key ingredient of our approach, we develop a generic framework for graph
classes closed under taking induced topological minors that allows us, roughly
speaking, to reduce the problem of computing a tree decomposition with bounded
independence number satisfying some additional requirements to the case of
$3$-connected graphs, in linear time (see Theorem 4.16). We then apply our
framework to the classes of $K_{5}^{-}$\- and $W_{4}$-induced-minor-free
graphs, for which we obtain a particularly good structural understanding: any
such graph admits a tree decomposition in which each bag is a clique plus at
most three vertices, resembling a well-known characterization of chordal
graphs (where each bag is a clique). This property gives rise to conceptually
simpler proofs of $(\mathrm{tw},\omega)$-boundedness of these two graph
classes compared to the proofs from [35, 37], which rely on graph minors
theory; it also implies that the tree-independence number is bounded by $4$
and is likely to have further algorithmic applications besides the polynomial-
time solvability of the Max Weight Independent Packing problem. Furthermore,
we claimed in [37] that all the identified $(\mathrm{tw},\omega)$-bounded
graph classes have a polynomial binding function, but left out the proofs for
the case of $W_{4}$\- and $K_{5}^{-}$-induced-minor-free graphs, explaining
that we would prove these results in a future publication. This “future
publication” refers to the present work, where the aforementioned property
implies the existence of a linear $(\mathrm{tw},\omega)$-binding function for
these two classes. In particular, the classes of $W_{4}$\- and
$K_{5}^{-}$-induced-minor-free graphs are linearly $\chi$-bounded. Prior to
this work, it was not even known whether these classes are polynomially
$\chi$-bounded.111Esperet asked whether every $\chi$-bounded graph class
admits a polynomial $\chi$-binding function (see [44]). Esperet’s question was
recently answered in the negative by Briański, Davies, and Walczak [20].

Let us note that the class of $W_{4}$-induced-minor-free graphs generalizes
not only the class of chordal graphs but, more generally, also the class of
universally signable graphs studied by Conforti, Cornuéjols, Kapoor, Ajai, and
Vušković [32] (as can be seen using [32, Corollary 4.2]). Furthermore, the
class of graphs excluding both $W_{4}$ and $K_{5}^{-}$ as an induced minor was
studied in 2015 by Lewchalermvongs in his Ph.D. thesis [65]; this class of
graphs generalizes the class of graphs of separability at most $2$ studied by
Cicalese and Milanič [31].

The classes of $K_{2,q}$-induced-minor-free graphs, for all $q\geq 3$, form an
infinite family of graph classes that strictly generalize the class of chordal
graphs and that have bounded tree-independence number. It is an easy
observation that a graph is $K_{2,q}$-induced-minor-free if and only if no
independent set of size $q$ is contained in a minimal separator. Hence, by
showing that the tree-independence number is bounded in such classes, we
generalize the fact that the classes of graphs with minimal separators of
bounded size are $(\mathrm{tw},\omega)$-bounded [79].

####  1.2.2 Algorithmic implications

Our results generalize a number of results in the literature and answer
several questions from the literature. We now discuss these connections.

Most notably, we identify new graph classes where the Max Weight Independent
Set problem is solvable in polynomial time. This problem is one of the most
studied graph optimization problems, and is known to be (strongly) NP-hard in
general [62] and NP-hard to approximate on $n$-vertex graphs to within a
factor of $n^{1-\epsilon}$ for every $\epsilon>0$ [90]. Several recent results
consider the problem in restricted graph classes [29, 30, 18, 53, 1, 24, 49,
72, 50].

Before explaining the implications of our results and the results from [36]
for the Max Weight Independent Set problem, let us put them in context with
related work. While the complexity of the Max Weight Independent Set problem
was traditionally studied in _hereditary_ graph classes, that is, graph
classes closed under induced subgraphs, many of the graph classes for which
the complexity of the problem has been determined are also closed under the
induced topological minor, induced minor, or even the minor relation. For
example:

  * •

The Max Weight Independent Set problem is NP-hard in the class of planar
graphs [48], which is exactly the class of graphs with no $K_{5}$ and
$K_{3,3}$ as a minor.

  * •

The Max Weight Independent Set problem is solvable in polynomial time in the
class of graphs containing no induced $6$-vertex path [53]. For every positive
integer $p$, any class of graphs containing no induced $p$-vertex path is
closed under induced minors (in fact, it is exactly the class of graphs
excluding the $p$-vertex path as an induced minor).

  * •

The Max Weight Independent Set problem is solvable in polynomial time in the
class of graphs containing no induced cycles of length at least $5$ [1]. For
every positive integer $p$, any class of graphs containing no induced cycles
of length at least $p$ is also closed under induced minors (in fact, it is
exactly the class of graphs excluding the $p$-vertex cycle as an induced
minor).

  * •

The Max Weight Independent Set problem is solvable in polynomial time in the
class of wheel-free graphs excluding all induced subdivisions of the $K_{4}$
[68]. This class of graphs is closed under induced topological minors.

These results motivate the study of the complexity of the Max Weight
Independent Set problem in classes of graphs that are closed under minors,
induced minors, or induced topological minors. The simplest way to define such
a class is to exclude a single graph $H$ with respect to the considered
relation. If a non-planar graph $H$ is excluded, then the Max Weight
Independent Set problem is NP-hard in the class of $H$-minor-free graphs,
since this class contains the class of all planar graphs and the Max Weight
Independent Set problem is known to be NP-hard in the class of planar graphs
[48]. If a planar graph $H$ is excluded as a minor, then the treewidth is
bounded and the Max Weight Independent Set problem is solvable in linear time.
Thus, the interesting cases are when a planar graph $H$ is excluded with
respect to the induced minor or the induced topological minor relation. The
resulting graph classes are equivalent for the two relations if $H$ is a path
or a cycle. The case when $H$ is the $k$-vertex path $P_{k}$ is polynomial-
time solvable for $k\leq 6$ [53] and open for all $k\geq 7$; however, quasi-
polynomial-time algorithms are known for every fixed $k$, as shown by Gartland
and Lokshtanov [49] and Pilipczuk, Pilipczuk, and Rzążewski [72]. These
results were recently strengthened by Gartland, Lokshtanov, Pilipczuk,
Pilipczuk, and Rzażewski [50] to the case when $H$ is the $k$-vertex cycle,
which is polynomial-time solvable for $k\leq 5$ [1] and open for all $k\geq
6$.

Recall that for all the graph classes with bounded tree-independence number
considered in this work we are able to _efficiently_ compute a tree
decomposition with bounded independence number. Combined with the results from
[36], our results lead to a new infinite family of graph classes in which the
Max Weight Independent Set problem is solvable in polynomial time. This result
is summarized in the following theorem, which combines Corollaries 5.9, 6.9,
and 3.15.

######  Theorem 1.1.

The Max Weight Independent Set problem is solvable in polynomial time in the
class of $H$-induced-minor-free graphs whenever $H$ is either $W_{4}$,
$K_{5}^{-}$, or a complete bipartite graph $K_{2,q}$ for some positive integer
$q$.

In [37], we showed that the Max Weight Independent Set problem can be solved
in polynomial time in all the identified $(\mathrm{tw},\omega)$-bounded graph
classes, except possibly for the case when $H$ is excluded with respect to the
induced minor relation and $H$ is isomorphic to either $W_{4}$, $K_{5}^{-}$,
or $K_{2,q}$ where $q\geq 3$. In particular, we established polynomial-time
solvability of the Max Weight Independent Set problem in the classes of
$H$-induced-minor-free graphs when $H$ is either the diamond (that is, $K_{4}$
minus an edge) or the complete bipartite graph $K_{1,q}$ for some positive
integer $q$. The results given by Theorem 1.1 generalize these results and
establish polynomial-time solvability of the Max Weight Independent Set
problem for all the cases left open in [37].

Theorem 1.1 provides an infinite family of planar graphs $H$ such that
excluding $H$ as an induced minor results in polynomial-time solvability of
the Max Weight Independent Set problem. To further appreciate the result of
Theorem 1.1, note that the only graph class containing all classes of
$K_{2,q}$-induced-minor-free graphs is the class of all graphs. Furthermore,
unless $H\in\\{K_{2,1},K_{5}^{-}\\}$, each of the graph classes listed in
Theorem 1.1 generalizes the class of chordal graphs—for which a polynomial-
time algorithm for Max Weight Independent Set was given in 1976 by Frank
[47]—and, with the exception of the case $H=K_{2,2}$, all these
generalizations are proper. Additionally, the fact that Max Weight Independent
Set is solvable in polynomial time in the class of $K_{2,3}$-induced-minor-
free graphs implies a polynomial-time solution for Max Weight Independent Set
in the class of $1$-perfectly orientable graphs, which is a common
generalization of the classes of chordal graphs and circular-arc graphs. This
answers a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius
posed in [5, 6]. The analogous question for $k$-Coloring was answered in our
previous works [35, 37].

We in fact obtain results analogous to Theorem 1.1 but for the Max Weight
Independent Packing problem (Theorems 5.11, 6.11, and 3.14). These results
generalize the polynomial-time solvability of the Max Induced Matching problem
in the class of chordal graphs [21], of the $k$-Separator problem (for fixed
$k$) in the class of interval graphs [8], and of the Independent
$\mathcal{F}$-Packing problem in the class of chordal graphs [22].

###  1.3 Overview of our methodology

We develop two significantly different general approaches for establishing
boundedness of the tree-independence number for a given graph class, and for
computing tree decompositions of bounded independence number for graphs in the
class. Given a graph class $\mathcal{G}$, we say that (boundedness of the)
tree-independence number is _efficiently witnessed_ in $\mathcal{G}$ if there
exists a polynomial-time algorithm to compute a tree decomposition with
bounded independence number for every graph in $\mathcal{G}$.

First approach: removing small cutsets. We make use of two known and linear-
time computable decompositions of graphs into biconnected and triconnected
components: the decompositions based on the block-cutpoint trees and the SPQR
trees, respectively. Using these decompositions, we can reduce the problem to
connected graphs with no cutsets of size one and two, respectively.

The fact that block-cutpoint trees are useful for the tree-independence number
follows from a more general observation that the tree-independence number is
“well-behaved” with respect to clique cutsets, in the sense that it is bounded
in any graph class closed under induced subgraphs in which graphs _without
clique cutsets_ have bounded tree-independence number (see [36, Proposition
3.10] and its refinement, [36, Proposition 4.6], stated in this work as
Proposition 2.10). Indeed, the same approach shows that the tree-independence
number is bounded in any graph class closed under induced subgraphs in which
graphs _without cut vertices_ have bounded tree-independence number.
Furthermore, both reductions are algorithmically efficient. When the graph is
decomposed along a clique cutset into smaller subgraphs, if a tree
decomposition with bounded independence number is provided for each subgraph,
then one can combine these tree decompositions into a tree decomposition with
bounded tree independence number for the entire graph. In the case of block-
cutpoint trees, the whole procedure can be implemented in linear time
(Proposition 4.1).

Getting rid of cutsets of size two using SPQR trees can also be performed in
linear time but is significantly more involved. Besides, it cannot always be
applied, since it is not necessarily the case that bounded tree-independence
number of the “triconnected components” of the graph implies boundedness of
the tree-independence number of the whole graph (see Example 4.8). Additional
technical conditions need to be met. We postpone the precise statement of the
result to Section 4 (see Theorem 4.16), but let us remark that the result can
be applied within graph classes closed under induced topological minors.

We then use this combined decomposition approach and a classical result due to
Tutte [82] that any $3$-connected graph with at least $5$ vertices contains an
edge whose contraction results in a $3$-connected graph to show that the tree-
independence number of any graph that does not contain an induced minor
isomorphic to $W_{4}$ or to $K_{5}^{-}$ is bounded by $4$ (see Corollaries 5.7
and 6.7, respectively). Furthermore, we give a linear-time algorithm to
compute a tree decomposition with independence number at most $4$ of any such
graph. In the case of $W_{4}$-induced-minor-free graphs, particular tree
decompositions of chordal graphs known as _clique trees_ (see [14]) also play
an important role, along with moplex elimination orderings, and known linear-
time algorithms to compute them.

Second approach: potential maximal cliques and minimal triangulations. The
second approach relies on the notions of _potential maximal cliques_ and
_minimal triangulations_. Roughly speaking, a minimal triangulation of a graph
$G$ is a chordal graph obtained from $G$ by adding to it an inclusion-minimal
set of edges, and a potential maximal clique is a set of vertices that forms a
maximal clique in some minimal triangulation (see, e.g., [57]). By combining
known results on minimal triangulations and chordal graphs, one can compute in
polynomial time a tree decomposition of a given graph $G$ in which each bag is
a potential maximal clique. It follows that the tree-independence number is
bounded and efficiently witnessed in any class of graphs in which there is a
bound on the maximum size of an independent set contained in a potential
maximal clique.

To apply this observation to particular graph classes, we connect it with
another classical concept in algorithmic graph theory, that of a _minimal
separator_. A minimal separator in a graph is an inclusion-minimal set of
vertices separating some fixed non-adjacent vertex pair. Building on the work
of Bouchitté and Todinca [17], we show that in every graph, every potential
maximal clique is either a clique or is contained in the union of two minimal
separators (Theorem 3.8). Thus, the tree-independence number is bounded and
efficiently witnessed in any class of graphs for which there is a bound on the
maximum size of an independent set contained in a minimal separator. This last
condition is easily seen to be equivalent to the requirement that the graph is
$K_{2,q}$-induced-minor-free for some fixed integer $q$ and leads to
polynomial-time algorithms for computing tree decompositions with bounded
independence number in any such graph class.

###  1.4 Organization of the paper

In Section 2, we provide the necessary preliminaries. Then, in Section 3, we
prove that for every positive integer $q$, the class of $K_{2,q}$-induced-
minor-free graphs has bounded and efficiently witnessed tree-independence
number. A polynomial-time algorithm for the Max Weight Independent Set problem
in the class of $1$-perfectly orientable graphs is also derived in that
section. In Section 4, we develop a sufficient condition for bounded and
efficiently witnessed tree-independence number for graph classes closed under
induced topological minors. This general result is then applied to the
specific cases of $W_{4}$-induced-minor-free graphs and $K_{5}^{-}$-induced-
minor-free graphs in Sections 5 and 6, respectively. In Section 7, we consider
the six aforementioned graph containment relations and for each of them
characterize the graphs $H$ for which the class of graphs excluding $H$ has
bounded tree-independence number. We conclude the paper in Section 8.

##  2 Preliminaries

###  2.1 General notations and definitions

Throughout the paper, we denote by $\mathbb{Z}_{+}$ the set of nonnegative
integers and by $\mathbb{Q}_{+}$ the set of nonnegative rational numbers. We
assume familiarity with the basic concepts in graph theory as used, e.g., by
West [86]. We denote the vertex set and the edge set of a graph $G$ by $V(G)$
and $E(G)$, respectively. A graph is _null_ if it has no vertices. The
_neighborhood_ of a vertex $v$ in $G$, which corresponds to the set of
vertices adjacent to $v$ in $G$, is denoted by $N_{G}(v)$. The _closed
neighborhood_ of $v$ is the set $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. These concepts
are extended to sets $X\subseteq V(G)$ so that $N_{G}[X]$ is defined as the
union of all closed neighborhoods of vertices in $X$, and $N_{G}(X)$ is
defined as the set $N_{G}[X]\setminus X$. The _degree_ of $v$, denoted by
$d_{G}(v)$, is the cardinality of the set $N_{G}(v)$. When there is no
ambiguity, we may omit the subscript $G$ in the notations of the degree, and
open and closed neighborhoods, and thus simply write $d(v)$, $N(v)$, and
$N[v]$, respectively. Given a set $X\subseteq V(G)$, we denote by $G-X$ the
graph obtained from $G$ after deleting all the vertices in $X$. Similarly,
given a vertex $v\in V(G)$, we denote by $G-v$ the graph obtained from $G$
after deleting $v$. Given two disjoint vertex sets $A,B\subseteq V(G)$, we say
that $A$ is _anticomplete_ to $B$ (and vice versa) if no vertex in $A$ is
adjacent to a vertex in $B$. The fact that two graphs $G$ and $H$ are
isomorphic to each other is denoted by $G\cong H$. The _complement_ of a graph
$G$ is the graph, denoted by $\overline{G}$, with vertex set $V(G)$, in which
two distinct vertices are adjacent if and only if they are non-adjacent in
$G$. For a positive integer $n$, we denote the $n$-vertex complete graph,
path, and cycle by $K_{n}$, $P_{n}$, and $C_{n}$, respectively. Similarly, for
$n\geq 2$ we denote by $K_{n}^{-}$ the graph obtained from the complete graph
$K_{n}$ by deleting an edge, and for positive integers $m$ and $n$ we denote
by $K_{m,n}$ the complete bipartite graph with parts of sizes $m$ and $n$. The
graph $K_{4}^{-}$ is also called the _diamond_. For $n\geq 4$, we denote by
$W_{n}$ the _$n$ -wheel_, that is, the graph obtained from the graph $C_{n}$
by adding to it a universal vertex. A _wheel_ is a graph isomorphic to $W_{n}$
for some $n\geq 4$.

An _independent set_ in a graph $G$ is a set of pairwise non-adjacent
vertices, and a _clique_ is a set of pairwise adjacent vertices. Given a graph
$G$ and a weight function $w:V(G)\to\mathbb{Q}_{+}$, the Max Weight
Independent Set problem asks to find an independent set $I$ in $G$ of maximum
possible weight $w(I)$, where $w(I)=\sum_{x\in I}w(x)$. The _independence
number_ of $G$, denoted by $\alpha(G)$, is the maximum size of an independent
set in $G$. The _clique number_ of $G$, denoted by $\omega(G)$, is the maximum
size of a clique in $G$. Given a positive integer $k$, a graph $G$ is _$k$
-connected_ if it has at least $k+1$ vertices and for every set $X\subseteq
V(G)$ with $|X|<k$, the graph $G-X$ is connected. Given a graph $G$, a set
$X\subseteq V(G)$ is a _cutset_ in $G$ if $G-X$ is disconnected; a _$k$
-cutset_ is a cutset of cardinality $k$. (Note that if $G$ is disconnected,
the above definition allows the number of components of $G-X$ to be the same
as the number of components of $G$.) A _cut-vertex_ in a connected graph $G$
is a vertex $v$ such that $G-v$ is disconnected. A _cut-partition_ in a graph
$G$ is a triple $(A,B,C)$ such that $A\cup B\cup C=V(G)$, $A\neq\emptyset$,
$B\neq\emptyset$, and $G$ has no edges with one endpoint in $A$ and one in
$B$. A _clique cutset_ in $G$ is a clique $C$ such that $G$ has a cut-
partition $(A,B,C)$ for some $A$ and $B$. Given two non-adjacent vertices $u$
and $v$ in $G$, a _$u{,}v$ -separator_ is a set $S\subseteq
V(G)\setminus\\{u,v\\}$ such that $u$ and $v$ belong to different components
of $G-S$. A $u{,}v$-separator $S$ is _minimal_ if no proper subset of $S$ is a
$u{,}v$-separator. A _minimal separator_ in $G$ is a set $S\subseteq V(G)$
that is a minimal $u{,}v$-separator for some non-adjacent vertex pair $u{,}v$.
A well-known characterization of minimal separators (see, e.g., [51]) is that
a set $S\subseteq V(G)$ is a minimal separator if and only if the graph $G-S$
contains at least two _$S$ -full components_, that is, two components such
that every vertex in $S$ has a neighbor in each of them.

We now define the six graph containment relations studied in this paper. A
graph $H$ is said to be an _induced subgraph_ of $G$ if $H$ can be obtained
from $G$ by deleting vertices. If $H$ is obtained from $G$ by deleting
vertices and edges, then $H$ is a _subgraph_ of $G$. The _subdivision of an
edge_ $uv$ of a graph is the operation that deletes the edge $uv$ and adds a
new vertex $w$ and two edges $uw$ and $wv$. A _subdivision of a graph_ $H$ is
a graph obtained from $H$ by a sequence of edge subdivisions. A graph $H$ is
said to be a _topological minor_ of a graph $G$ if $G$ contains a subdivision
of $H$ as a subgraph. Similarly, $H$ is an _induced topological minor_ of $G$
if some subdivision of $H$ is isomorphic to an induced subgraph of $G$. An
_edge contraction_ is the operation of deleting a pair of adjacent vertices
and replacing them with a new vertex whose neighborhood is the union of the
neighborhoods of the two original vertices. If $H$ can be obtained from $G$ by
a sequence of vertex deletions, edge deletions, and edge contractions, then
$H$ is said to be a _minor_ of $G$. Finally, we say that $G$ contains $H$ as
an _induced minor_ if $H$ can be obtained from $G$ by a sequence of vertex
deletions and edge contractions. If $G$ does not contain an induced subgraph
isomorphic to $H$, then we say that $G$ is _$H$ -free_. Analogously, we also
say that $G$ is $H$-subgraph-free, $H$-topological-minor-free, $H$-induced-
topological-minor-free, $H$-minor-free, or $H$-induced-minor-free,
respectively, for the other five relations. Note that $G$ contains $H$ as an
induced minor if and only if there exists an _induced minor model_ of $H$ in
$G$, that is, a collection $(X_{u}:u\in V(H))$ of pairwise disjoint subsets of
$V(G)$ such that each $X_{u}$ induces a connected subgraph of $G$ and for
every two distinct vertices $u,v\in V(H)$, there is an edge in $G$ between a
vertex of $X_{u}$ and a vertex of $X_{v}$ if and only if $uv\in E(H)$.

A _tree decomposition_ of a graph $G$ is a pair
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ such that $T$ is a tree and every
node $t$ of $T$ is assigned a _bag_ , that is, a vertex subset $X_{t}\subseteq
V(G)$, such that the following conditions are satisfied: every vertex of $G$
is in at least one bag, for every edge $uv\in E(G)$ there exists a node $t\in
V(T)$ such that $X_{t}$ contains both $u$ and $v$, and for every vertex $u\in
V(G)$ the subgraph $T_{u}$ of $T$ induced by the set $\\{t\in V(T):u\in
X_{t}\\}$ is connected (that is, a tree). The _width_ of $\mathcal{T}$ is the
maximum value of $|X_{t}|-1$ over all $t\in V(T)$. The _treewidth_ of a graph
$G$, denoted by $\mathrm{tw}(G)$, is defined as the minimum width of a tree
decomposition of $G$.

A graph $G$ is _chordal_ if it has no induced cycles of length at least four.
It is known that a graph $G$ is chordal if and only if it admits a _clique
tree_ , that is, a tree decomposition of $G$ whose bags are exactly the
maximal cliques of $G$ (see, e.g., [14]). Given a graph $G=(V,E)$, a
_triangulation_ of $G$ is a chordal graph of the form $(V,E\cup F)$ where $F$
is a subset of the set of non-edges of $G$. A triangulation $(V,E\cup F)$ of
$G$ is a _minimal triangulation_ of $G$ if $G$ has no triangulation $(V,E\cup
F^{\prime})$ such that $F^{\prime}$ is a proper subset of $F$.

An (integer) _graph invariant_ is a mapping from the class of all graphs to
the set of nonnegative integers that does not distinguish between isomorphic
graphs. For a graph invariant $\rho$, we say that a graph class $\mathcal{G}$
has _bounded $\rho$_ if there exists an integer $k$ such that $\rho(G)\leq k$
for every graph $G$ in the class. A graph class $\mathcal{G}$ is said to be
_$(\mathrm{tw},\omega)$ -bounded_ if it admits a _$(\mathrm{tw},\omega)$
-binding function_, that is, a function $f$ such that for every graph $G$ in
the class and any induced subgraph $G^{\prime}$ of $G$, the treewidth of
$G^{\prime}$ is at most $f(\omega(G^{\prime}))$. Furthermore, $\mathcal{G}$ is
said to be _polynomially $(\mathrm{tw},\omega)$-bounded_ if it admits a
polynomial $(\mathrm{tw},\omega)$-binding function. Ramsey’s theorem [74]
states that for every two positive integers $p$ and $q$ there exists an
integer $N(p,q)$ such that every graph with at least $N(p,q)$ vertices
contains either a clique of size $p$ or an independent set of size $q$. The
least such positive integer is denoted by $R(p,q)$. Following Raghavan and
Spinrad [73], we say that an algorithm for a particular graph problem is
_robust_ for a graph class $\mathcal{G}$ if for every input graph $G$, the
algorithm either solves the problem or determines that the graph is not in
$\mathcal{G}$.

###  2.2 On the tree-independence number

Given a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of a
graph $G$, the _independence number_ of $\mathcal{T}$, denoted by
$\alpha(\mathcal{T})$, is defined as the maximum independence number of
$G[X_{t}]$ among all nodes $t\in V(T)$. The _tree-independence number_ of $G$,
denoted by $\mathsf{tree}\textnormal{-}\alpha(G)$, is the minimum independence
number among all possible tree decompositions of $G$.

Known properties of chordal graphs imply that the class of chordal graphs
coincides with the class of graphs with tree-independence number at most one
(see Theorem 3.3 in [36]).

######  Theorem 2.1.

Let $G$ be a graph. Then $\mathsf{tree}\textnormal{-}\alpha(G)\leq 1$ if and
only if $G$ is chordal.

While the tree-independence number can increase upon edge deletions, it is
monotone under vertex deletions and edge contractions.

######  Proposition 2.2 (Proposition 3.9 in [36]).

Let $G$ be a graph and $G^{\prime}$ an induced minor of $G$. Then
$\mathsf{tree}\textnormal{-}\alpha(G^{\prime})\leq\mathsf{tree}\textnormal{-}\alpha(G)$.

A possible reason for large tree-independence number is the presence of a
large induced balanced complete bipartite subgraph.

######  Lemma 2.3 (Corollary 3.6 in [36]).

For every positive integer $n$, we have
$\mathsf{tree}\textnormal{-}\alpha(K_{n,n})=n$.

Given a graph $G$ and a family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected
subgraphs of $G$, we denote by $G(\mathcal{H})$ the graph with vertex set $J$,
in which two distinct elements $i,j\in J$ are adjacent if and only if $H_{i}$
and $H_{j}$ either have a vertex in common or there is an edge in $G$
connecting them. A subfamily $\mathcal{H}^{\prime}$ of $\mathcal{H}$ is said
to be an _independent $\mathcal{H}$-packing_ in $G$ if every two graphs in
$\mathcal{H}^{\prime}$ are vertex-disjoint and there is no edge between them,
that is, $\mathcal{H}^{\prime}$ is an independent set in the graph
$G(\mathcal{H})$. Assume now that the subgraphs in $\mathcal{H}$ are equipped
with a weight function $w:J\to\mathbb{Q}_{+}$ assigning weight $w_{j}$ to each
subgraph $H_{j}$. For any set $I\subseteq J$, we define the _weight_ of the
family $\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ as the sum $\sum_{i\in
I}w_{i}$. Given a graph $G$, a finite family $\mathcal{H}=\\{H_{j}\\}_{j\in
J}$ of connected nonnull subgraphs of $G$, and a weight function
$w:J\to\mathbb{Q}_{+}$ on the subgraphs in $\mathcal{H}$, the Max Weight
Independent Packing problem asks to find an independent $\mathcal{H}$-packing
in $G$ of maximum weight. Note that the problem is equivalent to the Max
Weight Independent Set problem on the derived graph $G(\mathcal{H})$.

The construction $G(\mathcal{H})$ was considered by Cameron and Hell in [22],
who focused on the following particular case. Given a graph $G$ and a (finite
or infinite) set $\mathcal{F}$ of connected graphs, we denote by
$\mathcal{H}(G,\mathcal{F})$ the family of all subgraphs of $G$ isomorphic to
a member of $\mathcal{F}$. Note that, for
$\mathcal{H}=\mathcal{H}(G,\mathcal{F})$, the graph $G(\mathcal{H})$ is
isomorphic to $G$ if $\mathcal{F}=\\{K_{1}\\}$ and to the square of the line
graph of $G$ if $\mathcal{F}=\\{K_{2}\\}$. In the special case of the Max
Weight Independent Packing when $\mathcal{H}=\mathcal{H}(G,\mathcal{F})$, we
obtain the Max Weight Independent $\mathcal{F}$-Packing problem, a common
generalization of several problems studied in the literature, including the
Independent $\mathcal{F}$-Packing problem (see [22]), the Max Weight
Independent Set problem, the Max Weight Induced Matching problem (see, e.g.,
[2, 71]), the Dissociation Set problem (see, e.g., [89, 87, 70]), and the
$k$-Separator problem (see, e.g., [64, 8]).

In the previous work of the series [36], we developed a polynomial-time
algorithm for the Max Weight Independent Packing problem under the assumption
that the input graph is equipped with a tree decomposition of bounded
independence number.

######  Theorem 2.4 (Theorem 7.2 in [36]).

Let $k$ be a positive integer. Then, given a graph $G$ and a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected nonnull subgraphs of $G$, the
Max Weight Independent Packing problem can be solved in time
$\mathcal{O}(|J|\cdot((|J|+|V(T)|)\cdot|V(G)|+|E(G)|+|J|^{k}\cdot|V(T)|)$ if
$G$ is given together with a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ with independence number at most
$k$.

One of the key steps in the proof of Theorem 2.4 was a dynamic programming
algorithm for the Max Weight Independent Set problem obtained by adapting the
standard dynamic programming approach over tree decompositions of bounded
width to the more general setting of tree decompositions with bounded
independence number. In fact, an improved version of this algorithmic result
was given using the notion of an _$\ell$ -refined tree decomposition_, that
is, a tree decomposition in which each bag comes equipped with a subset of at
most $\ell$ vertices. Ignoring such vertices when computing the independence
number of the subgraph induced by the bag may lead to improved running times
(Theorem 2.8). Two particular examples of such improvements are explained in
Remarks 5.10 and 6.10.

######  Definition 2.5.

Given a nonnegative integer $\ell$, an _$\ell$ -refined tree decomposition_ of
a graph $G$ is a pair $\widehat{\mathcal{T}}=(T,\\{(X_{t},U_{t})_{t\in
V(T)}\\})$ such that $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ is a tree
decomposition of $G$, and for every $t\in V(T)$ we have $U_{t}\subseteq X_{t}$
and $|U_{t}|\leq\ell$. We will refer to $\mathcal{T}$ as the _underlying tree
decomposition_ of $\widehat{\mathcal{T}}$.

Any concept defined for tree decompositions can be naturally extended to
$\ell$-refined tree decompositions, simply by considering it on the underlying
tree decomposition.

The definition of $\ell$-refined tree decomposition leads to the following
refinement of the tree-independence number.

######  Definition 2.6.

Given a nonnegative integer $\ell$, the _residual independence number_ of an
$\ell$-refined tree decomposition $\widehat{\mathcal{T}}$ of a graph $G$ is
defined as $\max_{t\in V(T)}\alpha(G[X_{t}\setminus U_{t}])$ and denoted by
$\widehat{\alpha}(\widehat{\mathcal{T}})$. The _$\ell$ -refined tree-
independence number_ of a graph $G$ is defined as the minimum residual
independence number of an $\ell$-refined tree decomposition of $G$, and
denoted by $\ell$-$\mathsf{tree}\textnormal{-}\alpha(G)$.

The notion of $\ell$-refined tree decompositions with bounded residual
independence number generalizes the notion of $(k,\ell)$-semi clique tree
decompositions studied by Jacob, Panolan, Raman, and Sahlot in [61], as well
as tree decompositions where each bag is obtained from a clique by deleting a
bounded number of edges used by Fomin and Golovach [45].

######  Observation 2.7 (Observation 4.3 in [36]).

For every graph $G$ and every integer $\ell\geq 0$, we have

$\ell\textnormal{-}\mathsf{tree}\textnormal{-}\alpha(G)\leq\mathsf{tree}\textnormal{-}\alpha(G)\leq\ell\textnormal{-}\mathsf{tree}\textnormal{-}\alpha(G)+\ell\,.$

In particular, equalities hold when $\ell=0$, that is,
$0\textnormal{-}\mathsf{tree}\textnormal{-}\alpha(G)=\mathsf{tree}\textnormal{-}\alpha(G)$.

We now state precisely the aforementioned algorithmic results for the Max
Weight Independent Set problem.

######  Theorem 2.8 (Theorem 5.2 in [36]).

For every integer $k\geq 1$, Max Weight Independent Set is solvable in time
$\mathcal{O}(2^{\ell}\cdot|V(G)|^{k+1}\cdot|V(T)|)$ if the input vertex-
weighted graph $G$ is given with an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}=(T,\\{(X_{t},U_{t})\\}_{t\in V(T)})$ with residual
independence number at most $k$.

The case $\ell=0$ yields the following.

######  Corollary 2.9 (Corollary 5.3 in [36]).

For every $k\geq 1$, Max Weight Independent Set is solvable in time
$\mathcal{O}(|V(G)|^{k+1}\cdot|V(T)|)$ if the input vertex-weighted graph $G$
is given with a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$
with independence number at most $k$.

Computing $\ell$-refined tree decompositions with bounded residual
independence number can be reduced to graphs without clique cutsets; in
particular, to $2$-connected graphs. We will use this result in the proof of
Proposition 4.1.

######  Proposition 2.10 (Proposition 4.6 in [36]).

Let $C$ be a clique cutset in a graph $G$ and let $(A,B,C)$ be a cut-partition
of $G$. Let $G_{A}=G[A\cup C]$ and $G_{B}=G[B\cup C]$, and let
$\widehat{\mathcal{T}}_{A}$ and $\widehat{\mathcal{T}}_{B}$ be $\ell$-refined
tree decompositions of $G_{A}$ and $G_{B}$, respectively. Then we can compute
in time $\mathcal{O}(|\widehat{\mathcal{T}}_{A}|+|\widehat{\mathcal{T}}_{B}|)$
an $\ell$-refined tree decomposition $\widehat{\mathcal{T}}$ of $G$ such that
$\widehat{\alpha}(\widehat{\mathcal{T}})=\max\\{\widehat{\alpha}(\widehat{\mathcal{T}}_{A}),\widehat{\alpha}(\widehat{\mathcal{T}}_{B})\\}$.

The next lemma, showing $(\mathrm{tw},\omega)$-boundedness, combines Lemmas
3.2 and 4.4 in [36].

######  Lemma 2.11.

For every two nonnegative integers $k$ and $\ell$, the class of graphs with
$\ell$-refined tree-independence number at most $k$ is
$(\mathrm{tw},\omega)$-bounded, with a binding function
$f(p)=R(p+1,k+1)+\ell-2$, which is upper-bounded by a polynomial in $p$ of
degree $k$.222The fact that for fixed $k$, the Ramsey number $R(p+1,k+1)$ is
upper-bounded by a polynomial in $p$ of degree $k$ follows from a well-known
upper bound on the Ramsey numbers stating that $R(a,b)\leq{a+b-2\choose a-1}$
for all positive integers $a$ and $b$. In particular, for every positive
integer $k$, the class of graphs with tree-independence number at most $k$ is
$(\mathrm{tw},\omega)$-bounded, with a binding function $f(p)=R(p+1,k+1)-2$.

##  3 $K_{2,q}$-induced-minor-free graphs

In this section, we prove boundedness of the tree-independence number in the
classes of $K_{2,q}$-induced-minor-free graphs. We build on the work of
Bouchitté and Todinca [17] and make use of a number of concepts that are often
used in the literature in relation with tree decompositions: minimal
separators, minimal triangulations, and potential maximal cliques.

######  Definition 3.1.

A _potential maximal clique_ in a graph $G$ is a set $X\subseteq V(G)$ such
that $X$ is a maximal clique in some minimal triangulation of $G$.

Our approach can be summarized as follows. First, we characterize the
$K_{2,q}$-induced-minor-free graphs in terms of minimal separators. Second,
using the fact that every graph has an efficiently computable tree
decomposition in which every bag is a potential maximal clique, we show that
the tree-independence number is bounded and efficiently witnessed in any class
of graphs in which there is a bound on the maximum size of an independent set
contained in a potential maximal clique. Finally, we connect this observation
with minimal separators by proving that in every graph, every potential
maximal clique is either a clique or is contained in the union of two minimal
separators (Theorem 3.8).

######  Lemma 3.2.

Given a positive integer $q$, a graph $G$ is $K_{2,q}$-induced-minor-free if
and only if every minimal separator in $G$ induces a subgraph with
independence number less than $q$.

###### Proof.

Fix $q\geq 1$ and a graph $G$. Let $S$ be a minimal separator in $G$, and let
$C$ and $D$ be two $S$-full components of $G-S$. Note that for any independent
set $I$ of $G$ contained in $S$, deleting from $G$ all vertices in
$V(G)\setminus(V(C)\cup V(D)\cup I)$ and then contracting all edges fully
contained within $C$ or $D$ yields a graph isomorphic to $K_{2,|I|}$, showing
that $G$ contains $K_{2,|I|}$ as an induced minor. Thus, if $G$ is
$K_{2,q}$-induced-minor-free, then $\alpha(G[S])<q$.

Suppose now that $G$ contains $K_{2,q}$ as an induced minor. Fix a bipartition
$\\{A,B\\}$ of $K_{2,q}$ such that $A=\\{a_{1},a_{2}\\}$ and
$B=\\{b_{1},\ldots,b_{q}\\}$, and let $M=(X_{u}:u\in V(K_{2,q}))$ be an
induced minor model of $K_{2,q}$ in $G$ that minimizes the sum $\sum_{b\in
B}|X_{b}|$. Since each vertex $b\in B$ has degree two in $K_{2,q}$, the
minimality of $M$ implies that $|X_{b}|=1$ for all $b\in B$. Let $I=\cup_{b\in
B}X_{b}$ and $W=I\cup X_{a_{1}}\cup X_{a_{2}}$. Since $M$ is an induced minor
model of $K_{2,q}$ in $G$, the set $I$ is independent in $G$, while the sets
$X_{a_{1}}$ and $X_{a_{2}}$ induce connected subgraphs of $G$ and are
anticomplete to each other. In particular, since every vertex in $I$ has a
neighbor in $G$ in both $X_{a_{1}}$ and $X_{a_{2}}$, we infer that $I$ is a
minimal separator in the subgraph of $G$ induced by $W$. Furthermore, since
$I\cup(V(G)\setminus W)$ separates $X_{a_{1}}$ from $X_{a_{2}}$ in $G$, there
exists a minimal separator $S$ in $G$ such that $I\subseteq S$. Consequently,
$\alpha(G[S])\geq|I|=|B|=q$. ∎

The importance of potential maximal cliques for our purpose is due to the
following upper bound on the tree-independence number. Given a graph $G$, we
denote by $\alpha_{pmc}(G)$ the _pmc-independence number_ of $G$, defined as
the maximum independence number of a subgraph of $G$ induced by some potential
maximal clique in $G$. Note that the value of $\alpha_{pmc}(G)$ is well-
defined, since every graph has at least one potential maximal clique. In the
next lemma, we denote by $\mu$ the _matrix multiplication exponent_ , that is,
the smallest real number such that two $n\times n$ binary matrices can be
multiplied in time $\mathcal{O}(n^{\mu+\epsilon})$ for all $\epsilon>0$. It is
known that $\mu<2.37286$ [3].

######  Lemma 3.3.

Let $G$ be an $n$-vertex graph. Then
$\mathsf{tree}\textnormal{-}\alpha(G)\leq\alpha_{pmc}(G)$. Furthermore, a tree
decomposition of $G$ with at most $n$ nodes and with independence number at
most $\alpha_{pmc}(G)$ can be computed in time $\mathcal{O}(n^{\mu}\log n)$.

###### Proof.

First we compute a minimal triangulation $G^{\prime}$ of $G$; this can be done
in time $\mathcal{O}(n^{\mu}\log{n})$ [58]. Since $G^{\prime}$ is a chordal
graph, we use an algorithm due to Berry and Simonet [11] to compute in time
$\mathcal{O}(|V(G^{\prime})|+|E(G^{\prime})|)=\mathcal{O}(n^{2})$ a clique
tree $\mathcal{T}=(T,\\{X_{t}:t\in V(T)\\})$ of $G^{\prime}$ with at most
$|V(G^{\prime})|=n$ nodes. By construction, every bag in this tree
decomposition is a maximal clique of $G^{\prime}$, and hence a potential
maximal clique in $G$. Furthermore, $\mathcal{T}$ is a tree decomposition of
$G$. Since the independence number of this tree decomposition is at most
$\alpha_{pmc}(G)$, this is also an upper bound on the tree-independence number
of $G$. ∎

The following theorem due to Bouchitté and Todinca [16] characterizes
potential maximal cliques.

######  Theorem 3.4.

Let $G$ be a graph and let $X\subseteq V(G)$. Then $X$ is a potential maximal
clique in $G$ if and only if the following two conditions hold:

  1. 1.

For every component $C$ of $G-X$, some vertex of $X$ has no neighbors in $C$.

  2. 2.

For every two non-adjacent vertices $u,v\in X$ there exists a component $C$ of
$G-X$ in which both $u$ and $v$ have a neighbor.

Furthermore, if $X$ is a potential maximal clique, then the family of minimal
separators $S$ in $G$ such that $S\subset X$ equals the family of the
neighborhoods, in $G$, of the components of $G-X$.

Let $X$ be a potential maximal clique in a graph $G$, let $C$ be a component
of $G-X$, and let $S=N_{G}(V(C))$. We say that $S$ is an _active separator for
$X$_ if there exist two non-adjacent vertices $u,v\in S$ such that $C$ is the
only component of $G-X$ in which $u$ and $v$ both have neighbors. (This
definition is formulated slightly differently in [17, Definition 13]. However,
the two definitions are equivalent, due to Theorem 3.4.) Not every potential
maximal clique contains an active separator, but for those that do, the
following result holds, as a consequence of [17, Theorem 15].

######  Theorem 3.5.

Let $X$ be a potential maximal clique in a graph $G$ and let $S$ be an active
minimal separator for $X$. Then there exists a minimal separator $T$ of $G$
such that $X\subseteq S\cup T$.

The following is a part of the statement of [17, Proposition 19].

######  Proposition 3.6.

Let $a\in V(G)$ and let $X$ be a potential maximal clique of $G$ and such that
$a\not\in X$. Let $C_{a}$ be the connected component of $G-X$ containing $a$
and let $S=N_{G}(V(C_{a}))$. Then either $X$ is a potential maximal clique of
$G-a$ or $S$ is active for $X$.

For the next theorem we need the following property of minimal separators.

######  Lemma 3.7.

Let $G$ be a graph, let $G^{\prime}$ be an induced subgraph of $G$, and let
$S^{\prime}$ be a minimal separator in $G^{\prime}$. Then there exists a
minimal separator $S$ in $G$ such that $S^{\prime}\subseteq S$.

###### Proof.

Let $C^{\prime}$ and $D^{\prime}$ be two $S^{\prime}$-full components of the
graph $G^{\prime}-S^{\prime}$. Fix two vertices $u\in V(C^{\prime})$ and $v\in
V(D^{\prime})$. Consider the set $\tilde{S}=S^{\prime}\cup(V(G)\setminus
V(G^{\prime}))$. This set is a $u{,}v$-separator in $G$, and therefore
contains a minimal $u{,}v$-separator $S$ in $G$. Since the set $\tilde{S}$ is
disjoint from $V(C^{\prime})\cup V(D^{\prime})$ and $S\subseteq\tilde{S}$, the
set $S$ is also disjoint from $V(C^{\prime})\cup V(D^{\prime})$. Furthermore,
since every vertex in $S^{\prime}$ has a neighbor in both $C^{\prime}$ and
$D^{\prime}$, we must have $S^{\prime}\subseteq S$ as otherwise $S$ would not
be a $u{,}v$-separator in $G$. ∎

Theorem 3.5 implies that every potential maximal clique that contains an
active minimal separator can be covered by two minimal separators in $G$. For
an arbitrary potential maximal clique, the following holds.

######  Theorem 3.8.

Let $G$ be a graph and let $X$ be a potential maximal clique in $G$. Then $X$
is either a clique in $G$ or there exist two minimal separators $S$ and $T$ in
$G$ such that $X\subseteq S\cup T$.

###### Proof.

We use induction on the number of vertices of $G$. If $G$ is chordal, then the
only minimal triangulation of $G$ is $G$ itself, and hence the potential
maximal cliques of $G$ coincide with its maximal cliques. So we may assume
that $G$ is not chordal.

Consider a potential maximal clique $X$ of $G$. Assume that $X$ is not a
clique. Then, by Item 2 of Theorem 3.4, $X\neq V(G)$. If $X$ contains an
active minimal separator $S$, then by Theorem 3.5, there exists a minimal
separator $T$ of $G$ such that $X\subseteq S\cup T$.

Assume now that $X$ does not contain any active minimal separator. Since
$X\neq V(G)$, there exists a vertex $a\in V(G)\setminus X$. Let
$G^{\prime}=G-a$, let $C_{a}$ be the connected component of $G-X$ containing
$a$, and let $S=N_{G}(V(C_{a}))$. Since $S$ is not an active separator for
$X$, Proposition 3.6 implies that $X$ is a potential maximal clique of
$G^{\prime}$. By the induction hypothesis, there exist two minimal separators
$S^{\prime}$ and $T^{\prime}$ in $G^{\prime}$ such that $X\subseteq
S^{\prime}\cup T^{\prime}$. By Lemma 3.7, there exist two minimal separators
$S$ and $T$ in $G$ such that $S^{\prime}\subseteq S$ and $T^{\prime}\subseteq
T$. Thus, $X\subseteq S\cup T$. ∎

We now return our attention to the class of $K_{2,q}$-induced-minor-free
graphs, where $q$ is a positive integer. The case $q=1$ is not of particular
interest, as every connected $K_{2,1}$-induced-minor-free graph is complete.
However, for all $q\geq 2$, the class of $K_{2,q}$-induced-minor-free graphs
contains the class of chordal graphs, and this containment is proper for all
$q\geq 3$.

Lemmas 3.2 and 3.8 imply the following.

######  Lemma 3.9.

For every integer $q\geq 2$ and every $K_{2,q}$-induced-minor-free graph $G$,
the pmc-independence number of $G$ is at most $2q-2$.

The upper bound from Lemma 3.9 is not sharp for the case $q=2$, when we obtain
the class of chordal graphs; for a chordal graph $G$, its potential maximal
cliques coincide with its maximal cliques, and hence $\alpha_{pmc}(G)\leq 1$.
We can also improve the bound for the case $q=3$.

######  Lemma 3.10.

If $G$ is a $K_{2,3}$-induced-minor-free graph, then $\alpha_{pmc}(G)\leq 3$.

###### Proof.

Suppose for a contradiction that $G$ is a $K_{2,3}$-induced-minor-free graph
that contains an independent set $I$ of size $4$ that is contained in a
potential maximal clique $X$. By Theorem 3.4, every two non-adjacent vertices
in $X$ are in the neighborhood of some component of $G-X$. We can thus fix,
for any two distinct vertices $x,y\in I$, a component $C(x,y)$ of $G-X$ in
which both $x$ and $y$ have a neighbor. Next, we show that these components
are pairwise distinct. Suppose that this is not the case. Then there exists a
component $C$ of $G-X$ with at least three neighbors in $I$. By Theorem 3.4,
the neighborhood of $V(C)$ is a minimal separator in $G$. However, by Lemma
3.2 no minimal separator in $G$ contains three pairwise non-adjacent vertices,
which implies that $|N(V(C))\cap I|\leq 2$, a contradiction. To complete the
proof, let us fix, for any two distinct vertices $x,y\in I$, an arbitrary
induced $x,y$-path $P(x,y)$ in $G$ such that all internal vertices of $P(x,y)$
belong to $C(x,y)$. Writing $I=\\{x,y,u,v\\}$, we now see that $x$, $y$, the
path $P(x,y)$, the concatenation of the paths $P(x,u)$ and $P(u,y)$, and the
concatenation of the paths $P(x,v)$ and $P(v,y)$ form an induced subgraph of
$G$ isomorphic to a subdivision of $K_{2,3}$. This contradicts the fact that
$G$ is $K_{2,3}$-induced-minor-free. ∎

The bound given by Lemma 3.10 is sharp, as verified by the $6$-cycle. Indeed,
any maximum independent set in the $6$-cycle is a potential maximal clique,
showing that $\alpha_{pmc}(C_{6})\geq 3$. We suspect that the bound from Lemma
3.9 may in fact not be sharp for any $q\geq 2$, but leave this question for
future work.

Lemmas 3.9 and 3.3 immediately imply the following result.

######  Theorem 3.11.

For every integer $q\geq 2$ and every $n$-vertex $K_{2,q}$-induced-minor-free
graph $G$, the tree-independence number of $G$ is at most $2q-2$. Furthermore,
a tree decomposition of $G$ with at most $n$ nodes and with independence
number at most $2q-2$ can be computed in time $\mathcal{O}(n^{\mu}\log n)$,
where $\mu<2.37286$ is the matrix multiplication exponent.

We do not know if the bound on the tree-independence number of
$K_{2,q}$-induced-minor-free graphs given by Theorem 3.11 is sharp. In fact,
for all we know, it may even be possible that for all $q\geq 2$, the correct
bound is $q-1$ instead of $2(q-1)$. Recall that the tree-independence number
of the complete bipartite graph $K_{q-1,q-1}$ is equal to $q-1$ (see Lemma
2.3), so the bound of $q-1$, if true, would be sharp.

######  Remark 3.12.

One can show that the algorithm used to compute a tree decomposition of a
$K_{2,q}$-induced-minor-free graph, as given in Theorem 3.11, can be turned
into a robust polynomial-time algorithm, as follows. First, for a given
$n$-vertex graph $G$ we compute a tree decomposition $\mathcal{T}$ of $G$ in
time $\mathcal{O}(n^{\mu}\log n)$, as explained in Lemma 3.3. Then, for each
bag $X$ of $\mathcal{T}$, we check in polynomial time (where the degree of the
polynomial depends on $q$) whether $G[X]$ contains an independent set of size
at least $2q-1$. If that is the case, then the algorithm returns that $G$ is
not $K_{2,q}$-induced-minor-free (which follows by Lemmas 3.9 and 3.3).
Otherwise, the tree decomposition $\mathcal{T}$ has tree-independence number
at most $2q-2$. $\blacktriangle$

Lemmas 3.2 and 3.11 give an alternative proof of the fact that any class of
graphs in which all minimal separators are of bounded size has bounded tree-
independence number (see [36, Theorem 3.8]). We adopt the same notation as in
[36] and denote for a graph $G$ by $\mathrm{mms}(G)$ the maximum size of a
minimal separator of $G$ (unless $G$ is complete, in which case we set
$\mathrm{mms}(G)=0$).

######  Corollary 3.13.

For every graph $G$, we have
$\mathsf{tree}\textnormal{-}\alpha(G)\leq\max\\{1,2\cdot\mathrm{mms}(G)\\}$.

###### Proof.

The inequality holds for complete graphs, so we may assume that $G$ is not
complete and that for some positive integer $s$, every minimal separator in
$G$ has size at most $s$. Then every minimal separator in $G$ induces a
subgraph with independence number less than $s+1$. By Lemma 3.2, $G$ is
$K_{2,s+1}$-induced-minor-free. Hence, by Theorem 3.11 the tree-independence
number of $G$ is at most $2s$. ∎

Theorems 3.11 and 2.4 have the following consequence for the Max Weight
Independent Packing problem.

######  Theorem 3.14.

For every integer $q\geq 2$, given a $K_{2,q}$-induced-minor-free graph $G$
and a finite family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected nonnull
subgraphs of $G$, the Max Weight Independent Packing problem can be solved in
time $\mathcal{O}(|J|\cdot|V(G)|\cdot(|V(G)|+|J|^{2q-2}))$.

###### Proof.

Let $G$ be an $n$-vertex $K_{2,q}$-induced-minor-free graph,
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ a finite family of connected nonnull
subgraphs of $G$, and $w:J\to\mathbb{Q}_{+}$ a weight function. By Theorem
3.11, we can compute in time $\mathcal{O}(n^{\mu}\log n)$ a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$ with $\mathcal{O}(n)$ nodes
and with independence number at most $2q-2$. Thus, by Theorem 2.4, Max Weight
Independent Packing can be solved on $G$ in time $\mathcal{O}(|J|\cdot
n\cdot(n+|J|^{2q-2}))$. ∎

Applying Theorem 3.14 to the case when $\mathcal{H}$ corresponds to the set of
all $1$-vertex subgraphs of the input graph $G$, we obtain the following.

######  Corollary 3.15.

For every integer $q\geq 2$, the Max Weight Independent Set problem is
solvable in time $\mathcal{O}(n^{2q})$ on $n$-vertex $K_{2,q}$-induced-minor-
free graphs.

For the case $q=3$ the bounds on the running time of the algorithm proving
Theorem 3.14 can be improved by using Lemma 3.10 instead of Lemma 3.9, which,
by Lemma 3.3, improves the upper bound on the tree-independence number of
$K_{2,3}$-induced-minor-free graphs from $4$ to $3$. We thus obtain the
following.

######  Theorem 3.16.

Let $G$ be an $n$-vertex $K_{2,3}$-induced-minor-free graph and let
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ be a finite family of connected nonnull
subgraphs of $G$. Then the Max Weight Independent Packing problem can be
solved in time $\mathcal{O}(|J|\cdot|V(G)|\cdot(|V(G)|+|J|^{3}))$. In
particular, the Max Weight Independent Set problem is solvable in time
$\mathcal{O}(n^{5})$ on $n$-vertex $K_{2,3}$-induced-minor-free graphs.

Theorem 3.16 answers the question regarding the complexity of the Max
Independent Set problem in the class of $1$-perfectly orientable graphs posed
by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in [5, 6]. A graph
$G$ is said to be _$1$ -perfectly orientable_ if its edges can be oriented so
that no vertex has a pair of non-adjacent out-neighbors. The class of
$1$-perfectly orientable graphs was introduced in 1982 by Skrien [80] and
studied by Bang-Jensen, Huang, and Prisner [4] and, more recently, by
Hartinger and Milanič [56] and by Brešar, Hartinger, Kos, Milanič [19]. While
the class of $1$-perfectly orientable graphs is known to be a common
generalization of the classes of chordal graphs and circular-arc graphs, the
structure of graphs in this class remains elusive. Nevertheless, it is known
that every $1$-perfectly orientable graph is $K_{2,3}$-induced-minor-free (see
[56]), and hence Theorem 3.16 has the following consequence.

######  Corollary 3.17.

The Max Weight Independent Set problem is solvable in time
$\mathcal{O}(n^{5})$ on $n$-vertex $1$-perfectly orientable graphs.

This result complements the $\mathcal{O}(n(n\log n+m\log\log n))$ algorithm
for the Max Weight Clique problem on $1$-perfectly orientable graphs with $n$
vertices and $m$ edges due to Beisegel, Chudnovsky, Gurvich, Milanič, and
Servatius [5, 6] and a linear-time algorithm for the List $k$-Coloring problem
in the same class of graphs, which follows from the corresponding algorithm
for $(\mathrm{tw},\omega)$-bounded graph classes due to Chaplick and Zeman
[28] (see also [27]) and the fact that the class of $K_{2,3}$-induced-minor-
free graphs is $(\mathrm{tw},\omega)$-bounded (by a computable binding
function) [35, 37].

##  4 Tree-independence number and SPQR trees

In this section, we use block-cutpoint trees and SPQR trees to develop a
sufficient condition for bounded and efficiently witnessed tree-independence
number for graph classes closed under induced topological minors. For the
description and analysis of running times of algorithms for computing tree
decompositions, as well as for the numbers of nodes of these decompositions,
we use the following definition. Let
$f:\mathbb{Z}_{+}\times\mathbb{Z}_{+}\to\mathbb{Z}_{+}$ be a function. We say
that $f$ is _superadditive_ if the inequality

$f(x_{1}+x_{2},y_{1}+y_{2})\geq f(x_{1},y_{1})+f(x_{2},y_{2})$

holds for all $x_{1},y_{1},x_{2},y_{2}\in\mathbb{Z}_{+}$. Note that any
superadditive function is non-decreasing with respect to both coordinates. A
similar argument shows that $f$ is non-decreasing in the second coordinate.

While the reductions described in this section could all be done with usual
tree decompositions, with respect to their independence numbers, we develop
the reductions in the more general context of $\ell$-refined tree
decompositions, with respect to their residual independence numbers. This will
lead to significant improvements in the running times of the algorithms for
the Max Weight Independent Set problem in the classes of $W_{4}$\- and
$K_{5}^{-}$-induced-minor-free graphs presented in Sections 5 and 6 (cf.
Remarks 5.10 and 6.10).

###  4.1 Reducing the problem to blocks

Given a graph $G$, a _block_ of $G$ is a maximal connected subgraph of $G$
without a cut-vertex. Every connected graph $G$ has a unique _block-cutpoint_
tree, that is, a tree $T$ with $V(T)=\mathcal{B}(G)\cup\mathcal{C}(G)$, where
$\mathcal{B}(G)$ is the set of blocks of $G$ and $\mathcal{C}(G)$ is the set
of cut-vertices of $G$, such that every edge of $T$ has an endpoint in
$\mathcal{B}(G)$ and the other in $\mathcal{C}(G)$, with $B\in\mathcal{B}(G)$
adjacent to $v\in\mathcal{C}(G)$ if and only if $v\in V(B)$. Every leaf of the
block-cutpoint tree is a block of $G$, called a _leaf block_ of $G$. As shown
by Hopcroft and Tarjan [59], a block-cutpoint tree of a connected graph $G$
can be computed in linear time.

Applying Proposition 2.10 to clique cutsets of size at most one, we obtain the
following algorithmic result, reducing the problem of computing $\ell$-refined
tree decompositions with small residual independence number to the case of
$2$-connected graphs in a hereditary graph class $\mathcal{G}$.

######  Proposition 4.1.

Let $\mathcal{G}$ be a hereditary graph class for which there exist
nonnegative integers $k$ and $\ell$ such that for each $2$-connected graph in
${\mathcal{G}}$, with $n$ vertices and $m$ edges, one can compute in time
$f(n,m)$ an $\ell$-refined tree decomposition with at most $g(n,m)$ nodes and
residual independence number at most $k$, where $f$ and $g$ are superadditive
functions. Then, for any graph $G$ in $\mathcal{G}$ with $n\geq 1$ vertices
and $m$ edges, one can compute in time $\mathcal{O}(n+m+f(2n,m))$ an
$\ell$-refined tree decomposition of $G$ with $\mathcal{O}(n+g(2n,m))$ nodes
and residual independence number at most $\max\\{2-\ell,k\\}$.333In the case
$k=1$, a simple adaptation of the proof shows that the bound
$\max\\{2-\ell,k\\}$ can be replaced with $k$, which matches the bound for all
$k\geq 2$. If one is only interested in preserving the usual tree-independence
number (which corresponds to the case $\ell=0$), then the Hopcroft–Tarjan
algorithm [59] combined with Proposition 2.10 also leads to a bound of $k$
(except if $k=0$, in which case the bound becomes $1$).

###### Proof.

Let $G\in\mathcal{G}$ be a graph with $n\geq 1$ vertices and $m$ edges. Using
Breadth-First Search and the Hopcroft-Tarjan algorithm, we compute in time
$\mathcal{O}(n+m)$ the connected components $G_{1},\ldots,G_{p}$ of $G$ and
the corresponding block-cutpoint trees $T_{1},\dots,T_{p}$. Let
$\mathcal{B}_{2}(G_{i})$ and $\mathcal{B}_{3}(G_{i})$ denote the sets of
blocks of $G_{i}$ with exactly two, resp. at least three, vertices. For each
component $G_{i}$ we compute an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{G_{i}}$ of $G_{i}$ recursively as follows.

At each step of the recursion, let $G_{i}^{\prime}$ be the current graph and
$B$ be a leaf block of $G_{i}^{\prime}$. Initially, we take
$G_{i}^{\prime}=G_{i}$.

  1. 1.

First, if $G_{i}^{\prime}=B$, then we consider the following two cases.

If $B\in\mathcal{B}_{2}(G_{i})$, then $B$ is a complete graph of order at most
two. In this case we compute the $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{G_{i}^{\prime}}$ of $G_{i}^{\prime}$ consisting of a
single node $t$ whose bag $X_{t}$ is $V(G_{i}^{\prime})$ and the set $U_{t}$
to be any subset of $V(G_{i}^{\prime})$ with $\min\\{\ell,2\\}$ vertices. We
can compute $\widehat{\mathcal{T}}_{G_{i}^{\prime}}$ in constant time; note
that this $\ell$-refined tree decomposition of $G_{i}^{\prime}$ satisfies

$\widehat{\alpha}(\widehat{\mathcal{T}}_{G_{i}^{\prime}})=\alpha(G_{i}^{\prime}[X_{t}\setminus
U_{t}])\leq|X_{t}|-|U_{t}|=2-\min\\{\ell,2\\}=\max\\{2-\ell,0\\}\leq\max\\{2-\ell,k\\}\,.$

Otherwise, $B\in\mathcal{B}_{3}(G_{i})$ is $2$-connected, and we compute in
time $f(|V(G_{i}^{\prime})|,|E(G_{i}^{\prime})|)$ an $\ell$-refined tree
decomposition $\widehat{\mathcal{T}}_{G_{i}^{\prime}}$ of $G_{i}^{\prime}$
with at most $f(|V(G_{i}^{\prime})|,|E(G_{i}^{\prime})|)$ nodes and residual
independence number at most $k\leq\max\\{2-\ell,k\\}$.

  2. 2.

Second, if $G_{i}^{\prime}\neq B$, let $(X,Y,Z)$ be a cut-partition where
$X=V(B)\setminus\\{v\\}$, $Y=V(G_{i}^{\prime})\setminus V(B)$, and $Z=\\{v\\}$
for the unique cut-vertex $v$ of $G_{i}^{\prime}$ contained in $B$. We then
compute an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{G_{i}^{\prime}}$ of $G_{i}^{\prime}$ by recursively
computing $\ell$-refined tree decompositions of the block $B$ and the graph
$G_{i}^{\prime}[Y\cup Z]$, and applying Proposition 2.10 to the cut-partition
$(X,Y,Z)$.

This recursive procedure takes time

$\mathcal{O}\left(|\mathcal{B}_{2}(G_{i})|\right)+\sum_{B\in\mathcal{B}_{3}(G_{i})}f(|V(B)|,|E(B)|)\,=\,\mathcal{O}\left(|V(T_{i})|+\sum_{B\in\mathcal{B}(G_{i})}f(|V(B)|,|E(B)|)\right)\,.$

The total number of nodes of $\widehat{\mathcal{T}}_{G_{i}}$ is upper bounded
by

$|\mathcal{B}_{2}(G_{i})|+\sum_{B\in\mathcal{B}_{3}(G_{i})}g(|V(B)|,|E(B)|)\quad\leq\quad|V(T_{i})|+\sum_{B\in\mathcal{B}(G_{i})}g(|V(B)|,|E(B)|)\,.$

Finally, we create an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}$ of $G$ with residual independence number at most
$\max\\{2-\ell,k\\}$ by combining the $\ell$-refined tree decompositions
$\widehat{\mathcal{T}}_{G_{1}},\ldots,\widehat{\mathcal{T}}_{G_{p}}$ of its
connected components in the obvious way (for example, by iteratively applying
Proposition 2.10 with respect to a sequence of cut-partitions involving the
empty clique cutset). The number of nodes of $\widehat{\mathcal{T}}$ is the
sum of the numbers of nodes of $\widehat{\mathcal{T}}_{G_{i}}$ over all
$i\in\\{1,\ldots,p\\}$. The overall running time of the algorithm is

$\mathcal{O}\left(\sum_{i=1}^{p}|V(T_{i})|+\sum_{i=1}^{p}\sum_{B\in\mathcal{B}(G_{i})}f(|V(B)|,|E(B)|)\right)\,.$

An inductive argument based on the number of blocks shows that for every
connected graph $H$ with at least one cut-vertex (and thus with at least two
blocks), we have $|\mathcal{C}(H)|<|\mathcal{B}(H)|\leq|V(H)|-1$. Thus, for
all $i\in\\{1,\ldots,p\\}$, we have
$|V(T_{i})|=|\mathcal{B}(G_{i})|+|\mathcal{C}(G_{i})|\leq 2|V(G_{i})|-3$,
which implies $\sum_{i=1}^{p}|V(T_{i})|=\mathcal{O}(n)$. Furthermore, for all
$i\in\\{1,\ldots,p\\}$, we have

$\displaystyle\sum_{B\in\mathcal{B}(G_{i})}|V(B)|$
$\displaystyle=|V(G_{i})|+\sum_{v\in\mathcal{C}(G_{i})}(d_{T_{i}}(v)-1)$
$\displaystyle=|V(G_{i})|+|E(T_{i})|-|\mathcal{C}(G_{i})|$
$\displaystyle=|V(G_{i})|+|V(T_{i})|-1-|\mathcal{C}(G_{i})|$
$\displaystyle=|V(G_{i})|+|\mathcal{B}(G_{i})|-1$ $\displaystyle\leq
2|V(G_{i})|-2$

and

$\sum_{B\in\mathcal{B}(G_{i})}|E(B)|\leq\sum_{B\in\mathcal{B}(G_{i})}|E(B)|=|E(G_{i})|\,.$

Since $f$ is superadditive and non-decreasing in the first coordinate, we have

$\displaystyle\sum_{B\in\mathcal{B}(G_{i})}f(|V(B)|,|E(B)|)$
$\displaystyle\leq
f\left(\sum_{B\in\mathcal{B}(G_{i})}|V(B)|,\sum_{B\in\mathcal{B}(G_{i})}|E(B)|\right)$
$\displaystyle\leq f\left(2|V(G_{i})|-2,|E(G_{i})|\right)\,.$

Applying the superadditivity and monotonicity properties of $f$ once again, we
obtain

$\displaystyle\sum_{i=1}^{p}f\left(2|V(G_{i})|-2,|E(G_{i})|\right)$
$\displaystyle\leq
f\left(2\sum_{i=1}^{p}|V(G_{i})|-2p,\sum_{i=1}^{p}|E(G_{i})|\right)$
$\displaystyle\leq f\left(2n,m\right),$

and the running time of the algorithm is $\mathcal{O}(n+m+f(2n,m))$, as
claimed.

The number of nodes of $\widehat{\mathcal{T}}$ is at most

$\sum_{i=1}^{p}\left(|V(T_{i})|+\sum_{B\in\mathcal{B}(G_{i})}g(|V(B)|,|E(B)|)\right).$

Applying the same arguments as we did above for the function $f$ to the
function $g$ leads to an upper bound for the number of nodes of
$\widehat{\mathcal{T}}$ given by $\mathcal{O}(n+g(2n,m))$. ∎

Proposition 4.1 leads to a sharp upper bound on the tree-independence number
of block-cactus graphs, which is needed in the proof of Theorem 7.3. A _block-
cactus graph_ is a graph every block of which is a cycle or a complete graph.
To derive the upper bound, we first show the following lemma.

######  Lemma 4.2.

For every integer $n\geq 4$, the tree-independence number of the cycle $C_{n}$
is exactly $2$.

###### Proof.

Since $C_{n}$ is not a chordal graph, Theorem 2.1 implies that
$\mathsf{tree}\textnormal{-}\alpha(C_{n})\geq 2$. Let $v_{1},\ldots,v_{n}$ be
an order of the vertices of $C_{n}$ along the cycle. We construct a tree
decomposition $\mathcal{T}=(T,\\{X_{t}:t\in V(T)\\})$ of $C_{n}$. The tree $T$
is an $(n-2)$-vertex path $(t_{1},\ldots,t_{n-2})$; for each
$i\in\\{1,\ldots,n-2\\}$, bag $X_{t_{i}}$ consists of vertices
$\\{v_{i},v_{i+1},v_{n}\\}$. Note that in every bag $X$ there exist two
consecutive vertices of $C_{n}$ in the order, and hence $G[X]$ contains at
least one edge. Furthermore, each bag $X$ contains exactly $3$ vertices. This
readily implies that $\alpha(G[X])\leq|X|-1=2$. Hence,
$\alpha(\mathcal{T})\leq 2$ and consequently
$\mathsf{tree}\textnormal{-}\alpha(C_{n})\leq 2$. ∎

Following the fact that every complete graph has tree-independence number at
most one, Propositions 4.1 and 4.2 imply the following.

######  Corollary 4.3.

The tree-independence number of any block-cactus graph is at most $2$.

###  4.2 Preliminaries on SPQR trees

We use a classical tool for decomposing $2$-connected graphs into triconnected
components, the SPQR trees. The SPQR tree data structure was introduced by Di
Battista and Tamassia in 1990 [39] (see also [40, 54, 60, 75]); however, the
underlying decomposition of a $2$-connected graph into its triconnected
components has been used already by Mac Lane in 1937 [67] and developed in
detail by Tutte [83, 84] (see also [33, 52, 43, 23] for generalizations). Most
applications of SPQR trees in the literature are related to questions
involving planarity [41, 67, 12], the Steiner tree problem [12], and graph
drawing [69]. More recent applications also involve improved recognition
algorithms of certain well-structured graph classes [38] and layered pathwidth
in minor-closed graph classes [42].

We use the notation of Dujmović, Eppstein, Joret, Morin, and Wood [42]. Given
a $2$-connected graph $G$, an _SPQR tree_ of $G$ is a tree $S$ with three
types of nodes: P-nodes, R-nodes, and S-nodes. Each node $a$ is associated
with a set $X_{a}\subseteq V(G)$. If $a$ is a P-node, then $X_{a}$ is a
$2$-cutset in $G$. If $a$ is an R-node or an S-node, then $X_{a}$ is the
vertex set of a graph $G_{a}$ associated to node $a$. For every S-node $a$,
the graph $G_{a}$ is a cycle, while for every R-node $a$, the corresponding
graph $G_{a}$ is $3$-connected. Every edge in $S$ has exactly one endpoint
that is a P-node. For every two adjacent nodes $a$ and $b$ of $S$ such that
$b$ is a P-node, the two vertices in $X_{b}$ are adjacent in $G_{a}$. An edge
$uv$ in $G_{a}$ such that $uv\notin E(G)$ is called a _virtual edge_ ;
otherwise, it is called a _real edge_. For every virtual edge $uv$ in $G_{a}$
there exists a P-node $b$ adjacent to $a$ in $S$ such that $X_{b}=\\{u,v\\}$.
No two P-nodes are associated with the same $2$-cutset of $G$. We denote the
sets of all P-nodes, R-nodes, and S-nodes of $S$ by $N_{\text{P}}(S)$,
$N_{\text{R}}(S)$, and $N_{\text{S}}(S)$, or simply by $N_{\text{P}}$,
$N_{\text{R}}$, and $N_{\text{S}}$, respectively, if the SPQR tree $S$ is
clear from the context.

An SPQR tree need not be unique. For example, if $G$ is the cycle $C_{n}$,
then an SPQR tree of $G$ can consist of a single node $a$, which is an S-node
such that $G_{a}=G$. At the other extreme, an SPQR tree of $G$ could be a tree
with as many as $n-2$ S-nodes, each with the corresponding graph $G_{a}$
isomorphic to the cycle $C_{3}$, and these S-nodes are connected to each other
via $n-3$ P-nodes each corresponding to a virtual edge. There are also many
other intermediate possibilities. However, if we consider an SPQR tree of $G$
with the minimum total number of nodes, then such a tree $S$ can be uniquely
obtained, by a simple transformation, from a rooted SPQR tree as originally
defined by Di Battista and Tamassia [39]. In this case, the graphs $G_{a}$
where $a$ is an R- or S-node are called _triconnected components_ of $G$ and
are uniquely defined (see [40, 67, 60]). From now on, we assume this
uniqueness property and refer to _the_ SPQR tree of $G$.

Thus, given a $2$-connected graph $G$, the SPQR tree $S$ of $G$ represents the
collection of triconnected components of $G$ that are joined at $2$-cutsets
(P-nodes). This structure can be described recursively as follows. The SPQR
tree $S$ is a single-vertex tree with a node $a$ if and only if $G$ is either
$3$-connected, in which case $a$ is an R-node, or $G$ is a cycle, in which
case $a$ is an S-node; in both cases, $G_{a}=G$. Otherwise, $S$ has a leaf
node $a$ that is either an R-node or an S-node such that its unique neighbor
$b$ in $S$ is a P-node. The P-node $b$ corresponds to a $2$-cutset $X_{b}$ of
$G$ separating $X_{a}\setminus X_{b}$ from $V(G)\setminus X_{a}$. Furthermore,
the tree $S^{\prime}$ obtained from $S$ by deleting $a$, as well as its
neighbor $b$ if it becomes a leaf, is the SPQR tree of the $2$-connected graph
$G^{\prime}$ obtained from $G$ by deleting the vertices in $X_{a}\setminus
X_{b}$ and adding the edge between the two vertices in $X_{b}$ if it does not
yet exist. In particular, since there exists a path in $G$ connecting the two
vertices of $X_{b}$ and having all internal vertices in $V(G_{a})\setminus
X_{b}$, there exists a subdivision of $G^{\prime}$ that is an induced subgraph
of $G$ (hence, $G^{\prime}$ is an induced topological minor of $G$). For each
R-node or S-node $a^{\prime}$ of $S^{\prime}$, the graph $G_{a^{\prime}}$
associated with node $a^{\prime}$ is the same as the corresponding graph
associated with $a^{\prime}$ in $S$. An inductive argument on the number of
nodes of the SPQR tree shows the following.

######  Lemma 4.4.

Let $G$ be a $2$-connected graph and $S$ the SPQR tree of $G$. For each node
$a$ of $S$ that is either an R-node or an S-node, the graph $G_{a}$ is an
induced topological minor of $G$.

The SPQR tree of any graph $G$ has $\mathcal{O}(|V(G)|)$ nodes (see [40]). As
shown by Gutwenger and Mutzel [54], the SPQR tree of $G$ can be computed in
linear time. The algorithm by Gutwenger and Mutzel computes a slightly
different and rooted variant of SPQR tree, but that tree can easily be turned
into the SPQR tree with $\mathcal{O}(|V(G)|)$ nodes and satisfying the
properties from our definition in linear time. Note that the SPQR tree $S$ of
a graph $G$ naturally defines a tree decomposition $\mathcal{T}$ of $G$ simply
by assigning to each node $a\in V(S)$ the set $X_{a}$ as the corresponding
bag.

For a graph $G$ we denote by $\eta(G)$ the _Hadwiger number_ of $G$, that is,
the maximum integer $p$ such that $G$ contains $K_{p}$ as a minor. Since the
Hadwiger number is monotone under taking minors, we readily obtain the
following inequality (which we will use in the following sections).

######  Corollary 4.5.

Let $G$ be a graph, $S$ the SPQR tree of $G$, and $a$ an R-node or S-node of
$S$. Then $\eta(G)\geq\eta(G_{a})$.

######  Lemma 4.6.

Let $G$ be a $2$-connected $n$-vertex graph and $S$ the SPQR tree of $G$. Then

$\sum_{a\in N_{\text{R}}\cup N_{\text{S}}}|X_{a}|\leq 3n-6\hskip
28.45274pt\text{~{}and~{}}\hskip 28.45274pt\sum_{a\in N_{\text{R}}}|X_{a}|\leq
2n-4\,.$

###### Proof.

We use induction on the number of nodes of $S$. Assume first that $S$ is a
single-vertex tree. Then $G=G_{\ell}$ for the unique R-node or S-node $\ell$
of $S$, and $|X_{\ell}|=n$. If $\ell$ is an R-node, then $n\geq 4$ and thus
$n\leq 2n-4$. If $\ell$ is an S-node, then $n\geq 3$ and thus $n\leq 3n-6$.

Consider now the general case. Then $S$ has a leaf node $\ell$ that is either
an R-node or an S-node such that its unique neighbor $p$ in $S$ is a P-node.
Let $G^{\prime}$ be the graph obtained from $G$ by deleting the vertices in
$X_{\ell}\setminus X_{p}$ and adding the edge between the two vertices in
$X_{p}$ if it does not yet exist, and let $S^{\prime}$ be the tree obtained
from $S$ by deleting $\ell$ as well as its neighbor $p$ if it becomes a leaf.
Then $S^{\prime}$ is the SPQR tree of $G^{\prime}$. Let
$n^{\prime}=|V(G^{\prime})|$. By the induction hypothesis, we have

$\sum_{a\in N_{\text{R}}(S^{\prime})\cup N_{\text{S}}(S^{\prime})}|X_{a}|\leq
3n^{\prime}-6\hskip 28.45274pt\text{~{}and~{}}\hskip 28.45274pt\sum_{a\in
N_{\text{R}}(S^{\prime})}|X_{a}|\leq 2n^{\prime}-4\,.$

Note that

$\sum_{a\in N_{\text{R}}(S)\cup N_{\text{S}}(S)}|X_{a}|=\sum_{a\in
N_{\text{R}}(S^{\prime})\cup N_{\text{S}}(S^{\prime})}|X_{a}|+|X_{\ell}|$

and

$\sum_{a\in N_{\text{R}}(S)}|X_{a}|\leq\sum_{a\in
N_{\text{R}}(S^{\prime})}|X_{a}|+|X_{\ell}|\,.$

Furthermore, we have

$n^{\prime}=n-|X_{\ell}\setminus X_{p}|=n-|X_{\ell}|+2\,.$

Since $|X_{\ell}|\geq 3$, we thus obtain

$\displaystyle\sum_{a\in N_{\text{R}}(S)\cup N_{\text{S}}(S)}|X_{a}|$
$\displaystyle=\sum_{a\in N_{\text{R}}(S^{\prime})\cup
N_{\text{S}}(S^{\prime})}|X_{a}|+|X_{\ell}|$ $\displaystyle\leq
3n^{\prime}-6+|X_{\ell}|$ $\displaystyle=3(n-|X_{\ell}|+2)-6+|X_{\ell}|$
$\displaystyle=3n-2|X_{\ell}|$ $\displaystyle\leq 3n-6\,.$

Furthermore, if $\ell$ is an S-node, then

$\displaystyle\sum_{a\in N_{\text{R}}(S)}|X_{a}|=\sum_{a\in
N_{\text{R}}(S^{\prime})}|X_{a}|\leq 2n^{\prime}-4\leq 2n-4\,,$

and if $\ell$ is an R-node, then $|X_{\ell}|\geq 4$ and thus

$\displaystyle\sum_{a\in N_{\text{R}}(S)}|X_{a}|$ $\displaystyle\leq\sum_{a\in
N_{\text{R}}(S^{\prime})}|X_{a}|+|X_{\ell}|$ $\displaystyle\leq
2n^{\prime}-4+|X_{\ell}|$ $\displaystyle=2(n-|X_{\ell}|+2)-4+|X_{\ell}|$
$\displaystyle=2n-|X_{\ell}|$ $\displaystyle\leq 2n-4\,.\qed$

Additionally, we use the following bound on the total number of edges in the
graphs $G_{a}$.

######  Lemma 4.7 (Hopcroft and Tarjan [60]).

Let $G$ be a $2$-connected graph and $S$ the SPQR tree of $G$. Then

$\sum_{a\in N_{\text{R}}\cup N_{\text{S}}}|E(G_{a})|\leq 3|E(G)|-6\,.$

###  4.3 Reducing the problem to triconnected components

Let us first observe that even if every triconnected component of a graph has
bounded independence number, the graph does not necessarily have bounded tree-
independence number.

######  Example 4.8.

Let $n\geq 4$ and let $G$ be the graph obtained from a complete graph $K_{n}$
by subdividing every edge once. Observe that the SPQR tree $S$ of $G$ contains
a unique R-node $a$ with $G_{a}\cong K_{n}$ to which every P-node is adjacent,
where the P-nodes correspond to the $2$-cutsets that separate the vertices
with degree $2$ from the rest of the graph (see Fig. 1). In particular, every
P-node $a$ is adjacent to exactly one S-node $a^{\prime}$, and $a^{\prime}$ is
a leaf of the SPQR tree $S$ such that the corresponding graph $G_{a^{\prime}}$
is a cycle on $3$ vertices. Hence, every triconnected component of $G$ has
independence number $1$. However,
$\mathsf{tree}\textnormal{-}\alpha(G)\geq\lfloor n/2\rfloor$. Indeed, since
$G$ contains every graph with at most $n$ vertices as an induced topological
minor, this in particular implies that the complete bipartite graph
$K_{\lfloor n/2\rfloor,\lfloor n/2\rfloor}$ is an induced topological minor of
$G$. By Lemmas 2.3 and 2.2, we obtain that
$\mathsf{tree}\textnormal{-}\alpha(G)\geq\mathsf{tree}\textnormal{-}\alpha(K_{\lfloor
n/2\rfloor,\lfloor n/2\rfloor})=\lfloor n/2\rfloor$.

$\mathstrut a$$\mathstrut b$$\mathstrut c$$\mathstrut d$$\mathstrut
a$$\mathstrut b$$\mathstrut a$$\mathstrut c$$\mathstrut a$$\mathstrut
d$$\mathstrut b$$\mathstrut c$$\mathstrut b$$\mathstrut d$$\mathstrut
c$$\mathstrut d$$\mathstrut a$$\mathstrut b$$\mathstrut a$$\mathstrut
c$$\mathstrut a$$\mathstrut d$$\mathstrut b$$\mathstrut c$$\mathstrut
b$$\mathstrut d$$\mathstrut c$$\mathstrut d$S-nodesP-nodesR-node$\mathstrut
a$$\mathstrut b$$\mathstrut c$$\mathstrut d$ Figure 1: On the left, the graph
$G$ obtained from subdividing every edge of $K_{4}$ once, as in Example 4.8.
On the right, a schematic representation of the SPQR tree of $G$.

As indicated by Example 4.8, the reason for the increase in the tree-
independence number of a graph when compared to the tree-independence numbers
of its triconnected components is due to the fact that subdividing edges can
increase the tree-independence number. Informally speaking, this is due to the
possibly complicated structure of the virtual edges present in the
triconnected components of the graph.

Let us explain this in more detail. Given a $2$-connected graph $G$ and the
SPQR tree $S$ of $G$, as observed in Lemma 4.4, for every R-node $a$ of $S$,
the triconnected component $G_{a}$ of $G$ is an induced topological minor of
$G$. Furthermore, the subgraph of $G$ induced by $V(G_{a})$ is a spanning
subgraph of $G_{a}$ and every edge in $G_{a}$ that is not an edge of $G$ is a
virtual edge. Assuming that $G_{a}$ has bounded tree-independence number, we
would like to infer a similar conclusion for the subgraph $G^{\prime}$ of $G$
induced by $V(G_{a})$. We can do this whenever the set $F$ of virtual edges
within $G_{a}$ can be covered with a bounded number $\ell$ of vertices (see
Definition 4.9). Indeed, deleting any such set of vertices from $G_{a}$
results in an induced subgraph of $G$, which means that this part of $G$ will
have bounded tree-independence number. Since only a bounded number of vertices
is deleted, the tree-independence number of the subgraph of $G$ induced by
$V(G_{a})$ will remain bounded.

######  Definition 4.9.

Let $G$ be a graph, $F^{*}\subseteq E(G)$ and $G^{\prime}$ a subgraph of $G$.
We say that a set $U\subseteq V(G^{\prime})$ is an _$F^{*}\\!$ -cover_ of
$G^{\prime}$ if $U$ contains at least one endpoint of every edge in
$E(G^{\prime})\cap F^{*}$.

The meaning and usefulness of the following definitions will become clearer
later, in the proof of Lemma 4.14.

######  Definition 4.10.

Let $G$ be graph and $F^{*}\subseteq E(G)$. An $\ell$-refined tree
decomposition $\widehat{\mathcal{T}}=(T,\\{(X_{t},U_{t})_{t\in V(T)}\\})$ of
$G$ is said to be _$F^{*}\\!$ -covering_ if for every node $t\in V(T)$ the set
$U_{t}$ is an $F^{*}\\!$-cover of $G[X_{t}]$.

######  Definition 4.11.

Let $\mathcal{G}$ be a graph class, let $G$ be a graph in $\mathcal{G}$, and
let $F^{*}\subseteq E(G)$. We say that $F^{*}$ is a _$\mathcal{G}$ -safe_ set
of edges of $G$ if deleting from $G$ any subset of $F^{*}$ results in a graph
that belongs to $\mathcal{G}$.

######  Definition 4.12.

Let $G$ be a graph, $F\subseteq E(G)$, and $\mathcal{T}$ a tree decomposition
(either usual or $\ell$-refined) of $G$. An _$F$ -mapping_ of $\mathcal{T}$ is
a mapping with domain $F$ assigning to every edge $e\in F$ a node $t_{e}\in
V(T)$ such that $e\subseteq X_{t_{e}}$.

Note that for any graph $G$, any set $F\subseteq E(G)$, and any (usual or
$\ell$-refined) tree decomposition $\mathcal{T}$ of $G$, there exists an
$F$-mapping of $\mathcal{T}$, since the endpoints of every edge in $G$ are
contained in some bag of $\mathcal{T}$. Furthermore, it is clear that an
$F$-mapping of $\mathcal{T}$ can be computed in polynomial time. However, for
a more efficient computation of an $F$-mapping of $\mathcal{T}$, it may be
best to compute it together with $\mathcal{T}$. To this end, we consider the
following property of a graph class and an associated problem.

######  Definition 4.13.

Given two nonnegative integers $k$ and $\ell$, a graph class $\mathcal{G}$ is
said to be _$(k,\ell)$ -tree decomposable_ if for every $3$-connected graph
$G\in\mathcal{G}$ and any $\mathcal{G}$-safe set $F^{*}$ of edges of $G$,
there exists an $F^{*}\\!$-covering $\ell$-refined tree decomposition of $G$
with residual independence number at most $k$.

$(k,\ell)$-Tree Decomposition($\mathcal{G})$
Input: A $3$-connected graph $G\in\mathcal{G}$ and two sets of edges
$F^{*}\subseteq F\subseteq E(G)$ such that $F^{*}$ is $\mathcal{G}$-safe.
Output: An $F^{*}\\!$-covering $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}$ of $G$ with residual independence number at most $k$
and an $F$-mapping of $\widehat{\mathcal{T}}$.

For a $(k,\ell)$-tree decomposable graph class $\mathcal{G}$ closed under
induced topological minors, the following key lemma reduces the problem of
computing $\widehat{\alpha}$-bounded $\ell$-refined tree decompositions of
$2$-connected graphs in $\mathcal{G}$ to the $(k,\ell)$-tree
Decomposition($\mathcal{G})$ problem.

######  Lemma 4.14.

Let $\mathcal{G}$ be a graph class closed under induced topological minors for
which there exist nonnegative integers $k$ and $\ell$ such that $\mathcal{G}$
is $(k,\ell)$-tree decomposable and $(k,\ell)$-tree
Decomposition($\mathcal{G})$ can be solved in time $f(n,m)$ on graphs with $n$
vertices and $m$ edges so that the resulting $\ell$-refined tree decomposition
has $g(n,m)$ nodes, where $f$ and $g$ are superadditive functions. Then, for
any $2$-connected graph $G$ in $\mathcal{G}$, with $n$ vertices and $m$ edges,
one can compute in time $\mathcal{O}(m+f(2n,3m))$ an $\ell$-refined tree
decomposition of $G$ with $\mathcal{O}(n+g(2n,3m))$ nodes and residual
independence number at most $\max\\{3-\ell,k\\}$.

###### Proof.

Let $G$ be a $2$-connected graph in $\mathcal{G}$ with $n$ vertices and $m$
edges. We compute in time $\mathcal{O}(n+m)$ the SPQR tree $S$ of $G$. Let
$\widehat{\mathcal{T}}=(T,\\{(X_{t},U_{t}):t\in V(T)\\})$ be the $0$-refined
tree decomposition of $G$ corresponding to the SPQR tree $S$. Note that
$\widehat{\mathcal{T}}$ is $\ell$-refined. Our goal is to obtain an
$\widehat{\alpha}$-bounded $\ell$-refined tree decomposition of $G$ by
updating $\widehat{\mathcal{T}}$ iteratively, as follows.

First, we iterate over all P-nodes $b$ in $S$ and set $U_{b}$ to be any subset
of $X_{b}$ with cardinality $\min\\{\ell,2\\}$. Since the number of P-nodes is
$\mathcal{O}(n)$, this modification takes time $\mathcal{O}(n)$. Furthermore,
for each P-node $b$ we then have

$\alpha(G[X_{b}\setminus
U_{b}])\leq|X_{b}|-|U_{b}|=2-\min\\{\ell,2\\}=\max\\{2-\ell,0\\}\leq\max\\{3-\ell,k\\}\,.$

Then, for each R-node or S-node $a$ in $S$ we compute an
$\widehat{\alpha}$-bounded $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{a}$ of $G_{a}$ (using the assumption of the lemma in
the case of R-nodes) and replace the corresponding node in
$\widehat{\mathcal{T}}$ with $\widehat{\mathcal{T}}_{a}$. Let us describe the
update procedure in detail. For each node $a$ of $S$ that is an R-node or an
S-node, we perform the following three steps.

Step 1. We compute two sets of edges $F_{a}^{*}$ and $F_{a}$ such that
$F_{a}^{*}\subseteq F_{a}\subseteq E(G_{a})$. Recall that node $a$ is adjacent
in $S$ to P-nodes only, and for every neighbor $b$ of $a$ in $S$, the set
$X_{b}$ corresponding to the node $b$ is a $2$-cutset in $G$ such that the two
vertices in $X_{b}$ are adjacent in $G_{a}$. We define
$F_{a}=\\{X_{b}:b\text{~{}is adjacent to~{}}a\text{~{}in~{}}S\\}$ and
$F_{a}^{*}=\\{e\in F_{a}:e\text{~{}is a virtual edge in~{}}G_{a}\\}$. Clearly,
$F_{a}$ and $F^{*}_{a}$ can be obtained in time $\mathcal{O}(d_{S}(a))$.

The second step relies on the following property of the sets $F^{*}_{a}$.

######  Claim 4.15.

For each R-node or S-node $a$ of $S$, the set $F^{*}_{a}$ is a
$\mathcal{G}$-safe set of edges of $G_{a}$.

###### Proof.

By Lemma 4.4, there exists a subdivision $G_{a}^{\prime}$ of $G_{a}$ that is
an induced subgraph of $G$. We want to show that deleting from $G_{a}$ any
subset of edges in $F_{a}^{*}$ results in a graph in $\mathcal{G}$. Since
every edge $e\in F_{a}^{*}$ is a virtual edge of $G_{a}$, the two endpoints of
$e$ are non-adjacent in $G$. Thus, the edges in $F_{a}^{*}$ correspond to a
collection of internally vertex-disjoint paths $\\{P_{e}:e\in F_{a}^{*}\\}$
such that each $P_{e}$ is an induced path of length at least two in
$H^{\prime}_{a}$ (and thus in $G$) connecting the endpoints of $e$. Consider
an arbitrary set $F\subseteq F_{a}^{*}$. Since $G_{a}^{\prime}$ is an induced
subgraph of $G$, each real edge in $G_{a}$ is also an edge in
$G_{a}^{\prime}$. It follows that the graph $G_{a}-F$ can be obtained from
$G_{a}^{\prime}$ by deleting the internal vertices of $P_{e}$ for all $e\in F$
and by contracting to a single edge each path $P_{e}$ for all $e\in
F_{a}^{*}\setminus F$. Hence, $G_{a}-F$ is an induced topological minor of
$G_{a}^{\prime}$ and thus of $G$. Since $G\in\mathcal{G}$ and $\mathcal{G}$ is
closed under induced topological minors, we have $G_{a}-F\in\mathcal{G}$, as
claimed. ∎

Step 2. We compute an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{a}=(T_{a},\\{(X^{a}_{t},U^{a}_{t}):t\in V(T_{a})\\})$
of $G[X_{a}]$ with residual independence number at most $\max\\{3-\ell,k\\}$
and an $F_{a}$-mapping of $\widehat{\mathcal{T}}_{a}$. We do so by computing
an $\ell$-refined tree decomposition of $G_{a}$. Since $G[X_{a}]$ is a
subgraph of $G_{a}$, the decomposition $\widehat{\mathcal{T}}_{a}$ is also an
$\ell$-refined tree decomposition of $G[X_{a}]$. We consider two cases
depending on whether $a$ is an S-node or an R-node of $S$.

  * •

If $a$ is an S-node of $S$, then $G_{a}$ is a cycle and we can apply a similar
approach as in Lemma 4.2. In time $\mathcal{O}(|V(G_{a})|)$ we compute a
cyclic order $v_{1},\ldots,v_{h}$ of the vertices of the cycle. We construct
the desired $\ell$-refined tree decomposition $\widehat{\mathcal{T}}_{a}$ of
$G_{a}$ as follows. The tree $T_{a}$ is an $(h-2)$-vertex path
$(t_{1},\ldots,t_{h-2})$; for each $i\in\\{1,\ldots,h-2\\}$, the bag
$X^{a}_{t_{i}}$ consists of vertices $\\{v_{i},v_{i+1},v_{h}\\}$, and
$U^{a}_{t_{i}}$ is any subset of $X^{a}_{t_{i}}$ with exactly
$\min\\{\ell,|X^{a}_{t_{i}}|\\}$ vertices. Note that every bag $X^{a}_{t}$ of
$\widehat{\mathcal{T}}_{a}$ has size $3$ and hence

$\alpha(G[X^{a}_{t}\setminus
U^{a}_{t}])\leq|X^{a}_{t}|-|U^{a}_{t}|\leq\max\\{3-\ell,0\\}\leq\max\\{3-\ell,k\\}\,.$

The corresponding $F_{a}$-mapping of $\widehat{\mathcal{T}}_{a}$ can be
obtained as follows. For each edge $e=v_{i}v_{i+1}\in F_{a}$ with $1\leq i\leq
h$ (indices modulo $h$), we do the following: if $1\leq i\leq h-2$, we map $e$
to $t_{i}\in V(T_{a})$; if $i=h-1$, we map $e$ to $t_{h-2}\in V(T_{a})$; and
if $i=h$, we map $e$ to $t_{1}\in V(T_{a})$. Clearly, both
$\widehat{\mathcal{T}}_{a}$ and the $F_{a}$-mapping can be obtained in
$\mathcal{O}(|V(G_{a})|)$ time.

  * •

Otherwise, $a$ is an R-node of $S$. Recall that $\mathcal{G}$ is closed under
induced topological minors. By Lemma 4.4, $G_{a}$ is an induced topological
minor of $G\in\mathcal{G}$, and thus $G_{a}$ belongs to $\mathcal{G}$. By
4.15, $F_{a}^{*}$ is a $\mathcal{G}$-safe set of edges of $G_{a}$. Since
$G_{a}$ is $3$-connected, by the assumption of the lemma, we can compute an
$F^{*}_{a}$-covering $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}_{a}$ of $G_{a}$ with residual independence number at
most $k$ and an $F_{a}$-mapping of $\widehat{\mathcal{T}}_{a}$ in time
$f(|V(G_{a})|,|E(G_{a})|)$. Let $t$ be a node of $\widehat{\mathcal{T}}_{a}$.
Since $U^{a}_{t}$ is an $F_{a}^{*}\\!$-cover of $G_{a}[X^{a}_{t}]$, every
virtual edge in $G_{a}[X^{a}_{t}]$ has an endpoint in $U^{a}_{t}$. We infer
that the subgraphs of $G$ and $G_{a}$ induced by the set $X^{a}_{t}\setminus
U^{a}_{t}$ are the same and thus,

$\alpha(G[X^{a}_{t}\setminus U^{a}_{t}])=\alpha(G_{a}[X^{a}_{t}\setminus
U^{a}_{t}])\leq\widehat{\alpha}(\widehat{\mathcal{T}}_{a})\leq
k\leq\max\\{3-\ell,k\\}\,.$

Step 3. This step consists in, informally speaking, replacing the node $a$ and
the bag $X_{a}$ in $\widehat{\mathcal{T}}$ by the newly computed
$\ell$-refined tree decomposition $\widehat{\mathcal{T}}_{a}$ of $G_{a}$. We
first compute the forest $T^{\prime}=(T-a)+T_{a}$ and then make $T^{\prime}$
connected by iterating over all neighbors $b$ of $a$ in $S$. Since every edge
of $S$ has exactly one endpoint which is a P-node and $a$ is not a P-node of
$S$, we infer that $b$ must be a P-node of $S$, and thus $X_{b}$ contains
exactly two vertices in $G$, which are adjacent in $G_{a}$. Let $e\in
E(G_{a})$ be the edge with endpoints in $X_{b}$. By the definition of $F_{a}$,
the edge $e$ belongs to $F_{a}$. Recall that an $F_{a}$-mapping of
$\widehat{\mathcal{T}}_{a}$ has been computed in Step 2. Hence, given the edge
$e$, the $F_{a}$-mapping of $\widehat{\mathcal{T}}_{a}$ returns, in constant
time, a node $c$ of the tree $T_{a}$ whose bag $X_{c}$ contains the endpoints
of $e$. We connect $b$ to $c$ in $T^{\prime}$. Notice that once all the
neighbors of $a$ have been considered, $T^{\prime}$ becomes a tree. We now set
$\widehat{\mathcal{T}}=(T^{\prime},\\{(X_{t},U_{t}):t\in
V(T-a)\\}\cup\\{(X^{a}_{t},U^{a}_{t}):u\in V(T_{a})\\})$. It is not difficult
to verify that after this modification, $\widehat{\mathcal{T}}$ remains an
$\ell$-refined tree decomposition of $G$. The time complexity of this step is
proportional to $\mathcal{O}(d_{S}(a)+|\widehat{\mathcal{T}}_{a}|)$.

We now reason about the overall time complexity of Steps 1–3 for a fixed
R-node or S-node $a$ of $S$. Recall that $N_{\text{R}}$ and $N_{\text{S}}$
denote the sets of R-nodes and S-nodes of $S$, respectively. Assume first that
$a\in N_{\text{S}}$. Then the complexity is
$\mathcal{O}(d_{S}(a)+|V(G_{a})|+|\widehat{\mathcal{T}}_{a}|)$. Since $G_{a}$
is a cycle and our construction of $\widehat{\mathcal{T}}_{a}$ implies that
$|\widehat{\mathcal{T}}_{a}|=\mathcal{O}(|V(G_{a})|)$, this simplifies to
$\mathcal{O}(d_{S}(a)+|V(G_{a})|)$. Assume now that $a\in N_{\text{R}}$. Then
the complexity is
$\mathcal{O}(d_{S}(a)+f(|V(G_{a})|,|E(G_{a})|)+|\widehat{\mathcal{T}}_{a}|)$,
which simplifies to $\mathcal{O}(d_{S}(a)+f(|V(G_{a})|,|E(G_{a})|))$ since
$f(|V(G_{a})|,|E(G_{a})|)\geq|\widehat{\mathcal{T}}_{a}|$.

By construction, the final $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}$ has residual independence number at most
$\max\\{3-\ell,k\\}$. The overall time complexity of the algorithm is

$\mathcal{O}\left(n+m+\sum_{a\in N_{\text{S}}}(d_{S}(a)+|V(G_{a})|)+\sum_{a\in
N_{\text{R}}}(d_{S}(a)+f(|V(G_{a})|,|E(G_{a})|))\right)\,,$

or, equivalently,

$\mathcal{O}\left(n+m+\sum_{a\in N_{\text{R}}\cup
N_{\text{S}}}d_{S}(a)+\sum_{a\in N_{\text{S}}}|V(G_{a})|+\sum_{a\in
N_{\text{R}}}f(|V(G_{a})|,|E(G_{a})|)\right)\,.$

Lemma 4.6 implies that $\sum_{a\in N_{\text{S}}}|V(G_{a})|\leq\sum_{a\in
N_{\text{R}}\cup N_{\text{S}}}|X_{a}|\leq 3n-6$. Furthermore, we know that
$\sum_{a\in N_{\text{R}}\cup N_{\text{S}}}d_{S}(a)=|E(S)|=\mathcal{O}(m)$
[54]. Since the function $f$ is superadditive, we have

$\sum_{a\in N_{\text{R}}}f(|V(G_{a})|,|E(G_{a})|)\leq f\left(\sum_{a\in
N_{\text{R}}}|V(G_{a})|,\sum_{a\in N_{\text{R}}}|E(G_{a})|\right)\,.$

By Lemma 4.6, we have that $\sum_{a\in N_{\text{R}}}|V(G_{a})|\leq 2n$.
Additionally, by Lemma 4.7 we get that $\sum_{a\in N_{\text{R}}}|E(G_{a})|\leq
3m$. Since $f$ is non-decreasing in each coordinate and $m\geq n$ as $G$ is
$2$-connected, the running time simplifies to
$\mathcal{O}\left(m+f(2n,3m)\right)$.

The number of nodes of $\widehat{\mathcal{T}}$ is at most

$|N_{\text{P}}|+\sum_{a\in N_{\text{S}}}(|V(G_{a})|-2)+\sum_{a\in
N_{\text{R}}}g(|V(G_{a})|,|E(G_{a})|)\,.$

Following the fact that $|N_{\text{P}}|\leq|V(S)|=\mathcal{O}(n)$ and by Lemma
4.6, we get that $|N_{\text{P}}|+\sum_{a\in
N_{\text{S}}}(|V(G_{a})|-2)=\mathcal{O}(n)$. Applying the same arguments as we
did for the function $f$ to the function $g$ shows that $\sum_{a\in
N_{\text{R}}}g(|V(G_{a})|,|E(G_{a})|)\leq g(2n,3m)$. Thus, the number of nodes
of $\widehat{\mathcal{T}}$ is of the order $\mathcal{O}(n+g(2n,3m))$. This
completes the proof. ∎

We now combine the reduction using block-cutpoint trees (given by Proposition
4.1) with the reduction using SPQR trees (given by Lemma 4.14) to derive the
main result of this section.

######  Theorem 4.16.

Let $\mathcal{G}$ be a graph class closed under induced topological minors for
which there exist nonnegative integers $k$ and $\ell$ such that $\mathcal{G}$
is $(k,\ell)$-tree decomposable and $(k,\ell)$-tree
Decomposition($\mathcal{G})$ can be solved in time $f(n,m)$ on graphs with $n$
vertices and $m$ edges so that the resulting $\ell$-refined tree decomposition
has $g(n,m)$ nodes, where $f$ and $g$ are superadditive functions. Then, for
any graph $G$ in $\mathcal{G}$ with $n\geq 1$ vertices and $m$ edges, one can
compute in time $\mathcal{O}(n+m+f(4n,3m))$ an $\ell$-refined tree
decomposition of $G$ with $\mathcal{O}(n+g(4n,3m))$ nodes and with residual
independence number at most $\max\\{3-\ell,k\\}$.

###### Proof.

By Lemma 4.14, there exist positive integers $c$ and $d$ such that for any
$2$-connected graph $G\in\mathcal{G}$ with $n$ vertices and $m$ edges, one can
compute in time $c\cdot(m+f(2n,3m))$ an $\ell$-refined tree decomposition of
$G$ with residual independence number at most $\max\\{3-\ell,k\\}$ and with
$d\cdot(n+g(2n,3m))$ nodes. Let $\hat{k}=\max\\{3-\ell,k\\}$ and let us define
two functions, $\hat{f}:\mathbb{Z}_{+}\times\mathbb{Z}_{+}\to\mathbb{Z}_{+}$
and $\hat{g}:\mathbb{Z}_{+}\times\mathbb{Z}_{+}\to\mathbb{Z}_{+}$, as follows:
for each $(x,y)\in\mathbb{Z}_{+}\times\mathbb{Z}_{+}$, we set
$\hat{f}(x,y)=c\cdot(y+f(2x,3y))$ and $\hat{g}(x,y)=d\cdot(x+g(2x,3y))$. Thus,
$\mathcal{G}$ is a hereditary graph class such that for each $2$-connected
graph $G$ in ${\mathcal{G}}$ with $n$ vertices and $m$ edges, one can compute
in time $\hat{f}(n,m)$ an $\ell$-refined tree decomposition
$\widehat{\mathcal{T}}$ with $\hat{g}(n,m)$ nodes and with residual
independence number at most $\hat{k}$. Furthermore, the fact that $f$ and $g$
are superadditive implies that $\hat{f}$ and $\hat{g}$ are superadditive. By
Proposition 4.1, for any graph $G$ in $\mathcal{G}$ with $n\geq 1$ vertices
and $m$ edges, one can compute in time $\mathcal{O}(n+m+\hat{f}(2n,m))$ an
$\ell$-refined tree decomposition of $G$ with $\mathcal{O}(n+\hat{g}(2n,m))$
nodes and with residual independence number at most
$\max\\{2-\ell,\hat{k}\\}=\max\\{3-\ell,k\\}$. Since
$\hat{f}(2n,m)=c\cdot(m+f(4n,3m))$ and $\hat{g}(2n,m)=c\cdot(n+g(4n,3m))$, the
theorem follows. ∎

##  5 $W_{4}$-induced-minor-free graphs

In this section and the next one, we apply Theorem 4.16 to prove that if
$\mathcal{G}$ is the class of $H$-induced-minor-free graphs for
$H\in\\{W_{4},K_{5}^{-}\\}$, then $\mathcal{G}$ has bounded and efficiently
witnessed tree-independence number. In fact, we show that $\mathcal{G}$ is
$(1,3)$-tree decomposable and develop a polynomial-time algorithm for the
$(1,3)$-tree Decomposition($\mathcal{G})$ problem. Combining this result with
Theorem 2.8 leads to an $\mathcal{O}(|V(G)|^{3})$ algorithm for the Max Weight
Independent Set problem for vertex-weighted graphs $G\in\mathcal{G}$.
Similarly, applying Theorem 2.4 leads to polynomial-time algorithms for the
Max Weight Independent Packing problem.

Since the $(k,\ell)$-tree Decomposition($\mathcal{G})$ problem deals with
$3$-connected graphs, we first need to characterize the $3$-connected graphs
in $\mathcal{G}$. We start with the $W_{4}$-induced-minor-free graphs.

$P$$Q$$u$$v$$w$$R$$H$ Figure 2: A schematic representation of the situation in
the proof of Lemma 5.1.

######  Lemma 5.1.

Let $G$ be a $3$-connected graph. Then $G$ is $W_{4}$-induced-minor-free if
and only if $G$ is chordal.

###### Proof.

First, let us assume that $G$ is a $3$-connected $W_{4}$-induced-minor-free
graph. Suppose that there exists an induced cycle $C$ of length at least $4$
in $G$. Since $G$ is $3$-connected, it cannot equal to $C$. Thus, there exists
a component $H$ of $G-V(C)$. Let $S$ be the set of vertices of $C$ that have a
neighbor in $H$. The $3$-connectedness of $G$ implies that $|S|\geq 3$. On the
other hand, $|S|\leq 3$, since otherwise we could contract $H$ into a single
vertex, delete all the other components, and contract some edges of $C$ to
obtain a $W_{4}$ as an induced minor of $G$. Thus, $|S|=3$. Since $C$ has
length at least $4$, there exists a pair $\\{u,v\\}$ of nonadjacent vertices
in $S$. Let $P$ and $Q$ be the two paths of the graph $C-\\{u,v\\}$. Note that
$P$ and $Q$ are both nonempty. Furthermore, one of the two paths $P$ and $Q$
does not contain any vertex from $S$. By symmetry, we may assume that
$V(P)\cap S=\emptyset$, that is, no vertex from $H$ has a neighbor in $P$. It
follows that the third neighbor of $H$ on $C$, call it $w$, belongs to $V(Q)$.
Since $G$ is $3$-connected, the graph $G-\\{u,v\\}$ is connected, and hence
contains a path from $V(P)$ to $V(Q)$. Let $R^{\prime}$ be a shortest path in
$G-\\{u,v\\}$ from $V(P)$ to $V(Q)$ and let $R$ be the subpath obtained by
deleting the endpoints of $R^{\prime}$. Note that since $C$ is an induced
cycle, the path $R$ is nonempty. Furthermore, since $w$ is the only vertex in
$Q$ with a neighbor in $H$, the path $R$ cannot contain any vertex of $H$ (see
Figure 2). We now derive a contradiction by showing that there exists an
induced minor model of $W_{4}$ in $G$. Let $X_{0}=V(Q)\cup V(R)$,
$X_{1}=\\{u\\}$, $X_{2}=V(P)$, $X_{3}=\\{v\\}$, and $X_{4}=V(H)$. Then
$X_{0},X_{1},\ldots,X_{4}$ are pairwise disjoint subsets of $V(G)$, each
inducing a connected subgraph, such that for each $i\in\\{1,2,3,4\\}$ there is
an edge in $G$ with one endpoint in $X_{0}$ and the other in $X_{i}$ as well
as an edge in $G$ with one endpoint in $X_{i}$ and the other in $X_{i+1}$
(with $X_{5}=X_{1}$), no edge in $G$ has one endpoint in $X_{1}$ and another
in $X_{3}$, and no edge in $G$ has one endpoint in $X_{2}$ and another in
$X_{4}$. Therefore, the sets $X_{0},X_{1},\ldots,X_{4}$ form an induced minor
model of $W_{4}$ in $G$, a contradiction.

For the other direction, assume that $G$ is a chordal graph. Suppose that $G$
contains $W_{4}$ as an induced minor. It follows that $G$ also contains
$C_{4}$ as an induced minor. But then, $G$ contains some cycle of length at
least four as an induced subgraph which is a contradiction with the assumption
that $G$ is chordal. ∎

By Lemma 5.1, every $3$-connected graph in the class $\mathcal{G}$ of
$W_{4}$-induced-minor-free graphs is chordal. To show that $\mathcal{G}$ is
$(1,3)$-tree decomposable and develop a linear-time algorithm for the
$(1,3)$-tree Decomposition($\mathcal{G})$ problem (Lemma 5.3), we need the
following concepts related to chordal graphs.

Let $G$ be a graph. A _vertex ordering_ of $G$ is a total order
$(v_{1},\ldots,v_{n})$ of its vertices. A _module_ in $G$ is a set $M\subseteq
V(G)$ such that every vertex not in $M$ that has a neighbor in $M$ is adjacent
to all vertices in $M$. A _moplex_ in $G$ is an inclusion-maximal module
$M\subseteq V(G)$ that is a clique and its neighborhood $N(M)$ is either empty
or a minimal separator in $G$. A _perfect moplex partition_ of $G$ is an
ordered partition $(M_{1},\ldots,M_{k})$ of $V(G)$ such that for all
$i\in\\{1,\ldots,k\\}$, $M_{i}$ is a moplex in the subgraph of $G$ induced by
$\cup_{j=i}^{k}M_{j}$. Given an ordered partition $\pi=(Z_{1},\ldots,Z_{k})$
of $V(G)$ and a vertex ordering $\sigma=(v_{1},\ldots,v_{n})$ of $G$, we say
that $\sigma$ is _compatible with_ $\pi$ if $v_{i}\in Z_{p}$, $v_{j}\in
Z_{q}$, and $p<q$ imply $i<j$. Berry and Bordat showed in [10] that every
graph has a moplex. Consequently, every graph has a perfect moplex partition.
A _perfect moplex ordering_ of $G$ is a vertex ordering compatible with a
perfect moplex partition. Using graph search algorithms such as Lexicographic
Breadth-First Search (LexBFS) [77] or Maximum Cardinality Search (MCS) [81],
one can compute in linear time a perfect moplex ordering of a given graph by
reversing the ordering returned by LexBFS or MCS (see [10, 14, 9]). The reader
may know the concept of _perfect elimination ordering_ ; it is easily observed
that every perfect moplex ordering is a perfect elimination ordering.

######  Lemma 5.2.

Let $G$ be a chordal graph with $n$ vertices and $m$ edges and $F\subseteq
E(G)$. Then one can compute in time $\mathcal{O}(n+m)$ a clique tree
$\mathcal{T}$ of $G$ with at most $n$ nodes and an $F$-mapping of
$\mathcal{T}$.

###### Proof.

Using LexBFS or MCS, we compute in linear time a perfect moplex ordering
$(v_{1},\ldots,v_{n})$ of $G$. Berry and Simonet gave in [11] a linear-time
algorithm that takes as input a connected chordal graph $G$ and a perfect
moplex ordering of $G$, and computes a clique tree ${\mathcal{T}}$ of $G$. We
explain the idea of their algorithm in terms of the perfect moplex partition
$(M_{1},\ldots,M_{k})$ of $G$ corresponding to the given perfect moplex
ordering. The bags of the computed clique tree $\mathcal{T}$ are the maximal
cliques of $G$, which are exactly the sets $X_{1},\ldots,X_{k}$ of the form
$X_{i}=N_{G_{i}}[M_{i}]$ for all $i\in\\{1,\ldots,k\\}$ where $G_{i}$ is the
subgraph of $G$ induced by $\cup_{j=i}^{k}M_{j}$. The algorithm processes the
moplexes in order from $M_{k}$ to $M_{1}$. It starts with a clique tree
$\mathcal{T}_{k}$ of $G_{k}$ with a tree containing a unique node $k$ and the
corresponding bag $X_{k}=M_{k}$. Then, for each $i=k-1,\ldots,1$, the
algorithm computes a clique tree $\mathcal{T}_{i}$ of $G_{i}$ from the clique
tree $\mathcal{T}_{i+1}$ of $G_{i+1}$ by adding to the tree of
${\mathcal{T}}_{i+1}$ a new node $i$ associated with bag $X_{i}$, and an edge
$(i,j)$ where $j$ is the smallest number in $\\{i+1,\ldots,k\\}$ such that
there is an edge in $G$ from $M_{i}$ to $M_{j}$. The final clique tree of
$G=G_{1}$ is given by ${\mathcal{T}}={\mathcal{T}}_{1}$.

We compute an $F$-mapping of ${\mathcal{T}}$ as follows. For each edge
$v_{i}v_{j}\in F$ such that $i<j$, we assign the edge $v_{i}v_{j}$ to the
unique node $p\in\\{1,\ldots,k\\}$ of $\mathcal{T}$ such that $v_{i}\in
M_{p}$. This can be done in time $\mathcal{O}(|F|)=\mathcal{O}(|E(G)|)$.

Let us justify that the so-defined mapping is indeed an $F$-mapping of
${\mathcal{T}}$. Consider an edge $v_{i}v_{j}\in F$ with $i<j$, and let $p$
and $q$ be the unique nodes of $\mathcal{T}$ such that $v_{i}\in M_{p}$ and
$v_{j}\in M_{q}$, respectively. Since the vertex ordering
$(v_{1},\ldots,v_{n})$ is compatible with the perfect moplex partition
$(M_{1},\ldots,M_{k})$, we have $p\leq q$. We need to show that $v_{i}$ and
$v_{j}$ both belong to $X_{p}=N_{G_{p}}[M_{p}]$. First, we have that $v_{i}\in
M_{p}\subseteq X_{p}$. Second, since $p\leq q$, we have $v_{j}\in V(G_{p})$
and thus $v_{j}$ is adjacent to $v_{i}$ in $G_{p}$. In particular, we have
$v_{j}\in N_{G_{p}}[M_{p}]$. Thus, $v_{i}v_{j}\subseteq X_{p}$, which is what
we wanted to show.

Let now $G$ be an arbitrary chordal graph with $n$ vertices and $m$ edges. The
above approach can be extended in a straightforward way to the case when $G$
is not connected, by computing the connected components and applying the above
algorithm to each component. The resulting forest of clique trees of the
components can be turned into a clique tree of $G$ by adding the appropriate
number of edges between the clique trees of the components. By construction,
the obtained clique tree ${\mathcal{T}}$ of $G$ has at most $n$ nodes. ∎

######  Lemma 5.3.

Let $\mathcal{G}$ be the class of $W_{4}$-induced-minor-free graphs. Then
$\mathcal{G}$ is $(1,3)$-tree decomposable and $(1,3)$-Tree
Decomposition($\mathcal{G}$) can be solved on graphs with $n$ vertices and $m$
edges in time $\mathcal{O}(n\cdot m)$ so that the resulting $3$-refined tree
decomposition with residual independence number at most $1$ has at most $n$
nodes.

###### Proof.

Let $G$ be a $3$-connected $W_{4}$-induced-minor-free graph with $n$ vertices
and $m$ edges and let $F^{*}\subseteq F\subseteq E(G)$ such that $F^{*}$ is
$\mathcal{G}$-safe. We want to compute an $F^{*}\\!$-covering $3$-refined tree
decomposition $\widehat{\mathcal{T}}$ of $G$ with
$\widehat{\alpha}(\widehat{\mathcal{T}})\leq 1$, together with an $F$-mapping
of $\widehat{\mathcal{T}}$.

By Lemma 5.1, $G$ is chordal. By Lemma 5.2, one can compute in linear time a
$0$-refined tree decomposition
$\widehat{\mathcal{T}}=(T,\\{(X_{t},U_{t})\\}_{t\in V(T)})$ of $G$ with
residual independence number $1$ having at most $n$ nodes and an $F$-mapping
of $\widehat{\mathcal{T}}$. Note that $\widehat{\mathcal{T}}$ already
satisfies all the desired properties, except that it may fail to be
$F^{*}\\!$-covering. To fix this, we next redefine the sets $U_{t}$ for all
$t\in V(T)$.

Let $t\in V(T)$. If $|X_{t}|\leq 4$, then we set $U_{t}$ to be any subset of
$\min\\{|X_{t}|,3\\}$ vertices of $X_{t}$. This in particular implies that
$|X_{t}\setminus U_{t}|\leq 1$, and hence $U_{t}$ is an $F^{*}\\!$-cover of
$G[X_{t}]$ of size at most $3$.

Now suppose that $|X_{t}|\geq 5$. Consider the set $L$ of all edges in $F^{*}$
that have both endpoints in $X_{t}$. We claim that any two edges in $L$ have a
common endpoint. Suppose that this is not the case, and let $e=uv$ and $f=xy$
be two disjoint edges in $L$. As $|X_{t}|\geq 5$, there exists a vertex $z$ in
$X_{t}$ distinct from any of $u,v,x,y$. Since $X_{t}$ is a clique in $G$, the
subgraph $H$ of $G$ induced by $\\{u,v,x,y,z\\}$ is isomorphic to $K_{5}$, and
thus $H-\\{e,f\\}$ is isomorphic to $W_{4}$. This implies that $G-\\{e,f\\}$
is not $W_{4}$-induced-minor-free. However, since $\\{e,f\\}\subseteq
L\subseteq F^{*}$, this is a contradiction with the fact that $F^{*}$ is
$\mathcal{G}$-safe.

If $L=\emptyset$, we set $U_{t}=\emptyset$. Otherwise, we choose an arbitrary
edge $e=xy\in L$ and set $U_{t}=\\{x,y\\}$. Such a set $U_{t}$ can be computed
in time $\mathcal{O}(|X_{t}|\cdot|F^{*}|)=\mathcal{O}(n\cdot m)$, by iterating
over the edges in $F^{*}$ and checking whether their endpoints both belong to
$X_{t}$. Note that since any two edges in $L$ have a common endpoint, all
edges of the graph $G[X_{t}\setminus U_{t}]$ are in $E(G)\setminus F^{*}$, and
thus $U_{t}$ is an $F^{*}\\!$-cover of $G[X_{t}]$ of size at most $2$. ∎

Theorems 4.16 and 5.3 imply the following.

######  Theorem 5.4.

For any $W_{4}$-induced-minor-free graph $G$ with $n$ vertices and $m$ edges,
one can compute in time $\mathcal{O}(n\cdot m)$ a $3$-refined tree
decomposition of $G$ with $\mathcal{O}(n)$ nodes and residual independence
number at most $1$.

###### Proof.

The class of $W_{4}$-induced-minor-free graphs is closed under induced
topological minors, and Lemma 5.3 shows that Theorem 4.16 is satisfied with
$k=1$ and $\ell=3$, $f(n,m)=\mathcal{O}(n\cdot m)$, and $g(n,m)=n$. Therefore,
given a $W_{4}$-induced-minor-free graph $G$ with $n$ vertices and $m$ edges,
Theorem 4.16 implies that one can compute an $\ell$-refined tree decomposition
of $G$ with $\mathcal{O}(n)$ nodes and with residual independence number at
most $\max\\{3-\ell,k\\}=1$ in time $\mathcal{O}(n+m+f(4n,3m))$, which is
$\mathcal{O}(n\cdot m)$. ∎

######  Remark 5.5.

The algorithm for computing a $3$-refined tree decomposition of a
$W_{4}$-induced-minor-free graph can be turned into a polynomial-time robust
algorithm, as follows. First, after we compute the SPQR tree $S$ of a given
graph $G$, we check for every $R$-node $a$ if the corresponding graph $G_{a}$
in $S$ is a chordal graph. If this is not the case, the algorithm returns that
the graph does not belong to the class of $W_{4}$-induced-minor-free graphs.
This check can be done in linear time. Assume now that each graph $G_{a}$
corresponding to an $R$ node $a$ of $S$ is chordal. Then, once we compute a
clique tree $\mathcal{T}$ of $G_{a}$, we check for each bag $X$ of
$\mathcal{T}$ if the graph $G[X]$ contains an independent set of size $5$,
which can be checked in polynomial time. If some graph $G[X]$ contains an
independent set of size $5$, then the algorithm returns that $G$ is not in the
class of $W_{4}$-induced-minor-free graphs; otherwise, the algorithm correctly
computes a $3$-refined tree decomposition of $G$ with residual independence
number at most $1$. $\blacktriangle$

In the first paper of the series [37] we established
$(\mathrm{tw},\omega)$-boundedness of the class of $W_{4}$-induced-minor-free
graphs, although without an explicit binding function. Lemmas 2.11 and 5.4
imply that the class of $W_{4}$-induced-minor-free graphs admits a linear
$(\mathrm{tw},\omega)$-binding function $f(p)=R(p+1,2)+3-2=p+2$. Furthermore,
our approach leading to the proof of Theorem 5.4 can be used to show,
additionally, that if $G$ is a $W_{4}$-induced-minor-free graph, then the
inequality $\mathrm{tw}(G)\geq\eta(G)-1$, which holds for all graphs, is
satisfied with equality. Indeed, assuming that $G$ is $2$-connected, the proof
of Theorem 5.4 provides a tree decomposition of $G$ obtained from tree
decompositions of graphs $G_{a}$ over all R- and S-nodes $a$ of a fixed SPQR
tree of $G$. Using the structure of the corresponding graphs $G_{a}$, it can
be verified that the constructed tree decompositions are only composed of bags
with at most $\eta(G_{a})$ vertices. Applying Corollary 4.5 then shows that
the overall tree decomposition only contains bags with at most $\eta(G)$
vertices.

######  Proposition 5.6.

If $G$ is a $W_{4}$-induced-minor-free graph, then $\mathrm{tw}(G)=\eta(G)-1$.

Let us emphasize that for general classes of $H$-induced-minor-free graphs
where $H$ is planar, only the existence of a function bounding the treewidth
in terms of the Hadwiger number is known (see [7, 19, 85]).

By Theorem 5.4, every $W_{4}$-induced-minor-free graph $G$ satisfies the
inequality $3$-$\mathsf{tree}\textnormal{-}\alpha(G)\leq 1$. Using 2.7 we thus
obtain the following.

######  Corollary 5.7.

The tree-independence number of any $W_{4}$-induced-minor-free graph is at
most $4$.

######  Remark 5.8.

The bound on the tree-independence number given by Corollary 5.7 is sharp:
there exist arbitrarily large $2$-connected $W_{4}$-induced minor-free graphs
with tree-independence number $4$. Take an integer $q\geq 4$ and let $F_{q}$
be the graph obtained from a complete graph with vertex set $S=\\{1,2,3,4\\}$
by replacing each of its edges $ij$ with $q$ paths of length two connecting
$i$ and $j$. Note that $F_{q}$ has exactly $4$ vertices of degree more than
two. Neither deleting vertices nor contracting edges having an endpoint of
degree at most two can increase the number of vertices of degree more than
two. It follows that every induced minor of $F_{q}$ has at most $4$ vertices
of degree more than two. Since the graph $W_{4}$ has $5$ vertices and minimum
degree $3$, we infer that $F_{q}$ is $W_{4}$-induced-minor-free, and hence
$\mathsf{tree}\textnormal{-}\alpha(F_{q})\leq 4$ by Theorem 5.4. To see that
the inequality is satisfied with equality, it suffices to show that
$\mathsf{tree}\textnormal{-}\alpha(F_{4})\geq 4$. But this was already
observed in the proof of [36, Theorem 3.8]. $\blacktriangle$

Theorems 5.4 and 2.8 imply the existence of a polynomial-time algorithm for
the Max Weight Independent Set problem in the class of $W_{4}$-induced-minor-
free graphs.

######  Corollary 5.9.

The Max Weight Independent Set problem can be solved in time
$\mathcal{O}(n^{3})$ for $n$-vertex $W_{4}$-induced-minor-free graphs.

######  Remark 5.10.

By applying Corollary 2.9 instead of Theorem 2.8, one could also use usual
tree decompositions instead of $\ell$-refined ones. However, this approach
would only lead to a running time of $\mathcal{O}(n^{6})$ instead of
$\mathcal{O}(n^{3})$. $\blacktriangle$

Furthermore, since a $3$-refined tree decomposition with residual independence
number at most $1$ has independence number at most $4$, Theorems 5.4 and 2.4
imply the existence of a polynomial-time algorithm for the Max Weight
Independent Packing problems in the class of $W_{4}$-induced-minor-free
graphs.

######  Theorem 5.11.

Given a $W_{4}$-induced-minor-free graph $G$ and a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected nonnull subgraphs of $G$, the
Max Weight Independent Packing problem can be solved in time
$\mathcal{O}(|J|\cdot|V(G)|\cdot(|V(G)|+|J|^{4}))$.

###### Proof.

Let $G$ be an $n$-vertex $W_{4}$-induced-minor-free graph, given along with a
finite family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected nonnull
subgraphs and a weight function $w:J\to\mathbb{Q}_{+}$. By Theorems 5.4 and
2.7, we can compute in time $\mathcal{O}(n^{3})$ a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$ with $\mathcal{O}(n)$ nodes
and with independence number at most $4$. The conclusion now follows from
Theorem 2.4. ∎

######  Remark 5.12.

Cameron and Hell showed in [22] that if $G$ is a chordal graph, then for every
nonempty family $\mathcal{F}$ of connected graphs, the derived graph
$G(\mathcal{H})$ where $\mathcal{H}=\mathcal{H}(G,\mathcal{F})$ is chordal.
One may wonder whether a similar statement holds for the more general class of
$W_{4}$-induced-minor-free graphs. This would be algorithmically interesting
as it would imply the existence of an $\mathcal{O}(n^{3r})$ algorithm for the
Max Weight Independent $\mathcal{F}$-Packing problem for $n$-vertex
$W_{4}$-induced-minor-free graphs, where $r$ is the maximum order of a graph
in $\mathcal{F}$, a significant improvement of the $\mathcal{O}(n^{5r+1})$
time complexity following from Theorem 5.11.444We could compute in time
$\mathcal{O}(n^{2r})$ the graph $G(\mathcal{H})$ (as in the proof of [36,
Theorem 7.3]), which has $\mathcal{O}(n^{r})$ vertices, and if this graph is
$W_{4}$-induced-minor-free, Corollary 5.9 applies and leads to an
$\mathcal{O}(n^{3r})$ algorithm for the Max Weight Independent
$\mathcal{F}$-Packing problem on $G$. Unfortunately, this statement is in
general not true, as the following example shows. Let
$\mathcal{F}=\\{K_{2}\\}$ and let $G$ be the $6$-cycle. Then $G$ is
$W_{4}$-induced-minor-free. However, the graph $G(\mathcal{H})$ obtained with
$\mathcal{H}=\mathcal{H}(G,\mathcal{F})$, that is, the square of the line
graph of $G$, has the property that deleting any one vertex from it results in
a graph isomorphic to $W_{4}$. $\blacktriangle$

##  6 $K_{5}^{-}$-induced-minor-free graphs

We now apply the approach outlined at the beginning of Section 5 to the case
of $K_{5}^{-}$-induced-minor-free graphs. As before, we start with
characterizing the $3$-connected graphs in the class. Recall that a _wheel_ is
any graph $W_{n}$ obtained from a cycle $C_{n}$, $n\geq 4$, by adding to it a
universal vertex. Our proof makes use of the following classical result on
$3$-connected graphs.

######  Theorem 6.1 (Tutte [82]).

Every $3$-connected graph with at least $5$ vertices has an edge whose
contraction results in a $3$-connected graph.

######  Theorem 6.2.

For every graph $G$, the following statements are equivalent.

  1. 1.

$G$ is $3$-connected and $K_{5}^{-}$-induced-minor-free.

  2. 2.

$G$ is either a complete graph with at least four vertices, a wheel, $K_{3,3}$
or $\overline{C_{6}}$.

###### Proof.

It is straightforward to verify that if $G$ is either a complete graph $K_{n}$
with $n\geq 4$, a wheel, $G\cong K_{3,3}$, or $G\cong\overline{C_{6}}$, then
$G$ is $3$-connected and $K_{5}^{-}$-induced-minor-free.

We prove the converse direction using induction on $n=|V(G)|$. So let $G$ be a
$3$-connected $K_{5}^{-}$-induced-minor-free graph. Since $G$ is
$3$-connected, $n\geq 4$, and if $n=4$, then $G$ is complete since otherwise
it would contain a vertex of degree at most two. Suppose that $n\geq 5$. By
Theorem 6.1, $G$ has an edge $e=uv$ whose contraction results in a
$3$-connected graph $G^{\prime}$. Since $G^{\prime}$ is also
$K_{5}^{-}$-induced-minor-free, the induction hypothesis implies that
$G^{\prime}$ is either a complete graph, a wheel, $G^{\prime}\cong K_{3,3}$,
or $G^{\prime}\cong\overline{C_{6}}$. We analyze each of the four cases
separately.

_Case 1: $G^{\prime}$ is a complete graph._
In this case, $N_{G}(u)\cup N_{G}(v)=V(G)\setminus\\{u,v\\}$. Let
$a=|N_{G}(u)\setminus N_{G}(v)|$, $b=|N_{G}(u)\cap N_{G}(v)|$, and
$c=|N_{G}(v)\setminus N_{G}(u)|$. If $a=c=0$, then $G$ is complete. We may
thus assume by symmetry that $a>0$. If $b\geq 2$, then any two vertices from
$N_{G}(u)\cap N_{G}(v)$, along with $u$, $v$, and a vertex from
$N_{G}(u)\setminus N_{G}(v)$, would induce a subgraph of $G$ isomorphic to
$K_{5}^{-}$, a contradiction. Thus $b\leq 1$. Since $G$ is $3$-connected, we
have $d_{G}(v)\geq 3$ and hence $c=d_{G}(v)-(b+1)\geq 2-b>0$. If $a=c=1$, then
the $3$-connectedness of $G$ implies that $b=1$, and $G$ is isomorphic to
$W_{4}$. We may thus assume by symmetry that $a\geq 2$. If $b=1$, then any two
vertices from $N_{G}(u)\setminus N_{G}(v)$, along with $u$, a vertex from
$N_{G}(u)\cap N_{G}(v)$, and a vertex from $N_{G}(v)\setminus N_{G}(u)$, form
an induced subgraph of $G$ isomorphic to $K_{5}^{-}$, a contradiction. Thus
$b=0$ and consequently $c=d_{G}(v)-1\geq 2$. But now, the graph obtained from
the subgraph $H$ of $G$ induced by $u$, $v$, any two vertices from
$N_{G}(u)\setminus N_{G}(v)$, and any two vertices from $N_{G}(v)\setminus
N_{G}(u)$ by contracting an edge from $u$ to one of the vertices in
$V(H)\cap(N_{G}(u)\setminus N_{G}(v))$ is isomorphic to $K_{5}^{-}$, a
contradiction.

_Case 2: $G^{\prime}$ is a wheel $W_{n-2}$ with $n\geq 6$._
Let $x$ be the universal vertex in $G^{\prime}$ and let $C$ be the cycle
$G^{\prime}-x$, with a cyclic order of the vertices $v_{1},\ldots,v_{n-2}$. We
analyze two subcases depending on whether the vertex $w$ of $G^{\prime}$ to
which the edge $uv$ was contracted corresponds to $x$, the central vertex of
the wheel, or not.

_Case 2.1: $w=x$._
In this case, $V(C)\subseteq N_{G}(u)\cup N_{G}(v)$. Since $G$ is
$3$-connected, each of $u$ and $v$ has at least two neighbors on $C$. Suppose
first that each of $u$ and $v$ has only two neighbors on $C$. Since $C$ has at
least four vertices, the neighborhoods of $u$ and $v$ on $C$ are disjoint.
Thus $|V(C)|=4$ and $G$ is either $\overline{C_{6}}$ or $K_{3,3}$, depending
on whether the two neighbors of $u$ on $C$ are adjacent or not. We may thus
assume that one of $u$ and $v$, say $v$, has at least three neighbors on $C$.
If $u$ and $v$ are both adjacent to three consecutive vertices on $C$, say
$v_{j},v_{j+1},v_{j+2}$ (indices modulo $n-2$), then the subgraph of $G$
induced by $\\{u,v,v_{j},v_{j+1},v_{j+2}\\}$ is isomorphic to $K_{5}^{-}$, a
contradiction. Thus, we may assume in particular that $u$ is not adjacent to
$v_{1}$, and, consequently, $v$ is adjacent to $v_{1}$. Let $v_{i}$ and
$v_{j}$ be the two neighbors of $u$ on $C$ such that $i$ is as small as
possible and $j$ is as large as possible. Then $1<i<j\leq n-2$. Now, if $v$
has a neighbor in $\\{v_{2},\ldots,v_{j-1}\\}$ and a neighbor in
$\\{v_{j},\ldots,v_{n-2}\\}$, then contracting in $G$ all the edges of the
paths $(v_{2},v_{3},\ldots,v_{j-1})$ and $(v_{j},v_{j+1},\ldots,v_{n-2})$