17414 LABEL:LastPageJan. 08, 2020Nov. 29, 2021

# On Supergraphs Satisfying CMSO Properties

Mateus de Oliveira Oliveira  Department of Informatics - University of Bergen,
Bergen, Norway<EMAIL_ADDRESS>
###### Abstract.

Let CMSO denote the counting monadic second-order logic of graphs. We give a
constructive proof that for some computable function $f$, there is an
algorithm $\mathfrak{A}$ that takes as input a CMSO sentence $\varphi$, a
positive integer $t$, and a connected graph $G$ of maximum degree at most
$\Delta$, and determines, in time $f(|\varphi|,t)\cdot 2^{O(\Delta\cdot
t)}\cdot|G|^{O(t)}$, whether $G$ has a supergraph $G^{\prime}$ of treewidth at
most $t$ such that $G^{\prime}\models\varphi$.

The algorithmic metatheorem described above sheds new light on certain
unresolved questions within the framework of graph completion algorithms. In
particular, using this metatheorem, we provide an explicit algorithm that
determines, in time $f(d)\cdot 2^{O(\Delta\cdot d)}\cdot|G|^{O(d)}$, whether a
connected graph of maximum degree $\Delta$ has a planar supergraph of diameter
at most $d$. Additionally, we show that for each fixed $k$, the problem of
determining whether $G$ has an $k$-outerplanar supergraph of diameter at most
$d$ is strongly uniformly fixed parameter tractable with respect to the
parameter $d$.

This result can be generalized in two directions. First, the diameter
parameter can be replaced by any contraction-closed effectively CMSO-definable
parameter $\mathbf{p}$. Examples of such parameters are vertex-cover number,
dominating number, and many other contraction-bidimensional parameters. In the
second direction, the planarity requirement can be relaxed to bounded genus,
and more generally, to bounded local treewidth.

###### Key words and phrases:

CMSO Logic, Algorithmic Metatheorems, Graph Completion, Bidimensionality

##  1\. Introduction

††A preliminary version of this work appeared at the 26th EACSL Annual
Conference on Computer Science Logic, CSL 2017 [dOO17].

A parameterized problem ${\mathcal{L}}\subseteq\Sigma^{*}\times{\mathbb{N}}$
is said to be fixed parameter tractable (FPT) if there exists a function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ such that for each
$(x,k)\in\Sigma^{*}\times{\mathbb{N}}$, one can decide whether
$(x,k)\in{\mathcal{L}}$ in time $f(k)\cdot|x|^{O(1)}$, where $|x|$ is the size
of $x$ [DF99]. Using non-constructive methods derived from Robertson and
Seymour’s graph minor theory, one can show that certain problems can be solved
in time $f(k)\cdot|x|^{O(1)}$ for some function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$. The caveat is that the function $f$
arising from these non-constructive methods is often not known to be
computable. Interestingly, for some problems it is not even clear how to
obtain algorithms running in time $f_{1}(k)\cdot|x|^{f_{2}(k)}$ for some
computable functions $f_{1}$ and $f_{2}$. In this work we will use techniques
from automata theory and structural graph theory to provide constructive FPT
and XP algorithms for problems for which only non-constructive parameterized
algorithms were known.

The counting monadic second-order logic of graphs $(\mbox{CMSO})$ extends
first order logic by allowing quantifications over sets of vertices and sets
of edges, and by introducing the notion of modular counting predicates. This
logic is expressive enough to define several interesting graph properties,
such as Hamiltonicity, $3$-colorability, connectivity, planarity, fixed genus,
minor embeddability, etc. Additionally, when restricted to graphs of constant
treewidth, CMSO logic is able to define precisely those properties that are
recognizable by finite state tree-automata operating on encodings of tree-
decompositions, or equivalently, those properties that can be described by
equivalence relations with finite index [Cou90, AF93, BP16, BP17].

The expressiveness of CMSO logic has had a great impact in algorithmic theory
due to Courcelle’s model-checking theorem [Cou90]. This theorem states that
for some computable function $f:{\mathbb{N}}^{2}\rightarrow{\mathbb{N}}$, one
can determine in time111$|G|$ denotes the number of vertices in $G$, and
$|\varphi|$, the number of symbols in $\varphi$. $f(|\varphi|,t)\cdot|G|$
whether a given graph $G$ of treewidth at most $t$ satisfies a given CMSO
sentence $\varphi$. As a consequence of Courcelle’s theorem, many
combinatorial problems, such as Hamiltonicity or $3$-colorability, which are
NP-hard on general graphs, can be solved in linear time on graphs of constant
treewidth. In this work we will consider a class problems on graphs of
constant treewidth which cannot be directly addressed via Courcelle’s theorem,
either because it is not clear how to formulate the set of positive instances
of such a problem as a CMSO-definable set, or because although the set of
positive instances is CMSO-definable, it is not clear how to explicitly
construct a CMSO sentence $\varphi$ defining such set. For instance, sets of
graphs that are closed under minors very often fall in the second category due
to Robertson and Seymour’s graph minor theorem.

###  1.1. Main Result

Let $\varphi$ be a CMSO sentence, and $t$ be a positive integer. We say that a
graph $G^{\prime}$ is a $(\varphi,t)$-supergraph of a graph $G$ if the
following conditions are satisfied: $G^{\prime}$ satisfies $\varphi$,
$G^{\prime}$ has treewidth at most $t$, and $G^{\prime}$ is a supergraph of
$G$ (possibly containing more vertices than $G$).

In our main result, Theorem 10, we devise an algorithm $\mathfrak{A}$ that
takes as input a CMSO sentence $\varphi$, a positive integer $t$, and a
connected graph $G$ of maximum degree $\Delta$, and determines in time
$f(|\varphi|,t)\cdot 2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}$ whether $G$ has a
$(\varphi,t)$-supergraph. We note that our algorithm determines the existence
of such a $(\varphi,t)$-supergraph $G^{\prime}$ without the need of
necessarily constructing $G^{\prime}$. Therefore, no bound on the size of a
candidate supergraph $G^{\prime}$ is imposed. Note that a priori even the fact
that the problem is decidable is not clear.

In the next three sub-sections we show how Theorem 10 can be used to provide
partial solutions to certain long-standing open problems in parameterized
complexity theory.

###  1.2. Planar Diameter Improvement

In the planar diameter improvement problem (PDI), we are given a graph $G$,
and a positive integer $d$, and the goal is to determine whether $G$ has a
planar supergraph $G^{\prime}$ of diameter at most $d$. Note that the set of
YES instances for the PDI problem is closed under minors. In other words, if
$G$ has a planar supergraph of diameter at most $d$, then any minor $H$ of $G$
also has such a supergraph. Therefore, using non-constructive arguments from
Robertson and Seymour’s graph minor theory [RS95, RS04] in conjunction with
the fact planar graphs of constant diameter have constant treewidth, one can
show that for each fixed $d$, there exists an algorithm $\mathfrak{A}_{d}$
which determines in linear time whether a given $G$ has diameter at most $d$.
The problem is that the non-constructive techniques mentioned above provide us
with no clue about what the algorithm $\mathfrak{A}_{d}$ actually is. This
problem can be partially remedied using a technique called effectivization by
self-reduction introduced by Fellows and Langston [FL89, DF99]. Using this
technique one can show that for some function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, there exists a single algorithm
$\mathfrak{A}$ which takes a graph $G$ and a positive integer $d$ as input,
and determines in time $f(d)\cdot|G|^{O(1)}$ whether $G$ has a planar
supergraph of diameter at most $d$. The caveat is that the function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ bounding the influence of the
parameter $d$ in the running time of the algorithm mentioned above is not
known to be computable.

Obtaining a fixed parameter tractability result for the PDI problem with a
computable function $f$ is a notorious and long-standing open problem in
parameterized complexity theory [DF99, FD95, CFK+15]. Indeed, when it comes to
explicit algorithms, the status of the PDI problem is much more elusive. As
remarked in [CGK+15], even the problem of determining whether PDI can be
solved in time $f_{1}(d)\cdot|G|^{f_{2}(d)}$ for computable functions
$f_{1},f_{2}:{\mathbb{N}}\rightarrow{\mathbb{N}}$ is open.

Using Theorem 10 we provide an explicit algorithm that solves the PDI problem
for connected graphs in time ${f(d)\cdot 2^{O(\Delta\cdot d)}\cdot|G|^{O(d)}}$
where $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ is a computable function, and
$\Delta$ is the maximum degree of $G$. This result settles an open problem
stated in [CGK+15] in the case in which the input graph is connected and has
bounded (even logarithmic) degree. We note that our algorithm imposes no
restriction on the degree of a prospective supergraph $G^{\prime}$.

###  1.3. $k$-Outerplanar Diameter Improvement

A graph is $1$-outerplanar if it can be embedded in the plane in such a way
that all vertices lie in the outer-face of the embedding. A graph is
$k$-outerplanar if it can be embedded in the plane in such a way that that
deleting all vertices in the outer-face of the embedding yields a
$(k-1)$-outerplanar graph. The $k$-outerplanar diameter improvement problem
($k$-OPDI) is the straightforward variant of PDI in which the completion is
required to be $k$-outerplanar instead of planar. In [CGK+15] Cohen at al.
devised an explicit polynomial time algorithm for the $1$-OPDI problem. The
complexity of the $k$-outerplanar diameter improvement problem was left open
for $k\geq 2$. Using Theorem 10 we show that the $k$-OPDI problem can be
solved in time $f(k,d)\cdot 2^{O(\Delta\cdot k)}\cdot|G|^{O(k)}$ where
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$ is a computable
function. In other words, for each fixed $k$, the $k$-outerplanar diameter
improvement problem is strongly uniformly fixed parameter tractable with
respect to the diameter parameter $d$ for bounded degree connected input
graphs.

###  1.4. Contraction-Closed Parameters

A graph parameter is a function $\mathbf{p}$ that associates a non-negative
integer with each graph. We say that such a parameter is contraction-closed if
$\mathbf{p}(G)\leq\mathbf{p}(G^{\prime})$ whenever $G$ is a contraction of
$G^{\prime}$. For instance, the diameter of a graph is clearly a contraction-
closed parameter. We say that a graph parameter $\mathbf{p}$ is effectively
CMSO-definable if there exists a computable function $\alpha$, and an
algorithm that takes a positive integer $k$ as input and constructs a CMSO
formula $\varphi_{k}$ that is true on a graph $G$ if and only if
$\mathbf{p}(G)\leq k$.

The results described in the previous subsections can be generalized in two
directions. First, the diameter parameter can be replaced by any effectively
CMSO-definable contraction closed parameter that is unbounded on Gamma graphs.
These graphs were defined in [FGT11] with the goal to provide a simplified
exposition of the theory of contraction-bidimensionality. In particular, many
well studied parameters that arise often in bidimensionality theory satisfy
the conditions listed above. Examples of such parameters are the sizes of a
minimum vertex cover, feedback vertex set, maximal matching, dominating set,
edge dominating set, connected dominating set etc. On the other direction, the
planarity requirement can be relaxed to CMSO definable graph properties that
exclude some apex graph as a minor. These properties are also known in the
literature as bounded local-treewidth properties. For instance, embeddability
on surfaces of genus $g$, for fixed $g$, is one of such properties.

###  1.5. Related Work

As mentioned above, given a CMSO sentence $\psi$ and a positive integer $t$,
one can use Courcelle’s model checking theorem to determine in time
$f(|\psi|,t)\cdot|G|^{O(1)}$ whether a given graph $G$ of treewidth at most
$t$ satisfies $\psi$. Therefore, given a CMSO sentences $\varphi$ and a
positive integer $t$, we may consider the following algorithmic approach to
decide whether a given graph $G$ has a $(\varphi,t)$-supergraph: first, we
construct a formula $\psi_{\varphi,t}$ which is true on a graph $G$ if there
is a model $G^{\prime}$ of $\varphi$ of treewidth at most $t$ such that $G$ is
a subgraph of $G^{\prime}$. In other words, $\psi_{\varphi,t}$ defines the
subgraph closure of the set of models of $\varphi$ of treewidth at most $t$.
Then, to determine whether $G$ has a $(\varphi,t)$-supergraph, it is enough to
determine whether $G$ satisfies $\psi_{\varphi,t}$ using Courcelle’s model
checking theorem.

Unfortunately, this approach cannot work in general. The problem is that there
exist CMSO definable families of graphs whose subgraph closure is not CMSO
definable. For instance, let $\mathcal{L}=\\{L_{n}\\}_{n\in{\mathbb{N}}}$ be
the family of ladder graphs, where $L_{n}$ is the ladder with $n$ steps222The
vertices of $L_{n}$ are $a_{1},...,a_{n}$ and $b_{1},...,b_{n}$, and the edges
are $\\{a_{i},b_{i}\\}$ for $i\in[n]$, $\\{a_{i},a_{i+1}\\}$ for $i\in[n-1]$,
and $\\{b_{i},b_{i+1}\\}$ for $i\in[n-1]$.. It is easy to see that
$\mathcal{L}$ is CMSO definable and every graph in $\mathcal{L}$ has treewidth
at most $2$. Nevertheless, the subgraph closure of $\mathcal{L}$ does not have
finite index. Therefore, this subgraph closure is not CMSO definable, since
CMSO definable classes of graphs of constant treewidth have finite index.

Interestingly, when the property defined by $\varphi$ is contraction closed,
then the sentence $\psi_{\varphi,t}$ defines a minor-closed property
$\mathcal{P}$ whose treewidth is bounded by $t$. Additionally, it follows from
Robertson and Seymour graph minor theorem that each minor-closed property can
be characterized by a finite set $\mathcal{M}$ of forbidden minors. Therefore,
if we were able to enumerate the minors in $\mathcal{M}$ constructively, we
would immediately obtain a constructive polynomial time algorithm for
determining whether a given graph $G$ has a $(\varphi,t)$-supergraph. It is
worth noting that Adler, Kreutzer and Grohe have shown that if a minor-free
graph property $\mathcal{P}$ is MSO definable and has constant treewidth, then
one can effectively enumerate the set of forbidden minors for $\mathcal{P}$
[AGK08]. In particular, by giving the sentence $\psi_{\varphi,t}$ as input to
the algorithm in [AGK08] we would get a list of forbidden minors
characterizing the set of graphs that have a $(\varphi,t)$-supergraph.
Nevertheless, the problem with this approach is that it is not clear how the
sentence $\psi_{\varphi,t}$ can be constructed from $\varphi$ and $t$.

In the embedded planar diameter improvement problem (EPDI), the input consists
of a planar graph $G$ embedded in the plane, and a positive integer $d$. The
goal is to determine whether one can add edges to the faces of this embedding
in such a way that the resulting graph has diameter at most $d$. The
difference between this problem and the PDI problem mentioned above is that in
the EPDI problem, an embedding is given at the input, and edges must be added
in such a way that the embedding is preserved, while in the PDI problem, no
embedding is given at the input. Recently, it was shown in [LdOOS18] that EPDI
for $n$-vertex graphs can be solved in time $2^{d^{O(d)}}n^{O(d)}$, while the
analogous embedded problem for $k$-outerplanar graphs can be solved in time
$2^{d^{O(d)}}n^{O(k)}$.

It is worth noting that the algorithms in [LdOOS18] heavily exploit the
embedding of the input graph by viewing separators as nooses \- simple closed
curves in the plane that touch the graph only in the vertices (see e.g.
[BMT03]). Additionally, it is currently unknown both whether PDI can be
reduced to EPDI in XP time and whether EPDI can be reduced in XP time to PDI.
Therefore it is not clear if the algorithm for EPDI can be used to provide a
strongly uniform XP algorithm for PDI on general graphs. It is also worth
noting that no hardness results for either PDI or EPDI are known. Indeed,
determining whether either of these problems is NP-hard is also a long-
standing open problem.

###  1.6. Proof Sketch And Organization of the Paper

In Section 2 we state some preliminary definitions. In Section 3 we define the
notions of concrete bags, and concrete tree decompositions. Intuitively, a
concrete tree-decomposition is an algebraic structure that represents a graph
together with one of its tree decompositions. Using such structures we are
able to define infinite families of graphs via tree-automata that accept
infinite sets of tree decompositions. In particular, Courcelle’s theorem can
be transposed to this setting. More precisely, there is a computable function
$f$ such that for each CMSO sentence $\varphi$ and each $t\in{\mathbb{N}}$,
one can construct in time $f(|\varphi|,t)$ a tree automaton
${\mathcal{A}}(\varphi,t)$ which accept precisely those concrete tree
decompositions of width at most $t$ that give rise to graphs satisfying
$\varphi$ (Theorem 2).

In Section 4 we define the notion of sub-decomposition of a concrete tree
decomposition. Intuitively, if a concrete tree decomposition $\mathbf{T}$
represents a graph $G$, then a sub-decomposition of $\mathbf{T}$ represents a
sub-graph of $G$. We show that given a tree-automaton ${\mathcal{A}}$
accepting a set ${\mathcal{L}}({\mathcal{A}})$ of concrete tree
decompositions, one can construct a tree automaton
$\mathrm{Sub}({\mathcal{A}})$ which accepts precisely those sub-decompositions
of concrete tree decompositions in ${\mathcal{L}}({\mathcal{A}})$ (Theorem 3).

In Section 5, we introduce the main technical tool of this work. More
specifically, we show that for each connected graph $G$ of maximum degree
$\Delta$, one an construct in time $2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}$ a
tree-automaton ${\mathcal{A}}(G,t)$ whose language
${\mathcal{L}}({\mathcal{A}}(G,t))$ consists precisely of those concrete tree
decompositions of width at most $t$ that give rise to $G$ (Theorem 8).

In Section 6 we argue that the problem of determining whether $G$ has a
supergraph of treewidth at most $t$ satisfying $\varphi$ is equivalent to
determining whether the intersection of ${\mathcal{L}}({\mathcal{A}}(G,t+1))$
with ${\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$ is non-empty.
By combining Theorems 2, 3 and 8, we infer that this problem can be solved in
time ${f(|\varphi|,t)\cdot 2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}}$ (Theorem 10).
Finally, in Section 7, we apply Theorem 10 to obtain explicit algorithms for
several supergraph problems involving contraction-closed parameters.

##  2\. Preliminaries

For each $n\in{\mathbb{N}}$, we let $[n]=\\{1,...,n\\}$. We let
$[0]=\emptyset$. For each finite set $U$, we let $\mathcal{P}(U)$ denote the
set of subsets of $U$. For each $r\in{\mathbb{N}}$ and each finite set $U$, we
let $\mathcal{P}^{\leq}(U,r)=\\{U^{\prime}\subseteq U\mid|U^{\prime}|\leq
r\\}$ be the set of subsets of $U$ of size at most $r$, and
$\mathcal{P}^{=}(U,r)=\\{U^{\prime}\subseteq U\mid|U^{\prime}|=r\\}$ be the
set of subsets of $X$ of size precisely $r$. If $A,A_{1},...,A_{k}$ are sets,
then we write $A=A_{1}\;\dot{\cup}\;A_{2}\;\dot{\cup}...\dot{\cup}\;A_{k}$ to
indicate that $A_{i}\cap A_{j}=\emptyset$ for $i\neq j$, and that $A$ is the
disjoint union of $A_{1},..,A_{k}$.

##### Graphs:

A graph is a triple $G=(V_{G},E_{G},\mathrm{Inc}_{G})$ where $V_{G}$ is a set
of vertices, $E_{G}$ is a set of edges, and $\mathrm{Inc}_{G}\subseteq
E_{G}\times V_{G}$ is an incidence relation. For each $e\in E_{G}$ we let
$\mathit{endpts}(e)=\\{v\mid\mathrm{Inc}_{G}(e,v)\\}$ be the set of endpoints
of $e$, and we assume that $|\mathit{endpts}(e)|$ is either $0$ or $2$. We
note that our graphs are allowed to have multiple edges, but no loops. We say
that a graph $H$ is a subgraph of $G$ if $V_{H}\subseteq V_{G}$,
$E_{H}\subseteq E_{G}$ and $\mathrm{Inc}_{H}=\mathrm{Inc}_{G}\cap E_{H}\times
V_{H}$. Alternatively, we say that $G$ is a supergraph of $H$. The degree of a
vertex $v\in V_{G}$ is the number $d(v)$ of edges incident with $v$. We let
$\Delta(G)$ denote the maximum degree of a vertex of $G$.

A path in a graph $G$ is a sequence $v_{1}e_{1}v_{2}...e_{n-1}v_{n}$ where
$v_{i}\in V_{G}$ for $i\in[n]$, $e_{i}\in E_{G}$ for $i\in[n-1]$, $v_{i}\neq
v_{j}$ for $i\neq j$, and $\\{v_{i},v_{i+1}\\}=\mathit{endpts}(e_{i})$ for
each $i\in[n-1]$. We say that $G$ is connected if for every two vertices
$v,v^{\prime}\in V_{G}$ there is a path whose first vertex is $v$ and whose
last vertex is $v^{\prime}$.

Let $G$ and $H$ be graphs. An isomorphism from $G$ to $H$ is a pair of
bijections $\mu=(\dot{\mu}:V_{G}\rightarrow
V_{H},\overline{\mu}:E_{G}\rightarrow E_{H})$ such that for every $e\in E_{G}$
if $\mathit{endpts}(e)=\\{v,v^{\prime}\\}$ then
$\mathit{endpts}(\overline{\mu}(e))=\\{\dot{\mu}(v),\dot{\mu}(v^{\prime})\\}$.
We say that $G$ and $H$ are isomorphic if there is an isomorphism from $G$ to
$H$.

##### Treewidth:

A tree is an acyclic graph $T$ containing a unique connected component. To
avoid confusion we may call the vertices of a tree “nodes” and call their
edges “arcs”. We let $\mathit{nodes}(T)$ denote the set of nodes of $T$ and
$\mathit{arcs}(T)$ denote its set of arcs. A tree decomposition of a graph $G$
is a pair $(T,\beta)$ where $T$ is a tree and
$\beta:\mathit{nodes}(T)\rightarrow\mathcal{P}(V_{G})$ is a function that
labels nodes of $T$ with subsets of vertices of $G$ in such a way that the
following conditions are satisfied.

  1. (1)

$\bigcup_{u\in\mathit{nodes}(T)}\beta(u)=V_{G}$

  2. (2)

For every $e\in E_{G}$, there exists a node $u\in\mathit{nodes}(T)$ such that
$\mathit{endpts}(e)\subseteq\beta(u)$

  3. (3)

For every $v\in V_{G}$, the set $T_{v}=\\{u\in\mathit{nodes}(T)\mid
v\in\beta(u)\\}$, i.e., the set of nodes of $T$ whose corresponding bags
contain $v$, induces a connected subtree of $T$.

The width of a tree decomposition $(T,\beta)$ is defined as
$\mathit{max}_{u\in\mathit{nodes}(T)}|\beta(u)|-1$, that is, the maximum bag
size minus one. The treewidth of a graph $G$, denoted by $\mathrm{tw}(G)$, is
the minimum width of a tree decomposition of $G$.

#####  CMSO Logic:

The counting monadic second-order logic of graphs, here denoted by CMSO,
extends first order logic by allowing quantifications over sets of vertices
and edges, and by introducing the notion of modular counting predicates. More
precisely, the syntax of CMSO logic includes the logical connectives
$\vee,\wedge,\neg,\Leftrightarrow,\Rightarrow$, variables for vertices, edges,
sets of vertices and sets of edges, the quantifiers $\exists,\forall$ that can
be applied to these variables, and the following atomic predicates:

  1. (1)

$x\in X$ where $x$ is a vertex variable and $X$ a vertex-set variable;

  2. (2)

$y\in Y$ where $y$ is an edge variable and $Y$ an edge-set variable;

  3. (3)

$\mathrm{Inc}(x,y)$ where $x$ is a vertex variable, $y$ is an edge variable,
and the interpretation is that the edge $x$ is incident with the edge $y$.

  4. (4)

$\mathit{card}_{a,r}(Z)$ where $0\leq a<r$, $r\geq 2$, $Z$ is a vertex-set or
edge-set variable, and the interpretation is that $|Z|=a\;\;(\\!\\!\\!\mod
r)$;

  5. (5)

equality of variables representing vertices, edges, sets of vertices and sets
of edges.

A CMSO sentence is a CMSO formula without free variables. If $\varphi$ is a
CMSO sentence, then we write $G\models\varphi$ to indicate that $G$ satisfies
$\varphi$.

##### Terms:

Let $\Sigma$ be a finite set. The set $\mathit{Ter}(\Sigma)$ of terms over
$\Sigma$ is inductively defined as follows.

  1. (1)

If $a\in\Sigma$, then $a\in\mathit{Ter}(\Sigma)$.

  2. (2)

If $a\in\Sigma$, and $t\in\mathit{Ter}(\Sigma)$, then
$a(t)\in\mathit{Ter}(\Sigma)$.

  3. (3)

If $a\in\Sigma$, and $t_{1},t_{2}\in\mathit{Ter}(\Sigma)$, then
$a(t_{1},t_{2})\in\mathit{Ter}(\Sigma)$.

Note that the alphabet $\Sigma$ is unranked and the symbols in $\Sigma$ may be
regarded as function symbols or arity $0$, $1$ or $2$. The set of positions of
a term $t=a(t_{1},...,t_{r})\in\mathit{Ter}(\Sigma)$ is defined as follows.

$\mathit{Pos}(t)=\\{{\lambda}\\}\cup\bigcup_{j\in\\{1,...,r\\}}\\{jp\;|\;p\in\mathit{Pos}(t_{j})\\}.$

Note that $\mathit{Pos}(t)$ is a set of strings over the alphabet $\\{1,2\\}$
and that ${\lambda}$ is the empty string. If $t=a$ for some $a\in\Sigma$, then
$\mathit{Pos}(t)=\\{\lambda\\}$. If $p,pj\in\mathit{Pos}(t)$ where
$j\in\\{1,2\\}$, then we say that $pj$ is a child of $p$. Alternatively, we
say that $p$ is the parent of $pj$. We say that $p$ is a leaf if it has no
children. We let $\tau(t)$ be the tree that has $\mathit{Pos}(t)$ as nodes and
$\\{\\{p,pj\\}\mid j\in\\{1,2\\},\;p,pj\in\mathit{Pos}(t)\\}$ as arcs. We say
that a subset $P\subseteq\mathit{Pos}(t)$ is connected if the sub-tree of
$\tau(t)$ induced by $P$ is connected. If $P$ is connected, then we say that a
position $p\in P$ is the root of $P$ if the parent of $p$ does not belong to
$P$.

If $t=a(t_{1},...,t_{r})$ is a term in $\mathit{Ter}(\Sigma)$ for
$r\in\\{0,1,2\\}$, and $p\in\mathit{Pos}(t)$, then the symbol $t[p]$ at
position $p$ is inductively defined as follows. If $p={\lambda}$, then
$t[p]=a$. On the other hand, if $p=jp^{\prime}$ where $j\in\\{1,2\\}$, then
$t[p]=t_{j}[p^{\prime}]$.

##### Tree Automata:

Let $\Sigma$ be a finite set of symbols. A bottom-up tree-automaton over
$\Sigma$ is a tuple ${\mathcal{A}}=(Q,\Sigma,F,\Delta)$ where $Q$ is a set of
states, $F\subseteq Q$ a set of final states, and $\Delta$ is a set of
transitions of the form
$({\mathfrak{q}}_{1},...,{\mathfrak{q}}_{r},a,{\mathfrak{q}})$ with
$a\in\Sigma$, $0\leq r\leq 2$, and
${\mathfrak{q}}_{1},...,{\mathfrak{q}}_{r},{\mathfrak{q}}\in Q$. The size of
${\mathcal{A}}$, which is defined as $|{\mathcal{A}}|=|Q|+|\Delta|$, measures
the number of states in $Q$ plus the number of transitions in $\Delta$. The
set ${\mathcal{L}}({\mathcal{A}},{\mathfrak{q}},i)$ of all terms reaching a
state ${\mathfrak{q}}\in Q$ in depth at most $i$ is inductively defined as
follows.

$\begin{array}[]{l}{\mathcal{L}}({\mathcal{A}},{\mathfrak{q}},1)=\\{a\;|\;(a,{\mathfrak{q}})\in\Delta\\}\\\
\\\
{\mathcal{L}}({\mathcal{A}},{\mathfrak{q}},i)={\mathcal{L}}({\mathcal{A}},{\mathfrak{q}},i-1)\;\cup\\\
\hskip 54.06006pt\\{a(t_{1},...,t_{r})\;|\;r\in\\{1,2\\},\mbox{ and
}\exists({\mathfrak{q}}_{1},...,{\mathfrak{q}}_{r},a,{\mathfrak{q}})\in\Delta,\;t_{j}\in{\mathcal{L}}({\mathcal{A}},{\mathfrak{q}}_{j},i-1)\\}\end{array}$

We denote by ${\mathcal{L}}({\mathcal{A}},{\mathfrak{q}})$ the set of all
terms reaching state ${\mathfrak{q}}$ in finite depth, and by
${\mathcal{L}}({\mathcal{A}})$ the set of all terms reaching some final state
in $F$.

${\mathcal{L}}({\mathcal{A}},{\mathfrak{q}})=\bigcup_{i\in{\mathbb{N}}}{\mathcal{L}}({\mathcal{A}},{\mathfrak{q}},i)\hskip
42.67912pt{\mathcal{L}}({\mathcal{A}})=\bigcup_{{{\mathfrak{q}}\in
F}}{\mathcal{L}}({\mathcal{A}},{\mathfrak{q}})$ (1)

We say that the set ${\mathcal{L}}({\mathcal{A}})$ is the language accepted by
${\mathcal{A}}$.

Let $\mathbold{\pi}:\Sigma\rightarrow\Sigma^{\prime}$ be a map between finite
sets of symbols $\Sigma$ and $\Sigma^{\prime}$. Such mapping can be
homomorphically extended to a mapping
$\mathbold{\pi}:\mathit{Ter}(\Sigma)\rightarrow\mathit{Ter}(\Sigma^{\prime})$
between terms by setting $\mathbold{\pi}(t)[p]=\mathbold{\pi}(t[p])$ for each
position $p\in\mathit{Pos}(t)$. Additionally, $\mathbold{\pi}$ can be further
extended to a set of terms ${\mathcal{L}}\subseteq\mathit{Ter}(\Sigma)$ by
setting
${\mathbold{\pi}({\mathcal{L}})=\\{\mathbold{\pi}(t)\;|\;t\in\mathit{Ter}(\Sigma)\\}}$.
Below we state some well known closure and decidability properties for tree
automata.

###### Restatement of Lemma Properties of Tree Automata [CDG+07].

Let $\Sigma$ and $\Sigma^{\prime}$ be finite sets of symbols. Let
${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$ be tree automata over $\Sigma$,
and $\mathbold{\pi}:\Sigma\rightarrow\Sigma^{\prime}$ be a mapping.

  1. (1)

One can construct in time $O(|{\mathcal{A}}_{1}|\cdot|{\mathcal{A}}_{2}|)$ a
tree automaton ${\mathcal{A}}_{1}\cap{\mathcal{A}}_{2}$ such that
${\mathcal{L}}({\mathcal{A}}_{1}\cap{\mathcal{A}}_{2})={\mathcal{L}}({\mathcal{A}}_{1})\cap{\mathcal{L}}({\mathcal{A}}_{2})$.

  2. (2)

One can determine whether ${\mathcal{L}}({\mathcal{A}}_{1})\neq\emptyset$ in
time $O(|{\mathcal{A}}_{1}|)$.

  3. (3)

One can construct in time $O(|{\mathcal{A}}_{1}|)$ a tree automaton
$\mathbold{\pi}({\mathcal{A}}_{1})$ such that
${\mathcal{L}}(\mathbold{\pi}({\mathcal{A}}_{1}))=\mathbold{\pi}({\mathcal{L}}({\mathcal{A}}_{1}))$.

##  3\. Concrete Tree Decompositions

A $t$-concrete bag  is a pair $(B,b)$ where $B\subseteq[t]$, and $b\subseteq
B$ with $b=\emptyset$ or $|b|=2$. We note that $B$ is allowed to be empty. We
let $\mathcal{B}(t)$ be the set of all $t$-concrete bags. Note that
$|\mathcal{B}(t)|\leq t^{2}\cdot 2^{t}$. We regard the set $\mathcal{B}(t)$ as
a finite alphabet which will be used to construct terms representing tree
decompositions of graphs.

A $t$-concrete tree decomposition is a term
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$. We let
$\mathbf{T}[p]=(\mathbf{T}[p].B,\mathbf{T}[p].b)$ be the $t$-concrete bag at
position $p$ of $\mathbf{T}$. For each $s\in[t]$, we say that a non-empty
subset $P\subseteq\mathit{Pos}(\mathbf{T})$ is $s$-maximal if the following
conditions are satisfied.

  1. (1)

$P$ is connected in $\mathit{Pos}(\mathbf{T})$.

  2. (2)

$s\in\mathbf{T}[p].B$ for every $p\in P$.

  3. (3)

If $P^{\prime}$ is a connected subset of $\mathit{Pos}(\mathbf{T})$ and
$s\in\mathbf{T}[p].B$ for every $p\in P^{\prime}$, then either $P\cap
P^{\prime}=\emptyset$ or $P^{\prime}\subseteq P$.

Note that if $P$ and $P^{\prime}$ are $s$-maximal then either $P=P^{\prime}$,
or $P\cap P^{\prime}=\emptyset$. Additionally, for each
$p\in\mathit{Pos}(\mathbf{T})$, and each $s\in\mathbf{T}[p].B$, there exists a
unique subset $P\subseteq\mathit{Pos}(\mathbf{T})$ such that $P$ is
$s$-maximal and $p\in P$. We denote this unique set by $P(p,s)$. Intuitively,
each such set $P(p,s)$ corresponds to a vertex in the graph represented by
$\mathbf{T}$. Two disjoint $s$-maximal sets $P(p,s)$ and $P(p^{\prime},s)$
correspond to two distinct vertices in the graph.

Let $\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$. The graph
${\mathcal{G}}(\mathbf{T})$ associated with $\mathbf{T}$ is defined as
follows.

  1. (1)

$V_{{\mathcal{G}}(\mathbf{T})}=\\{v_{s,P}\;|\;s\in[t],\;P\subseteq\mathit{Pos}(\mathbf{T}),\;P\mbox{
is $s$-maximal}\\}$.

  2. (2)

$E_{{\mathcal{G}}(\mathbf{T})}=\\{e_{p}\;|\;p\in\mathit{Pos}(\mathbf{T}),\;b\neq\emptyset\\}$.

  3. (3)

$\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}=\\{(e_{p},v_{s,P(p,s)})\;|\;e_{p}\in
E_{{\mathcal{G}}(\mathbf{T})},\;s\in\mathbf{T}[p].b\\}$.

Intuitively, a $t$-concrete tree decomposition may be regarded as a way of
representing a graph together with one of its tree decompositions. This idea
is widespread in texts dealing with recognizable properties of graphs [BP16,
AGK08, CE12, Elb16, FFG02]. Within this framework it is customary to define a
bag of width $t$ as a graph with at most $t$ vertices together with a function
that labels the vertices of these graphs with numbers from $\\{1,...,t\\}$.
Our notion of $t$-concrete bag, on the other hand, may be regarded as a
representation of a graph with at most $t$ vertices injectively labeled with
numbers from $\\{1,...t\\}$ and at most one edge. Within this point of view,
the representation used here is a syntactic restriction of the former. On the
other hand, any decomposition which uses bags with arbitrary graphs of size
$t$ can be converted into a $t$-concrete decomposition, by expanding each bag
into a sequence of $t^{2}$ concrete bags. The following observation is
immediate, using the fact that if a graph has treewidth $t$, then it has a
rooted tree decomposition in which each node has at most two children [Elb16].

A graph $G$ has treewidth $t$ if and only if there exists some
$(t+1)$-concrete tree decomposition
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t+1))$ such that
${\mathcal{G}}(\mathbf{T})$ is isomorphic to $G$.

The next theorem (Theorem 2) may be regarded as a variant of Courcelle’s
theorem [CE12]. For completeness, we include a proof of Theorem 2 in Appendix
A.

###### Restatement of Theorem Variant of Courcelle’s Theorem.

There exists a computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$ such that for each
CMSO sentence $\varphi$, and each $t\in{\mathbb{N}}$, one can construct in
time $f(|\varphi|,t)$ a tree-automaton $\mathcal{A}(\varphi,t)$ accepting the
following tree language.

${\mathcal{L}}({\mathcal{A}}(\varphi,t))=\\{\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))\;|\;{\mathcal{G}}(\mathbf{T})\models\varphi\\}.$
(2)

##  4\. Sub-Decompositions

In this section we introduce the notion of sub-decompositions of a
$t$-concrete decomposition. Intuitively, if a $t$-concrete tree decomposition
$\mathbf{T}$ represents a graph $G$ then sub-decompositions of $\mathbf{T}$
represent subgraphs of $G$. The main result of this section states that given
a tree automaton ${\mathcal{A}}$ over $\mathcal{B}(t)$, one can efficiently
construct a tree automaton $\mathrm{Sub}({\mathcal{A}})$ over $\mathcal{B}(t)$
which accepts precisely the sub-decompositions of $t$-concrete tree
decompositions in ${\mathcal{L}}({\mathcal{A}})$.

We say that a $t$-concrete bag $(B,b)$ is a sub-bag of a $t$-concrete bag
$(B^{\prime},b^{\prime})$ if $B\subseteq B^{\prime}$ and $b\subseteq
b^{\prime}$.

We say that a $t$-concrete tree decomposition
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$ is a sub-decomposition of a
$t$-concrete tree decomposition
$\mathbf{T}^{\prime}\in\mathit{Ter}(\mathcal{B}(t))$ if the following
conditions are satisfied.

  1. S1.

$\mathit{Pos}(\mathbf{T})=\mathit{Pos}(\mathbf{T}^{\prime})$.

  2. S2.

For each $p\in\mathit{Pos}(\mathbf{T})$, $\mathbf{T}[p]$ is a sub-bag of
$\mathbf{T}^{\prime}[p]$.

  3. S3.

For each $p,pj\in\mathit{Pos}(\mathbf{T})$, and for each $s\in[t]$, if
$s\in\mathbf{T}^{\prime}[p].B$ and $s\in\mathbf{T}^{\prime}[pj].B$, then
$s\notin\mathbf{T}[p].B$ if and only if $s\notin\mathbf{T}[pj].B$.

The following theorem states that sub-decompositions of $\mathbf{T}^{\prime}$
are in one to one correspondence with subgraphs of
${\mathcal{G}}(\mathbf{T}^{\prime})$.

###### Restatement of Theorem .

Let $G$ and $G^{\prime}$ be graphs and let
$\mathbf{T}^{\prime}\in\mathit{Ter}(\mathcal{B}(t))$ be a $t$-concrete tree
decomposition such that ${\mathcal{G}}(\mathbf{T}^{\prime})=G^{\prime}$. Then
$G$ is a subgraph of $G^{\prime}$ if and only if there exists some
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$ such that $\mathbf{T}$ is a sub-
decomposition of $\mathbf{T}^{\prime}$ with ${\mathcal{G}}(\mathbf{T})=G$.

###### Restatement of Proof .

  1. (1)

Let $G$ be a subgraph of ${\mathcal{G}}(\mathbf{T}^{\prime})$. We show that
there exists a sub-decomposition $\mathbf{T}$ of $\mathbf{T}^{\prime}$ such
that ${\mathcal{G}}(\mathbf{T})=G$. Since $G$ is a subgraph of
${\mathcal{G}}(\mathbf{T})$, we have that $V_{G}\subseteq
V_{{\mathcal{G}}(\mathbf{T}^{\prime})}$, $E_{G}\subseteq
E_{{\mathcal{G}}(\mathbf{T}^{\prime})}$, and
$\mathrm{Inc}_{G}=\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T}^{\prime})}\cap
E_{G}\times V_{G}$. We define $\mathbf{T}$ by setting $\mathbf{T}[p]$ as
follows for each
$p\in\mathit{Pos}(\mathbf{T})=\mathit{Pos}(\mathbf{T}^{\prime})$.

    1. (a)

$\mathbf{T}[p].B=\mathbf{T}^{\prime}[p].B\backslash\\{s\;|\;v_{s,P(p,s)}\in
V_{{\mathcal{G}}(\mathbf{T}^{\prime})}\backslash V_{G}\\}$.

    2. (b)

$\mathbf{T}[p].b=\emptyset$ if $e_{p}\in
E_{{\mathcal{G}}(\mathbf{T}^{\prime})}\backslash E_{G}$ and
$\mathbf{T}[p].b=\mathbf{T}^{\prime}[p].b$ otherwise.

First, we note that $v_{s,P}\in V_{{\mathcal{G}}(\mathbf{T})}$ if and only if
$v_{s,P}\in V_{G}$, $e_{p}\in E_{{\mathcal{G}}(\mathbf{T})}$ if and only if
$e_{p}\in E_{G}$, and
$(e_{p},v_{i,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$ if and only if
$(e_{p},v_{i,P})\in V_{G}$. Therefore, $G={\mathcal{G}}(\mathbf{T})$. We will
check that the $t$-concrete decomposition $\mathbf{T}$ defined above is indeed
a sub-decomposition of $\mathbf{T}^{\prime}$. In other words, we will verify
that conditions S1, S2 and S3 above are satisfied. The fact that S1 is
satisfied is immediate, since we define $\mathbf{T}[p]$ for each
$p\in\mathit{Pos}(\mathbf{T}^{\prime})$. Therefore,
$\mathit{Pos}(\mathbf{T})=\mathit{Pos}(\mathbf{T}^{\prime})$. Condition S2 is
also satisfied, since by $(a)$ and $(b)$ we have that
$\mathbf{T}[p].B\subseteq\mathbf{T}^{\prime}[p].B$ and that $\mathbf{T}[p].b$
is either $\emptyset$, or equal to $\mathbf{T}^{\prime}[p].b$. Finally,
condition S3 is also satisfied, since (a) guarantees that for each number
$s\in[t]$, and each $s$-maximal set
$P\subseteq\mathit{Pos}(\mathbf{T}^{\prime})$, if $s$ is removed from
$\mathbf{T}^{\prime}[p].B$ for some $p\in P$, then $s$ is indeed removed from
$\mathbf{T}^{\prime}[p].B$ for every $p\in P$.

  2. (2)

For the converse, let $\mathbf{T}$ be a sub-decomposition of
$\mathbf{T}^{\prime}$. We show that the graph ${\mathcal{G}}(\mathbf{T})$ is a
subgraph of ${\mathcal{G}}(\mathbf{T}^{\prime})$. First, we note that
condition S3 guarantees that for each $s\in[t]$ and each
$P\subseteq\mathit{Pos}(\mathbf{T})$, if $P$ is $s$-maximal in $\mathbf{T}$
then $P$ is $s$-maximal in $\mathbf{T}^{\prime}$. Therefore,
$V_{{\mathcal{G}}(\mathbf{T})}\subseteq
V_{{\mathcal{G}}(\mathbf{T}^{\prime})}$. Now, Condition S2 guarantees that
$e_{p}\in E_{{\mathcal{G}}(\mathbf{T})}$ implies that $e_{p}\in
E_{{\mathcal{G}}(\mathbf{T}^{\prime})}$. Therefore,
$E_{{\mathcal{G}}(\mathbf{T})}\subseteq
E_{{\mathcal{G}}(\mathbf{T}^{\prime})}$. Finally, by definition
$(e_{p},v_{s,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$ if and only if
$s\in\mathbf{T}[p].b$ for each $p\in P$. Since the fact that
$s\in\mathbf{T}[p].b$ implies that $s\in\mathbf{T}^{\prime}[p].b$, we have
that $(e_{p},v_{s,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$ implies that
$(e_{p},v_{s,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T}^{\prime})}$.
Therefore,
$\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}\subseteq\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T}^{\prime})}$.
Additionally, since
$(e_{p},v_{s,P(s,p)})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$ for each
$e_{p}\in E_{{\mathcal{G}}(\mathbf{T})}$ and each $s\in\mathbf{T}[p].b$, we
have that
$\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}=\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T}^{\prime})}\cap
E_{{\mathcal{G}}(\mathbf{T})}\times V_{{\mathcal{G}}(\mathbf{T})}$. This shows
that ${\mathcal{G}}(\mathbf{T})$ is a subgraph of
${\mathcal{G}}(\mathbf{T}^{\prime})$.

The following theorem states that given a tree automaton ${\mathcal{A}}$ over
$\mathcal{B}(t)$, one can efficiently construct a tree automaton
$\mathrm{Sub}({\mathcal{A}})$ which accepts precisely the sub-decompositions
of $t$-concrete tree decompositions in ${\mathcal{L}}({\mathcal{A}})$.

###### Restatement of Theorem Sub-Decomposition Automaton.

Let ${\mathcal{A}}$ be a tree automaton over $\mathcal{B}(t)$. Then one can
construct in time $2^{O(t)}\cdot|{\mathcal{A}}|$ a tree automaton
$\mathrm{Sub}({\mathcal{A}})$ over $\mathcal{B}(t)$ accepting the following
language.

${\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}))=\\{\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))\;|\;\exists\mathbf{T}^{\prime}\in{\mathcal{L}}({\mathcal{A}})\mbox{
s.t. $\mathbf{T}$ is a sub-decomposition of $\mathbf{T}^{\prime}$}\\}.$

###### Restatement of Proof .

Let ${\mathcal{A}}=(Q,\mathcal{B}(t),\Delta,F)$ be a tree automaton over
$\mathcal{B}(t)$. As a first step we create an intermediate tree automaton
${\mathcal{A}}^{\prime}=(Q^{\prime},\mathcal{B}(t),\Delta^{\prime},F^{\prime})$
which accepts the same language as ${\mathcal{A}}$. The tree automaton
${\mathcal{A}}^{\prime}$ is defined as follows.

$\begin{array}[]{c}Q^{\prime}=\\{{\mathfrak{q}}_{B}\;|\;{\mathfrak{q}}\in
Q,\;B\subseteq[t]\\}\hskip
28.45274ptF^{\prime}=\\{{\mathfrak{q}}_{B}\;|\;{\mathfrak{q}}\in
F,\;B\subseteq[t]\\}\\\ \\\
\Delta^{\prime}=\\{({\mathfrak{q}}_{B_{1}}^{1},...,{\mathfrak{q}}_{B_{r}}^{r},(B,b),{\mathfrak{q}}_{B})\;|\;({\mathfrak{q}}^{1},...,{\mathfrak{q}}^{r},(B,b),{\mathfrak{q}})\in\Delta,\;B_{i}\subseteq[t]\mbox{
for $i\in[r]$}\\}.\end{array}$

Note that for each ${\mathfrak{q}}\in Q$, each $B\subseteq[t]$, and each
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$, $\mathbf{T}$ reaches state
${\mathfrak{q}}_{B}$ in ${\mathcal{A}}^{\prime}$ if and only if $\mathbf{T}$
reaches state ${\mathfrak{q}}$ in ${\mathcal{A}}$ and
$\mathbf{T}[{\lambda}].B=B$, where $\mathbf{T}[{\lambda}]$ is the $t$-concrete
bag at the root of $\mathbf{T}$. In particular, this implies that a term
$\mathbf{T}$ belongs to ${\mathcal{L}}({\mathcal{A}}^{\prime})$ if and only if
$\mathbf{T}\in{\mathcal{L}}({\mathcal{A}})$.

Now, consider the tree automaton
$\mathrm{Sub}(\mathcal{A})=(Q^{\prime\prime},\mathcal{B}(t),\Delta^{\prime\prime},F^{\prime\prime})$
over $\mathcal{B}(t)$ where

$\begin{array}[]{l}Q^{\prime\prime}=\\{{\mathfrak{q}}_{B,B^{\prime}}\;|\;{\mathfrak{q}}\in
Q,B\subseteq B^{\prime}\subseteq[t]\\}\hskip
28.45274ptF^{\prime\prime}=\\{{\mathfrak{q}}_{B,B^{\prime}}\;|\;{\mathfrak{q}}\in
F,B\subseteq B^{\prime}\subseteq[t]\\}\\\ \\\
\Delta^{\prime\prime}=\\{({\mathfrak{q}}^{1}_{B_{1},B_{1}^{\prime}},...,{\mathfrak{q}}^{r}_{B_{r},B_{r}^{\prime}},(B,b),{\mathfrak{q}}_{B,B^{\prime}})\;|\;\exists({\mathfrak{q}}^{1}_{B_{1}^{\prime}},...,{\mathfrak{q}}^{r}_{B_{r}^{\prime}},(B^{\prime},b^{\prime}),{\mathfrak{q}}_{B^{\prime}})\in\Delta^{\prime}\mbox{
such that}\\\ \hskip 133.72786ptB_{i}\subseteq B_{i}^{\prime},\;B\subseteq
B^{\prime},\\\ \hskip 133.72786pt(B,b)\mbox{ is a sub-bag of
}(B^{\prime},b^{\prime})\\\ \hskip 133.72786pt\mbox{for each $j\in[r]$, if
$s\in B^{\prime}\wedge s\in B_{j}^{\prime}$ then $s\notin B\Leftrightarrow
s\notin B_{j}$}\\}.\end{array}$

It follows by induction on the height of terms that a term
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$ reaches a state
${\mathfrak{q}}_{B,B^{\prime}}$ in $\mathrm{Sub}({\mathcal{A}})$ if and only
if there exists some term $\mathbf{T}^{\prime}\in\mathit{Ter}(\mathcal{B}(t))$
such that $\mathbf{T}^{\prime}$ reaches state ${\mathfrak{q}}_{B^{\prime}}$ in
${\mathcal{A}}^{\prime}$, $\mathbf{T}[\lambda].B=B$,
$\mathbf{T}^{\prime}[\lambda].B=B^{\prime}$, and $\mathbf{T}$ is a sub-
decomposition of $\mathbf{T}^{\prime}$. In particular, $\mathbf{T}$ reaches a
final state of $\mathrm{Sub}({\mathcal{A}})$ if and only if $\mathbf{T}$ is a
sub-decomposition of some $\mathbf{T}^{\prime}$ which reaches a final state of
${\mathcal{A}}^{\prime}$.

##  5\. Representing All Tree Decompositions of a Given Graph

In this section we show that given a connected graph $G$ of maximum degree
$\Delta$, and a positive integer $t$, one can construct in time
$2^{O(\Delta\cdot t)}\cdot|V_{G}|^{O(t)}$ a tree automaton
${\mathcal{A}}(G,t)$ over $\mathcal{B}(t)$ that accepts the set of all
$t$-concrete tree decompositions of $G$ (of all shapes and sizes).

Let $G$ be a graph. A $(G,t)$-concrete bag is a tuple $(B,b,\nu,\eta,y,\rho)$
where $(B,b)$ is a $t$-concrete bag; ${\nu:B\rightarrow V_{G}}$ is an
injective function that assigns a vertex of $G$ to each element of $B$;
${\eta:B\rightarrow\mathcal{P}^{\leq}(E_{G},\Delta(G))}$ is a function that
assigns to each element $s\in B$, a set of edges incident with $\nu(s)$ of
size at most $\Delta(G)$; $y$ is a subset of $E_{G}$ such that $|y|\leq 1$ and
$y\subseteq\eta(s)$ whenever $s\in b$; and $\rho$ is a subset of $B$.

We let $\mathcal{B}(G,t)$ be the set of all $(G,t)$-concrete bags. Note that
$\mathcal{B}(G,t)$ has at most $2^{O(\Delta(G)\cdot t)}\cdot|V_{G}|^{O(t)}$
elements. We let $\mathit{Ter}(\mathcal{B}(G,t))$ be the set of all terms over
$\mathcal{B}(G,t)$. If $\hat{\mathbf{T}}$ is a term in $\mathcal{B}(G,t)$ then
for each $p\in\mathit{Pos}(\mathbf{T})$, the $(G,t)$-concrete bag of
$\hat{\mathbf{T}}$ at position $p$ is denoted by the tuple

$(\hat{\mathbf{T}}[p].B,\hat{\mathbf{T}}[p].b,\hat{\mathbf{T}}[p].\nu,\hat{\mathbf{T}}[p].\eta,\hat{\mathbf{T}}[p].y,\hat{\mathbf{T}}[p].\rho).$

.

We say that a term $\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ is a
$(G,t)$-concrete tree decomposition if the following conditions are satisfied
for each each $p\in\mathit{Pos}(\hat{\mathbf{T}})$ and each $s\in[t]$.

  1. C1.

If $pj\in\mathit{Pos}(\hat{\mathbf{T}})$ and
$s\in\hat{\mathbf{T}}[p].B\cap\hat{\mathbf{T}}[pj].B$ then
${\hat{\mathbf{T}}[p].\nu(s)=\hat{\mathbf{T}}[pj].\nu(s)}$.

  2. C2.

If $\hat{\mathbf{T}}[p].b=\\{s,s^{\prime}\\}$ then
$\hat{\mathbf{T}}[p].y=\\{e\\}$ for some edge $e$ with

$\mathit{endpts}(e)=\\{\hat{\mathbf{T}}[p].\nu(s),\hat{\mathbf{T}}[p].\nu(s^{\prime})\\}.$

  3. C3.

Let $r\in\\{0,1,2\\}$, and $p1,...,pr$ be the children333If $r=0$ then $p$ has
no child. of $p$, then

$\hat{\mathbf{T}}[p].\eta(s)=\hat{\mathbf{T}}[p].y\;\dot{\cup}\;\hat{\mathbf{T}}[p1].\eta(s)\;\dot{\cup}\;...\;\dot{\cup}\;\hat{\mathbf{T}}[pr].\eta(s).$

  4. C4.

If $s\in\hat{\mathbf{T}}[p].\rho$ then
$\hat{\mathbf{T}}[p].\eta(s)=\\{e\;|\;(e,\hat{\mathbf{T}}[p].\nu(s))\in\mathrm{Inc}_{G}\\}$.

  5. C5.

If $p={\lambda}$ then $\hat{\mathbf{T}}[p].\rho=\hat{\mathbf{T}}[p].B$. If
$pj\in\mathit{Pos}(\hat{\mathbf{T}})$ then $s\in\hat{\mathbf{T}}[pj].\rho$ if
and only if $s\in\hat{\mathbf{T}}[pj].B$ and $s\notin\hat{\mathbf{T}}[p].B$.

Let $\mathbold{\pi}:\mathcal{B}(G,t)\rightarrow\mathcal{B}(t)$ be a function
such that $\mathbold{\pi}(B,b,\nu,\eta,y,\rho)=(B,b)$ for each
${(G,t)}$-concrete bag $(B,b,\nu,\eta,y,\rho)\in\mathcal{B}(G,t)$. In other
words, $\mathbold{\pi}$ transforms a $(G,t)$-concrete bag into a $t$-concrete
bag by erasing the four last coordinates of the former. If $\hat{\mathbf{T}}$
is a term in $\mathit{Ter}(\mathcal{B}(G,t))$ then we let
$\mathbold{\pi}(\hat{\mathbf{T}})$ be the term in
$\mathit{Ter}(\mathcal{B}(t))$ which is obtained by setting
$\mathbold{\pi}(\hat{\mathbf{T}})[p]=\mathbold{\pi}(\hat{\mathbf{T}}[p])$ for
each position $p\in\mathit{Pos}(\hat{\mathbf{T}})$.

###### Restatement of Theorem .

Let $G$ be a connected graph and let
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$. Then $\mathbf{T}$ is a
$t$-concrete tree decomposition of $G$ if and only if
$|V_{{\mathcal{G}}(\mathbf{T})}|=|V_{G}|$ and there exists a $(G,t)$-concrete
tree decomposition $\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ such
that $\mathbf{T}=\mathbold{\pi}(\hat{\mathbf{T}})$.

###### Restatement of Proof .

Assume that $G={\mathcal{G}}(\mathbf{T})$. Then we have
$|V_{G}|=|V_{{\mathcal{G}}(\mathbf{T})}|$. We will show how to construct a
$(G,t)$-concrete tree decomposition
$\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ such that
$\mathbold{\pi}(\hat{\mathbf{T}})=\mathbf{T}$. Clearly, we must have
$\mathit{Pos}(\hat{\mathbf{T}})=\mathit{Pos}(\mathbf{T})$, and for each
$p\in\mathit{Pos}(\mathbf{T})$, we must have
$\hat{\mathbf{T}}[p].B=\mathbf{T}[p].B$ and
$\hat{\mathbf{T}}[p].b=\mathbf{T}[p].b$. Additionally, the set
$\mathbf{T}[p].\rho$ is completely determined by the sets $\mathbf{T}[p].B$
and $\mathbf{T}[p^{\prime}].B$, where $p^{\prime}$ is the parent of $p$.
Therefore, it is enough to specify the functions $\hat{\mathbf{T}}[p].\nu$,
$\hat{\mathbf{T}}[p].\eta$, and the set $\hat{\mathbf{T}}[p].y$ for each
$p\in\mathit{Pos}(\mathbf{T})$.

Let $\beta:\mathit{Pos}(\mathbf{T})\rightarrow\\{\emptyset,\\{e_{p}\\}\\}$ be
a function such that for each $p\in\mathit{Pos}(\mathbf{T})$,
$\beta(p)=\emptyset$ if $\mathbf{T}[p].b=\emptyset$ and $\beta(p)=\\{e_{p}\\}$
if $\mathbf{T}[p].b\neq\emptyset$.

  1. (1)

For each $p\in\mathit{Pos}(\mathbf{T})$ and each $s\in\hat{\mathbf{T}}[p].B$
we set $\hat{\mathbf{T}}[p].\nu(s)=v_{s,P(s,p)}$.

  2. (2)

For each $p\in\mathit{Pos}(\mathbf{T})$ such that
$\mathbf{T}[p].b\neq\emptyset$, we set $\hat{\mathbf{T}}[p].y=\\{e_{p}\\}$.

  3. (3)

For each $p\in\mathit{Pos}(\mathbf{T})$, and each $s\in\hat{\mathbf{T}}[p].B$,
we set

$\hat{\mathbf{T}}[p].\eta(s)=\left\\{\begin{array}[]{rcl}\beta(p)\;\dot{\cup}\;\hat{\mathbf{T}}[p1].\eta(s)\;\dot{\cup}\;...\;\dot{\cup}\;\hat{\mathbf{T}}[pr].\eta(s)&&\mbox{if
$s\in\mathbf{T}[p].b$,}\\\ \\\
\hat{\mathbf{T}}[p1].\eta(s)\;\dot{\cup}\;...\;\dot{\cup}\;\hat{\mathbf{T}}[pr].\eta(s)&&\mbox{otherwise.}\\\
\end{array}\right.$

where $p1,...,pr$ are the children of $p$.

Now one can check by induction on the height of positions that for each
$s\in[t]$ and each position $p\in\mathit{Pos}(\hat{\mathbf{T}})$, the five
conditions C1-C5 of Definition 5 are satisfied. This implies that
$\hat{\mathbf{T}}$ is a $(G,t)$-concrete tree decomposition.

For the converse, suppose that
$\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ is a $(G,t)$-concrete tree
decomposition such that $\mathbf{T}=\mathbold{\pi}(\hat{\mathbf{T}})$ and
$|V_{{\mathcal{G}}(\mathbf{T})}|=|V_{G}|$. We will show that
${\mathcal{G}}(\mathbf{T})$ is isomorphic to $G$. Let
$\dot{\mu}:V_{{\mathcal{G}}(\mathbf{T})}\rightarrow V_{G}$ and
$\overline{\mu}:E_{{\mathcal{G}}(\mathbf{T})}\rightarrow E_{G}$ be functions
that are defined as follows for each vertex $v_{s,P}\in
V_{{\mathcal{G}}(\mathbf{T})}$ and each edge $e_{p}\in
E_{{\mathcal{G}}(\mathbf{T})}$ respectively.

$\dot{\mu}(v_{s,P})=\hat{\mathbf{T}}[p].\nu(s)\mbox{ if $P=P(s,p)$ for some
$p\in P$.}\\\ $ (3) $\overline{\mu}(e_{p})=e\mbox{ if
$\hat{\mathbf{T}}[p].y=\\{e\\}$}.$ (4)

We claim that the pair $\mu=(\dot{\mu},\overline{\mu})$ is an isomorphism from
${\mathcal{G}}(\mathbf{T})$ to $G$. First, let
$(e_{p},v_{s,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$. Then, by
Condition 3 of Definition 3, we have that $s\in\mathbf{T}[p].b$. Therefore, by
Equation 4 and by Condition C2 of Definition 5,
$(\overline{\mu}(e_{p}),\hat{\mathbf{T}}[p].\nu(s))\in\mathrm{Inc}_{G}$. Since
by Equation 3, $\dot{\mu}(v_{s,P})=\hat{\mathbf{T}}[p].\nu(s)$, we have that
$(\overline{\mu}(e_{p}),\dot{\mu}(v_{s,P}))\in\mathrm{Inc}_{G}$. In other
words, whenever $(e_{p},v_{s,P})\in\mathrm{Inc}_{{\mathcal{G}}(\mathbf{T})}$,
we have that $(\overline{\mu}(e_{p}),\dot{\mu}(v_{s,P}))\in\mathrm{Inc}_{G}$.
This shows that the pair $\mu$ is a morphism from ${\mathcal{G}}(\mathbf{T})$
to $G$ in the sense that it preserves adjacencies. In order to show that $\mu$
is indeed an isomorphism, we need to prove that the functions $\dot{\mu}$ and
$\overline{\mu}$ are bijections.

Since by assumption we have that $|V_{G}|=|V_{{\mathcal{G}}(\mathbf{T})}|$, to
show that $\dot{\mu}$ is a bijection, it is enough to show that for each
vertex $v\in V_{G}$ there is some vertex $v_{s,P}\in
V_{{\mathcal{G}}(\mathbf{T})}$ such that $\mu(v_{s,P})=v$. In other words, it
is enough to show that $\dot{\mu}$ is surjective. This proceeds as follows.
Let $v\in V_{G}$ and $v_{s,P}\in V_{{\mathcal{G}}(\mathbf{T})}$ be such that
$\dot{\mu}(v_{s,P})=v$. By Equation 3, there is some $p\in P$ such that
$\mathbf{T}[p].\nu(s)=v$. Therefore, since $P=P(s,p)$, by Condition C1 of
Definition 5, $\mathbf{T}[p].\nu(s)=v$ for every $p\in P$. By Conditions C3
and C4 of Definition 5, for each edge $e$ such that
$(e,v)\in\mathrm{Inc}_{G}$, there exists a (unique) $p\in P$ such that
$\hat{\mathbf{T}}[p].y=\\{e\\}$. Now, let $p\in P$, and $e$ be the unique edge
such that $\hat{\mathbf{T}}[p].y=\\{e\\}$ and assume that
$\mathit{endpts}(e)=\\{v,v^{\prime}\\}$. Then by Condition C2, there is some
$s^{\prime}$ such that $\hat{\mathbf{T}}[p].b=\\{s,s^{\prime}\\}$ and
$\hat{\mathbf{T}}[p].\nu(s^{\prime})=v^{\prime}$. Therefore, by Equation 3, we
have that $\dot{\mu}(v_{s^{\prime},P(s^{\prime},p)})=v^{\prime}$. In other
words, we have shown that if $\mu(v_{s,P})=v$, then for each neighbour
$v^{\prime}$ of $v$, there is some $p\in P$ and some $s^{\prime}\in[t]$ such
that $\dot{\mu}(v_{s^{\prime},P(s^{\prime},p)})=v^{\prime}$. Since $G$ is
connected, this implies that for each $v\in V_{G}$ there is some $v_{s,P}$
such that $\dot{\mu}(v_{s,P})=v$.

Now, it remains to show that the function $\overline{\mu}$ is also a
bijection. Let $e$ be an edge in $E_{G}$, and let $v$ be an endpoint of $e$.
Then there is some $v_{s,P}\in{\mathcal{G}}(\mathbf{T})$ such that
$\dot{\mu}(v_{s,P})=v$. By the discussion above, this implies that for some
$p\in P$, $\hat{\mathbf{T}}[p].y=\\{e\\}$. Therefore, by Equation 4, we have
that $\overline{\mu}(e_{p})=e$. Thus we have shown that for each edge $e\in
E_{G}$ there exists some $p\in\mathit{Pos}(\mathbf{T})$ such that
$\overline{\mu}(e_{p})=e$. In other words, we have shown that $\overline{\mu}$
is surjective. Now we need to show that $\overline{\mu}$ is injective. Towards
this goal, assume that
$\overline{\mu}(e_{p})=\overline{\mu}(e_{p^{\prime}})=e$ for some $e\in E_{G}$
and some distinct positions $p,p^{\prime}\in\mathit{Pos}(\mathbf{T})$ and
assume that $\mathit{endpts}(e)=\\{u,v\\}$. Then we have that there exists
$s_{1},s_{2}\in[t]$ such that $\mathbf{T}[p].b=\\{s_{1},s_{2}\\}$ and
$\mathbf{T}[p].\nu(s_{1})=v$ and $\mathbf{T}[p].\nu(s_{2})=u$. Analogously,
there exists $s_{1}^{\prime},s_{2}^{\prime}\in[t]$ such that
$\mathbf{T}[p^{\prime}].b=\\{s_{1}^{\prime},s_{2}^{\prime}\\}$ and
$\mathbf{T}[p^{\prime}].\nu(s_{1}^{\prime})=v$ and
$\mathbf{T}[p].\nu(s_{2}^{\prime})=u$. Then, from Equation 3 and from the fact
that $\dot{\mu}$ is injective, we have that $s_{1}=s_{1}^{\prime}$,
$P(s_{1},p)=P(s_{1}^{\prime},p^{\prime})$, $s_{2}=s_{2}^{\prime}$ and
$P(s_{2},p)=P(s_{2}^{\prime},p)$. But by Conditions C3 and C4 of Definition 5,
there is a unique position $p\in P(s_{1},p)=P(s_{1},p^{\prime})$ such that
$\mathbf{T}[p].y=\\{e\\}$. Therefore, $p=p^{\prime}$. This shows that the
function $\overline{\mu}$ is injective.

Note that conditions C1-C5 are local in the sense that they may be verified at
each position $p\in\mathit{Pos}(\hat{\mathbf{T}})$ by analysing only the
concrete bags
$\hat{\mathbf{T}}[p],\hat{\mathbf{T}}[p1],...,\hat{\mathbf{T}}[pr]$ where
$p1,...,pr$ are the children of $p$. This allows us to define a tree automaton
$\hat{{\mathcal{A}}}(G,t)$ over $\mathcal{B}(G,t)$ that accepts a term
$\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ if and only if
$\hat{\mathbf{T}}$ is a $(G,t)$-concrete tree decomposition.

###### Restatement of Lemma .

For each positive integer $t$ and each graph $G$ of maximum degree $\Delta$,
one can construct in time $2^{O(\Delta)}\cdot|V_{G}|^{O(t)}$ a tree automaton
$\hat{{\mathcal{A}}}(G,t)$ over $\mathcal{B}(G,t)$ accepting the following
language.

${\mathcal{L}}(\hat{{\mathcal{A}}}(G,t))=\\{\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))\;|\;\hat{\mathbf{T}}\mbox{
is a $(G,t)$-concrete tree decomposition.}\\}$ (5)

###### Restatement of Proof .

Let $\hat{B}_{1},...,\hat{B}_{r},\hat{B}$ be $(G,t)$-concrete bags for $0\leq
r\leq 2$, where $\hat{B}=(B,b,\nu,\eta,y)$
$\hat{B}_{j}=(B_{j},b_{j},\nu_{j},\eta_{j},y_{j})$ for $j\in[r]$. We say that
the tuple $(\hat{B}_{1},...,\hat{B}_{r},\hat{B})$ is $(G,t)$-compatible if the
following conditions are satisfied for each $s\in[t]$.

  1. (1)

If $s\in B_{j}\cap B$ for some $j\in[r]$ then $\nu(s)=\nu_{j}(s)$.

  2. (2)

If $s\in b$ then $y=\\{e\\}$ for some edge $e$ such that
$(e,\nu(s))\in\mathrm{Inc}_{G}$.

  3. (3)

$\eta(s)=y\;\dot{\cup}\;\eta_{1}(s)\;\dot{\cup}\;...\;\dot{\cup}\;\eta_{r}(s).$

  4. (4)

If $s\in\rho$ then $\eta(s)=\\{e\;|\;(e,\nu(v))\in\mathrm{Inc}_{G}\\}$.

  5. (5)

$s\in\rho_{j}$ if and only if $s\in B_{j}$ and $s\notin B$.

We define the tree automaton ${\mathcal{A}}=(Q,\mathcal{B}(G,t),F,\Delta)$ as
follows.

$\begin{array}[]{c}Q=\\{{\mathfrak{q}}_{\hat{\mathbold{B}}}\;|\;\mbox{
$\hat{B}$ is a $(G,t)$-concrete bag.}\\}\hskip
28.45274ptF=\\{{\mathfrak{q}}_{\hat{\mathbold{B}}}\in
Q\;|\;\hat{\mathbold{B}}.\rho=\hat{\mathbold{B}}.B\\}\\\ \\\
\Delta=\\{({\mathfrak{q}}_{\hat{\mathbold{B}}_{1}},...,{\mathfrak{q}}_{\hat{\mathbold{B}}_{k}},\hat{\mathbold{B}},{\mathfrak{q}}_{\hat{\mathbold{B}}})\;|\;(\hat{\mathbold{B}}_{1},...,\hat{\mathbold{B}}_{r},\hat{\mathbold{B}})\mbox{
is $(G,t)$-compatible.}\\}\end{array}$ (6)

Now, it can be shown by induction on the height of terms that a term
$\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ reaches a state
${\mathfrak{q}}_{\hat{\mathbold{B}}}$ if and only if
$\mathbf{T}[{\lambda}]=\hat{\mathbold{B}}$ and that conditions C1-C5 of
Definition 5 are satisfied for each $p\in\mathit{Pos}(\hat{\mathbf{T}})$ and
each $s\in[t]$. In particular, this implies that $\hat{{\mathcal{A}}}(G,t)$
accepts a term $\hat{\mathbf{T}}\in\mathit{Ter}(\mathcal{B}(G,t))$ if and only
if $\hat{\mathbf{T}}$ is a $(G,t)$-concrete tree decomposition.

The next lemma states that for each positive integers $t$ and $n$, one can
efficiently construct a tree automaton ${\mathcal{A}}(t,n)$ which accepts
precisely those $t$-concrete tree decompositions which give rise to graphs
with $n$ vertices.

###### Restatement of Lemma .

Let $t$ and $n$ be positive integers with $t\leq n$. One can construct in time
$2^{O(t)}\cdot n^{3}$ a tree automaton ${\mathcal{A}}(t,n)$ over
$\mathcal{B}(t)$ accepting the following language.

${\mathcal{L}}({\mathcal{A}}(t,n))=\\{\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))\;|\;|V_{{\mathcal{G}}(\mathbf{T})}|=n\\}$

###### Restatement of Proof .

Let $\mathbf{T}$ be a term in $\mathit{Ter}(\mathcal{B}(t))$. Recall that for
each position $p\in\mathit{Pos}(\mathbf{T})$, and each $s\in[t]$, the set
$P(s,p)$ is the unique $s$-maximal subset of $\mathit{Pos}(\mathbf{T})$ that
contains position $p$. We say that $(s,p)$ is a $\mathbf{T}$-root-pair if $p$
is the root of $P(s,p)$. We note that the number of vertices of the graph
${\mathcal{G}}(\mathbf{T})$ is equal to the number of $\mathbf{T}$-root-pairs
in $[t]\times\mathit{Pos}(\mathbf{T})$. Therefore, in order to construct an
automaton that accepts precisely the terms
$\mathbf{T}\in\mathit{Pos}(\mathbf{T})$ that give rise to graphs with $n$
vertices, it is enough to define an automaton that accepts precisely those
terms $\mathbf{T}$ that admit $n$ $\mathbf{T}$-root-pairs.

A root marking for a set $B\subseteq[t]$ is a set $\rho\subseteq B$. The
automaton ${\mathcal{A}}(t,n)=(Q,\mathcal{B}(t),F,\Delta)$ is defined as
follows.

$\begin{array}[]{l}Q=\\{{\mathfrak{q}}_{B,\rho,j}\;|\;j\in\\{0,...,n\\},\;B\subseteq[t],\;\rho\mbox{
is a root marking for $B$}\\}\hskip
28.45274ptF=\\{{\mathfrak{q}}_{B,\rho,n}\\}\\\ \\\
\Delta=\\{({\mathfrak{q}}_{B_{1},\rho_{1},j_{1}},...,{\mathfrak{q}}_{B_{r},\rho_{r},j_{r}},(B,b),{\mathfrak{q}}_{B,\rho,j})\;|\;0\leq
r\leq 2,\;(B,b)\in\mathcal{B}(t),\;j=|\rho|+\sum_{i=1}^{r}|\rho_{i}|,\\\
\hskip 156.49014pt\mbox{for each $s\in[t]$, if $s\in\rho_{i}$ for some
$i\in[r]$ then $s\notin B$}\\}\end{array}$

Then it follows by induction on the height of terms that a term
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$ reaches a state
${\mathfrak{q}}_{B,\rho,j}$ if and only if $\mathbf{T}[{\lambda}].B=B$,
$(s,{\lambda})$ is a $\mathbf{T}$-root-pair for each $s\in\rho$, and $j$ is
the number of $\mathbf{T}$-root-pairs in $[t]\times\mathit{Pos}(\mathbf{T})$.
In particular, the number of $\mathbf{T}$-root-pairs is equal to $n$ if and
only if $\mathbf{T}$ reaches some final state of ${\mathcal{A}}$. Note that
since $|\mathcal{B}(t)|=2^{O(t)}$, and since $r\leq 2$, there are at most
$2^{O(t)}\cdot n$ states in $Q$ and at most $2^{O(t)}\cdot n^{3}$ transitions
in $\Delta$. Therefore, ${\mathcal{A}}(t,n)$ can be constructed in time
$2^{O(t)}\cdot n^{3}$.

The main result of this section (Theorem 8), follows by a combination of
Theorem 5, Lemma 6 and Lemma 7.

###### Restatement of Theorem .

Let $G$ be a connected graph of treewidth $t$ and maximum degree $\Delta$.
Then one can construct in time $2^{O(\Delta\cdot t)}\cdot|V_{G}|^{O(t)}$ a
tree automaton $\mathcal{A}(G,t)$ over $\mathcal{B}(t)$ such that for each
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$,
$\mathbf{T}\in{\mathcal{L}}(\mathcal{A}(G,t))$ if and only if $\mathbf{T}$ is
a concrete tree decomposition of $G$.

###### Restatement of Proof .

By Lemma 6, one can construct in time $2^{O(\Delta\cdot
t)}\cdot|V_{G}|^{O(t)}$ a tree automaton $\hat{{\mathcal{A}}}(G,t)$ over
$\mathcal{B}(G,t)$ which accepts precisely the $(G,t)$ concrete tree
decompositions that belong to $\mathit{Ter}(\mathcal{B}(G,t))$.

Therefore, the tree automaton $\mathbold{\pi}({\mathcal{A}})$ accepts
precisely those $t$-concrete tree decompositions
$\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))$ such that
$\mathbf{T}=\mathbold{\pi}(\hat{\mathbf{T}})$ for some $(G,t)$-concrete tree
decomposition $\hat{\mathbf{T}}\in{\mathcal{L}}(\hat{{\mathcal{A}}}(G,t))$.
Note that $\mathbold{\pi}(\hat{{\mathcal{A}}}(G,t))$ can be constructed in
time $O(|\hat{{\mathcal{A}}}(G,t)|)$ by Lemma 1.

Now, by Lemma 7 we can construct in time $2^{O(t)}\cdot|V_{G}|^{O(1)}$ a tree
automaton ${\mathcal{A}}(t,|V_{G}|)$ over $\mathcal{B}(t)$ which accepts a
$t$-concrete tree decomposition in $\mathit{Ter}(\mathcal{B}(t))$ if and only
if $|V_{{\mathcal{G}}(\mathbf{T})}|=|V_{G}|$.

Therefore if we set
${\mathcal{A}}(G,t)=\mathbold{\pi}(\hat{{\mathcal{A}}}(G,t))\cap{\mathcal{A}}(t,|V_{G}|)$,
then we have that ${\mathcal{A}}(G,t)$ accepts precisely those $t$-concrete
tree decompositions $\mathbf{T}\in\mathcal{B}(t)$ such that
$|V_{{\mathcal{G}}(\mathbf{T})}|=|V_{G}|$ and
$\mathbf{T}=\mathbold{\pi}(\hat{\mathbf{T}})$ for some $(G,t)$-concrete tree
decomposition $\hat{\mathbf{T}}$. By Lemma 1, ${\mathcal{A}}(G,t)$ can be
constructed in time $2^{O(\Delta\cdot t)}\cdot|V_{G}|^{O(t)}$.

##  6\. $(\varphi,t)$-Supergraphs

Let $\varphi$ be a CMSO sentence, and $t$ be a positive integer. Let $G$ and
$G^{\prime}$ be graphs. We say that $G^{\prime}$ is a $(\varphi,t)$-supergraph
of $G$ if the following three conditions are satisfied:
${G^{\prime}\models\varphi}$, $G^{\prime}$ has treewidth at most $t$, and $G$
is a subgraph of $G^{\prime}$.

###### Restatement of Lemma .

Let $\varphi$ be a CMSO sentence and $t$ be a positive integer. Then a graph
$G$ has a $(\varphi,t)$-supergraph if and only if there exists a
$(t+1)$-concrete tree decomposition
$\mathbf{T}\in{\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1))$ such
that ${\mathcal{G}}(\mathbf{T})$ is isomorphic to $G$.

###### Restatement of Proof .

Assume that $G$ is a graph that has a $(\varphi,t)$-supergraph $G^{\prime}$.
Then $G^{\prime}$ satisfies $\varphi$, $G^{\prime}$ has treewidth at most $t$,
and $G$ is a subgraph of $G^{\prime}$. By Observation 3, $G^{\prime}$ has a
$(t+1)$-concrete tree decomposition
$\mathbf{T}^{\prime}\in\mathit{Ter}(\mathcal{B}(t+1))$, and therefore by
Theorem 2, $\mathbf{T}^{\prime}\in{\mathcal{L}}({\mathcal{A}}(\varphi,t))$.
Since $G$ is a subgraph of $G^{\prime}$, by Theorem 3, $\mathbf{T}^{\prime}$
has a sub-decomposition $\mathbf{T}$ which is a $(t+1)$-concrete tree
decomposition of $G$. Therefore, $\mathbf{T}$ belongs to
$\mathrm{Sub}({\mathcal{A}}(\varphi,t+1))$.

For the converse, let
$\mathbf{T}\in{\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$ and let
$\mathbf{T}$ be a $(t+1)$-concrete tree decomposition of $G$. Then
$\mathbf{T}$ is a sub-decomposition of some $(t+1)$-concrete tree
decomposition $\mathbf{T}^{\prime}$ in
${\mathcal{L}}({\mathcal{A}}(\varphi,t+1))$. By Theorem 2,
$\mathbf{T}^{\prime}$ is a $(t+1)$-concrete tree decomposition of some graph
$G^{\prime}$ of treewidth at most $t$ such that $G^{\prime}\models\varphi$.
Since $\mathbf{T}$ is a sub-decomposition of $\mathbf{T}^{\prime}$, by Theorem
3, $G$ is a subgraph of $G^{\prime}$. Therefore, $G^{\prime}$ is a
$(\varphi,t)$-supergraph of $G$.

We note that Lemma 9 alone does yield an algorithm to determine whether a
graph $G$ has a $(\varphi,t)$-supergraph. If $G$ does not admit such a
supergraph, then no $(t+1)$-concrete tree decomposition $G$ belongs to
${\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$. However, if $G$
does admit a $(\varphi,t)$-supergraph, then Theorem 4 only guarantees that
some $(t+1)$-concrete tree decomposition $\mathbf{T}$ of $G$ belongs to
$\mathrm{Sub}({\mathcal{A}}(\varphi,t+1))$. The problem is that $G$ may have
infinitely many $(t+1)$-concrete tree decompositions and we do not know a
priori which of these should be tested for membership in
${\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$.

The issue described above can be remedied with the results from Section 5.
More specifically, from Theorem 8 we have that for any given connected graph
$G$ of treewidth $t$ and maximum degree $\Delta$, one can construct a tree
automaton ${\mathcal{A}}(G,t+1)$ over $\mathcal{B}(t+1)$ which accepts a
$(t+1)$-concrete tree decomposition $\mathbf{T}$ if and only if the graph
${\mathcal{G}}(\mathbf{T})$ is isomorphic to $G$. Note that
${\mathcal{L}}({\mathcal{A}}(G,t+1))$ is an infinite language that contains
$(t+1)$-concrete tree decompositions of $G$ of all shapes and sizes.
Therefore, a connected graph $G$ has a $(\varphi,t)$-supergraph if and only if

${\mathcal{L}}({\mathcal{A}}(G,t+1))\;\cap\;{\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))\neq\emptyset.$
(7)

The next theorem states that Equation 7 yields an efficient algorithm for
testing whether connected graphs of bounded degree have a
$(\varphi,t)$-supergraph.

###### Restatement of Theorem Main Theorem.

There is a computable function $f$, and an algorithm $\mathfrak{A}$ that takes
as input a CMSO sentence $\varphi$, a positive integer $t$, and a connected
graph $G$ of maximum degree $\Delta$, and determines in time
$f(|\varphi|,t)\cdot 2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}$ whether $G$ has a
$(\varphi,t)$-supergraph.

###### Restatement of Proof .

By Lemma 9, $G$ has a $(\varphi,t)$-supergraph if and only if there exists
some $\mathbf{T}\in{\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$
such that $\mathbf{T}$ is a $(t+1)$-concrete tree decomposition of $G$. By
Theorem 8, ${\mathcal{L}}({\mathcal{A}}(G,t+1))$ accepts a $(t+1)$-tree
decomposition of $G$ if and only if ${\mathcal{G}}(\mathbf{T})$ is isomorphic
to $G$. Therefore, $G$ has a $(\varphi,t)$-supergraph if and only the
intersection of ${\mathcal{L}}({\mathcal{A}}(G,t+1))$ with
${\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))$ is nonempty.

By Theorem 8, the tree-automaton ${\mathcal{A}}(G,t+1)$ can be constructed in
time $2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}$, and therefore the size of
${\mathcal{A}}(G,t+1)$ is bounded by $2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}$. By
Theorem 4 and Theorem 2, the tree-automaton
$\mathrm{Sub}({\mathcal{A}}(\varphi,t+1))$ can be constructed in time
$f(|\varphi|,t)$ for some computable function
$f:{\mathbb{N}}^{2}\rightarrow{\mathbb{N}}$, and therefore, the size of
$\mathrm{Sub}({\mathcal{A}}(\varphi,t))$ is bounded by $f(|\varphi|,t)$.

Finally, given tree automata ${\mathcal{A}}_{1}$ and ${\mathcal{A}}_{2}$, one
can determine whether
${\mathcal{L}}({\mathcal{A}}_{1})\cap{\mathcal{L}}({\mathcal{A}}_{2})\neq\emptyset$
in time $O(|{\mathcal{A}}_{1}|\cdot|{\mathcal{A}}_{2}|)$ (Lemma 1). In
particular, one can determine whether

${\mathcal{L}}({\mathcal{A}}(G,t+1))\cap{\mathcal{L}}(\mathrm{Sub}({\mathcal{A}}(\varphi,t+1)))\neq\emptyset$

in time ${f(|\varphi|,t)\cdot 2^{O(\Delta\cdot t)}\cdot|G|^{O(t)}}$.

##  7\. Contraction Closed Graph Parameters

In this section we deal with simple graphs, i.e., graphs without loops or
multiple edges. Therefore, we may write $\\{u,v\\}$ to denote an edge $e$
whose endpoints are $u$ and $v$. Additionally, whenever speaking of a property
specified by an CMSO formula $\varphi$, we assume that $\varphi$ ensures that
its models are simple graphs.

Let $G$ be a graph and $\\{u,v\\}$ be an edge of $G$. We let $G/uv$ denote the
graph that is obtained from $G$ by deleting the edge $\\{u,v\\}$ and by
merging vertices $u$ and $v$ into a single vertex $x_{uv}$. We say that $G/uv$
is obtained from $G$ by an edge-contraction. We say that a graph $G^{\prime}$
is a contraction of $G$ if $G^{\prime}$ is obtained from $G$ by a sequence of
edge contractions. We say that $G^{\prime}$ is a minor of $G$ if $G^{\prime}$
is a contraction of some subgraph of $G$. We say that a graph $G$ is an apex
graph if after deleting some vertex of $G$ the resulting graph is planar.

A graph parameter is a function $\mathbf{p}$ mapping graphs to non-negative
integers in such a way that $\mathbf{p}(G)=\mathbf{p}(G^{\prime})$ whenever
$G$ is isomorphic to $G^{\prime}$. We say that $\mathbf{p}$ is contraction
closed if $\mathbf{p}(G^{\prime})\leq\mathbf{p}(G)$ whenever $G^{\prime}$ is a
contraction of $G$.

A graph property is simply a set $\mathcal{P}$ of graphs. We say that a
property $\mathcal{P}$ is contraction-closed if for every two graphs
$G,G^{\prime}$ for which $G^{\prime}$ is a contraction of $G$, the fact that
$G\in\mathcal{P}$ implies that $G^{\prime}\in\mathcal{P}$.

###  7.1. Diameter Improvement Problems

Let $u$ and $v$ be vertices in an graph $G$. The distance from $u$ to $v$,
denoted by $\mathit{dist}(u,v)$ is the number of edges in the shortest path
from $u$ to $v$. If no such path exists, we set $\mathit{dist}(u,v)=\infty$.
The diameter of $G$ is defined as
$\mathit{diam}(G)=\max_{u,v}\mathit{dist}(u,v)$. In the planar diameter
improvement problem (PDI), we are given an graph $G$ and a positive integer
$d$, and the goal is to determine whether $G$ has a planar supergraph
$G^{\prime}$ of diameter at most $d$. As mentioned in the introduction, there
is an algorithm that solves the PDI problem in time $f(d)\cdot|G|^{O(1)}$,
where $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ is not known to be computable.
Additionally, even the problem of determining whether PDI admits an algorithm
running in time $f_{1}(d)\cdot|G|^{f_{2}(d)}$ for computable functions
$f_{1},f_{2}$ remains open for more than two decades [FL89, CGK+15]. The next
theorem solves this problem when the input graphs are connected and have
bounded degree.

###### Restatement of Theorem .

There is a computable function $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, and an
algorithm $\mathfrak{A}$ that takes as input, a positive integer $d$, and a
connected graph $G$ of maximum degree $\Delta$, and determines in time
$f(d)\cdot 2^{O(\Delta\cdot d)}\cdot|G|^{O(d)}$ whether $G$ has a planar
supergraph $G^{\prime}$ of diameter at most $d$.

###### Restatement of Proof .

It should be clear that there is an algorithm that takes a positive integer
$d$ as input, and constructs, in time $O(d)$, a CMSO formula
$\mathit{Diam}_{d}$ which is true on a graph $G^{\prime}$ if and only if
$G^{\prime}$ has diameter at most $d$. Additionally, using Kuratowski’s
theorem, and the fact that minor relation is CMSO expressible, one can define
a CMSO formula $\mathit{Planar}$ which is true on a graph $G^{\prime}$ if and
only if $G^{\prime}$ is planar. Finally, it can be shown that any planar graph
of diameter at most $d$ has treewidth $O(d)$ (see Lemma 1 of [Epp00]).
Therefore, by setting $\varphi=\mathit{Diam}_{d}\wedge\mathit{Planar}$,
$t=O(d)$, and by renaming $f(|\varphi|,t)$ to $f(d)$ in Theorem 10, we have an
algorithm running in time $f(d)\cdot 2^{O(\Delta\cdot d)}\cdot|G|^{O(d)}$ to
determine whether $G$ has a planar supergraph $G^{\prime}$ of diameter at most
$d$.

We note that the algorithm $\mathfrak{A}$ of Theorem 11 does not impose any
restriction on the degree of a prospective supergraph $G^{\prime}$ of $G$.
Theorem 11 can be generalized to the setting of graphs of constant genus as
follows.

###### Restatement of Theorem .

There is a computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$, and an algorithm
$\mathfrak{A}$ that takes as input, positive integers $d,g$, and a connected
graph $G$ of maximum degree $\Delta$, and determines in time $f(d,g)\cdot
2^{O(\Delta\cdot d)}\cdot|G|^{O(d\cdot g)}$ whether $G$ has a supergraph
$G^{\prime}$ of genus at most $g$ and diameter at most $d$.

###### Restatement of Proof .

It can be shown that there is an explicit algorithm that takes a positive
integer $g$ as input and constructs a CMSO sentence $\mathit{Genus}_{g}$ that
is true on a graph $G^{\prime}$ if and only if $G^{\prime}$ has genus at most
$g$ [AGK08]. Additionally, it can be shown that graphs of genus $g$ and
diameter $d$ have treewidth at most $O(g\cdot d)$ [Epp00]. Therefore, by
setting $\varphi=\mathit{Genus}_{g}\wedge\mathit{Diam}_{d}$, $t=O(g\cdot d)$,
and by renaming $f(|\varphi|,t)$ to $f(g,d)$ in Theorem 10, we have that one
can determine in time $f(d,g)\cdot 2^{O(\Delta\cdot d)}\cdot|G|^{O(d\cdot g)}$
whether $G$ has a supergraph $G^{\prime}$ of genus at most $g$ and diameter at
most $d$.

A graph is $1$-outerplanar if it can be embedded in the plane in such a way
that every vertex lies in the outer face of the embedding. A graph is
$k$-outerplanar if it can be embedded in the plane in such a way that after
deleting all vertices in the outer face, the remaining graph is
${(k-1)}$-outerplanar. In [CGK+15] Cohen et al. have considered the
$k$-outerplanar diameter improvement problem ($k$-OPDI), a variant of the PDI
problem in which the target supergraph is required to be $k$-outerplanar
instead of planar. In particular, they have shown that the $1$-OPDI problem
can be solved in polynomial time. The complexity of the $k$-OPDI problem with
respect to explicit algorithms was left as an open problem for $k\geq 2$. The
next theorem states that for each fixed $k$, $k$-OPDI is strongly uniformly
fixed parameter tractable with respect to the parameter $d$ on connected
graphs of bounded degree.

###### Restatement of Theorem .

There is a computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$, and an algorithm
$\mathfrak{A}$ that takes as input, positive integers $d,k$, and a connected
graph $G$ of maximum degree $\Delta$, and determines in time $f(k,d)\cdot
2^{O(\Delta\cdot k)}\cdot|G|^{O(k)}$ whether $G$ has a $k$-outerplanar
supergraph $G^{\prime}$ of diameter at most $d$.

###### Restatement of Proof .

There is an algorithm that takes an integer $k$ as input and constructs in
time $O(k)$ a CMSO sentence $\mathit{Outer}_{k}$ that is true on a graph $G$
if and only if $G$ is $k$-outerplanar [JB15]. Additionally, it can be shown
that $k$-outerplanar graphs have treewidth $O(k)$. Therefore, by setting
$\varphi=\mathit{Outer}_{k}\wedge\mathit{Diam}_{d}$, and $t=O(k)$ in Theorem
10, it follows that the problem of determining whether $G$ has a
$k$-outerplanar supergraph of diameter at most $d$ can be decided in time
$f(k,d)\cdot 2^{O(\Delta\cdot k)}\cdot|G|^{O(k)}$ for some computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$.

Finally, the series-parallel diameter improvement problem (SPDI) consists in
determining whether a graph $G$ has a series parallel supergraph of diameter
at most $d$. The parameterized complexity of this problem was left as an open
problem in [CGK+15]. The next theorem states that SPDI is strongly uniformly
fixed parameter tractable with respect to the parameter $d$ on connected
graphs of bounded degree.

###### Restatement of Theorem .

There is a computable function $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, and an
algorithm $\mathfrak{A}$ that takes as input, a positive integer $d$ and a
connected graph $G$ of maximum degree $\Delta$, and determines in time
$f(d)\cdot 2^{O(\Delta)}\cdot|G|^{O(1)}$ whether $G$ has a series-parallel
supergraph $G^{\prime}$ of diameter at most $d$.

###### Restatement of Proof .

There is a CMSO formula $\mathit{SP}$ which is true on a graph $G^{\prime}$ if
and only if $G^{\prime}$ is series parallel. Additionally, series parallel
graphs have treewidth at most $2$. Therefore, by setting
$\varphi=\mathit{SP}\wedge\mathit{Diam}_{d}$ and $t=O(1)$ in Theorem 10, it
follows that the problem of determining whether $G$ has a series-parallel
supergraph of diameter at most $d$ can be decided in time $f(d)\cdot
2^{O(\Delta)}\cdot|G|^{O(1)}$ for some computable function $f$.

###  7.2. Contraction Bidimensional Parameters

Fomin, Golovach and Thilikos [FGT11] have defined a sequence
$\\{\Gamma_{k}\\}_{k\in{\mathbb{N}}}$ of graphs and have shown that these
graphs serve as obstructions for small treewidth on $H$-minor free graphs,
whenever $H$ is an apex graph. More precisely, they have proved the following
result.

###### Restatement of Theorem Fomin-Golovach-Thilikos [FGT11].

For every apex graph $H$, there is a $c_{H}>0$ such that every connected
$H$-minor-free graph of treewidth at least $c_{H}\cdot k$ contains
$\Gamma_{k}$ as a contraction.

We say that a graph parameter $\mathbf{p}$ is Gamma-unbounded if there is a
computable function $\alpha:{\mathbb{N}}\rightarrow{\mathbb{N}}$ such that
$\alpha\in\omega(1)$, and $\mathbf{p}(\Gamma_{k})\geq\alpha(k)$ for every
$k\in{\mathbb{N}}$.

We say that a parameter $\mathbf{p}$ is effectively CMSO definable if there is
a computable function $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, and an
algorithm $\mathfrak{A}$ that takes as input a positive integer $k$ and
constructs, in time at most $f(k)$, a CMSO-sentence $\varphi$ which is true on
an graph $G$ if and only if $\mathbf{p}(G)\leq k$. The following theorem is a
corollary of Theorem 10 and Theorem 15.

###### Restatement of Theorem .

Let $\mathbf{p}$ be a Gamma-unbounded effectively CMSO definable graph
parameter, and let $\mathcal{P}$ be a CMSO definable graph property excluding
some apex graph $H$ as a minor. Then there is a computable function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ and an algorithm $\mathfrak{A}$ that
takes as input a positive integer $k$, and a connected graph $G$ of maximum
degree $\Delta$, and determines, in time $f(k)\cdot 2^{O(\Delta\cdot
f(k))}\cdot|G|^{f(k)}$, whether $G$ has a supergraph $G^{\prime}$ such that
$G^{\prime}\in\mathcal{P}$ and $\mathbf{p}(G^{\prime})\leq k$.

Note that similarly to the case of diameter improvement problem, if
$\mathbf{p}$ is an unbounded effectively CMSO definable graph parameter, then
we can determine whether a graph $G$ has an $r$-outerplanar supergraph
$G^{\prime}$ with $\mathbf{p}(G^{\prime})\leq k$ in time $f(r,k)\cdot
2^{O(\Delta\cdot r)}\cdot|G|^{O(r)}$ for some computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$. In other words,
this problem, for connected bounded degree graphs, is strongly uniformly fixed
parameter tractable with respect to the parameter $\mathbf{p}$ for each fixed
$r$.

A graph parameter $\mathbf{p}$ is contraction-bidimensional if the following
conditions are satisfied.

  1. (1)

$\mathbf{p}$ is contraction-closed.

  2. (2)

If $G$ is a graph which has $\Gamma_{k}$ as a contraction, then
$\mathbf{p}(G)\geq\Omega(k^{2})$.

For instance, the following parameters are contraction bidimensional.

  1. (1)

Size of a vertex cover.

  2. (2)

Size of a feedback vertex set.

  3. (3)

Size of a minimum maximal matching.

  4. (4)

Size of a dominating set.

  5. (5)

Size of a edge dominating set.

  6. (6)

Size of a clique traversal set.

[[FGT11, FLST10]] Let $\mathbf{p}$ be a bidimensional parameter. Then if
$\mathbf{p}(G)\leq k$, the treewidth of $\mathbf{p}$ is at most $O(\sqrt{k})$.

###### Restatement of Theorem .

For each effectively $CMSO$-definable contraction-bidimensional parameter
$\mathbf{p}$, there exists a computable function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$ and an algorithm $\mathfrak{A}$ that
takes as input a positive integer $k$, and a connected graph $G$ of maximum
degree $\Delta$, and determines in time $f(k)\cdot
2^{O(\Delta\cdot\sqrt{k})}\cdot|G|^{O(\sqrt{k})}$ whether $G$ has a planar
supergraph $G^{\prime}$ with $\mathbf{p}(G^{\prime})\leq k$.

###### Restatement of Proof .

Since $\mathbf{p}$ is effectively CMSO definable, there is some computable
function $\alpha$ and an algorithm that take a positive integer $k$ as input
and constructs in time $\alpha(k)$ a CMSO sentence $\varphi_{\mathbf{p}}$
which is true on an graph $G$ if and only if $\mathbf{p}(G)\leq k$.
Additionally, by Theorem 16, if $\mathbf{p}(G)\leq k$, then the treewidth of
$G$ is bounded by $\sqrt{k}$. Therefore, by applying Theorem 10 with
$\varphi=\varphi_{\mathbf{p}}$, and $t=O(\sqrt{k})$, the theorem follows.

For instance, Theorem 17 states that for some computable function
$f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, one can determine in time $f(k)\cdot
2^{O(\Delta\cdot\sqrt{k})}\cdot|G|^{O(\sqrt{k})}$ whether $G$ has a planar
supergraph $G^{\prime}$ with feedback vertex set at most $k$. We note that in
view of Theorem 16, the planarity requirement of Theorem 17 can be replaced
for any CMSO definable property $\mathcal{P}$ which excludes some apex graph
as a minor.

## Acknowledgements

This work was supported by the Bergen Research Foundation and by the Research
Council of Norway (Proj. no. 288761). The author thanks Michael Fellows, Fedor
Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh for interesting
discussions. The author also thanks anonymous reviewers for several useful
comments and suggestions for improvement.

## References

  * [AF93] Karl Abrahamson and Michael Fellows.  Finite automata, bounded treewidth, and well-quasiordering.  Contemporary Mathematics, 147:539–539, 1993.
  * [AGK08] Isolde Adler, Martin Grohe, and Stephan Kreutzer.  Computing excluded minors.  In Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pages 641–650. SIAM, 2008.
  * [BMT03] Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca.  Chordal embeddings of planar graphs.  Discrete Mathematics, 273(1):85–102, 2003.
  * [BP16] Mikołaj Bojańczyk and Michal Pilipczuk.  Definability equals recognizability for graphs of bounded treewidth.  In Proc. of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016), pages 407–416. ACM, 2016.
  * [BP17] Mikolaj Boja’nczyk and Michal Pilipczuk.  Optimizing tree decompositions in MSO.  In Proc. of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of LIPIcs, pages 15:1–15:13, 2017.
  * [CDG+07] H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi.  Tree Automata Techniques and Applications.  2007\.
  * [CE12] Bruno Courcelle and Joost Engelfriet.  Graph structure and monadic second-order logic: A language-theoretic approach, volume 138.  Cambridge University Press, 2012.
  * [CFK+15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [CGK+15] Nathann Cohen, Daniel Gonçalves, Eunjung Kim, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos, and Mathias Weller.  A polynomial-time algorithm for outerplanar diameter improvement.  In Proc. of the 10th International Computer Science Symposium in Russia (CSR 2015), volume 9139 of LNCS, pages 123–142, 2015.
  * [Cou90] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Inf. Comput., 85(1):12–75, 1990.
  * [DF99] Rodney G. Downey and Michael R. Fellows.  Parameterized Complexity.  Monographs in Computer Science. Springer, 1999.
  * [dOO17] Mateus de Oliveira Oliveira.  On supergraphs satisfying CMSO properties.  In Proc. of the 26th Conference on Computer Science Logic (CSL 2017), volume 82 of LIPIcs, 2017.
  * [Elb16] Michael Elberfeld.  Context-free graph properties via definable decompositions.  In Proc. of the 25th Conference on Computer Science Logic (CSL 2016), volume 62 of LIPIcs, pages 17:1–17:16, 2016.
  * [Epp00] David Eppstein.  Diameter and treewidth in minor-closed graph families.  Algorithmica, 27(3):275–291, 2000.
  * [FD95] Michael R. Fellows and Rodney G. Downey.  Parameterized computational feasibility.  Feasible Mathematics II, 13:219–244, 1995.
  * [FFG02] Jörg Flum, Markus Frick, and Martin Grohe.  Query evaluation via tree-decompositions.  Journal of the ACM (JACM), 49(6):716–752, 2002.
  * [FGT11] Fedor V Fomin, Petr Golovach, and Dimitrios M Thilikos.  Contraction obstructions for treewidth.  Journal of Combinatorial Theory, Series B, 101(5):302–314, 2011\.
  * [FL89] Michael R Fellows and Michael A Langston.  On search decision and the efficiency of polynomial-time algorithms.  In Proc. of the 21st Annual ACM Symposium on Theory of Computing (STOC 1989), pages 501–512. ACM, 1989.
  * [FLST10] Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M Thilikos.  Bidimensionality and kernels.  In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 503–510, 2010.
  * [JB15] Lars Jaffke and Hans L. Bodlaender.  Definability equals recognizability for k-outerplanar graphs.  In Proc. of the 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, volume 43, pages 175–186, 2015.
  * [LdOOS18] Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Saket Saurabh.  A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem.  In Proc. of the 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, volume 115 of LIPIcs, pages 25:1–25:13, 2018.
  * [RS95] Neil Robertson and Paul D Seymour.  Graph minors. XIII. the disjoint paths problem.  Journal of combinatorial theory, Series B, 63(1):65–110, 1995.
  * [RS04] Neil Robertson and Paul D Seymour.  Graph minors. XX. Wagner’s conjecture.  Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004\.

##  Appendix A Proof of Theorem 2

###### Restatement of Theorem 2.

There exists a computable function
$f:{\mathbb{N}}\times{\mathbb{N}}\rightarrow{\mathbb{N}}$ such that for each
CMSO sentence $\varphi$, and each $t\in{\mathbb{N}}$, one can construct in
time $f(|\varphi|,t)$ a tree-automaton $\mathcal{A}(\varphi,t)$ accepting the
following tree language.

${\mathcal{L}}({\mathcal{A}}(\varphi,t))=\\{\mathbf{T}\in\mathit{Ter}(\mathcal{B}(t))\;|\;{\mathcal{G}}(\mathbf{T})\models\varphi\\}.$
(8)

###### Restatement of Proof .

Let $S$ and $S^{\prime}$ be sets and let $R\subseteq S\times S^{\prime}$ be a
relation. For each element $s\in S$, we let
$\mathrm{Im}(R,s)=\\{s^{\prime}\;:\;(s,s^{\prime})\in R\\}$ be the image of
$s$ under $R$.

Let $\mathcal{X}$ be a set of first-order variables and second-order variables
and let $G$ be a graph. An interpretation of $\mathcal{X}$ in $G$ is a
function $\mathcal{J}:\mathcal{X}\rightarrow(V\cup E)\cup(2^{V}\cup 2^{E})$
that assigns a vertex $\mathcal{J}(x)$ to each first-order vertex-variable
$x$, an edge $\mathcal{J}(y)$ to each first-order edge-variable $y$, a set of
vertices $\mathcal{J}(X)$ to each second-order vertex-variable $X$, and a set
of edges $\mathcal{J}(Y)$ to each second-order edge-variable $Y$. The
semantics of a formula $\varphi$ with free variables $\mathcal{X}$ being true
on a graph $G$ under interpretation $\mathcal{J}$ is the standard one.

Let $\mathcal{X}$ be a set of free first-order and second-order variables, and
let $(B,b)$ be a $t$-concrete bag. An interpretation of $\mathcal{X}$ in
$(B,b)$ is a relation $I\subseteq\mathcal{X}\times(B\cup\\{b\\})$ such that
the following conditions are satisfied: $\mathrm{Im}(I,x)\subseteq B$ and
$|\mathrm{Im}(I,x)|\leq 1$ for each first-order vertex-variable $x$;
$\mathrm{Im}(I,X)\subseteq B$ for each second-order vertex-variable $X$;
$\mathrm{Im}(I,y)\subseteq\\{b\\}$ for each first-order edge-variable $y$; and
$\mathrm{Im}(I,Y)\subseteq\\{b\\}$ for each second-order variable $Y$. We let
$\mathcal{B}(t,\mathcal{X})$ be the set of all triples of the form $(B,b,I)$
where $(B,b)$ is a $t$-concrete bag and $I$ is an interpretation of
$\mathcal{X}$ in $(B,b)$.

If $\mathbf{T}$ is a $t$-concrete decomposition in
$\mathit{Ter}(\mathcal{B}(t))$, then an interpretation of $\mathcal{X}$ in
$\mathbf{T}$ is a function
$\mathcal{I}:\mathit{Pos}(\mathbf{T})\rightarrow\mathcal{B}(t,\mathcal{X})$
where for each position $p\in\mathit{Pos}(\mathbf{T})$, $\mathcal{I}(p)$ is an
interpretation of $\mathcal{X}$ in the $t$-concrete bag $\mathbf{T}[p]$, and
for each first-order vertex-variable $x$ (edge-variable $y$), there is at most
one position $p\in\mathit{Pos}(\mathbf{T})$ such that $|\mathrm{Im}(I,x)|=1$
($|\mathrm{Im}(I,y)|=1$). If $\mathcal{I}$ is an interpretation of
$\mathcal{X}$ in $\mathbf{T}$, then the interpretation of $\mathcal{X}$ in
${\mathcal{G}}(\mathbf{T})$ induced by $\mathcal{I}$ is the function

$\hat{\mathcal{I}}:\mathcal{X}\rightarrow(V_{{\mathcal{G}}(\mathbf{T})}\cup
E_{{\mathcal{G}}(\mathbf{T})})\cup(2^{V_{{\mathcal{G}}(\mathbf{T})}}\cup
2^{E_{{\mathcal{G}}(\mathbf{T})}})$

defined as follows.

  1. (1)

For each $s\in[t]$, each $s$-maximal component
$P\subseteq\mathit{Pos}(\mathbf{T})$, and each first-order or second-order
vertex-variable $\mathbf{x}$, the vertex $v_{s,P}$ belongs to
$\mathrm{Im}(\hat{\mathcal{I}},\mathbf{x})$ if and only if there exists a
position $p\in P$ such that $(\mathbf{x},s)\in\mathcal{I}(p)$.

  2. (2)

For each $p\in\mathit{Pos}(\mathbf{T})$ such that
$\mathbf{T}[p].b\neq\emptyset$, and each first-order or second-order edge-
variable $\mathbf{y}$, the edge $e_{p}$ belongs to
$\mathrm{Im}(\hat{\mathcal{I}},\mathbf{y})$ if and only if
$(\mathbf{y},\mathbf{T}[p].b)\in\mathcal{I}(p)$.

If $\mathbf{T}$ is a $t$-concrete decomposition in
$\mathit{Ter}(\mathcal{B}(t))$ and $\mathcal{I}$ is an interpretation of
$\mathcal{X}$ in $\mathbf{T}$, then we write $\mathbf{T}^{\mathcal{I}}$ to
denote the term in $\mathit{Ter}(\mathcal{B}(t,\mathcal{X}))$ where
$\mathbf{T}^{\mathcal{I}}[p]=(\mathbf{T}[p],\mathcal{I}(p))$ for each position
$p\in\mathit{Pos}(\mathbf{T})$. We say that $\mathbf{T}^{\mathcal{I}}$ is an
interpreted term. We note that one can straightforwardly construct a tree
automaton ${\mathcal{A}}(t,\mathcal{X})$ over the alphabet
$\mathcal{B}(t,\mathcal{X})$ that accepts precisely the interpreted terms in
$\mathit{Ter}(\mathcal{B}(t,\mathcal{X}))$.

For each CMSOformula $\psi$ with free variables $\mathcal{X}$ we will
construct a tree-automaton ${\mathcal{A}}(\psi,t)$ over the alphabet
$\mathcal{B}(t,\mathcal{X})$ whose language
${\mathcal{L}}({\mathcal{A}}(\psi,t))$ consists of all interpreted terms
$\mathbf{T}^{\mathcal{I}}\in\mathit{Ter}(\mathcal{B}(t,\mathcal{X}))$ such
that ${\mathcal{G}}(\mathbf{T})\models\psi$ under the interpretation
$\hat{\mathcal{I}}$ of $\mathcal{X}$ in ${\mathcal{G}}(\mathbf{T})$ induced by
$\mathcal{I}$. The tree-automaton ${\mathcal{A}}(\psi,t)$ is constructed by
induction on the structure of the formula $\psi$.

#### Base Case

In the base case, the formula $\psi$ is an atomic predicate. There are five
cases to be considered. Below, we describe the behavior of the tree-automaton
${\mathcal{A}}(\psi,t)$ in each of these five cases. The proper specification
of the set of states and set of transitions of each of the tree-automata
described below is straightforward.

  1. (1)

If $\psi\equiv(\mathbf{z}_{1}=\mathbf{z}_{2})$ where $\mathbf{z}_{1}$ and
$\mathbf{z}_{2}$ are both vertex-variables, both edge-variables, both vertex-
set variables or both edge-set variables, then ${\mathcal{A}}(\psi,t)$ accepts
a term $\mathbf{T}^{\mathcal{I}}$ if and only if $\mathbf{T}^{\mathcal{I}}$ is
an interpreted term, and for each position $p\in\mathit{Pos}(\mathbf{T})$, and
each $s\in\mathbf{T}[p].B$,
$(\mathbf{z}_{1},s)\in\mathcal{I}(p)\Leftrightarrow(\mathbf{z}_{2},s)\in\mathcal{I}(p)$.

  2. (2)

If $\psi\equiv z\in Z$ where either $z$ is a vertex-variable and $Z$ is a
vertex-set variable, or $z$ is an edge-variable and $Z$ is an edge-set
variable, then ${\mathcal{A}}(\psi,t)$ accepts a term
$\mathbf{T}^{\mathcal{I}}$ if and only if $\mathbf{T}^{\mathcal{I}}$ is an
interpreted term and for each position $p\in\mathit{Pos}(\mathbf{T})$, and
each element $r\in\mathbf{T}[p].B\cup\\{\mathbf{T}[p].b\\}$,
$(z,r)\in\mathcal{I}(p)\Leftrightarrow(Z,r)\in\mathcal{I}(p)$.

  3. (3)

If $\psi\equiv\mathrm{Inc}(y,x)$ where $y$ is an edge variable and $x$ is a
vertex variable, then the automaton ${\mathcal{A}}(\psi,t)$ accepts a term
$\mathbf{T}^{\mathcal{I}}$ if and only if $\mathbf{T}^{\mathcal{I}}$ is an
interpreted term and there is some position $p\in\mathit{Pos}(\mathbf{T})$ and
some $s\in\mathbf{T}[p].B$ such that $(x,s)\in\mathcal{I}(p)$,
$s\in\mathbf{T}[p].b$, and $(y,\mathbf{T}[p],b)\in\mathcal{I}(p)$.

  4. (4)

If $\psi\equiv\mathit{card}_{a,r}(Z)$ where $0\leq a<r$, $r\geq 2$, and $Z$ is
an edge-set variable, then the tree automaton ${\mathcal{A}}(\psi,t)$ accepts
$\mathbf{T}^{\mathcal{I}}$ if and only if $\mathbf{T}^{\mathcal{I}}$ is an
interpreted term, and the number of positions $p\in\mathit{Pos}(\mathbf{T})$
such that $\mathbf{T}[p].b\neq\emptyset$ and
$(Z,\mathbf{T}[p].b)\in\mathcal{I}(p)$ is equal to $a\mod r$.

  5. (5)

If $\psi\equiv\mathit{card}_{a,r}(Z)$ where $0\leq a<r$, $r\geq 2$, and $Z$ is
a vertex-set variable then the tree automaton ${\mathcal{A}}(\psi,t)$ accepts
$\mathbf{T}^{\mathcal{I}}$ if and only if $\mathbf{T}^{\mathcal{I}}$ is an
interpreted term and the number of pairs of the form
$(s,p)\in[t]\times\mathit{Pos}(\mathbf{T})$ such that $s\in\mathbf{T}[p].B$
and $p$ is the root of $P_{s,p}$ is equal to $a\mod r$.

#### Disjunction, conjunction and negation

The three boolean operations $\vee,\wedge,\neg$ are dealt with using the fact
that tree-automata are effectively closed under union, intersection and
complement (Lemma 1). Below, we let ${\mathcal{A}}(t,\mathcal{X})$ be the tree
automaton generating the set of interpreted terms over
$\mathcal{B}(t,\mathcal{X})$.

$\begin{array}[]{c}{\mathcal{A}}(\psi\vee\psi^{\prime},t)={\mathcal{A}}(\psi,t)\cup{\mathcal{A}}(\psi^{\prime},t)\\\
\\\
{\mathcal{A}}(\psi\wedge\psi^{\prime},t)={\mathcal{A}}(\psi,t)\cap{\mathcal{A}}(\psi^{\prime},t)\\\
\\\
{\mathcal{A}}(\neg\psi,t)=\overline{{\mathcal{A}}(\psi,t)}\cap{\mathcal{A}}(t,\mathcal{X})\\\
\end{array}$ (9)

Observe that in the definition of ${\mathcal{A}}(\neg\psi,t)$, the
intersection with the tree-automaton ${\mathcal{A}}(t,\mathcal{X})$ guarantees
that all terms in ${\mathcal{L}}({\mathcal{A}}(\neg\psi,t))$ are interpreted.

#### Existential Quantification

Let $I$ be an interpretation of $\mathcal{X}$ in $(B,b)$, and let $Z$ be
either a first-order or a second-order variable in $\mathcal{X}$. We let
$I-Z=I\cap\left[(\mathcal{X}\backslash Z)\times(B\cup\\{b\\})\right]$ be the
relation obtained from $I$ by deleting all pairs of the form $(Z,r)$ for $r\in
B\cup\\{b\\}$. To eliminate existential quantifiers we proceed as follows: For
each variable $Z\in\mathcal{X}$, we let
$\mathit{Proj}_{Z}:\mathcal{B}(t,\mathcal{X})\rightarrow\mathcal{B}(t,\mathcal{X}\backslash
Z)$ be the map that sends each interpreted $t$-concrete bag
$(B,b,I)\in\mathcal{B}(t,\mathcal{X})$ to the interpreted $t$-concrete bag
$(B,b,I-Z)\in\mathcal{B}(t,\mathcal{X}\backslash Z)$. Subsequently, we extend
$\mathit{Proj}_{Z}$ homomorphically to terms by setting
$\mathit{Proj}_{Z}(\mathbf{T})[p]=\mathit{Proj}_{Z}(\mathbf{T}[p])$ for each
position $p$ in $\mathit{Pos}(\mathbf{T})$. Finally, we extend
$\mathit{Proj}_{Z}$ to tree languages over $\mathcal{B}(t,\mathcal{X})$ by
applying this map to each term of the language. Then we set

${\mathcal{A}}(\exists
Z\psi(Z),t)=\mathit{Proj}_{Z}({\mathcal{A}}(\psi(Z),t)).$

We note that if $\psi$ is a sentence, i.e., a formula without free variables,
then by the end of this inductive process all variables occurring in $\psi$
will have been eliminated. In this way, the language
${\mathcal{L}}({\mathcal{A}}(\psi,t))$ will consist precisely of the
interpreted decompositions
$\mathbf{T}^{\varepsilon}\in\mathit{Ter}(\mathcal{B}(t,\emptyset))$ where
$\varepsilon$ is the empty interpretation, that assigns
$\varepsilon(p)=\emptyset$ for each $p\in\mathit{Pos}(\mathbf{T})$, and
$\mathbf{T}\models\psi$. Now consider the map that
$\mathfrak{m}:\mathcal{B}(t,\emptyset)\rightarrow\mathcal{B}(t)$ that sends
each triple $(B,b,\emptyset)\in\mathcal{B}(t,\emptyset)$ to the $t$-concrete
bag $(B,b)$. Then, by setting
${\mathcal{A}}(\psi,t)\leftarrow\mathfrak{m}({\mathcal{A}}(\psi,t))$, we have
that ${\mathcal{A}}(\psi,t)$ accepts a term $\mathbf{T}\in\mathcal{B}(t)$ if
and only if $\mathbf{T}$ is a $t$-concrete tree decomposition such that
$\mathbf{T}\models\varphi$.