# Tree decompositions with bounded independence number:
beyond independent sets

Martin Milanič
FAMNIT and IAM, University of Primorska, Koper, Slovenia
<EMAIL_ADDRESS>
Paweł Rzążewski
Warsaw University of Technology and University of Warsaw, Poland
<EMAIL_ADDRESS>
###### Abstract

We continue the study of graph classes in which the treewidth can only be
large due to the presence of a large clique, and, more specifically, of graph
classes with bounded tree-independence number. In [Dallard, Milanič, and
Štorgel, Treewidth versus clique number. II. Tree-independence number, 2022],
it was shown that the Maximum Weight Independent Packing problem, which is a
common generalization of the Independent Set and Induced Matching problems,
can be solved in polynomial time provided that the input graph is given along
with a tree decomposition with bounded independence number. We provide further
examples of algorithmic problems that can be solved in polynomial time under
this assumption. This includes, for all even positive integers $d$, the
problem of packing subgraphs at distance at least $d$ (generalizing the
Maximum Weight Independent Packing problem) and the problem of finding a large
induced sparse subgraph satisfying an arbitrary but fixed property expressible
in counting monadic second-order logic. As part of our approach, we generalize
some classical results on powers of chordal graphs to the context of general
graphs and their tree-independence numbers.

##  1 Introduction

Structured graph decompositions and the corresponding graph width parameters
have become one of the central tools for dealing with algorithmically hard
graph problems. One of the most well-known and well-studied graph width
parameters is the _treewidth_ of a graph, which, roughly speaking, measures
how similar the graph is to a tree. Since graphs of bounded treewidth are
necessarily sparse, several generalizations of treewidth were proposed in the
literature that allow for families of dense graphs, including clique-width,
rank-width, Boolean-width, mim-width, and twin-width. A common feature of all
these parameters is that when the parameter of the input graph is bounded by a
fixed constant, efficient dynamic programming algorithms can be developed for
various graph problems, typically applied along some hierarchical
decomposition of the graph into simpler parts (see, e.g., [4, 18, 34, 12, 8,
9, 11, 20], as well as the algorithmic metatheorems [3, 6, 13, 18]).

Another generalization of bounded treewidth that allows for families of dense
graphs is given by the concept of _$(\mathrm{tw},\omega)$ -boundedness_, a
property of a graph class meaning that the treewidth of graphs in the class
can only be large due to the presence of a large clique, and the same is true
for all induced subgraphs of graphs in the class. While this property is known
to imply some good algorithmic properties related to clique and coloring
problems (see [16, 15, 22, 25, 23]), it is an interesting question whether
$(\mathrm{tw},\omega)$-boundedness has any other algorithmic implications, in
particular, for problems related to independent sets. This question was
partially answered by Dallard, Milanič, and Štorgel, who initiated a
systematic investigation of $(\mathrm{tw},\omega)$-bounded graph classes (see
[25, 22], as well as [23, 24]). In particular, in [23] a sufficient condition
was identified 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. These results were obtained using the notion of _tree-
independence number_ , a graph invariant related to tree decompositions, which
is defined similarly to treewidth but aims at minimizing the maximum size of
an _independent_ set of vertices contained in a bag of a tree decomposition—as
opposed to an arbitrary set of vertices, which is the case for treewidth.

Ramsey’s theorem implies that every graph class with bounded tree-independence
number is $(\mathrm{tw},\omega)$-bounded. As shown in [24], the converse
implication is known to hold in graph classes defined by excluding a single
graph with respect to any of six well-known graph containment relations (the
subgraph, topological minor, and minor relations, as well as their induced
variants). In general, it is not known whether the two concepts are
equivalent; it is conjectured that they are [24]. The main algorithmic result
from [23] states 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. (The precise definition of the
problem and the result statement will be given in Section 2.) Several
questions regarding the computation of tree-independence number left open by
the work [23] were resolved in a subsequent work by Dallard et al. [21], where
the following results were obtained. First, it was shown that the exact
computation of the tree-independence number is para-NP-hard, more precisely,
that for every $k\geq 4$ it is NP-complete to determine if a given graph has
tree-independence number at most $k$. Second, a polynomial-time algorithm was
developed for computing a tree decomposition with bounded independence number,
whenever one exists. Given an $n$-vertex graph $G$ and an integer $k$, in time
$2^{\mathcal{O}(k^{2})}n^{\mathcal{O}(k)}$ the algorithm either outputs a tree
decomposition of $G$ with independence number at most $8k$, or determines that
the tree-independence number of $G$ is larger than $k$.

Combined with the results from [23], it follows that the Max Weight
Independent Packing problem is polynomial-time solvable in any class of graphs
with bounded tree-independence number. Thus, boundedness of the tree-
independence number is an algorithmically useful refinement of
$(\mathrm{tw},\omega)$-boundedness that is still general enough to capture a
wide variety of families of graph classes, including, among others, graph
classes of bounded treewidth, graph classes of bounded independence number,
and intersection graphs of connected subgraphs of graphs with bounded
treewidth (see [23, Theorem 3.12]).

In this paper, we provide further examples for algorithmic usefulness of
bounded tree-independence number.

###  1.1 Our results and relation to previous work

We obtain two main sets of results.

First, we generalize the polynomial-time solvability of the Max Weight
Independent Packing problem in classes of graphs equipped with a tree
decomposition with bounded tree-independence number from [23] to the problem
of packing subgraphs at distance $d$, for all even positive integers $d$. The
case $d=2$ corresponds to the result from [23]. Unless
$\textsf{P}=\textsf{NP}$, this result does not generalize to odd values of
$d$, since the distance-$3$ variant of the Independent Set problem is NP-hard
for chordal graphs, which have tree-independence number at most one.

We obtain this algorithmic result by proving a structural result on tree-
independence number that may be of interest on its own. Given a graph $G$ and
a positive integer $k$, we denote by $G^{k}$ the _$k$ -th power_ of $G$, that
is, the graph obtained from the graph $G$ by adding to it all edges between
pairs of vertices at distance at most $k$. We show that for any graph $G$ and
any positive integer $k$, the tree-independence number of the graph $G^{k+2}$
cannot exceed that of the graph $G^{k}$. This is a significant generalization
of a result of Duchet [26], who proved the same result for the case when
$G^{k}$ is a chordal graph (that is, when $G^{k}$ has tree-independence number
at most one). As a consequence, we obtain that for every positive integer $k$,
the class of graphs with tree-independence number at most $k$ is closed under
taking odd powers, which generalizes the analogous result for the class of
chordal graphs proved by Balakrishnan and Paulraja [5]. We complement this
result by observing that the class of even powers of chordal graphs (for any
fixed power) is not contained in any nontrivial hereditary graph class. This
implies in particular that any such class is $(\mathrm{tw},\omega)$-unbounded
and has unbounded tree-independence number.

Our second set of results is an algorithmic metatheorem for graphs equipped
with a tree decomposition with bounded independence number. It deals with the
problem of finding a large induced subgraph of bounded chromatic number,
satisfying an arbitrary but fixed property expressible in Counting Monadic
Second-Order logic ($\mathsf{CMSO}_{2}$). This far-reaching generalization of
Max Weight Independent Set goes along the lines of analogous results proven in
various settings, e.g., for bounded-treewidth graphs [17], for graphs with
polynomially many _potential maximal cliques_ [28], or for graphs with no long
induced cycles [1, 31]. An astute reader might notice that usually such
problems concern finding large _sparse_ subgraphs, which typically means
bounded treewidth [28, 1] or degeneracy [31]. However, it is straightforward
to observe that in classes of bounded tree-independence number treewidth is
bounded by a linear function of the chromatic number. Note that this is far
from the truth in general graphs; consider, e.g., large complete bipartite
graphs.

Some examples of problems that can be solved in polynomial time with this
approach include

  * •

finding the largest induced forest (which is equivalent to Min Feedback Vertex
Set),

  * •

finding the largest induced bipartite subgraph (which is equivalent to Min Odd
Cycle Transversal),

  * •

finding the largest induced planar subgraph (which is equivalent to
Planarization),

  * •

finding the maximum number of pairwise disjoint and non-adjacent cycles,

  * •

given a graph whose every vertex $v$ is equipped with a list
$L(v)\subseteq\\{1,\ldots,r\\}$ for constant $r$, finding a largest induced
subgraph that admits a proper $r$-coloring respecting lists $L$.

We point out that the bound on the chromatic number of the subgraph we are
looking for must be constant. Indeed, Coloring is NP-hard in graphs with tree-
independence number 2, and List Coloring is NP-hard in graphs with tree-
independence number 1 (i.e., chordal graphs).

###  1.2 Organization of the paper

In Section 2, we provide the necessary preliminaries. In Section 3, we
consider the tree-independence number in the context of graph powers, and
develop algorithmic implications of the structural results for the problem of
packing connected subgraphs at even distance. In Section 4, we develop a
general theorem about polynomial-time solvability of the problem of finding a
large induced subgraph of small chromatic number satisfying an arbitrary but
fixed property expressible in $\mathsf{CMSO}_{2}$ logic, provided that the
input graph is equipped with a tree decomposition with bounded independence
number.

##  2 Preliminaries

For an integer $n$, by $[n]$ we denote the set $\\{1,\ldots,n\\}$. Let $G$ be
a graph. For a set $X\subseteq V(G)$, by $G[X]$ we denote the subgraph of $G$
induced by $X$. A _clique_ in a graph $G$ is a set of pairwise adjacent
vertices; an _independent set_ is a set of pairwise non-adjacent vertices.

The _distance_ between two vertices $u$ and $v$ in $G$ is denoted by
$\textsf{dist}_{G}(u,v)$ and defined as the length of a shortest path between
$u$ and $v$ (or $\infty$ if there is no $u$-$v$-path in $G$). Given a positive
integer $k$, the _$k$ -th power_ of $G$ is the graph $G^{k}$ with vertex set
$V$, in which two distinct vertices $u$ and $v$ are adjacent if and only if
$\textsf{dist}_{G}(u,v)\leq k$. Note that $G^{1}=G$.

A graph is _chordal_ if it does not contain any induced cycles of length at
least four. A graph is _split_ if it admits a partition of the vertex set into
a clique and an independent set. It is known (and easy to see) that every
split graph is a chordal graph.

#### Tree decompositions and tree-independence number.

A _tree decomposition_ of a graph $G$ is a pair
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ where $T$ is a tree and every node
$t$ of $T$ is assigned a vertex subset $X_{t}\subseteq V(G)$ called a _bag_
such that the following conditions are satisfied: every vertex 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 of $T$ induced by the set $\\{t\in V(T):u\in X_{t}\\}$ is connected
(that is, a tree).

Usually we consider tree decompositions to be rooted. For a node $t$ of $T$,
by $T_{t}$ we denote the subtree of $T$ rooted at $t$, and by $G_{t}$ we
denote the subgraph of $G$ induced by $\bigcup_{t^{\prime}\in
V(T_{t})}X_{t^{\prime}}$. A rooted tree decomposition
$\mathcal{T}=(T,\\{X\\}_{t\in V(T)})$ of a graph $G$ is _nice_ if each node
$t$ is of one of the following types:

leaf

a leaf in the decomposition tree such that $|X_{t}|=1$,

introduce

an inner node with a single child $t^{\prime}$, such that
$X_{t}=X_{t^{\prime}}\cup\\{v\\}$ for some $v\in V(G)\setminus
X_{t^{\prime}}$,

forget

an inner node with a single child $t^{\prime}$, such that
$X_{t}=X_{t^{\prime}}\setminus\\{v\\}$ for some $v\in X_{t^{\prime}}$,

join

an inner node with exactly two children $t^{\prime},t^{\prime\prime}$, such
that $X_{t}=X_{t^{\prime}}=X_{t^{\prime\prime}}$.

It is well known that given a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$, one can obtain in polynomial
time a nice tree decomposition
$\mathcal{T}^{\prime}=(T^{\prime},\\{X^{\prime}t\\}_{t\in V(T^{\prime})})$ of
$G$ with at most $\max_{t\in V(T)}|X_{t}|\cdot|V(G)|$ nodes and whose every
bag is contained in some bag of $\mathcal{T}$ (see, e.g., the textbook [19],
or [23] for a treatment focused on the independence number).

Consider a graph $G$ and a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$. The _independence number_ of
$\mathcal{T}$, denoted by $\alpha(\mathcal{T})$, is defined as follows:

$\alpha(\mathcal{T})=\max_{t\in V(T)}\alpha(G[X_{t}])\,.$

Note that if $\mathcal{T}$ and $\mathcal{T}^{\prime}$ are tree decompositions
such that every bag of $\mathcal{T}^{\prime}$ is contained in some bag of
$\mathcal{T}$ (in particular, if $\mathcal{T}^{\prime}$ is a nice tree
decomposition obtained from $\mathcal{T}$), then we have
$\alpha(\mathcal{T}^{\prime})\leq\alpha(\mathcal{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$. A graph $G$ is _chordal_ if it
has no induced subgraphs isomorphic to a cycle of length at least four. A
graph $G$ is chordal if and only if $\mathsf{tree}\textnormal{-}\alpha(G)\leq
1$ (see [23]).

#### Independent packing of subgraphs.

Given a graph $G$ and a family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of 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. This construction was considered by Cameron and Hell in [14], who
focused on the particular case when $\mathcal{H}$ is the set of all subgraphs
of $G$ isomorphic to a member of a fixed family $\mathcal{F}$ of connected
graphs; they showed that if $G$ is a chordal graph, then so is
$\mathcal{H}(G)$. Dallard et al. generalized this result as follows.

######  Lemma 2.1 (Dallard et al. [23]).

Let $G$ be a graph, let $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be a tree
decomposition of $G$, and let $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ be a finite
family of connected non-null subgraphs of $G$. Then
$\mathcal{T}^{\prime}=\big{(}T,\\{X^{\prime}_{t}\\}_{t\in V(T)}\big{)}$ with
$X^{\prime}_{t}=\\{j\in J:V(H_{j})\cap X_{t}\neq\emptyset\\}$ for all $t\in
V(T)$ is a tree decomposition of $G(\mathcal{H})$ such that
$\alpha(\mathcal{T}^{\prime})\leq\alpha(\mathcal{T})$.

Let us now explain the main algorithmic result related to packing subgraphs
from [23]. Given a graph $G$ and a family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$
of subgraphs of $G$, 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, in other words, if $\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 $\mathfrak{w}:J\to\mathbb{Q}_{+}$ assigning
weight $\mathfrak{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}\mathfrak{w}_{i}$. In particular, the weight of any independent
$\mathcal{H}$-packing is well-defined. Given a graph $G$, a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null subgraphs of $G$, and
a weight function $\mathfrak{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.

When $\mathcal{H}$ is the set of all subgraphs of $G$ isomorphic to a member
of a fixed family $\mathcal{F}$ of connected graphs, the problem coincides
with the Max Weight Independent $\mathcal{F}$-Packing problem studied in
Dallard et al. [23]. This latter problem in turn generalizes several problems
studied in the literature, including the Independent $\mathcal{F}$-Packing
problem (see [14]), which corresponds to the unweighted case, the Max Weight
Independent Set problem, which corresponds to the case
$\mathcal{F}=\\{K_{1}\\}$, the Max Weight Induced Matching problem (see, e.g.,
[2, 38]), which corresponds to the case $\mathcal{F}=\\{K_{2}\\}$, and the
Dissociation Set problem (see, e.g., [40, 39, 37]), which corresponds to the
case when $\mathcal{F}=\\{K_{1},K_{2}\\}$ and the weight function assigns to
each subgraph $H_{j}$ the weight equal to $|V(H_{j})|$, and the $k$-Separator
problem (see, e.g., [35, 36, 7]), which corresponds to the case when
$\mathcal{F}$ contains all connected graphs with at most $k$ vertices, the
graph $G$ is equipped with a vertex weight function
$\mathfrak{w}:V(G)\to\mathbb{Q}_{+}$, and the weight function on $\mathcal{H}$
assigns to each subgraph $H_{j}$ the weight equal to $\sum_{x\in
V(H_{j})}\mathfrak{w}(x)$.

Dallard et al. showed in [23] that the Max Weight Independent Packing problem
can be solved in polynomial time for graphs equipped with a tree decomposition
with bounded independence number.

######  Theorem 2.2 (Dallard et al. [23]).

Fix an integer $k\geq 1$. 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$.

##  3 Packing subgraphs at even distance

Given a positive integer $d$, a _distance- $d$ independent set_ in a graph $G$
is a set of vertices at pairwise distance at least $d$, that is, an
independent set in the graph $G^{d-1}$. The Distance-$d$ Independent Set
problem is the following problem: Given a graph $G$ and a weight function
$\mathfrak{w}:V(G)\to\mathbb{Q}_{+}$, find a distance-$d$ independent set with
maximum total weight. For $d=2$, the problem coincides with the classical Max
Weight Independent Set problem.

###  3.1 Tree-independence number and graph powers

Balakrishnan and Paulraja proved in [5] that the class of chordal graphs is
closed under taking odd powers. Combined with the polynomial-time solvability
of the Max Weight Independent Set problem in the class of chordal graphs (see,
e.g., [29]), this implies that the Distance-$d$ Independent Set problem is
solvable in polynomial time in the class of chordal graphs for all even $d\geq
2$. On the other hand, Eto et al. [27] showed that the problem is NP-complete
in the class of chordal graphs for all odd $d\geq 3$.

The result of Balakrishnan and Paulraja was generalized by Duchet as follows.

######  Theorem 3.1 (Duchet [26]).

Let $G$ be a graph and $k$ a positive integer such that $G^{k}$ is chordal.
Then the graph $G^{k+2}$ is also chordal.

In terms of tree-independence number, Theorem 3.1 can be phrased as follows.

######  Theorem 3.2.

Let $G$ be a graph and $k$ a positive integer such that
$\mathsf{tree}\textnormal{-}\alpha(G^{k})\leq 1$. Then
$\mathsf{tree}\textnormal{-}\alpha(G^{k+2})\leq 1$.

We now generalize this result as follows.

######  Theorem 3.3.

Let $G$ be a graph and $k$ a positive integer. Then
$\mathsf{tree}\textnormal{-}\alpha(G^{k+2})\leq\mathsf{tree}\textnormal{-}\alpha(G^{k})$.

The proof of Theorem 3.3 will be based on the following lemma, the case $d=1$
of which was observed by Duchet in [26].

######  Lemma 3.4.

Let $G=(V,E)$ be a graph, and $k$ and $d$ positive integers. For $v\in V$, let
$H_{v}$ be the subgraph of $G$ induced by the vertices at distance at most $d$
from $v$, and let $\mathcal{H}=\\{H_{v}\\}_{v\in V}$. Then
$G^{k+2d}=G^{k}(\mathcal{H})$.

###### Proof.

Let us first observe that for every vertex $v$ of $G$, the graph $H_{v}$ is
also a subgraph of $G^{k}$. Hence, the graph $G^{k}(\mathcal{H})$ is well-
defined. The graphs $G^{k+2d}$ and $G^{k}(\mathcal{H})$ both have the same
vertex set, namely $V$.

As for the edge set, consider two distinct vertices $u$ and $v$ in $V$. Assume
first that $u$ and $v$ are adjacent in $G^{k}(\mathcal{H})$. Then the graphs
$H_{u}$ and $H_{v}$ either have a vertex in common, or they are vertex-
disjoint but there is an edge between them in $G^{k}$. If $H_{u}$ and $H_{v}$
have a vertex in common, say $x\in V(H_{u})\cap V(H_{v})$, then
$\textsf{dist}_{G}(u,v)\leq\textsf{dist}_{G}(u,x)+\textsf{dist}_{G}(x,v)\leq
2d\leq k+2d$, and hence $u$ and $v$ are adjacent in $G^{k+2d}$. If $H_{u}$ and
$H_{v}$ are vertex-disjoint but there exist vertices $x\in V(H_{u})$ and $y\in
V(H_{v})$ such that $\\{x,y\\}\in E(G^{k})$, then
$\textsf{dist}_{G}(u,v)\leq\textsf{dist}_{G}(u,x)+\textsf{dist}_{G}(x,y)+\textsf{dist}_{G}(y,v)\leq
d+k+d=k+2d$, and hence $u$ and $v$ are adjacent in $G^{k+2d}$.

Assume now that $u$ and $v$ are adjacent in $G^{k+2d}$. Then
$\textsf{dist}_{G}(u,v)\leq k+2d$. We want to show that the graphs $H_{u}$ and
$H_{v}$ either have a vertex in common, or they are vertex-disjoint but there
is an edge between them in $G^{k}$. If $u$ and $v$ at distance at most $2d$ in
$G$, then there exists a vertex $x\in V$ that is at distance in $G$ at most
$d$ from each of $u$ and $v$, and hence the graphs $H_{u}$ and $H_{v}$ have a
vertex in common. We may thus assume that $\textsf{dist}_{G}(u,v)\geq 2d+1$
or, equivalently, that the graphs $H_{u}$ and $H_{v}$ are vertex-disjoint.
Since $2d+1\leq\textsf{dist}_{G}(u,v)\leq k+2d$, there exists a $u$-$v$-path
$P=(u=u_{0},u_{1},\ldots,u_{q}=v)$ in $G$ such that $2d+1\leq q\leq k+2d$.
This implies that $1\leq\textsf{dist}_{G}(u_{d},u_{q-d})\leq k$ and hence the
vertices $u_{d}$ and $u_{q-d}$ are adjacent in $G^{k}$. Since $u_{d}$ is at
distance at most $d$ from $u$, it belongs to $H_{u}$. Similarly, $u_{q-d}$
belongs to $H_{v}$. Thus, $\\{u_{d},u_{q-d}\\}$ is an edge in $G^{k}$ between
the subgraphs $H_{u}$ and $H_{v}$. This shows that $u$ and $v$ are adjacent in
$G^{k}(\mathcal{H})$.

We showed that the graphs $G^{k+2d}$ and $G^{k}(\mathcal{H})$ have the same
vertex sets and the same edge sets. Hence, they are the same. ∎

###### Proof of Theorem 3.3..

Let $G=(V,E)$ be a graph and $k$ a positive integer. For $v\in V$, let $H_{v}$
be the subgraph of $G$ induced by $v$ and its neighbors, and let
$\mathcal{H}=\\{H_{v}\\}_{v\in V}$. Let
$q=\mathsf{tree}\textnormal{-}\alpha(G^{k})$ and let
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be a tree decomposition of $G^{k}$
such that the independence number of $\mathcal{T}$ equals $q$. Let
$\mathcal{T}^{\prime}=(T,\\{X^{\prime}_{t}\\}_{t\in V(T)})$ with
$X^{\prime}_{t}=\\{v\in V:V(H_{v})\cap X_{t}\neq\emptyset\\}$ for all $t\in
V(T)$. Since for each $v\in V$, the graph $H_{v}$ is a connected non-null
subgraph of $G^{k}$, Lemma 2.1 implies that $\mathcal{T}^{\prime}$ is a tree
decomposition of $G^{k}(\mathcal{H})$ such that
$\alpha(\mathcal{T}^{\prime})\leq\alpha(\mathcal{T})=q$. Since
$G^{k+2}=G^{k}(\mathcal{H})$ by Lemma 3.4, we conclude that
$\mathsf{tree}\textnormal{-}\alpha(G^{k+2})\leq\alpha(\mathcal{T}^{\prime})\leq
q=\mathsf{tree}\textnormal{-}\alpha(G^{k})$. ∎

Theorem 3.3 has the following consequence.

######  Corollary 3.5.

Let $G$ be a graph and $k$ an odd positive integer. Then
$\mathsf{tree}\textnormal{-}\alpha(G^{k})\leq\mathsf{tree}\textnormal{-}\alpha(G)$.

We will also make use of the following algorithmic version of Corollary 3.5.

######  Corollary 3.6.

For every positive odd integer $k$, there exists an algorithm that takes as
input a graph $G$ and a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ of $G$, and computes in time
$\mathcal{O}\left((|V(G)|+|V(T)|)\cdot(|V(G)|+|E(G)|)\right)$ the graph
$G^{k}$ and a tree decomposition
$\mathcal{T}^{\prime}=(T,\\{X^{\prime}_{t}\\}_{t\in V(T)})$ of $G^{k}$ such
that $\alpha(\mathcal{T}^{\prime})\leq\alpha(\mathcal{T})$.

###### Proof.

The statement is trivial for $k=1$, so let us assume that $k\geq 3$. Let
$d=(k-1)/2$. For $v\in V(G)$, let $H_{v}$ be the subgraph of $G$ induced by
the vertices at distance at most $d$ from $v$ in $G$, and let
$\mathcal{H}=\\{H_{v}\\}_{v\in V(G)}$. Lemma 3.4 implies that
$G^{k}=G(\mathcal{H})$. Let
$\mathcal{T}^{\prime}=(T,\\{X^{\prime}_{t}\\}_{t\in V(T)})$ with
$X^{\prime}_{t}=\\{v\in V(G):V(H_{v})\cap X_{t}\neq\emptyset\\}$ for all $t\in
V(T)$. Since for each $v\in V(G)$, the graph $H_{v}$ is a connected non-null
subgraph of $G$, Lemma 2.1 implies that $\mathcal{T}^{\prime}$ is a tree
decomposition of $G^{k}$ such that
$\alpha(\mathcal{T}^{\prime})\leq\alpha(\mathcal{T})$. Note that for a vertex
$v\in V(G)$, the condition $V(H_{v})\cap X_{t}\neq\emptyset$ is equivalent to
the condition that $v$ is at distance at most $d$ in $G$ from $X_{t}$. Thus,
each bag $X^{\prime}_{t}$ can be computed in time $\mathcal{O}(|V(G)|+|E(G)|)$
using a BFS traversal up to distance $d+1$ from a new vertex adjacent to all
vertices of the bag $X_{t}$. The graph $G^{k}$ can be computed using a BFS
traversal from each vertex $v\in V(G)$ in time
$\mathcal{O}(|V(G)|(|V(G)|+|E(G)|))$. The total time complexity of this
approach is $\mathcal{O}\left((|V(G)|+|V(T)|)\cdot(|V(G)|+|E(G)|)\right)$. ∎

Finally, let us remark that a result similar to Corollary 3.5 does not hold
for even powers.

######  Proposition 3.7.

Fix an even positive integer $k$. Then there is no function $f$ satisfying

$\mathsf{tree}\textnormal{-}\alpha(G^{k})\leq
f(\mathsf{tree}\textnormal{-}\alpha(G))$

for all graphs $G$.

###### Proof.

Since the tree-independence number of chordal graphs is at most one, it
suffices to show that the $k$-th powers of chordal graphs have arbitrarily
large tree-independence number. To this end, we show that for every graph $H$
there exists a chordal graph $G$ such that $G^{k}$ contains an induced
subgraph isomorphic to $H$. This will suffice, since there exist graphs with
arbitrarily large tree-independence numbers (for example complete bipartite
graphs $K_{n,n}$, see [23]). First, let $\widehat{H}$ be the graph obtained
from $H$ by subdividing each edge exactly once and adding edges so that the
newly introduced vertices form a clique. Then $V(H)$ is an independent set in
$\widehat{H}$ and $V(\widehat{H})\setminus V(H)$ is a clique in $\widehat{H}$.
Hence $\widehat{H}$ is a split graph and thus a chordal graph. We obtain the
graph $G$ from $\widehat{H}$ by appending to each vertex $v\in V(H)$ a path
$P^{v}$ of length $(k-2)/2$ such that one endpoint of $P^{v}$ is $v$ and all
the other vertices of $P^{v}$ are new. In particular, for any two different
vertices $v,w\in V(H)$, the corresponding paths $P^{v}$ and $P^{w}$ are
vertex-disjoint. By construction, the graph $G$ is chordal. For each vertex
$v\in V(H)$, let us denote the two endpoints of $P^{v}$ by $v$ and
$v^{\prime}$ (with $v^{\prime}=v$ if and only if $k=2$), and let
$X=\\{v^{\prime}:v\in V(H)\\}$. For arbitrary two distinct vertices $u,v\in
V(H)$, it holds that $u^{\prime}v^{\prime}\in E(G^{k})$ if and only if
$\textsf{dist}_{G}(u^{\prime},v^{\prime})\leq k$, which happens if and only if
$u$ and $v$ are adjacent in $H$. Thus, the subgraph of $G^{k}$ induced by $X$
is isomorphic to $H$. This shows that for every graph $H$ there exists a
chordal graph $G$ such that $G^{k}$ contains an induced subgraph isomorphic to
$H$, as claimed. ∎

######  Remark 3.8.

Since the balanced complete bipartite graph $K_{n,n}$ has clique number two
and treewidth $n$, the above proof shows, in fact, that for any even positive
integer $k$, the class of $k$-th powers of chordal graphs is
$(\mathrm{tw},\omega)$-unbounded.

###  3.2 Algorithmic consequences

Given a graph $G$ and two sets $A,B\subseteq V(G)$, we denote by
$\textsf{dist}_{G}(A,B)$ the minimum over all distances in $G$ between a
vertex in $A$ and a vertex in $B$. This definition is naturally extended to
subgraphs of $G$, by considering the distance between their vertex sets.

Fix a positive integer $d$. Given a graph $G$ and a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null subgraphs of $G$, a
_distance- $d$ $\mathcal{H}$-packing_ in $G$ is a subfamily
$\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ of subgraphs from $\mathcal{H}$
(that is, $I\subseteq J$) that are at pairwise distance at least $d$. If the
subgraphs in $\mathcal{H}$ are equipped with a weight function
$\mathfrak{w}:J\to\mathbb{Q}_{+}$ assigning weight $\mathfrak{w}_{j}$ to each
subgraph $H_{j}$, we define the _weight_ of a distance-$d$ independent
$\mathcal{H}$-packing $\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ in $G$ as
the sum $\sum_{i\in I}\mathfrak{w}_{i}$. Given a graph $G$, a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null subgraphs of $G$, and
a weight function $w:J\to\mathbb{Q}_{+}$ on the subgraphs in $\mathcal{H}$,
the Maximum Weight Distance-$d$ Packing problem asks to find a distance-$d$
$\mathcal{H}$-packing in $G$ of maximum weight. When $d=2$ and $\mathcal{H}$
is the set of all subgraphs of $G$ isomorphic to a member of a fixed family
$\mathcal{F}$ of connected graphs, the problem coincides with the Maximum
Weight Independent $\mathcal{F}$-Packing problem studied in Dallard et al.
[23].

######  Observation 3.9.

Let $d$ be a positive integer, let $G$ be a graph, let
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ be a finite family of connected non-null
subgraphs of $G$, and let $I\subseteq J$. Then, the corresponding subfamily
$\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ is a distance-$d$
$\mathcal{H}$-packing in $G$ if and only if $\mathcal{H}^{\prime}$ is an
independent $\mathcal{H}$-packing in the graph $G^{d-1}$.

###### Proof.

Consider two distinct elements $i,j\in I$. It suffices to show that
$\textsf{dist}_{G}(V(H_{i}),V(H_{j}))\geq d$ if and only if
$\textsf{dist}_{G^{d-1}}(V(H_{i}),V(H_{j}))\geq 2$, or, equivalently, that
$\textsf{dist}_{G}(V(H_{i}),V(H_{j}))\leq d-1$ if and only if
$\textsf{dist}_{G^{d-1}}(V(H_{i}),V(H_{j}))\leq 1$. Assume first that
$\textsf{dist}_{G}(V(H_{i}),V(H_{j}))\leq d-1$ and let
$P=(v_{0},\ldots,v_{r})$ be a path in $G$ from a vertex in $H_{i}$ to a vertex
in $H_{j}$ such that $r\leq d-1$. If $r=0$ then
$\textsf{dist}_{G^{d-1}}(V(H_{i}),V(H_{j}))=0$. If $r>0$, then in $G^{d-1}$,
vertices $v_{0}$ and $v_{r}$ are adjacent, and hence
$\textsf{dist}_{G^{d-1}}(V(H_{i}),V(H_{j}))\leq 1$. Assume now that
$\textsf{dist}_{G^{d-1}}(V(H_{i}),V(H_{j}))\leq 1$. If this distance is $0$,
then the graphs $H_{i}$ and $H_{j}$ have a vertex in common and hence
$\textsf{dist}_{G}(V(H_{i}),V(H_{j}))=0\leq d-1$. If this distance is $1$,
then there is a path $P$ in $G$ of length at most $d-1$ from a vertex in
$H_{i}$ to a vertex in $H_{j}$. Thus,
$\textsf{dist}_{G}(V(H_{i}),V(H_{j}))\leq d-1$. ∎

We now generalize Theorem 2.2.

######  Theorem 3.10.

For every even positive integer $d$ and every $k\geq 1$, given a graph $G$, a
finite family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null
subgraphs of $G$, and a weight function $\mathfrak{w}:J\to\mathbb{Q}_{+}$ on
the subgraphs in $\mathcal{H}$, the Maximum Weight Distance-$d$ Packing
problem is solvable in time
$\mathcal{O}\left((|V(G)|+|V(T)|)\cdot|E(G)|+|J|\cdot|V(G)|\cdot((|J|+|V(T)|+|V(G)|)+|J|^{k+1}\cdot|V(T)|)\right)$
if $G$ is given with a tree decomposition $\mathcal{T}=(T,\\{X_{t}\\}_{t\in
V(T)})$ with independence number at most $k$.

###### Proof.

Let the input to the Maximum Weight Distance-$d$ Packing be given by the graph
$G$, a finite family $\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null
subgraphs of $G$, and a weight function $\mathfrak{w}:J\to\mathbb{Q}_{+}$ on
the subgraphs in $\mathcal{H}$. The problem asks for a maximum-weight
distance-$d$ $\mathcal{H}$-packing in $G$, that is, a maximum-weight subfamily
$\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ of subgraphs from $\mathcal{H}$
that are at pairwise distance at least $d$ in $G$. By 3.9, for every
$I\subseteq J$, the corresponding subfamily
$\mathcal{H}^{\prime}=\\{H_{i}\\}_{i\in I}$ is a distance-$d$
$\mathcal{H}$-packing in $G$ if and only if $\mathcal{H}^{\prime}$ is an
independent $\mathcal{H}$-packing in the graph $G^{d-1}$.

By Corollary 3.6, the graph $G^{d-1}$ and a tree decomposition
$\mathcal{T}^{\prime}=(T,\\{X^{\prime}_{t}\\}_{t\in V(T)})$ of $G^{d-1}$ with
independence number at most $k$ can be computed from $G$ and $\mathcal{T}$ in
time $\mathcal{O}\left((|V(G)|+|V(T)|)\cdot(|V(G)|+|E(G)|)\right)$. By Theorem
2.2, a maximum-weight independent $\mathcal{H}$-packing in the graph $G^{d-1}$
can be computed in time
$\mathcal{O}(|J|\cdot((|J|+|V(T)|)\cdot|V(G^{d-1})|+|E(G^{d-1})|+|J|^{k}\cdot|V(T)|))$.
Using the fact that $|V(G^{d-1})|=|V(G)|$ and $|E(G^{d-1})|\leq|V(G)|^{2}$,
the time complexity simplifies to
$\mathcal{O}(|J|\cdot((|J|+|V(T)|)\cdot|V(G)|+|V(G)|^{2}+|J|^{k}\cdot|V(T)|))$.
Altogether, we obtain the claimed time complexity
$\mathcal{O}\left((|V(G)|+|V(T)|)\cdot|E(G)|+|J|\cdot|V(G)|\cdot((|J|+|V(T)|+|V(G)|)+|J|^{k+1}\cdot|V(T)|)\right)$.
∎

Note that the proof of Theorem 3.10 does not require the distance bound $d$ to
be fixed. The result remains true, and with the stated time complexity, even
if $d$ is part of input (as long as it is even). Furthermore, if the input
graph is not equipped with a tree decomposition of bounded independence
number, we can obtain one in polynomial time using a recent result of Dallard
et al. [21]. Thus, given a graph $G$, a finite family
$\mathcal{H}=\\{H_{j}\\}_{j\in J}$ of connected non-null subgraphs of $G$, and
a weight function $\mathfrak{w}:J\to\mathbb{Q}_{+}$ on the subgraphs in
$\mathcal{H}$, the Maximum Weight Distance-$d$ Packing problem is polynomial-
time solvable in any class of graphs in which the tree-independence number is
bounded by a constant.

On the other hand, the assumption that $d$ is even is necessary in Theorem
3.10, unless $\textsf{P}=\textsf{NP}$. Indeed, Eto et al. [27] showed that for
all odd $d\geq 3$, the Distance-$d$ Independent Set problem is NP-complete in
the class of chordal graphs, which is exactly the class of graphs with tree-
independence number at most $1$. Note that this NP-completeness result is in
line with the fact, shown in the proof of Proposition 3.7, that even powers of
chordal graphs may contain arbitrary graphs as induced subgraphs.

##  4 Finding large induced sparse subgraphs and $\mathsf{CMSO}_{2}$

We start this section by recalling some basic notions and properties related
to $\mathsf{CMSO}_{2}$.

###  4.1 $\mathsf{CMSO}_{2}$: basic notions and properties

####  $\mathsf{CMSO}_{2}$ logic on graphs

We assume that graphs are encoded as relational structures: each vertex and
each edge is represented by a single variable (distinguishable by a unary
predicate), and there is a single binary relation $\mathsf{inc}$ binding each
edge with its endvertices.

$\mathsf{MSO}_{2}$ (_Monadic Second Order_) logic is a logic on graphs that
allows us to use vertex variables, edge variables, vertex sets variables, and
edge set variables, and, furthermore, to quantify over them. An example of an
$\mathsf{MSO}_{2}$ formula is the following expression checking if the
chromatic number of a given graph is at most $r$ (for constant $r$). Here,
$S_{i}$’s are vertex set variables, $e$ is an edge variable, and $x,y$ are
vertex variables.

$\displaystyle\begin{split}\phi_{\chi\leq
r}\;:=\;&\exists_{S_{1},S_{2},\ldots,S_{r}}\;(\forall_{x}\;x\in S_{1}\cup
S_{2}\ldots\cup S_{r})\;\land\\\
&\forall_{e}\forall_{x,y}\;(\mathsf{inc}((e,x)\land\mathsf{inc}(e,y)\land
x\neq y)\to\bigwedge_{i=1}^{r}(x\notin S_{i}\lor y\notin S_{i}).\end{split}$
(1)

For a positive integer $p$, by $\mathsf{C}_{\leq p}\mathsf{MSO}_{2}$ we mean
the extension of $\mathsf{MSO}_{2}$ that allows us to use atomic formulae of
the form $|S|\equiv a\bmod b$, where $S$ is a (vertex of edge) set variable,
and $a,b\leq p$ are integers. We define $\mathsf{CMSO}_{2}$ (_Counting Monadic
Second Order_ logic) to be $\bigcup_{p>0}$$\mathsf{C}_{\leq
p}\mathsf{MSO}_{2}$. The _quantifier rank_ of a formula is the maximum number
of nested quantifiers in the formula.

#### Boundaried graphs and $\mathsf{CMSO}_{2}$ types

Let $\ell>0$ be an integer. An _$\ell$ -boundaried graph_ is a pair
$(G,\iota)$, where $G$ is a graph and $\iota$ is a partial injective function
from $V(G)$ to $[\ell]$. The domain of $\iota$, denoted by
$\mathrm{dom}(\iota)$ is the _boundary_ of $(G,\iota)$. For
$v\in\mathrm{dom}(\iota)$, the value of $\iota(v)$ is called the _label_ of
$v$.

Let us define two natural operations on boundaried graphs. For an
$\ell$-boundaried graph $(G,\iota)$ and $l\in[\ell]$, the result of
_forgetting the label $l$_ is the $[\ell]$-boundaried graph $(G,\iota_{\neg
l})$, here $\iota_{\neg
l}:=\iota|_{\mathrm{dom}(\iota)\setminus\iota^{-1}(l)}$. In other words, if
the boundary of $(G,\iota)$ contains vertex $v$ with label $l$, we remove the
label from $v$, while keeping $v$ in the graph. Note that if
$l\notin\mathrm{dom}(\iota)$, then this operation does not do anything.

For two $\ell$-boundaried graphs $(G_{1},\iota_{1})$ and $(G_{2},\iota_{2})$,
the result of _gluing_ them is the $\ell$-boundaried graph
$(G_{1},\iota_{1})\oplus_{[\ell]}(G_{2},\iota_{2})$ obtained from the disjoint
union of $(G_{1},\iota_{1})$ and $(G_{2},\iota_{2})$ by identifying vertices
with the same label. Note that it might happen that some label $l$ is used in,
e.g., $\iota_{1}$ but not in $\iota_{2}$. Then the vertex with label $l$ in
$(G_{1},\iota_{1})\oplus_{[\ell]}(G_{2},\iota_{2})$ is the copy of the vertex
with label $l$ from $(G_{1},\iota_{1})$.

It is straightforward to observe that a graph has treewidth less than $\ell$
if and only if it can be constructed from $\ell$-boundaried graphs with at
most two vertices by a sequence of forgetting and gluing operations (see,
e.g., [28]).

By $\mathsf{CMSO}_{2}$ in $[\ell]$-boundaried graphs we mean
$\mathsf{CMSO}_{2}$ extended with $\ell$ unary predicates: for each
$l\in[\ell]$ we have a predictate that selects a vertex with label $l$ (if
such a vertex exists). The following proposition is folklore (see, e.g., [33,
Lemma 6.1]). The exact formulation we use here comes from Gartland et al. [31,
Proposition 8].

######  Proposition 4.1.

For every triple of integers $\ell,p,q$, there exists a finite set
$\mathsf{Types}^{\ell,p,q}$ and a function that assigns to every
$\ell$-boundaried graph $(G,\iota)$ a _type_
$\mathsf{type}^{\ell,p,q}(G,\iota)\in\mathsf{Types}^{\ell,p,q}$ such that the
following holds:

  1. 1.

The types of isomorphic graphs are the same.

  2. 2.

For every $\mathsf{C}_{\leq p}\mathsf{MSO}_{2}$ sentence $\phi$ on
$\ell$-boundaried graphs, whether $(G,\iota)$ satisfies $\phi$ depends only on
the type $\mathsf{type}^{\ell,p,q}(G,\iota)$, where $q$ is the quantifier rank
of $\phi$. More precisely, there exists a subset
$\mathsf{Types}^{\ell,p,q}[\phi]\subseteq\mathsf{Types}^{\ell,p,q}$ such that
for every $\ell$-boundaried graph $(G,\iota)$ we have

$(G,\iota)\models\phi\qquad\textrm{if and only
if}\qquad\mathsf{type}^{\ell,p,q}(G,\iota)\in\mathsf{Types}^{\ell,p,q}[\phi].$

  3. 3.

The types of ingredients determine the type of the result of the gluing
operation. More precisely, for every two types
$\tau_{1},\tau_{2}\in\mathsf{Types}^{\ell,p,q}$ there exists a type
$\tau_{1}\oplus_{\ell,p,q}\tau_{2}$ such that for every two $\ell$-boundaried
graphs $(G_{1},\iota_{1})$, $(G_{2},\iota_{2})$, if
$\mathsf{type}^{\ell,p,q}(G_{i},\iota_{i})=\tau_{i}$ for $i=1,2$, then

$\mathsf{type}^{\ell,p,q}((G_{1},\iota_{1})\oplus_{[\ell]}(G_{2},\iota_{2}))=\tau_{1}\oplus_{\ell,p,q}\tau_{2}.$

Also, the operation $\oplus_{\ell,p,q}$ is associative and commutative.

  4. 4.

The type of the ingredient determines the type of the result of the forget
label operation. More precisely, for every type
$\tau\in\mathsf{Types}^{\ell,p,q}$ and $l\in[\ell]$ there exists a type
$\tau_{\neg l}$ such that for every $\ell$-boundaried graph $(G,\iota)$, if
$\mathsf{type}^{\ell,p,q}(G,\iota)=\tau$ and $(G,\iota_{\neg l})$ is the
result of forgetting $l$ in $(G,\iota)$, then

$\mathsf{type}^{\ell,p,q}(G,\iota_{\neg l})=\tau_{\neg l}.$

Intuitively, for any $\ell$-boundaried graph $(G,\iota)$, whether
$(G,\iota)\models\phi$ is fully determined by
$\mathsf{type}^{\ell,p,q}(G,\iota)$ (where $p$ and $q$ are as in Proposition
4.1). Furthermore, if $\phi$ and $\ell$ are fixed, then the sets
$\mathsf{Types}^{\ell,p,q}$ and $\mathsf{Types}^{\ell,p,q}[\phi]$ are of
constant size. Finally, it is known that there is an algorithm that, given
$\ell$ and $\phi$, computes $\mathsf{Types}^{\ell,p,q}$ and
$\mathsf{Types}^{\ell,p,q}[\phi]$ [10].

###  4.2 $\mathsf{CMSO}_{2}$-definable subgraphs of graphs with small tree-
independence number

Now we are ready to prove our main result concerning sparse induced subgraphs
satisfying some $\mathsf{CMSO}_{2}$-definable property.

######  Theorem 4.2.

For every $k,r$ and a $\mathsf{CMSO}_{2}$ formula $\psi$ there exists a
positive integer $f(k,r,\psi)$ such that the following holds. Let $G$ be a
graph given along with a tree decomposition of independence number at most
$k$, and let $\mathfrak{w}:V(G)\to\mathbb{Q}_{+}$ be a weight function. Then
in time $f(k,r,\psi)\cdot|V(G)|^{\mathcal{O}(kr)}$ we can find a set
$Y\subseteq V(G)$, such that

  1. 1.

$G[Y]\models\psi$,

  2. 2.

$\chi(G[Y])\leq r$,

  3. 3.

$F$ is of maximum weight subject to the conditions above,

or conclude that no such set exists.

###### Proof.

Let $\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ be a tree decomposition of $G$
with independence number at most $k$. Recall that without loss of generality
we can assume that $\mathcal{T}$ is nice. Let $F$ be a fixed (unknown) optimal
solution. Note that by removing all vertices from $V(G)\setminus F$ from each
bag of $\mathcal{T}$, we obtain a tree decomposition of $G[F]$ with
independence number at most $k$. As $\chi(G[F])\leq r$, we conclude that every
bag of $\mathcal{T}$ contains at most $kr$ vertices of $F$. In particular, the
treewidth of $G[F]$ is less than $\ell:=kr$. This is the only way in which we
use that $\chi(G[F])\leq r$. Thus, in order to make sure that the obtained
solution satisfies the bound on the chromatic number, instead of $\psi$ we
will use the $\mathsf{CMSO}_{2}$ formula $\phi:=\psi\land\phi_{\chi\leq r}$,
where $\phi_{\chi\leq r}$ is the formula (1).

We will think of $G[F]$ as constructed by a sequence of forgetting and gluing
operations on $\ell$-boundaried graphs.

Consider the minimum integer $p$ such that $\phi$ belongs to $\mathsf{C}_{\leq
p}\mathsf{MSO}_{2}$, and let $q$ be the quantifier rank of $\phi$. Let
$\mathsf{Types}^{\ell,p,q}$ and $\mathsf{Types}^{\ell,p,q}[\phi]$ be as in
Proposition 4.1. Recall that these sets are of constant size (since $k,r$, and
$\phi$ are fixed); we assume that they are hard-coded in our algorithm.
Similarly, we assume that the forgetting and gluing operations on types, i.e.,
functions

$(\tau_{1},\tau_{2})\mapsto\tau_{1}\oplus_{\ell,p,q}\tau_{2}\qquad\textrm{and}\qquad(\tau,l)\mapsto\tau_{\neg
l},$

are hard-coded. Finally, our algorithm has the list of types of all
$\ell$-boundaried graphs with at most $\ell$ vertices. As $\ell,p,q$ are fixed
throughout the algorithm, we will simplify the notation by dropping subscripts
and superscripts, i.e., we will simply write
$\mathsf{Types},\mathsf{Types}[\phi]$, and $\oplus$.

Our algorithm is a standard bottom-up dynamic programming on a nice tree
decomposition. We will describe how to compute the weight of an optimal
solution; adapting our approach to return the solution itself is a standard
task.

We introduce the table $\mathsf{Tab}[\cdot,\cdot]$ indexed by nodes $t$ of $T$
and _states_. Each state is a triple $(S,\iota,\tau)$, where $S\subseteq
X_{t}$ has at most $\ell$ vertices, $\iota$ is an injective function from $S$
to $[\ell]$, and $\tau\in\mathsf{Types}$. The value of
$\mathsf{Tab}[t,(S,\iota,\tau)]$ will encode the maximum weight of a subset
$F_{t}$ of $V(G_{t})$ such that

  1. 1.

$F_{t}\cap X_{t}=S$,

  2. 2.

$\mathsf{type}((G[F_{t}],\iota))=\tau$.

Intuitively, we think of $S$ as the intersection of a fixed optimal solution
with $X_{t}$ and we look for a maximum-weight induced $\ell$-boundaried
subgraph of $G_{t}$ with boundary $S$ and type $\tau$. If there is no subset
$F_{t}$ satisfying the conditions above, we will have
$\mathsf{Tab}[t,(S,\iota,\tau)]=-\infty$. Clearly, having computed all entries
of $\mathsf{Tab}[\cdot,\cdot]$, the weight of the sought-for optimum solution
is

$\max\mathsf{Tab}[\mathrm{root}(T),(S,\iota,\tau)]\text{ over all feasible
}S,\iota\text{ and }\tau\in\mathsf{Types}[\phi],$

where by $\mathrm{root}(T)$ we mean the root of $T$.

Let us now describe how we compute the entries $\mathsf{Tab}[t,\cdot]$ for a
node $t$ of $T$. The exact way depends on the type of $x$.

#### Case: $t$ is a leaf node.

Note that in this case $G_{t}$ has only one vertex, and thus the values of
$\mathsf{Tab}[t,\cdot]$ can be extracted from the information that is hard-
coded in the algorithm.

#### Case: $t$ is an introduce node.

Let $t^{\prime}$ be the child of $t$ in $T$, and let $v$ be the unique vertex
in $X_{t}\setminus X_{t^{\prime}}$. Clearly if $v\notin S$, then
$\mathsf{Tab}[t,(S,\iota,\tau)]=\mathsf{Tab}[t,(S,\iota,\tau)]$.

So suppose $v\in S$, let $S^{\prime}=S\setminus\\{v\\}$, and let
$\iota^{\prime}=\iota|_{S^{\prime}}$. Let $G_{S}$ be the subgraph of $X_{t}$
induced by $S$. As $|S|\leq\ell$, the value
$\tau_{S}:=\mathsf{type}((G_{S},\iota))$ is hard-coded in our algorithm. Now
we set

$\mathsf{Tab}[t,(S,\iota,\tau)]=\max_{\tau^{\prime}}\mathsf{Tab}[t^{\prime},(S^{\prime},\iota^{\prime},\tau^{\prime})],$

where the maximum is taken over all $\tau^{\prime}$ such that
$\tau_{S}\oplus\tau^{\prime}=\tau$.

#### Case: $t$ is a forget node.

Let $t^{\prime}$ be the child of $t$ in $\mathcal{T}$, and let $v$ be the
unique vertex in $X_{t^{\prime}}\setminus X_{t}$. Intuitively, partial
solutions at $t$ correspond to partial solutions at $t^{\prime}$ with the
label of $v$ (if any) forgotten.

Thus

$\mathsf{Tab}[t,(S,\iota,\tau)]=\max\left(\mathsf{Tab}[t^{\prime},(S,\iota,\tau)],\max_{\iota^{\prime},\tau^{\prime}}\mathsf{Tab}[t^{\prime},(S\cup\\{v\\},\iota^{\prime},\tau^{\prime})]\right),$

where in the second term we assume that $|S|<\ell$. The maximum in the second
term is computed over all pairs $\iota^{\prime},\tau^{\prime}$, such that
$\iota^{\prime}|_{S}=\iota$ and $\tau^{\prime}|_{\neg\iota^{\prime}(v)}=\tau$.

#### Case: $t$ is a join node.

Let $t^{\prime},t^{\prime\prime}$ be the children of $t$. Thus

$\mathsf{Tab}[t,(S,\iota,\tau)]=\max_{\tau^{\prime},\tau^{\prime\prime}}\mathsf{Tab}[t^{\prime},(S,\iota,\tau^{\prime})]+\mathsf{Tab}[t^{\prime\prime},(S,\iota,\tau^{\prime\prime})]-\mathfrak{w}(S),$

where the maximum is taken over all $\tau^{\prime},\tau^{\prime\prime}$ such
that $\tau^{\prime}\oplus\tau^{\prime\prime}=\tau$. Note that we subtract the
weight of $S$, as it is counted both for $t^{\prime}$ and for
$t^{\prime\prime}$.

The correctness of the procedure above follows directly from the properties of
tree decompositions and Proposition 4.1.

For each node $t$ of $T$, the number of states is at most
$|X_{t}|^{\ell}\cdot\ell!\cdot|\mathsf{Types}|$. Each entry of
$\mathsf{Tab}[\cdot,\cdot]$ can be computed in time proportional to the number
of states for each node (here we use that $k,r,\phi$ are fixed). As the number
of nodes of $T$ is polynomial in $|V(G)|$, we conclude that the running time
is $f(k,r,\psi)\cdot|V(G)|^{\mathcal{O}(kr)}$ for some function $f$ depending
on $k,r$, and $\psi$. ∎

###  4.3 Generalizations

In the first generalization we show that we can maximize the weight of some
carefully chosen subset of the solution. The formula $\psi$ uses this set as a
free variable.

######  Theorem 4.3.

For every $k,r$ and a $\mathsf{CMSO}_{2}$ formula $\psi$ with one free vertex-
set variable, there exists a positive integer $f(k,r,\psi)$ such that the
following holds. Let $G$ be a graph given along with a tree decomposition of
independence number at most $k$, and let $\mathfrak{w}:V(G)\to\mathbb{Q}_{+}$
be a weight function. Then in time $f(k,r,\psi)\cdot|V(G)|^{\mathcal{O}(kr)}$
we can find sets $X\subseteq F\subseteq V(G)$, such that

  1. 1.

$(G[F],X)\models\psi$,

  2. 2.

$\chi(G[F])\leq r$,

  3. 3.

$X$ is of maximum possible weight.

###### Proof sketch.

The proof follows by a simple trick used by Gartland et al. [31, Theorem 38].
We just sketch the argument here and refer the reader to [31, Theorem 38] for
more details.

For a graph $G$ and a subset $M\subseteq V(G)$, by $\breve{G}$ we denote the
_forked version of_ $(G,M)$, which is obtained as follows. We start the
construction with a copy of $G$. For every vertex $v$ of $G$ we introduce to
$\breve{G}^{M}$ three vertices of degree 1, each adjacent only to $v$. For
every vertex $v$ of $M$ we introduce to $\breve{G}^{M}$ a two-edge path, whose
one endvertex is identified with $v$. If $G$ is equipped with weights
$\mathfrak{w}$, we set the weights $\breve{\mathfrak{w}}$ of all vertices of
$\breve{G}^{M}$ to 0, with the exception that the value of $\mathfrak{w}(v)$
for $v\in M$ is transferred to the other endvertex of the two-edge path
attached to $v$.

Note that if $F^{\prime}$ is a forked version of some $(F,M)$, then $F$ and
$M$ can be uniquely decoded from $F^{\prime}$. Indeed, $F$ is the subgraph of
$F^{\prime}$ induced by vertices of degree at least four, and vertices of $M$
are those that are adjacent (in $F^{\prime}$) to a vertex of degree 2.
Furthermore, $\chi(F^{\prime})\leq\max(\chi(F^{\prime}),1)$.

Moreover, observe that if $G$ is given with a tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ with independence number at most
$k$, then we can easily obtain a tree decomposition
$\breve{\mathcal{T}}=(\breve{T},\\{\breve{X}_{t}\\}_{t\in V(\breve{T})})$ of
$\breve{G}^{V(G)}$ with independence number at most $k$. The idea is to call
the algorithm from Theorem 4.2 on $\breve{G}^{V(G)}$ and the formula
$\breve{\psi}$ that for a graph $F^{\prime}$ ensures that

  * •

if $F^{\prime}$ is a forked version of some $(F,M)$, then
$F^{\prime}\models\breve{\psi}$ if and only if $F\models\psi$,

  * •

otherwise $F^{\prime}\not\models\breve{\psi}$.

Such a formula can be easily constructed in $\mathsf{CMSO}_{2}$ [31]. We
observe that the solution found by the algorithm satisfies the conditions
stated in the theorem; again, see [31, Theorem 38] for details. ∎

The idea introduced in the proof of Theorem 4.3 allows us to annotate
vertices. In other words, our input is a graph and a constant number of
subsets of vertices. The formula $\psi$ uses these sets as free variables, and
we assume that the instance graph $G$ is given along with a valuation of these
free variables.

######  Theorem 4.4.

For every $k,r,p$ and a $\mathsf{CMSO}_{2}$ formula $\psi$ with $p+1$ free
vertex-set variables there exists a positive integer $f(k,r,p,\psi)$ such that
the following holds. Let $G$ be a graph given along with a tree decomposition
of independence number at most $k$, and let
$\mathfrak{w}:V(G)\to\mathbb{Q}_{+}$ be a weight function. Furthermore, let
$A_{1},A_{2},\ldots,A_{p}\subseteq V(G)$ be specified subsets of vertices of
$G$. Then in time $f(k,r,p,\psi)\cdot|V(G)|^{\mathcal{O}(kr)}$ we can find
sets $X\subseteq F\subseteq V(G)$, such that

  1. 1.

$(G[F],X,A_{1},A_{2},\ldots,A_{p})\models\psi$,

  2. 2.

$\chi(G[F])\leq r$,

  3. 3.

$X$ is of maximum possible weight.

Theorem 4.4 can be proven in a way analogous to Theorem 4.3, but this time we
distinguish the vertices from the sets $A_{i}$ by the number of attached
leaves. We skip the details, as they do not bring any new insight.

###  4.4 Algorithmic applications

Using the framework of Theorem 4.2 we can solve several well-studied problems
in graphs given with a tree decomposition of bounded independence number:

  * •

Max Weight Independent Set,

  * •

Max Weight Induced Forest, which is equivalent by complementation to Min
Weight Feedback Vertex Set,

  * •

Max Weight Induced Bipartite Subgraph, which is equivalent by complementation
to Min Weight Odd Cycle Transversal,

  * •

Max Weight Induced Odd Cactus, which is equivalent by complementation to Min
Weight Even Cycle Transversal,

  * •

Max Weight Induced Planar Subgraph, which is equivalent to Planarization.

Using the extension from Theorem 4.3 we can solve some other problems, for
example:

  * •

find the maximum number of pairwise independent induced cycles.

Note that the difference is that we maximize the _number_ of cycles, and not
their _total size_ (or weight), as we could do using Theorem 4.2. On other
other hand, the number of induced cycles in a graph might be very large, so
this problem cannot be solved using Theorem 2.2 (or Theorem 3.10). However, we
can solve our problem by calling Theorem 4.3 with the following parameters:

  * •

$d=3$,

  * •

$\psi$ is the formula saying that $G[F]$ is 2-regular (i.e., each component of
$G[F]$ is a cycle) and each vertex from $X$ must be in a distinct connected
component of $G[F]$, and

  * •

the weight of each vertex is 1.

Finally, the extension from Theorem 4.4 allows us to solve problems where we
allow annotations on vertices. An example of such a problem is the following
one:

  * •

given a graph, whose every vertex is equipped with a subset of $[r]$ (called a
_list_), find a maximum induced subgraph that admits a proper $r$-coloring
respecting the lists.

Indeed, it is sufficient to call Theorem 4.4, where each set $A_{i}$ contains
vertices with a given list (note that there are at most $2^{r}$, i.e., a
constant number of distinct lists), and $\psi$ is a formula similar to (1),
but also checking if the colors assigned to vertices respect the lists. Note
that the last problem is a generalization of List-$r$-Coloring (for constant
$r$).

Furthermore, let us recall that if the input graph is not equipped with a tree
decomposition with bounded independence number, we can again invoke a result
from [21] to infer that all of the above problems are polynomial-time solvable
in any class of graphs in which the tree-independence number is bounded by a
constant.

In conclusion, let us point out that in Theorems 4.2, 4.3 and 4.4 we need to
assume that the chromatic number $d$ of the solution is constant. Indeed, if
the number of colors is a part of the input, already the (List-) Coloring
problem becomes NP-hard in graphs of bounded tree-independence number.

######  Theorem 4.5.

The following problems are NP-hard:

  1. 1.

List-Coloring in graphs of tree-independence number 1,

  2. 2.

Coloring in graphs of tree-independence number 2.

###### Proof.

The first statement follows from the result of Golovach and Paulusma [32], who
showed that List-Coloring is NP-hard in complete split graphs, i.e., graphs
whose vertex set can be partitioned into an independent set and a clique, and
all edges between these two sets are present. Complete split graphs are in
particular chordal and thus of tree-independence number $1$.

To show the second statement, it suffices to observe that the Coloring problem
is NP-complete in the class of circular-arc graphs, as shown by Garey et al.
[30]. Furthermore, as we explain next, circular-arc graphs have tree-
independence number at most two. Every circular-arc graph $G$ is the
intersection graph of a family $\mathcal{F}$ of connected subgraphs of a graph
$H$ such that $H$ is a cycle. Fix a vertex $v\in V(H)$ and let $G_{\bar{v}}$
denote the intersection graph of the graphs in
$\mathcal{F}_{\bar{v}}=\\{F\in\mathcal{F}:v\not\in V(F)\\}$. Then
$G_{\bar{v}}$ is a chordal graph (in fact, an interval graph) and hence admits
a tree decomposition $\mathcal{T}$ in which each bag is a clique. Finally,
denoting by $K$ the set of vertices of $G$ corresponding to graphs in
$\mathcal{F}$ containing $v$, a tree decomposition of $G$ with independence
number at most $2$ can be obtained from the tree decomposition $\mathcal{T}$
of $G_{\bar{v}}$ by adding the vertices of the clique $K$ to every bag. ∎

### Acknowledgements

The authors are grateful to O-joung Kwon for asking about the complexity of
the Distance-$d$ Independent Set problem in classes of graphs with bounded
tree-independence number, and to Clément Dallard and Kenny Štorgel for helpful
discussions and remarks. This work is supported in part by the Slovenian
Research Agency (I0-0035, research program P1-0285 and research projects
J1-9110, N1-0102, N1-0160, J1-3001, J1-3002, and J1-3003).

## References

  * [1] T. Abrishami, M. Chudnovsky, M. Pilipczuk, P. Rzążewski, and P. D. Seymour.  Induced subgraphs of bounded treewidth and the container method.  In D. Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1948–1964. SIAM, 2021.
  * [2] B. Ahat, T. Ekim, and Z. C. Taşkın.  Integer programming formulations and benders decomposition for the maximum induced matching problem.  INFORMS J. Comput., 30(1):43–56, 2018.
  * [3] S. Arnborg, J. Lagergren, and D. Seese.  Easy problems for tree-decomposable graphs.  J. Algorithms, 12(2):308–340, 1991.
  * [4] S. Arnborg and A. Proskurowski.  Linear time algorithms for NP-hard problems restricted to partial $k$-trees.  Discrete Appl. Math., 23(1):11–24, 1989.
  * [5] R. Balakrishnan and P. Paulraja.  Powers of chordal graphs.  J. Austral. Math. Soc. Ser. A, 35(2):211–217, 1983.
  * [6] R. Belmonte and M. Vatshelle.  Graph classes with structured neighborhoods and algorithmic applications.  Theoret. Comput. Sci., 511:54–65, 2013.
  * [7] W. Ben-Ameur, M.-A. Mohamed-Sidi, and J. Neto.  The $k$-separator problem: polyhedra, complexity and approximation results.  J. Comb. Optim., 29(1):276–307, 2015.
  * [8] E. Bonnet, C. Geniet, E. J. Kim, S. Thomassé, and R. Watrigant.  Twin-width III: Max Independent Set, Min Dominating Set, and coloring.  In 48th International Colloquium on Automata, Languages, and Programming, volume 198 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. 35, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021.
  * [9] E. Bonnet, E. J. Kim, S. Thomassé, and R. Watrigant.  Twin-width I: tractable FO model checking.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science—FOCS 2020, pages 601–612. IEEE Computer Soc., Los Alamitos, CA, 2020.
  * [10] R. B. Borie, R. G. Parker, and C. A. Tovey.  Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families.  Algorithmica, 7(5&6):555–581, 1992.
  * [11] N. Brettell, J. Horsfield, A. Munaro, G. Paesani, and D. Paulusma.  Bounding the mim-width of hereditary graph classes.  In 15th International Symposium on Parameterized and Exact Computation, volume 180 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. 6, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2020\.
  * [12] B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle.  Boolean-width of graphs.  Theoret. Comput. Sci., 412(39):5187–5204, 2011.
  * [13] B.-M. Bui-Xuan, J. A. Telle, and M. Vatshelle.  Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems.  Theoret. Comput. Sci., 511:66–76, 2013.
  * [14] K. Cameron and P. Hell.  Independent packings in structured graphs.  Math. Program., 105(2-3, Ser. B):201–213, 2006.
  * [15] S. Chaplick, M. Töpfer, J. Voborník, and P. Zeman.  On $H$-topological intersection graphs.  Algorithmica, 83(11):3281–3318, 2021.
  * [16] S. Chaplick and P. Zeman.  Combinatorial problems on $H$-graphs.  Electron. Notes Discret. Math., 61:223–229, 2017.
  * [17] B. Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.
  * [18] B. Courcelle, J. A. Makowsky, and U. Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory Comput. Syst., 33(2):125–150, 2000.
  * [19] M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized algorithms.  Springer, Cham, 2015.
  * [20] K. K. Dabrowski, M. Johnson, and D. Paulusma.  Clique-width for hereditary graph classes.  In Surveys in combinatorics 2019, volume 456 of London Math. Soc. Lecture Note Ser., pages 1–56. Cambridge Univ. Press, Cambridge, 2019\.
  * [21] C. Dallard, F. V. Fomin, P. Golovach, T. Korhonen, and M. Milanič.  Computing tree decompositions with small independence number.  arXiv:2206.15092, 2022.
  * [22] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number in graph classes with a forbidden structure.  In I. Adler and H. Müller, editors, Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK, June 24-26, 2020, Revised Selected Papers, volume 12301 of Lecture Notes in Computer Science, pages 92–105. Springer, 2020.
  * [23] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. II. Tree-independence number.  arXiv:2111.04543, 2022.
  * [24] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. III. Tree-independence number of graphs with a forbidden structure.  arXiv:2206.15092, 2022.
  * [25] C. Dallard, M. Milanič, and K. Štorgel.  Treewidth versus clique number. I. Graph classes with a forbidden structure.  SIAM J. Discrete Math., 35(4):2618–2646, 2021.
  * [26] P. Duchet.  Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs.  In Topics on perfect graphs, volume 88 of North-Holland Math. Stud., pages 67–96. North-Holland, Amsterdam, 1984.
  * [27] H. Eto, F. Guo, and E. Miyano.  Distance-$d$ independent set problems for bipartite and chordal graphs.  J. Comb. Optim., 27(1):88–99, 2014.
  * [28] F. V. Fomin, I. Todinca, and Y. Villanger.  Large induced subgraphs via triangulations and CMSO.  SIAM J. Comput., 44(1):54–87, 2015.
  * [29] A. Frank.  Some polynomial algorithms for certain graphs and hypergraphs.  In Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975), pages 211–226. Congressus Numerantium, No. XV, 1976.
  * [30] M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou.  The complexity of coloring circular arcs and chords.  SIAM J. Algebraic Discrete Methods, 1(2):216–227, 1980.
  * [31] P. Gartland, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and P. Rzążewski.  Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time.  In S. Khuller and V. V. Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 330–341. ACM, 2021.
  * [32] P. A. Golovach and D. Paulusma.  List coloring in the absence of two subgraphs.  Discret. Appl. Math., 166:123–130, 2014.
  * [33] M. Grohe and S. Kreutzer.  Methods for algorithmic meta theorems.  In Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, Washington, DC, USA, January 5-8, 2009, volume 558 of Contemporary Mathematics, pages 181–206. American Mathematical Society, 2009.
  * [34] L. Jaffke, O.-j. Kwon, T. J. F. Strømme, and J. A. Telle.  Mim-width III. Graph powers and generalized distance domination problems.  Theoret. Comput. Sci., 796:216–236, 2019.
  * [35] E. Lee.  Partitioning a graph into small pieces with applications to path transversal.  In P. N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1546–1558. SIAM, 2017.
  * [36] E. Lee.  Partitioning a graph into small pieces with applications to path transversal.  Math. Program., 177(1-2, Ser. A):1–19, 2019.
  * [37] Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, and F. Werner.  The complexity of dissociation set problems in graphs.  Discrete Appl. Math., 159(13):1352–1366, 2011.
  * [38] B. S. Panda, A. Pandey, J. Chaudhary, P. Dane, and M. Kashyap.  Maximum weight induced matching in some subclasses of bipartite graphs.  J. Comb. Optim., 40(3):713–732, 2020.
  * [39] M. Yannakakis.  Node-deletion problems on bipartite graphs.  SIAM J. Comput., 10(2):310–327, 1981.
  * [40] J. You, J. Wang, and Y. Cao.  Approximate association via dissociation.  In Graph-theoretic Concepts in Computer Science, volume 9941 of Lecture Notes in Comput. Sci., pages 13–24. Springer, Berlin, 2016.


# Initial entanglement, entangling unitaries and completely positive maps

Vinayak Jagadish  Quantum Research Group, School of Chemistry and Physics,
University of KwaZulu-Natal, Durban 4001, South Africa  National Institute for
Theoretical Physics (NITheP), KwaZulu-Natal, South Africa  R. Srikanth
Poornaprajna Institute of Scientific Research, Bangalore- 560 080, India
Francesco Petruccione  Quantum Research Group, School of Chemistry and
Physics, University of KwaZulu-Natal, Durban 4001, South Africa  National
Institute for Theoretical Physics (NITheP), KwaZulu-Natal, South Africa

###### Abstract

The problem of conditions on the initial correlations between the system and
the environment that lead to completely positive (CP) or not-completely
positive (NCP) maps has been studied by various authors. Two lines of study
may be discerned: one concerned with families of initial correlations that
induce CP dynamics under the application of an arbitrary joint unitary on the
system and environment; the other concerned with specific initial states that
may be highly entangled. Here we study that latter problem, and highlight the
interplay between the initial correlations and the unitary applied. In
particular, for almost any initial entangled state, one can furnish infinitely
many joint unitaries that generate CP dynamics on the system.

##  I Introduction

The dynamics of a system $S$ is completely positive (CP) if $S$ begins
initially in a product state with its environment $E$, irrespective of the
interaction Breuer and Petruccione (2002). However, if there are initial
$S$-$E$ correlations, then the conditions under which they lead to positive or
not-completely positive (NCP) maps has been studied extensively over the last
decade and is still an active area of research Simmons and Park (1981); Raggio
and Primas (1982); Simmons and Park (1982); Pechukas (1994); Alicki (1995);
Pechukas (1995); Jordan  _et al._ (2004); Carteret  _et al._ (2008); Cuffaro
and Myrvold (2013). In the presence of initial correlations, It was shown
Štelmachovič and Bužek (2001) that identical initial reduced states can lead
to different evolutions under the same system-bath interaction, with the
initial separable state leading to a CP map, but an entangled state leading to
a NCP map. It was pointed out that the question of CPness depended not only on
the initial correlation, but on the joint dynamics, and in particular that
even with initial correlations, a factorizable joint dynamics will always lead
to CP reduced dynamics Salgado and Sanchez-Gomez (2002). This result was
generalized to arbitrary initial correlations in Hayashi  _et al._ (2003). It
was argued that the system dynamics is CP if and only if the initial
correlations lack quantum discord Shabani and Lidar (2009), but the “only if”
part was subsequently weakened Brodutch  _et al._ (2013); Shabani and Lidar
(2016).

Within the construct of direct-sum decomposition of state space, the set of
initial states which include both separable and entangled states for which the
reduced dynamics is CP is addressed Liu and Tong (2014). It was also pointed
out that the dynamics is CP for the set of states if all quantum degrees of
freedom are owned only by the system, and the classical degrees of freedom are
of local accessibility to the system Lu (2016). It was also shown Buscemi
(2014) that initial correlations that lead to a violation of the data
processing inequality correspond to NCP dynamics along with proving that
system-bath correlations that can be obtained by steering a third
(“reference”) system lead to CP dynamics under arbitrary joint unitaries,
generalizing instances of the kind obtained earlier Shabani and Lidar (2016);
Brodutch  _et al._ (2013). Intuitively, this result may be understood as
saying that bipartite correlations that are sufficiently weak as to be
derivable by measuring the reference system in a sufficiently strongly
correlated tripartite system allow CP dynamics of the system of interest.

The above works can be classified in broadly two ways: works that investigate
(sufficiently weak) initial correlations that entail CP dynamics under
arbitrary joint unitaries, and those that study arbitrary initial correlations
of specific states and their interplay with corresponding joint unitaries that
would lead to CP dynamics. It is fair to say that while the former has been
relatively well studied, the latter not so much. Accordingly, here, our focus
will not be on generic initial states that generate CP dynamics under all
system-environment unitaries, but instead to systematically point out how the
interplay of the initial state and the joint dynamics determines CPness of the
reduced dynamics. We thereby point out that even given initial entanglement,
there are in general an infinite number of entangling unitaries that can lead
to CP dynamics of the subsystem.

The plan of this article is as follows. In Sec. II, we motivate the result by
giving an example of an entangling unitary acting on an entangled state
leading to CP dynamics. We then discuss a caveat and state the result in Sec.
III. The measure of CP inducing unitaries are addressed in Sec. IV. We then
conclude in Sec. V.

##  II Entangling unitaries acting on entangled states

As mentioned in Sec. I, vanishing quantum discord is not necessary for CP
dynamics. We now provide a specific illustration of this idea. Consider the
following entangled state

$\ket{\Psi}\equiv\frac{1}{\sqrt{2}}\left[(1-\imath)\cos(\theta)\ket{01}+\sin(\theta)(-\imath\ket{10}+\ket{11})\right],$
(1)

where the system ($S$) is taken to be the second qubit and the first qubit is
treated to be the environment ($E$). To this state, we apply $\sqrt{\rm
CNOT}\equiv\ket{0}\bra{0}\otimes\mathbbm{1}+\ket{1}\bra{1}\otimes\sqrt{\sigma_{x}}$,
($\sigma_{x}$ being the Pauli matrix) which is an entangling unitary, with

$\sqrt{\sigma_{x}}\equiv\frac{1}{2}\left(\begin{array}[]{cc}1+\imath&1-\imath\\\
1-\imath&1+\imath\\\ \end{array}\right).$

At first blush, one might expect that acting such an entangling operation on
an entangled state will lead to NCP reduced dynamics. But, looking at the the
corresponding dynamical (Choi) matrix Sudarshan  _et al._ (1961); Jagadish and
Petruccione (2018), one finds that it turns out to be CP. Specifically, its
eigenvalues, $\lambda_{\pm}$ are as follows

$\lambda_{\pm}=1\pm\frac{\sqrt{7+8\cos(4\theta)+\cos(8\theta)}}{3+\cos(4\theta)},$
(2)

which can be clearly seen to be always positive. This example therefore shows
that a total entangling unitary acting on an entangled state can admit CP
dynamics. There is a simpler way to understand why the action of $\sqrt{\rm
CNOT}$ generates a CP dynamics here. It turns out that the state $\ket{\Psi}$
in Eq. (1) can be expressed as the action of the same entangling operator on a
product state: specifically, $\ket{\Psi}=\sqrt{\rm
CNOT}\ket{0}(\cos\theta\ket{0}+\sin\theta\ket{1})$. Therefore, $\sqrt{\rm
CNOT}\ket{\Psi}={\rm
CNOT}\ket{0}(\cos\theta\ket{0}+\sin\theta\ket{1})=\cos\theta\ket{00}+\sin\theta\ket{11}$.

In other words, the action of the entangling operation on $\ket{\Psi}$ in Eq.
(1) can be seen as an intermediate map of a CP-divisible channel acting on the
initial state $\ket{0}(\cos\theta\ket{0}+\sin\theta\ket{1})$. But it is well
recognized that the intermediate map of a CP-divisible channel– in this the
action of $\sqrt{\rm CNOT}$ on state $\ket{\Psi}$ is necesarily CP Rivas  _et
al._ (2010). This exercise alerts us to a class of entangling operations on
entangled states, that will lead to CP dynamics. This idea provides a broad
response to the belief sometimes held, as mentioned in Sec. I, that initial
entangled correlations necessarily lead to NCP dynamics. This can be used to
construct examples to show that non-vanishing quantum discord does not imply
NCPness, and that there can be (infinitely many, as we shall indicate later)
joint unitaries that lead to CP dynamics. An important caveat is due in this
context, which is discussed below.

##  III Issue of maximal entanglement

Suppose as above, we apply CNOT unitary successively to the product state
$\ket{0}(\cos\theta\ket{0}+\sin\theta\ket{1})$, with ${\rm
CNOT}\equiv\ket{0}\bra{0}\otimes\mathbbm{1}+\ket{1}\bra{1}\otimes\sigma_{x}$,
which has the property that ${\rm CNOT}^{2}=\mathbbm{1}$. Representing the map
in the form acting on the density matrix expressed as a column vector and
calling it the $\mathcal{A}$ matrix following Sudarshan  _et al._ (1961);
Jagadish and Petruccione (2018). Thus, the $\mathcal{A}$ matrix corresponding
to the first application of CNOT is $\mathcal{A}_{1}$, and that corresponding
to the second one is $\mathcal{A}_{2}$. We have
$\mathcal{A}_{1}\cdot\mathcal{A}_{2}=\mathbbm{1}_{4}$, and $\mathcal{A}_{2}$
can be evaluated to be

$\displaystyle\mathcal{A}_{2}$ $\displaystyle=$
$\displaystyle(\mathcal{A}_{1})^{-1}$ (7) $\displaystyle=$
$\displaystyle\sec(2\theta)\left(\begin{array}[]{cccc}\cos^{2}(\theta)&0&0&-\sin^{2}(\theta)\\\
0&\cos^{2}(\theta)&-\sin^{2}(\theta)&0\\\
0&-\sin^{2}(\theta)&\cos^{2}(\theta)&0\\\
-\sin^{2}(\theta)&0&0&\cos^{2}(\theta)\\\ \end{array}\right),$

which upon reshuffling yields the corresponding dynamical matrix (Choi) matrix
Sudarshan  _et al._ (1961); Jagadish and Petruccione (2018),

$\mathcal{B}_{2}=\sec(2\theta)\left(\begin{array}[]{cccc}\cos^{2}(\theta)&0&0&\cos^{2}(\theta)\\\
0&-\sin^{2}(\theta)&-\sin^{2}(\theta)&0\\\
0&-\sin^{2}(\theta)&-\sin^{2}(\theta)&0\\\
\cos^{2}(\theta)&0&0&\cos^{2}(\theta)\\\ \end{array}\right),$ (8)

whose non-vanishing eigenvalues are $-2\sin^{2}(\theta)\sec(2\theta)$ and
$2\cos^{2}(\theta)\sec(2\theta)$. Clearly, one of the two eigenvalues is
negative for any choice of $\theta\neq 0,n\pi$ ($n$ an integer), showing that
the dynamics $\mathcal{A}_{2}$, corresponding to the second action of CNOT is
NCP Jagadish  _et al._ (2019) for such choices. The disentanglement manifests
for example as an increase in system state purity and hence in the separation
of two suitable initial states of the system, leading to NCPness.

######  Lemma 1.

Given an initial state $\ket{\Phi}_{SE}$ that is not maximally entangled and a
unitary $U(t)\equiv e^{-\imath Ht}$ that acts on $\ket{\Phi}_{SE}$, the
reduced dynamics of the system $S$ is CP if there exists a product state
$\ket{\psi}_{S}\otimes\ket{\phi}_{E}$ such that $\ket{\Phi}_{SE}=e^{-\imath
Hs}\ket{\psi}_{S}\otimes\ket{\phi}_{E}$ for $s\geq 0$.

Proof: Suppose $\ket{\Phi}_{SE}=e^{-\imath
Hs}\ket{\psi}_{S}\otimes\ket{\phi}_{E}$. Then, $U(t)\ket{\Phi}_{SE}=e^{-\imath
H(s+t)}\ket{\psi}_{S}\otimes\ket{\phi}_{E}$ describes the joint state at time
$t$, and it is known that if the initial state is a product, then the
evolution in the interval $[-s,t]$ is CP-divisible. In turn, CP-divisibility
implies that intermediate dynamics of the system during the interval $[0,t]$
is CP Rivas  _et al._ (2010); Hall  _et al._ (2014). The restriction of non-
maximality is evident in the CNOT example above, where we find that the
further evolution of a maximally entangled state can lead to disentanglement
and hence NCP intermediate dynamics.

$\blacksquare$

As a matter of semantic clarification, let us mention that by “initial
correlation”, we mean the correlation between the system and the environment
at a fiducial instant of time designated $t=0$. The argument that initial
correlations should involve only product states is not only mathematically
more restrictive, but is potentially unverifiable.

##  IV Dimension of the set of unitaries inducing CP dynamics

The preceding surprising result evokes the question of the probability that,
given an entangled state $\ket{\phi}_{SE}$, applying a random joint unitary
will produce a CP reduced dynamics. Now, let us take the unitary to be
$\sqrt{\rm
CPHASE}\equiv\ket{0}\bra{0}\otimes\mathbbm{1}+\ket{1}\bra{1}\otimes\sqrt{\sigma_{z}}$
acting on the state $\ket{\Psi}_{SE}$ in Eq. (1) and look at the reduced
dynamics.

The corresponding dynamical matrix $\mathcal{B}$ turns out to be NCP. As an
example, $\mathcal{B}$ for $\theta=\pi/4$ is

$\mathcal{B}^{\pi/4}=\frac{1}{4}\left(\begin{array}[]{cccc}4&0&1-\imath&2-2\imath\\\
0&0&0&-1+\imath\\\ 1+\imath&0&0&0\\\ 2+2\imath&-1-\imath&0&4\\\
\end{array}\right),$ (9)

with the eigenspectrum {-0.0703, -0.2362, 0.5291, 1.7774}, the two negative
eigenvalues clearly indicating that the map is NCP. The important point to be
noted is that the same entangled state Eq. (1) when acted upon by two
different unitaries made the reduced dynamics CP in the case of $\sqrt{\rm
CNOT}$ and NCP for the case of $\sqrt{\rm CPHASE}$.

Per Lemma 1, the backward evolution using the Hamiltonian
$H_{\phi}\equiv\ket{0}\bra{0}\otimes\mathbbm{1}+\ket{1}\bra{1}\otimes\sigma_{z}$
that generates the C-Phase gate, will at no time lead to a product state. This
may be explicitly checked by finding that the application of the evolution
$e^{\imath H_{\phi}t}$ to the state in Eq. (1) leads to a non-vanishing
entanglement in the system $SE$. In fact, the reduced state of the system is

$\frac{1}{4}\left(\begin{array}[]{cc}1&-\imath e^{-\imath t}\\\ \imath
e^{\imath t}&3\\\ \end{array}\right),$ (10)

with a constant von Neumann entropy of
$\frac{1}{4}[5-2\sqrt{2}\coth^{-1}(\sqrt{2})]$, showing that the entanglement
is a constant.

Despite the above result, one can show that given any initial non-maximally
entangled state $\ket{\phi}_{SE}$, there are infinitely many joint unitaries
that, acting on a given entangled state $\ket{\Psi_{SE}}$ produce a CP
dynamics of the system $S$ for a finite time which leads to the following
result.

######  Theorem 1.

Given any non-maximally entangled state $\ket{\Phi}_{SE}$ of a system $S$ of
dimension $d_{S}$ and its environment $E$ of dimension $d_{E}$, there are
infinitely many entangling unitaries that induce CP dynamics on $S$. The
dimension $D$ of this set scales as $D=\mathcal{O}\left((d_{S})^{-2}\right)$
for a sufficiently large environment.

Proof.  For any given (possibly entangled) state $\ket{\Phi}_{SE}$, there is a
product state $\ket{\phi}_{S}\otimes\ket{\phi^{+}}_{E}$ and an entangling
Hamiltonian $H$, such that we can construct a unitary $U_{SE}^{(1)}(t)\equiv
e^{-\imath Ht}$ and
$\ket{\Phi}_{SE}=U_{SE}^{(1)}(t)\ket{\phi}_{S}\otimes\ket{\phi^{+}}_{E}$. Per
Lemma 1, there is an entangling unitary $U^{(2)}_{SE}\equiv e^{-\imath Hs}$,
for sufficiently small time parameter $s$, such that $U^{(2)}_{SE}$ acting on
$\ket{\Phi}_{SE}$ induces a CP dynamics on $S$ since it can be considered as
an intermediate map of the system’s CP-divisible evolution under
$U^{(2)}_{SE}\ket{\Phi}_{SE}=e^{-\imath
H(t+s)}\ket{\phi}_{S}\otimes\ket{\phi^{+}}_{E}$.

Now consider any other product state $\ket{\psi}_{S}\otimes\ket{\psi^{+}}_{E}$
in the same subspace. There necessarily exists an entangling unitary
$U_{SE}^{\prime}$ such that
$\ket{\Phi}_{SE}=U_{SE}^{\prime}\ket{\psi}_{S}\otimes\ket{\psi^{+}}_{E}$, and
we define Hamiltonian $H^{\prime}$ such that $U_{SE}^{\prime}=e^{-\imath
H^{\prime}t}$. Then, one can write down another entangling unitary
$U^{(2\prime)}_{SE}\equiv e^{-\imath H^{\prime}s}$, corresponding to the pre-
initial product state $\ket{\psi}_{S}\otimes\ket{\psi^{+}}_{E}$, that would
also induce a CP dynamics in the system $S$ starting in the same initial joint
state $\ket{\Phi}_{SE}$. Therefore, given an entangling interaction unitary
$U^{(2)}_{SE}$ that induces CP dynamics, we can produce another one
corresponding to another pre-initial product state.

Extending the above reasoning, every product state can be used to construct an
entangling unitary of the kind $U^{(2)}_{SE}$ that induces CP system dynamics
acting on the initial state $\ket{\Phi}_{SE}$. The pre-initial product states
can be put into a one-to-one correspondence with local unitaries $U_{\rm
loc}$, which are elements of the group $SU(d_{S})\times SU(d_{E})$. This is
because the set of all product states is equivalent to this group acting on a
fiducial product state. On the other hand, an arbitrary interaction unitary is
an element of the group $SU(d_{S}d_{E})$.

The ratio of the number of parameters required to characterize such a unitary
versus an arbitrary joint unitary is, then, simply the ratio between the
number of parameters required to specific an arbitrary local unitary versus an
arbitrary joint unitary, namely,

$\frac{|SU(d_{S})\times
SU(d_{E})|}{|SU(d_{S}d_{E})|}\approx\frac{d_{S}^{2}+d_{E}^{2}}{d_{S}^{2}d_{E}^{2}},$

which tends to $(d_{S})^{-2}$ in the limit that $d_{E}\gg d_{S}$. It is
possible that, for a given, specific initial state, other joint unitaries can
be found that, acting on a given entangled state, induce CP dynamics on the
system, hence the above count may be considered as a lower bound on the
dimension of the set of such unitary operators. $\blacksquare$

Quite generally, we may remark the following: suppose, following Theorem 1
that the initial entangled state $\ket{\Psi}_{SE}\equiv
U_{SE}(\ket{\phi_{1}}_{S}\otimes\ket{\phi_{2}}_{E})$ is such that
$U^{\prime}_{SE}\ket{\Psi}_{SE}$ induces CP dynamics on the system $S$. This
means that $U_{SE}^{\prime}$ leads to the intermediate map of the CP-divisible
map under the total evolution generated by $U_{SE}^{\prime}U_{SE}$. Let
$U_{L}$ be a local unitary with the property that $U_{L}^{\prime}\equiv
U_{SE}^{\dagger}U_{L}U_{SE}$ is also a local unitary. Then,
$(U^{\prime}_{SE}U_{L})\ket{\Psi}_{SE}$ will also correspond to CP dynamics of
$S$.

To show this note that
$U^{\prime}_{SE}U_{L}\ket{\Psi}_{SE}=U_{SE}^{\prime}U_{L}U_{SE}(\ket{\phi_{1}}_{S}\otimes\ket{\phi_{2}})=U_{SE}^{\prime}U_{SE}U_{L}^{\prime}(\ket{\phi_{1}}_{S}\otimes\ket{\phi_{2}})$,
i.e., leading to a CP-divisible evolution evolution given by the action of the
joint unitary $U_{SE}^{\prime}U_{SE}$ on the pre-initial product state
$U_{L}^{\prime}(\ket{\phi_{1}}_{S}\otimes\ket{\phi_{2}}_{E})$. By Lemma 1,
this will lead to CP dynamics on $S$.

As examples of this idea, suppose $U_{SE}=U_{SE}^{\prime}=\sqrt{\rm CNOT}$ as
in Example 1. One notes that $U_{L}:=\sigma_{z}\otimes\sigma_{x}$ preserves
its locality when transformed under $U_{SE}^{\prime}$. Then, it follows that
the action of $U_{SE}^{\prime}U_{L}\equiv\sqrt{\rm
CNOT}(\sigma_{z}\otimes\sigma_{x})$ will correspond to CP dynamics of system
$S$. Yet another example would be $\sqrt{\rm
CNOT}(\sigma_{z}\otimes\sqrt[\scriptstyle n]{\sigma_{x}})$, with $n$ being any
integer. On the other hand, we find that
$U_{SE}U_{L}U_{SE}^{\dagger}\equiv\sqrt{\rm
CNOT}(\sigma_{x}\otimes\sigma_{x})\sqrt{\rm CNOT}^{\dagger}$ is not a local
unitary, and correspondingly, $U_{SE}^{\prime}U_{L}\equiv\sqrt{\rm
CNOT}(\sigma_{x}\otimes\sigma_{x})$ will correspond to NCP dynamics of system
$S$. More generally, if
$U_{SE}=\ket{0}\bra{0}\otimes\mathbbm{1}+\ket{1}\bra{1}\otimes U$, then a
local operator $U_{L}\equiv\sigma_{z}\otimes V$, such that $[U,V]=0$ or
$\\{U,V\\}=0$, can be used to augment $U_{SE}^{\prime}$ to
$U_{SE}^{\prime}U_{L}$ while retaining the CP dynamics of the system $S$.

##  V Conclusions

The problem of initial entanglement and CP maps still poses new questions. In
this article, aided with simple examples, we have shown the interplay of the
initial correlations and the joint dynamics of the system and environment in
deciding the CPness of the reduced dynamics of the system of interest. In
particular, for any initial entangled state (barring maximal entanglement) of
the system and environment, one can furnish a two-body unitary that generates
CP dynamics on the system, and for any given interaction unitary one can
furnish an entangled state such that the action of the latter unitary
generates CP reduced dynamics on the system. We showed that in fact there are
in general an infinite number of such entangling unitaries that can act on a
given (non-maximal) entangled initial state, but still lead to CP dynamics of
the system. Specifically, we obtained the scaling of the dimension of the set
of these unitaries. The general description of entangling operators that may
be applied to a given entangled state leading to CP dynamics should be an
interesting problem of future study.

##  VI Acknowledgements

The work of V.J. and F.P. is based upon research supported by the South
African Research Chair Initiative of the Department of Science and Innovation
and National Research Foundation (NRF) (Grant UID: 64812). R.S. acknowledges
the support of Department of Science and Technology (DST), India, Grant No.:
MTR/2019/001516.

## References

  * Breuer and Petruccione (2002) H.-P. Breuer and F. Petruccione,  _The theory of open quantum systems_ (Oxford University Press, 2002).
  * Simmons and Park (1981) R. F. Simmons and J. L. Park, Found. Phys. 11, 47 (1981).
  * Raggio and Primas (1982) G. A. Raggio and H. Primas, Found. Phys. 12, 433 (1982).
  * Simmons and Park (1982) R. F. Simmons and J. L. Park, Found. Phys. 12, 437 (1982).
  * Pechukas (1994) P. Pechukas, Phys. Rev. Lett. 73, 1060 (1994).
  * Alicki (1995) R. Alicki, Phys. Rev. Lett. 75, 3020 (1995).
  * Pechukas (1995) P. Pechukas, Phys. Rev. Lett. 75, 3021 (1995).
  * Jordan  _et al._ (2004) T. F. Jordan, A. Shaji, and E. C. G. Sudarshan, Phys. Rev. A 70, 052110 (2004).
  * Carteret  _et al._ (2008) H. A. Carteret, D. R. Terno, and K. Życzkowski, Phys. Rev. A 77, 042113 (2008).
  * Cuffaro and Myrvold (2013) M. E. Cuffaro and W. C. Myrvold, Philosophy of Science 80, 1125 (2013).
  * Štelmachovič and Bužek (2001) P. Štelmachovič and V. Bužek, Phys. Rev. A 64, 062106 (2001).
  * Salgado and Sanchez-Gomez (2002) D. Salgado and J. L. Sanchez-Gomez, arXiv:quant-ph/0211164 (2002), arXiv: quant-ph/0211164.
  * Hayashi  _et al._ (2003) H. Hayashi, G. Kimura, and Y. Ota, Phys. Rev. A 67, 062109 (2003).
  * Shabani and Lidar (2009) A. Shabani and D. A. Lidar, Phys. Rev. Lett. 102, 100402 (2009).
  * Brodutch  _et al._ (2013) A. Brodutch, A. Datta, K. Modi, A. Rivas, and C. A. Rodrí guez-Rosario, Phys. Rev. A 87, 042301 (2013).
  * Shabani and Lidar (2016) A. Shabani and D. A. Lidar, Phys. Rev. Lett. 116, 049901 (2016).
  * Liu and Tong (2014) L. Liu and D. M. Tong, Phys. Rev. A 90, 012305 (2014).
  * Lu (2016) X.-M. Lu, Phys. Rev. A 93, 042332 (2016).
  * Buscemi (2014) F. Buscemi, Phys. Rev. Lett. 113, 140502 (2014).
  * Sudarshan  _et al._ (1961) E. C. G. Sudarshan, P. M. Mathews, and J. Rau, Phys. Rev. 121, 920 (1961).
  * Jagadish and Petruccione (2018) V. Jagadish and F. Petruccione, Quanta 7, 54 (2018).
  * Rivas  _et al._ (2010) A. Rivas, S. F. Huelga, and M. B. Plenio, Phys. Rev. Lett. 105, 050403 (2010).
  * Jagadish  _et al._ (2019) V. Jagadish, R. Srikanth, and F. Petruccione, Phys. Rev. A 100, 012336 (2019).
  * Hall  _et al._ (2014) M. J. W. Hall, J. D. Cresser, L. Li, and E. Andersson, Phys. Rev. A 89, 042120 (2014).