# Embedding phylogenetic trees in networks of low treewidth

Leo van Iersel111Delft Institute of Applied Mathematics, Delft University of
Technology, The Netherlands. Email<EMAIL_ADDRESS><EMAIL_ADDRESS>Mark Jones11footnotemark: 1 Mathias Weller222CNRS,
LIGM (UMR 8049), Université Gustave Eiffel, Champs-s/-Marne, France. Email:
<EMAIL_ADDRESS>
###### Abstract

Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic
tree, can the tree be embedded into the network? This problem, called Tree
Containment, arises when validating networks constructed by phylogenetic
inference methods. We present the first algorithm for (rooted) Tree
Containment using the treewidth $t$ of the input network $N$ as parameter,
showing that the problem can be solved in $2^{O(t^{2})}\cdot|N|$ time and
space.

##  1 Introduction

###  1.1 Background: phylogenetic trees and networks

Phylogenetic trees and networks are graphs used to represent evolutionary
relationships. In particular, a _rooted phylogenetic network_ is a directed
acyclic graph with distinctly labelled leaves, a unique root and no indegree-1
outdegree-1 vertex. Here, we will only consider rooted binary phylogenetic
networks, which we will call _networks_ for short. The labels of the leaves
(indegree-1 outdegree-0 vertices) can, for example, represent a collection of
studied biological species, and the network then describes how they evolved
from a common ancestor (the root, a unique indegree-0 outdegree-2 vertex).
Vertices with indegree 2 and outdegree 1 are called _reticulations_ and
represent events where lineages combine, for example the emergence of new
hybrid species. All other vertices have indegree 1 and outdegree 2. A network
without reticulations is a _phylogenetic tree_.

###  1.2 The Tree Containment problem

The evolutionary history of a small unit of hereditary information (for
example a gene, a fraction of a gene or (in linguistics) a word) can often be
described by a phylogenetic tree. This is because at each reticulation, each
unit is inherited from only one parent. Hence, if we trace back the
evolutionary history of such a hereditary unit in the network, we see that its
phylogenetic tree can be embedded in the network. This raises the fundamental
question: given a phylogenetic network and a phylogenetic tree, can the tree
be embedded into the network? This is called the Tree Containment problem (see
Fig. 1). To formalize this problem, we say that a network $N$ _displays_ a
tree $T$ if some subgraph of $N$ is a subdivision of $T$.

Input: phylogenetic network $N_{\textsc{in}}$ and tree $T_{\textsc{in}}$, both
on the same set of leaf labels Question: Does $N_{\textsc{in}}$ display
$T_{\textsc{in}}$? Tree Containment (TC)

$f$$d$$b$$e$$a$$c$

$f$$e$$d$$c$$b$$a$

Figure 1: Left: a phylogenetic tree $T$. Middle: a phylogenetic network $N$
displaying $T$ (solid lines indicate an embedding of $T$; black nodes indicate
reticulations). Right: the display graph $D(N,T)$ of $N$ and $T$ (see Section
1.4) with the network part drawn on top and the tree part drawn on the bottom.
Note that vertices of the display graph are not labelled. In the figure, the
leaves (square vertices) are ordered in the same way as in $N$.

####  1.2.1 Motivation

Apart from being a natural and perhaps one of the most fundamental questions
regarding phylogenetic networks, the Tree Containment problem has direct
applications in phylogenetics. The main application is the validation of
phylogenetic network inference methods. After constructing a network, one may
want to verify whether it is consistent with the phylogenetic trees. For
example, if a heuristic method is used to generate a network for a genomic
data set, and tree inference methods are used to generate trees for each gene,
then the quality of the produced network can be assessed by computing the
fraction of the gene trees that can be embedded into it. In addition, one may
want to find the actual embeddings for visualisation purposes and/or to assess
the importance of each network arc.

However, our main motivation for studying Tree Containment is that it is a
first step towards the wider application of treewidth based approaches in
phylogenetics (see Sections 1.3 and 1.4). The techniques we develop are not
exclusively designed for Tree Containment but intended to be useful also for
other problems such as Network Containment [33] and Hybridization Number [9,
42, 43, 44]. The former is the natural generalization of Tree Containment in
which we have two networks as input and want to decide whether one can be
embedded into the other. It can, in particular, be used to decide whether two
networks are isomorphic. In the latter problem, Hybridization Number, the
input consists of a set of phylogenetic trees, and the aim is to construct a
network with at most $k$ reticulations that embeds each of the input trees.
Although this will certainly be non-trivial, we expect that at least part of
the approach we introduce here can be applied to those and other problems in
phylogenetics. We also believe our approach may have application to problems
outside of phylogenetics, involving the reconciliation of multiple related
graphs.

###  1.3 Treewidth

The parameters that are most heavily used for phylogenetic network problems
(see eg. Section 1.5) are the reticulation number and the level. This is true
not only for Tree Containment but more generally in the phylogenetic networks
literature. Although these parameters are natural, their downside is that they
are not necessarily much smaller than the input size. This is why we study a
different parameter here.

The _treewidth_ of a graph measures its tree-likeness (see definition below),
similarly to the reticulation number and level. In that sense, it is also a
natural parameter to consider in phylogenetics, where networks are often
expected to be reasonably tree-like. A major advantage of treewidth is that it
is expected to be much smaller than the reticulation number and level. In
particular, there exist classes of networks for which the treewidth is at most
a constant factor times the square-root of the level (see [38] for an
example). Moreover, a broad range of advanced techniques have been developed
for designing FPT algorithms for graph problems when the parameter is the
treewidth [6, 12, 2, 15]. For these reasons, the treewidth has recently been
studied for phylogenetics problems [32, 39, 38, 40] and related width
parameters have been proposed [10]. However, using treewidth as parameter for
phylogenetic problems poses major challenges and, therefore, there are still
few algorithms in phylogenetics that use treewidth as parameter (see Section
1.4).

One of the most famous results in treewidth is Courcelle’s Theorem[13, 1],
which states, informally, that graph problems expressible in mondadic second-
order logic (MSOL) can be solved in linear time on graphs of bounded
treewidth. This makes MSOL formulations a powerful tool for establishing FPT
results. For practical purposes, it is often preferable to establish a
concrete algorithm, since the running times derived via Courcelle’s theorem
are dominated by a tower of exponentials of size bounded in the treewidth.

It will be convenient to define a _tree decomposition_ of a graph $G=(V,E)$ as
a rooted tree, where each vertex of the tree is called a _bag_ and is assigned
a partition $(P,S,F)$ of $V$, where $S$ is a separator between $P$ and $F$. We
will refer to $S$ as the _present_ of the bag. The set $P$ is equal to the
union of the presents of all descendant bags (minus the elements of $S$) and
we refer to it as the _past_ of the bag. The set $F=V\setminus(S\cup P)$ is
referred to as the _future_ of the bag. For each edge of the graph, there is
at least one bag for which both endpoints of the edge are in the present of
the bag. Finally, for each $v\in V$, the bags that have $v$ in the present
form a non-empty connected subtree of the tree decomposition. The _width_ of a
tree decomposition is one less than the maximum size of any bag’s present and
the _treewidth_ $tw(G)$ of a graph $G$ is the minimum width of any tree
decomposition of $G$. The treewidth of a phylogenetic network or other
directed graph is the treewidth of the underlying undirected graph.

Our dynamic programming works with _nice_ tree decompositions, in which the
root is assigned $(V,\varnothing,\varnothing)$ and each bag assigned $(P,S,F)$
has exactly one of four types: _Leaf_ bags have $P=S=\varnothing$ (hence
$F=V$) and have no child, _Introduce_ bags have a single child assigned
$(P,S\setminus\\{z\\},F\cup\\{z\\})$ for some $z\in S$, _Forget_ bags have a
single child assigned $(P\setminus\\{z\\},S\cup\\{z\\},F)$ for some $z\in P$,
and _Join_ bags have two children assigned $(L,S,F\cup R)$ and $(R,S,F\cup L)$
respectively, where $(L,R)$ is a partition of $P$. When the treewidth is
bounded by a constant, [7] showed that a minimum-width tree decomposition can
be found in linear time and [34] showed that a nice tree decomposition of the
same width can be obtained in linear time. Regarding approximation, it is
known that, for all graphs $G$, tree decompositions of width $O(tw(G))$ can be
computed in time single-exponential in $tw(G)$ [11, 3, 36] and tree
decompositions of width $O(tw(G)\sqrt{\log tw(G)})$ can be computed in
polynomial time [16].

###  1.4 Challenges

One of the main challenges of using treewidth as parameter in phylogenetics is
that the central goal in this field is to infer phylogenetic networks and,
thus, the network is not known _a priori_ so a tree decomposition cannot be
constructed easily. A possible strategy to overcome this problem is to work
with the _display graph_ (see Fig. 1). Consider a problem taking as input a
set of trees, such as Hybridization Number. Then, the _display graph_ of the
trees is obtained by taking all trees and identifying leaves with the same
label. Now we have a graph in the input and hence we can compute a tree
decomposition. Moreover, in some cases, there is a strong relation between the
treewidth of the display graph and the treewidth of an optimal network [22,
38, 32].

A few instances of exploiting (tree decompositions of) the display graph of
input networks for algorithm design have been published. Famously, Bryant and
Lagergren [4] designed MSOL formulations solving the Tree Consistency problem
on display graphs, which have been improved by a concrete dynamic programming
on a given tree decomposition of the display graph [8]. Kelk et al. [39] also
developed MSOL formulations on display graphs for multiple incongruence
measures on trees, based on so-called “agreement forests”. For the Tree
Containment problem, MSOL formulations acting on the display graph have been
used to prove fixed-parameter tractability with respect to the treewidth [32].
Analogously to the work of Baste et al. [8] for Tree Consistency, we develop
in this manuscript a concrete dynamic programming algorithm for Tree
Containment acting on display graphs.

Tree Containment is conceptually similar to Hybridization Number in the sense
that the main challenge is to decide which tree vertices correspond to which
vertices of the other trees (for Hybridization Number) or network vertices
(for Tree Containment). However, Hybridization Number is even more challenging
since the network may contain vertices that do not correspond to any input
vertex [42]. Therefore, Tree Containment is a natural first problem to develop
techniques for, aiming at extending them to Hybridization Number and other
problems in phylogenetics in the long run.

That being said, solving Tree Containment parameterized by treewidth poses
major challenges itself. Even though the general idea of dynamic programming
on a tree decomposition is clear, its concrete use for Tree Containment is
severely complicated by the fact that the tree decomposition does not know the
correspondence between tree vertices and network vertices. For example, when
considering a certain bag of the tree decomposition, a tree vertex that is in
the present of that bag may have to be embedded into a network vertex that is
in the past or in the future. It may also be necessary to map vertices from
the future of the tree to the past of the network and vice versa. Therefore,
it will not be possible to “forget the past” and “not worry about the future”.
In particular, this makes it much more challenging to bound the number of
possible assignments for a given bag. We will do this by bounding the number
of “time-travelling” vertices by a function of the treewidth. We will describe
these challenges in more detail in Section 2.2.

###  1.5 Previous work

Tree Containment was shown to be NP-hard [35], even for tree-sibling, time-
consistent, regular networks [31]. On the positive side, polynomial-time
algorithms were found for other restricted classes, including tree-child
networks [19, 20, 25, 26, 31, 45]. The first non-trivial FPT algorithm for
Tree Containment on general networks had running time $O(2^{k/2}n^{2})$, where
the parameter $k$ is the number of reticulations in the network [35]. Another
algorithm was proposed by [24] with the same parameter, but it is only shown
to be FPT for a restricted class of networks. Since the problem can be split
into independent subproblems at non-leaf cut-edges [31], the parameterization
can be improved to the largest number of reticulations in any biconnected
component (block), also called the _level_ of the network. Further improving
the parameterization, the maximum number $t^{*}$ of “unstable component-roots”
per biconnected component was considered and an algorithm (working also in the
non-binary case) was found with running time $O(3^{t^{*}}|N||T|)$ [45].
Herein, a parameterization “improves” over another if the first is provably
smaller than (a function of) the second in any input network.

Several generalizations and variants of the Tree Containment problem have been
studied. The more general Network Containment problem asks to embed a
_network_ in another and has been shown to be solvable in polynomial time on a
restricted network class [33]. When allowing multifurcations and non-binary
reticulations, two variants of Tree Containment have been considered: In the
firm version, each non-binary node (“polytomy”) of the tree has to be embedded
in a polytomy of the network whereas, in the soft version, polytomies may be
“resolved” into binary subtrees in any way [5]. Finally, the unrooted version
of Tree Containment was also shown to be NP-hard but fixed-parameter tractable
when the parameter is the reticulation number (the number of edges that need
to be deleted from the network to obtain a tree) [30]. While this version of
the problem is also known to be fixed-parameter tractable with respect to the
treewidth of the network [32], the work does not explicitly describe an
algorithm and the implied running time depends on Courcelle’s theorem [14]
which makes practical implementation virtually impossible.

Since the notion of “display” closely resembles that of “topological minor”
(with the added constraint that the embedding must respect leaf-labels), Tree
Containment can be understood as a special case of a variant of the well-known
Topological Minor Containment (TMC) problem for directed graphs. TMC is known
to be NP-complete in general by reduction from Hamiltonian Cycle and previous
algorithmic results focus on the undirected variant, parameterized by the
_size_ $h$ of the sought topological minor $H$ (corresponding to the input
tree for Tree Containment). In particular, undirected TMC can be solved in
$f(h)n^{O(1)}$ time [23, 18]. However, the dependency of the function $f$ on
$h$ makes such algorithms impractical for all but small values of $h$. By
contrast, in Tree Containment the input tree may be assumed to typically have
a size comparable to the overall input size. In the directed case, even the
definition of “topological minor” has been contested [21] and we are aware of
little to no algorithmic results. In Tree Containment, part of the embedding
of the host tree in the guest network is fixed by the leaf-labeling. If the
node-mapping is fixed for _all_ nodes of the host, then directed TMC
generalizes the Disjoint Paths problem [17], which is NP-complete for 2 paths
or in case the host network is acyclic. Indeed, one can show Tree Containment
to be NP-hard in a similar fashion [35].

###  1.6 Our contribution

In this paper, we present an FPT-algorithm for Tree Containment parameterized
by the treewidth of the input network. Our algorithm is one of the first
(constructive) FPT-algorithms for a problem in phylogenetics parameterized by
treewidth. We believe that this is an important development as the treewidth
can be much smaller than other parameters such as reticulation number and
level which are easier to work with. We see this algorithm as an important
step towards the wide application of treewidth-based methods in phylogenetics.

##  2 Preliminaries

###  2.1 Reformulating the problem

A key concept throughout this paper will be _display graphs_ [4], which are
the graphs formed from the union of a phylogenetic tree and a phylogenetic
network by identifying leaves with the same labels. Throughout this paper we
will let $N_{\textsc{in}}$ and $T_{\textsc{in}}$ denote the respective input
network and tree in our instance of Tree Containment. The main object of study
will be the “display graph” of $N_{\textsc{in}}$ and $T_{\textsc{in}}$. For
the purposes of our dynamic programming algorithm, we will often consider
graphs that are not exactly this display graph, but may be thought of as
roughly corresponding to subgraphs of it (though they are not exactly
subgraphs; see Section 3.1). In order to incorporate such graphs as well, we
will define display graphs in a slightly more general way than that usually
found in the literature. In particular, we allow for the two “sides” of a
display graph to be disconnected, and for some leaves to belong to one side
but not the other.

######  Definition 1 (display graph).

A _display graph_ is a directed acyclic graph $D=(V,A)$, with specified
subsets $V_{T},V_{N}\subseteq V$ such that $V_{T}\cup V_{N}=V$, satisfying the
following properties:

  * •

The graph $T:=D[V_{T}]$ is an out-forest;

  * •

Every vertex has in- and out-degree at most $2$ and total degree at most $3$;

  * •

Any vertex in $V_{N}\cap V_{T}$ has out-degree $0$ and in-degree at most $1$
in both $T$ and $N:=D[V_{N}]$.

Herein, we call $T$ the _tree side_ and $N$ the _network side_ of $D$ and we
will use the term $D(N,T)$ to denote a display graph with network side $N$ and
tree side $T$.

Given a phylogenetic network $N_{\textsc{in}}$ and phylogenetic tree
$T_{\textsc{in}}$ with the same leaf-label set, we define
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ to be the display graph
formed by taking the disjoint union of $N_{\textsc{in}}$ and $T_{\textsc{in}}$
and identifying pairs of leaves that have the same label. We note that, while
the leaves of $N_{\textsc{in}}$ and $T_{\textsc{in}}$ were originally
labelled, this labelling does not appear in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Labels are used to
construct $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, but in the rest
of the paper we will not need to consider them. Indeed, such labels are
relevant to the Tree Containment problem only insofar as they establish a
relation between the leaves of $T_{\textsc{in}}$ and $N_{\textsc{in}}$, and
this relation is now captured by the structure of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

We now reformulate the Tree Containment problem in terms of an _embedding
function_ on a display graph. Unlike the standard definition of an embedding
function (see, e.g., [31]), which is defined for a phylogenetic network $N$
and tree $T$, our definition of an embedding function applies directly to the
display graph $D(N,T)$. Because of our more general definition of display
graphs, our definition of an embedding function will also be more general than
that found in the literature. The key idea of an embedding function remains
the same, however: it shows how a subdivision of $T$ may be viewed as a
subgraph of $N$.

######  Definition 2 (embedding function).

Let $D$ be a display graph with network side $N$ and tree side $T$, and let
$\mathcal{P}(N)$ denote the set of all directed paths in $N$. An _embedding
function on $D$_ is a function $\phi:V(T)\cup A(T)\to V(N)\cup\mathcal{P}(N)$
such that:

  1. (a)

for each $u\in V(T)$, $\phi(u)\in V(N)$ and, for each arc $uv\in A(T)$,
$\phi(uv)$ is a directed $\phi(u)$-$\phi(v)$-path in $N$;

  2. (b)

for any distinct $u,v\in V(T)$, $\phi(u)\neq\phi(v)$;

  3. (c)

for any $u\in V(T)\cap V(N)$, $\phi(u)=u$;

  4. (d)

the paths $\\{\phi(uv)\mid uv\in A(T)\\}$ are arc-disjoint;

  5. (e)

for any distinct $p,q\in A(T)$, $\phi(p)$ and $\phi(q)$ share a vertex $z$
only if $p$ and $q$ share a vertex $w$ with $z=\phi(w)$;

Note that the standard definition of an embedding of a phylogenetic tree $T$
into a phylogenetic network $N$ (see e.g. [31]) coincides with the definition
of an embedding function on $D(N,T)$. Property (e) ensures that, while the
embeddings of arcs $uv,vw_{1},vw_{2}$ can all meet at $\phi(v)$, the
embeddings of different tree arcs cannot otherwise meet. (In particular, the
path $\phi(uv)$ cannot end at a reticulation that is also an internal vertex
of $\phi(u^{\prime}v^{\prime})$, something that is otherwise allowed by
properties (a)–(d).)

######  Lemma 1.

A phylogenetic network $N_{\textsc{in}}$ displays a phylogenetic tree
$T_{\textsc{in}}$ if and only if there is an embedding function on
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

###### Proof.

Suppose first that $N_{\textsc{in}}$ displays $T_{\textsc{in}}$, that is,
there is a subgraph $T_{\textsc{in}}^{\prime}$ of $N_{\textsc{in}}$ that is a
subdivision of $T_{\textsc{in}}$. Then, every vertex of $T_{\textsc{in}}$
corresponds to a vertex of $T_{\textsc{in}}^{\prime}$ and every arc $uv$ in
$T_{\textsc{in}}$ corresponds to a directed path in $T_{\textsc{in}}^{\prime}$
between the vertices corresponding to $u$ and $v$. Let $\phi$ denote this
correspondance relation. Then, (c) of Definition 2 follows from the definition
of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ while the other
properties follow from $\phi$ being an isomorphism (of a subdivision of
$T_{\textsc{in}}$ into $T_{\textsc{in}}^{\prime}$).

Conversely, suppose that there is an embedding function $\phi$ on
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ and let
$T_{\textsc{in}}^{\prime}$ be the subgraph formed by the arcs of
$N_{\textsc{in}}$ that are part of some path $\phi(uv)$ for an arc $uv$ in
$T$. Then, it can be verified that $T_{\textsc{in}}^{\prime}$ is a subdivision
of $T_{\textsc{in}}$. ∎

In light of Lemma 1, we may henceforth view Tree Containment as the following
problem:

Input: phylogenetic network $N_{\textsc{in}}$ and phylogenetic tree
$T_{\textsc{in}}$ with the same leaf-label set Task: Find an embedding
function on $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Tree
Containment (TC)

###  2.2 Overview of our approach

We study Tree Containment parameterized by the treewidth of the input network
$N_{\textsc{in}}$. A key tool will be the following theorem from [32]. In this
theorem, the display graph $D_{\textsc{in}}(N_{u},T_{u})$ for unrooted $N_{u}$
and $T_{u}$ is defined analogously to
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ for rooted
$N_{\textsc{in}},T_{\textsc{in}}$ – that is, it is the (undirected) graph
derived from the disjoint union of $N_{u}$ and $T_{u}$ by identifying leaves
with the same label.

######  Theorem 1 ([32]).

Let $N_{u}$ and $T_{u}$ be an unrooted binary phylogenetic network and tree,
respectively, with the same leaf-label set. If $N_{u}$ displays $T_{u}$ then
$tw(D_{\textsc{in}}(N_{u},T_{u}))\leq 2tw(N_{u})+1$.

By Theorem 1, we suppose that the display graph
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ has treewidth at most
$2k+1$, where $k$ is the treewidth of the underlying undirected graph $N_{u}$
of $N_{\textsc{in}}$, as otherwise
$tw(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))=tw(D_{\textsc{in}}(N_{u},T_{u}))>2k+1$
and $N_{u}$ does not display the unrooted version $T_{u}$ of
$T_{\textsc{in}}$, implying that $N_{\textsc{in}}$ does not display
$T_{\textsc{in}}$.

As is often the case for treewidth parameterizations, we will proceed via a
dynamic programming on a tree decomposition, in this case a tree decomposition
of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Recall that we view a
bag $(P,S,F)$ in the tree decomposition as partitioning the vertices of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ into past, present and
future. A typical dynamic programming approach is to store, for each bag, some
set of information about the present, while forgetting most information about
the past, and not yet caring about what happens in the future. The resulting
information is stored in a “signature”, and the algorithm works by calculating
which signatures are possible on each bag, in a bottom-up manner. This
approach is complicated by the fact that the sought-for embedding of
$T_{\textsc{in}}$ into $N_{\textsc{in}}$ may not map the past/present/future
of $T_{\textsc{in}}$ into the past/present/future (respectively) of
$N_{\textsc{in}}$. Vertices from the past of $T_{\textsc{in}}$ may be embedded
in the future of $N_{\textsc{in}}$, or vice versa. Thus, we have to store more
information than we might at first think. In particular, it is not enough to
store information about which present vertices of $T_{\textsc{in}}$ are
embedded in which present vertices of $N_{\textsc{in}}$ (indeed, depending on
the bag, it may be that none of them are). As such, our notion of a
“signature” has to track how vertices from the past of $T_{\textsc{in}}$ are
embedded in the present and future of $N_{\textsc{in}}$, and which vertices
from the past of $N_{\textsc{in}}$ contain vertices from the present or future
of $T_{\textsc{in}}$. Vertices of the past which are mapped to vertices of the
past, on the other hand, can mostly be forgotten about.

###  2.3 An informal guide to (compact) signatures

Roughly speaking, a _signature_ $\sigma$ for a bag $(P,S,F)$ in the tree
decomposition of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ consists
of the following items (see Fig. 3 for an example):

  1. 1.

a display graph $D(N,T)$, some of whose vertices correspond (isomorphically)
to $S\subseteq V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$, and the
rest of which are labeled past or future (which we may think of as vertices
corresponding to some vertex of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ in $P$ or $F$,
respectively). We use a function $\iota$ on $V(D(N,T))$ to capture both this
correspondence and labelling, where $\iota$ maps each vertex to an element of
$S$ or a label from $\\{\textsc{past},\textsc{future}\\}$. We emphasize here
that $D(N,T)$ is distinct from the input display graph
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

  2. 2.

an embedding $\phi$ of $T$ in $N$ such that, for no arc $uv$ of $T$, all of
$V(\phi(uv))\cup\\{u,v\\}$ have the same label
$y\in\\{\textsc{past},\textsc{future}\\}$ under $\iota$.

Signatures may be seen as “partial embedding functions” on parts of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ in a straightforward way.
In particular, we call $\sigma$ _valid_ for $(P,S,F)$ if, roughly speaking,
$\phi$ corresponds (via $\iota$) to something that can be extended to an
embedding function on the subgraph of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ induced by the vertices
$P\cup S$ introduced below $(P,S,F)$. In our dynamic programming algorithm, we
build valid signatures for a bag $x$ from valid signatures of the child bag(s)
of $x$ (in particular, validity of a signature for $x$ is characterized by the
validity of certain signatures for the child bag(s)).

Since the definition of a signature does not guarantee any bound on the number
of vertices labeled past or future, iterating over all signatures for a bag
$(P,S,F)$ (in order to check their validity) exceeds FPT time. Therefore we
will instead consider “compact” signatures, whose number and size are bounded
in the width $|S|$ of the bag $(P,S,F)$. If
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ admits an embedding
function $\phi^{*}$, then a compact signature corresponding to this embedding
function exists. In the following, we informally describe the compaction
process for this hypothetical solution $\phi^{*}$, thus giving a rough idea of
the definition of a “compact” signature. At all times, the (tentative)
signature will contain a display graph $D(N,T)$ (initially
$D(N,T)=D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$), and an embedding
function of $T$ into $N$ (initially $\phi^{*}$). For a more complete
description of our approach, see Section 3 and, for an illustration, see Fig.
2.

$F$$P$$N_{\textsc{in}}$$T_{\textsc{in}}$

future futurepast

Figure 2: Left: An example of a display graph
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ for which $N_{\textsc{in}}$
displays $T_{\textsc{in}}$ as witnessed by the embedding function $\phi$ that
is indicated by bold edges. Highlighting with dashed border represents the
sets $P$ and $F$, for some bag $(P,S,F)$ in a tree decomposition of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Right: A representation of
the (compact) signature for $(P,S,F)$ derived from this solution. Vertices
labelled past or future are highlighted in gray without border.

Step 1

After initiallization with $\phi^{*}$, we assign a label future to all
vertices of $F$, and a label past to all vertices in $P$ (Observe that no
vertex labeled past will be adjacent to a vertex labeled future, since $S$
separates $P$ from $F$ in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$).
Then, we “forget” which vertices of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ the vertices labelled past
or future correspond to. Our preliminary signature now contains (1) a display
graph $D(N,T)$ whose vertices are either labelled future or past or correspond
(isomorphically) to vertices in $S\subseteq
V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ (we refer the reader to
Section 3.1 for a more formal description), as well as (2) an embedding
function for $D(N,T)$ into $N$.

Step 2

We now simplify the structure of the preliminary signature. The main idea is
that, if $a$ is an arc of $T$ with both endpoints labelled past and all
vertices in the path $\phi(a)$ are also labelled past, then we can safely
forget $a$ and all the arcs in $\phi(a)$. Intuitively, the information that
$a$ will be embedded in $\phi(a)$ does not have any effect on the possible
solutions one could construct on the part of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ that is “above” the bag
$(P,S,F)$. Similarly, we can forget any arc $a$ of $T$ whose endpoints, as
well as every vertex in $\phi(a)$, are assigned the label future. Intuitively,
this is because this information should have no bearing on whether a solution
exists with this signature for
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ restricted to $P\cup S$. In
a similar way, we forget any vertex $u\in V(T)$ and its embedding $\phi(u)$ if
they are assigned the same label, provided that all their incident arcs can
also be forgotten. We will call the vertices and arcs fulfilling these
conditions “redundant” and we remove them from our tentative signature. We can
also safely delete the vertices and arcs of $N$ that are labelled
$y\in\\{\textsc{past},\textsc{future}\\}$ but are not part of the image of
$\phi$. As a result, we now have that for any remaining vertex $u\in T$,
either one of $\\{u,\phi(u)\\}$ is labelled past and the other labelled
future, or some vertex element of $S$ must appear as either one of
$\\{u,\phi(u)\\}$, a neighbor of $u$, or a vertex in the path $\phi(a)$ for an
incident arc $a$ of $u$. Thus, we have “forgotten” all the aspects of the
embedding except those that involve vertices from the present in some way, or
those where the embedding “time-travels” between the past and future (see
Section 3.3 for a more formal description of this process).

Step 3

Finally, we may end up with long paths of vertices with in-degree and out-
degree $1$ that are labelled past or future in $N$ (for example, if $u$ and
$v$ are labelled past, then $\phi(uv)$ may be a long path in $N$ with all
vertices labelled future). Such long paths do not contain any useful
information to us, we therefore compress these by suppressing vertices with
in-degree and out-degree $1$ (This gives the _compact signature_ , see Section
3.8).

future $N_{\textsc{in}}$$T_{\textsc{in}}$$N$$T$$\iota$$\phi$pastpastfuture

Figure 3: Example of a signature of a bag $(P,S,F)$. The $S$-part of
$D(N_{\textsc{in}},T_{\textsc{in}})$ is solid while the non-$S$ part is faded.
The embedding $\phi$ (right, indicated with gray edge-highlight) maps $T$ into
$N$. The dotted arcs labelled $\iota$ show the isomorphism between part of
$D(N,T)$ and $S\subseteq V(D(N_{\textsc{in}},T_{\textsc{in}}))$. Note that the
part of $D(N,T)$ that is not mapped to $S$ is not necessarily isomorphic to
anything in $D(N_{\textsc{in}},T_{\textsc{in}})$.

###  2.4 Bounding the number of signatures

We now outline the main arguments for why the number of possible (compact)
signatures for a given bag $(P,S,F)$ can be bounded in $|S|$. Such a bound on
the number of signatures ensures that the running time of the algorithm is
FPT, because the number of calculations required for each bag is bounded by a
function of the treewidth.

The main challenge is to bound the size of the display graph $D(N,T)$ in a
given signature for $(P,S,F)$. Once such a bound is achieved, this immediately
implies upper bounds (albeit quite large) for the number of possible display
graphs and the number of possible embeddings, and hence on the number of
possible signatures. We will focus here on bounding the size of the tree part
$T$. Once a bound is found for $|T|$ it is relatively straightforward to use
that to give a bound on $|N|$ (because the arcs of $N$ that are not used by
the embedding of $T$ into $N$ are automatically deleted, unless they are
themselves incident to a vertex in $S$, and because isolated vertices are
deleted and long paths suppressed).

It can be seen that a vertex $u\in V(T)$ is redundant (and so would be deleted
from the signature) unless one of the following properties holds:  (1) $u\in
S$,  (2) $\phi(u)\in S$,  (3) $u$is incident to an element of $S$ (4) for some
arc $a$ incident to $u$, the path $\phi(a)$ contains a vertex from $S$ or  (5)
$u$and $\phi(u)$ have different labels from
$\\{\textsc{past},\textsc{future}\\}$.  Essentially if none of (1)–(4) holds,
then all the vertices mentioned in those properties have the same label as
either $u$ or $\phi(u)$, using the fact that $S$ separates the vertices
labelled past from the vertices labelled future. If $u$ and $\phi(u)$ have the
same label, then all these vertices have the same label, which is enough to
show that $u$ is redundant. It remains to bound the number of vertices
satisfying one of these properties. For the first four properties, it is
straightforward to find a bound in terms of $|S|$. The vertices satisfying the
final property are “time-travelling” (in the sense that either $u$ is labelled
past and $\phi(u)$ future, or $u$ is labelled future and $\phi(u)$ past).
Because of the bounds on the other types of vertices, it is sufficient to
provide a bound on the number of _lowest_ time-travelling vertices in $T$.

To see the intuition why this bound should hold: consider some full solution
on the original input, i.e. an embedding function on
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, and suppose $u\in
V(T_{\textsc{in}})$ is a lowest tree vertex for which $u\in P,\phi(u)\in F$
(thus in the corresponding signature, $u$ has label past and $\phi(u)$ has
label future). Let $x\in V(N_{\textsc{in}})\cap V(T_{\textsc{in}})$ be some
leaf descendant of $u$. Then there is path in $T_{\textsc{in}}$ from $u$ to
$x$, and a path in $N_{\textsc{in}}$ from $\phi(u)$ to $\phi(x)=x$. Thus
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ has an (undirected) path
from $u$ to $\phi(u)$. As this is a path between a vertex in $P$ and a vertex
in $F$, some vertex on this path must be in $S$ (since $S$ separates $P$ from
$F$). Such a path must exist for every lowest time-travelling vertex $u$, and
these paths are distinct. The existence of these paths can then be used to
bound the number of lowest time-travelling vertices.

##  3 Filling in the details

###  3.1 Tracking the identity of vertices

In the following, consider a bag $(P,S,F)$ and recall that the sought solution
may embed parts of the past of $T$ in the future of $N$ or vice versa. Thus,
as previously indicated, a signature for $(P,S,F)$ will have to track
information about more vertices than those in $S$. This leads to the following
complexities in how we talk about the identity of vertices in signatures.

For the display graph $D(N,T)$ in a signature for $(P,S,F)$, we want some
vertices to correspond to specific vertices in $S\subseteq
V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ while, for other vertices
we want to express the fact that they correspond to a vertex of $P$ or $F$,
without specifying which one. Moreover, as our dynamic programming proceeds up
the tree decomposition and we move from one signature to another, vertices
will change between these two states. When we move from a child bag
$(P_{c},S_{c},F_{c})$ to a parent bag $(P_{p},S_{p},F_{p})$ and a vertex $x$
of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ “leaves the bag” (that
is, $x\in S_{c}\setminus S_{p}$) then we want to “forget” that a vertex $v$
corresponds to $x$ (instead labelling $v$ past), while still tracking its
adjacencies and embedding information. Similarly, a vertex labelled future
may, at some point, come to correspond to a particular vertex in $S$.

In order to keep this information straight, we have to be careful in how we
talk about the identity of these vertices. In particular, the vertices of the
display graph $D(N,T)$ are different from those in
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))=P\uplus S\uplus F$, but
the signature carries a “correspondance” function $\iota$ that, on some
subgraph of $D(N,T)$, acts as an isomorphism into the “$S$-part” of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ while, on other vertices,
acting as a labelling that assigns some vertices the label past and others the
label future. As such, we refer to $\iota$ as an “isolabelling”.

In the following definition, we consider an arbitrary set $\mathcal{Y}$ of
labels, rather than the set $\\{\textsc{past},\textsc{future}\\}$. While we
will often have $\mathcal{Y}=\\{\textsc{past},\textsc{future}\\}$, we will
come to use isolabellings in other contexts besides signatures.

######  Definition 3 (isolabelling).

Let $\mathcal{Y}$ be a set of labels and let $S\subseteq
V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$. An _$(S,\mathcal{Y})$
-isolabelling_ on a display graph $D(N,T)$ is a function $\iota:V(D(N,T))\to
S\cup\mathcal{Y}$ such that $S$ is a subset of the image of $\iota$ ($\iota$
is “surjective onto $S$”)333Every $v\in S$ has a $u\in V(D(N,T))$ with
$\iota(u)=v$, but not every $y\in\mathcal{Y}$ may have a $u\in V(D(N,T))$ with
$\iota(u)=y$. and, for any $u,v\in V(D(N,T))$ with $\iota(u),\iota(v)\in S$:

  1. (a)

$\iota(u)\in V(N_{\textsc{in}})$ only if $u\in V(N)$ and $\iota(u)\in
V(T_{\textsc{in}})$ only if $u\in V(T)$,

  2. (b)

$\iota(u)=\iota(v)$ only if $u=v$, and

  3. (c)

the arc $uv$ is in $D(N,T)$ if and only if $\iota(u)\iota(v)$ is in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

###  3.2 Signatures and containment structures

Before formally defining a signature for a bag $(P,S,F)$, let us remark that,
later in the paper, we will also discuss constructs which are similar in
construction to signatures, but with slightly different vertex and label sets
(“partial solutions” and “reconciliations”). For this reason, we define a more
general structure, called an $(S,\mathcal{Y})$-containment structure, that
encapsulates all these notions. In the definition that follows, a signature
for a bag $(P,S,F)$ corresponds to an $(S,\mathcal{Y})$-containment structure,
where $S$ is the present of the bag $(P,S,F)$ and $\mathcal{Y}$ is the label
set $\\{\textsc{past},\textsc{future}\\}$. For an intuitive understanding of a
containment structure, the most important features are the display graph,
embedding function and isolabelling.

######  Definition 4 (containment structure).

Let $\mathcal{Y}$ be a set of labels and let $S\subseteq
V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$. An _$(S,\mathcal{Y})$
-containment structure_ is a tuple $(D(N,T),\phi,\iota)$ consisting of

  * •

a display graph $D(N,T)$,

  * •

an embedding function $\phi$ on $D(N,T)$, and

  * •

an $(S,\mathcal{Y})$-isolabelling $\iota:V(D(N,T))\to S\cup\mathcal{Y}$.

In addition, each vertex $u$ of $D(N,T)$ should satisfy the following
properties:

  1. (a)

if $\iota(u)\in S$, then $u$ has the same in- and out-degree in $D(N,T)$ as
$\iota(u)$ in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

  2. (b)

if $u\in T$ and $\iota(u)\neq\iota(\phi(u))$, then $u$ has $2$ out-arcs in
$D(N,T)$.

See Fig. 3 for an example of an
$(S,\\{\textsc{past},\textsc{future}\\})$-containment structure
$(D(N,T),\phi,\iota)$. The last two properties of Definition 4 are used for
bookkeeping, and to help bound the size of the display graph.

######  Definition 5 (signature).

Let $(P,S,F)$ be a bag in the tree decomposition of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Then any
$(S,\\{\textsc{past},\textsc{future}\\})$-containment structure is called a
_signature for $(P,S,F)$_.

Through most of the paper, $\mathcal{Y}=\\{\textsc{past},\textsc{future}\\}$
and $S$ may be referred to as the “present” of the bag $(P,S,F)$.

However, our setup also allows us to talk about “partial solutions”, where $S$
is replaced by $P\cup S$ (essentially merging the past and the present) and
only the label set $\mathcal{Y}=\\{\textsc{future}\\}$ (corresponding to
vertices in $F$) is used. In some instances, we will use additional auxiliary
labels; in particular when considering Join bags in Section 3.6, we use the
labels left and right to distinguish between the pasts of different bags.
Finally, Definition 4 also allows capturing a solution for an instance of Tree
Containment. Indeed, if we replace the set $S$ with
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ and require that no
vertex is mapped to a label of $\mathcal{Y}$, then $D(N,T)$ is isomorphic to
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ and the embedding function
$\phi$ of $T$ into $N$ also describes an embedding of $T_{\textsc{in}}$ into
$N_{\textsc{in}}$.

######  Lemma 2.

$(N_{\textsc{in}},T_{\textsc{in}})$ is a Yes-instance of Tree Containment if
and only if there is a
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-containment
structure $(D(N,T),\phi,\iota)$ with ${\iota}^{-1}(\mathcal{Y})=\varnothing$.

###### Proof.

First, suppose $(D(N,T),\phi,\iota)$ is a
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-containment
structure with ${\iota}^{-1}(\mathcal{Y})=\varnothing$. Then, for every vertex
$u$ of $D(N,T)$, $\iota(u)$ is a vertex of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Moreover, for every vertex
$v$ of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, there is $u\in
V(D(N,T))$ such that $v=\iota(u)$ (see Definition 4). Thus, $\iota$ is a
bijective function between $V(D(N,T))$ and
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ and, by Definition 3(c),
$uv$ is an arc in $D(N,T)$ if and only if $\iota(u)\iota(v)$ is an arc in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Thus, $\iota$ is an
isomorphism, implying that $D(N,T)$ is isomorphic to
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Moreover $N$ is isomorphic
to $N_{\textsc{in}}$ and $T$ is isomorphic to $T_{\textsc{in}}$ (as $\iota$
maps vertices of $N$ to vertices of $N_{\textsc{in}}$ and vertices of $T$ to
vertices of $T_{\textsc{in}}$ by Definition 3(a)). As $\phi$ is an embedding
function on $D(N,T)$, combining $\iota$ with $\phi$ yields an embedding
function on $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

Conversely, suppose that there is an embedding function $\phi$ on
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Let $\iota$ be the
identity function on $V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ and
note that, by Definition 3, $\iota$ is a
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-isolabelling
on $V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ and
${\iota}^{-1}(\mathcal{Y})=\varnothing$. Then,
$(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}),\phi,\iota)$ satisfies the
first three conditions of an $(S,\mathcal{Y})$-containment structure. The
remaining properties, concerning the degrees of vertices, follow from the fact
that $N_{\textsc{in}}$ and $T_{\textsc{in}}$ are binary. In particular, for
any vertex $u$ in $T_{\textsc{in}}$ with $\iota(u)\neq\iota(\phi(u))$, it
holds that $u\neq\phi(u)$ and so $u$ is not a leaf of $T_{\textsc{in}}$ and,
thus, has out-degree $2$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. ∎

###  3.3 Formally defining the restriction

While Section 2.3 describes in broad strokes how a signature for a bag
$(P,S,F)$ could be derived from a solution for an instance of Tree
Containment, we now make this process more precise. Recall that we first
relabelled the vertices in $P$ and $F$ by past and future, respectively, and
then, “redundant” parts of the display graph were removed and the remaining
long paths contracted. Exactly which arcs and vertices should be removed is
made precise in the notion of _redundancy_ defined below.

######  Definition 6 (redundant).

Let $\chi:=(D(N,T),\phi,\iota)$ be an $(S,\mathcal{Y})$-containment structure,
and let $y\in\mathcal{Y}$. Then, we define the _$y$ -redundant_ arcs and
vertices of $D(N,T)$ as follows:

  * •

A tree arc $uv\in A(T)$ is $y$-redundant if $\iota(u)=\iota(v)=y$ and
$\iota(v^{\prime})=y$ for all vertices $v^{\prime}$ in the path $\phi(uv)$.

  * •

A network arc $u^{\prime}v^{\prime}\in A(N)$ is $y$-redundant if
$\iota(u^{\prime})=\iota(v^{\prime})=y$ and, if $u^{\prime}v^{\prime}$ is in
the path $\phi(uv)$ for some tree arc $uv\in A(T)$, $uv$ is $y$-redundant.

  * •

A tree vertex $v$ in $V(T)$ is $y$-redundant if $\iota(v)=\iota(\phi(v))=y$,
and $v$ and $\phi(v)$ are incident only to $y$-redundant arcs in $D(N,T)$.

  * •

A network vertex $v^{\prime}\in V(N)$ is $y$-redundant if
$\iota(v^{\prime})=y$ and $v^{\prime}$ is incident only to $y$-redundant arcs
and, if $v^{\prime}=\phi(v)$ for some $v\in V(T)$, $v$ is $y$-redundant.

We say that an arc or vertex of $D(N,T)$ is _redundant_ if it is $y$-redundant
for some $y\in\mathcal{Y}$. When it is important to specify the containment
structure $\chi$, we say an arc or vertex is _$y$ -redundant with respect to
$\chi$._

Just as we derived a signature from a solution in Section 2.3 by restricting
our attention to a subset of vertices (in that case, the set $S$), we can
restrict any $(S,\mathcal{Y})$-containment structure to an
$(S^{\prime},\mathcal{Y})$-containment structure for any $S^{\prime}\subseteq
S$. This will be a useful tool for deriving signatures for one bag from
signatures for another bag, as well as characterizing the “validity” of a
signature.

future pastpastfuturepastpastfuture$N$$T$

Figure 4: Illustration of Definition 7 (except non-$\mathcal{Y}$ parts of
$\iota$ and $\iota^{\prime}$). Left: The example containment structure $\psi$
of Fig. 3. The dashed area indicates $S^{\prime}$ and $g$: for all $u$ in the
dashed area, $g(\iota(u))=\textsc{past}$ while
$\iota(u)\notin\\{\textsc{past},\textsc{future}\\}$. Right: The
$g$-restriction of $\psi$. In accordance with Definition 7, note how (a) arcs
in the “past”-area of $N$ that are not mapped to by $\phi$ disappear in
$N^{\prime}$ while arcs that are mapped by $\phi$ persist, (b) many of the
arcs in $T$ are in the “past”-area, but embedded by $\phi$ into paths of $N$
that live (at least partially) in the “future”-area of $N$ and, therefore,
also persist, and (c) a common leaf of $T$ and $N$ has been removed since all
its incoming arcs have been deleted. Finally, as will be the case in the
dynamic programming later on, the “past”- and “future”-areas never touch in
$D(N^{\prime},T^{\prime})$.

######  Definition 7 (restriction, see Fig. 4).

Let $\chi=(D(N,T),\phi,\iota)$ be an $(S,\mathcal{Y})$-containment structure,
let $S^{\prime}\subseteq S$, and let $g:S\cup\mathcal{Y}\to
S^{\prime}\cup\mathcal{Y}$ be some function such that for all $v\in
S\cup\mathcal{Y}$, $g(v)=v$ if $v\in S^{\prime}$ and $g(v)\in\mathcal{Y}$
otherwise. Then, we call $g$ a _restriction function_. Further, the _$g$
-restriction_ of $\chi$ is the tuple
$(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$ constructed as
follows:

With $\iota_{g}(u)$ abbreviating $g(\iota(u))$ for all $u\in V(D(N,T))$, let
$D(N^{\prime},T^{\prime})$ be the display graph derived from $D(N,T)$ by
replacing the isolabelling $\iota$ with $\iota_{g}$, and then exhaustively
deleting redundant arcs and vertices (with respect to
$(D(N,T),\phi,\iota_{g})$) from $D(N,T)$. Finally, we define $\iota^{\prime}$
and $\phi^{\prime}$ as the respective restrictions of $\iota_{g}$ to
$D(N^{\prime},T^{\prime})$ and $\phi$ to $T^{\prime}$.

We will sometimes write $(S_{1}\to y_{1},\dots,S_{j}\to y_{j})$-restriction
instead of $g$-restriction, where $y_{1},\dots y_{j}$ are labels in
$\mathcal{Y}$ and $g(u):=y_{i}$ for all $u\in S_{i}$, and $g(u):=u$ for all
other $u$. For example, we may write $(P\to\textsc{past})$-restriction when
$g$ is the function that maps all vertices in $P$ to the label past, and
leaves other vertices unchanged. If any $S_{i}$ is a singleton set $\\{z\\}$,
we permit ourselves to write $z\to y_{i}$ instead of $\\{z\\}\to y_{i}$. In
particular, we will see $(\textsc{right}\to\textsc{future})$-restrictions,
where the label right is mapped to the label future. Such restrictions may
sometimes be used to “merge” labels. Note that Steps 1 and 2 of the process
described in Section 2.3 is (roughly analgous to) the process of constructing
the $(P\rightarrow\textsc{past},F\rightarrow\textsc{future})$-restriction of
some
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}),\varnothing)$-containment
structure corresponding to a solution.

Before proving results relating to $g$-restrictions, we make the following
observations about $g$-restrictions and redundant arcs and vertices, which are
straightforward consequences of Definition 6 and, thus, we omit their proofs.

######  Observation 1.

Any arc or vertex $a$ of $D(N,T)$ is $y$-redundant with respect to
$(D(N,T),\phi,\iota)$ if and only if $\iota(Q_{a})=\\{y\\}$ for a set of
vertices $Q_{a}$ that depends only on $D(N,T)$ and $\phi$:

  * •

If $a$ is a tree arc, then $Q_{a}=V(a)\cup V(\phi(a))$.

  * •

If $a$ is a network arc, then $Q_{a}=Q_{a^{\prime}}$ if $Q_{a}$ is part of a
path $\phi(a^{\prime})$, otherwise $Q_{a}=V(a)$.

  * •

If $a$ is a tree vertex, then $Q_{a}=a\cup\phi(a)\cup\bigcup_{uv\in
A(D(N,T)):a\in\\{u,v\\}}Q_{uv}$.

  * •

If $a$ is a network vertex and $a=\phi(u^{\prime})$, then
$Q_{a}=Q_{u^{\prime}}\cup\bigcup_{uv\in A(D(N,T)):a\in\\{u,v\\}}Q_{uv}$,
otherwise $Q_{a}=a\cup\bigcup_{uv\in A(D(N,T)):a\in\\{u,v\\}}Q_{uv}$.

######  Observation 2.

If a tree arc $uv$ is $y$-redundant then so is every arc in $\phi(uv)$. A tree
vertex $u$ is $y$-redundant if and only if $\phi(u)$ is $y$-redundant.

######  Lemma 3.

Let $\chi$ be an $(S,\mathcal{Y})$-containment structure, let
$S^{\prime}\subseteq S$, and let $\chi^{\prime}$ be the $g$-restriction of
$\chi$ for some restriction function $g:S\cup\mathcal{Y}\to
S^{\prime}\cup\mathcal{Y}$. Then, $\chi^{\prime}$ is an
$(S^{\prime},\mathcal{Y})$-containment structure.

###### Proof.

To show that $\chi=(D(N,T),\phi,\iota)$ being an $(S,\mathcal{Y})$-containment
structure implies
$\chi^{\prime}=(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$ being
an $(S^{\prime},\mathcal{Y})$-containment structure, we verify the five
conditions of Definition 4 individually.

$D(N^{\prime},T^{\prime})$ is a display graph.

As $D(N^{\prime},T^{\prime})$ was derived from $D(N,T)$ by deleting a subset
of arcs and vertices, it is clear that $D(N^{\prime},T^{\prime})$ remains a
display graph.

$\phi^{\prime}$ is an embedding function.

As $\phi^{\prime}$ is the restriction of $\phi$ to $T^{\prime}$, and no arc in
a path $\phi(uv)$ was deleted unless the arc $uv$ was deleted as well (and
similarly for vertices $\phi(u)$), $\phi^{\prime}$ is still a function that
maps vertices of $T^{\prime}$ to vertices of $N^{\prime}$ and arcs of
$T^{\prime}$ to directed paths of $N^{\prime}$. The other properties of an
embedding function (such as all paths being arc-disjoint) follow immediately
from the fact that these properties hold for $\phi$. Thus, $\phi^{\prime}$ is
an embedding function on $D(N^{\prime},T^{\prime})$.

$\iota^{\prime}$ is an $(S^{\prime},\mathcal{Y})$-isolabelling.

Note that the properties of an isolabelling follow immediately from
construction of $\iota^{\prime}$, the fact that $g(v)=v$ for all $v\in
S^{\prime}$ and the fact that $\iota$ is an $(S,\mathcal{Y})$-isolabelling. To
see that the image of $\iota^{\prime}$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ contains $S^{\prime}$, we
prove that, for every $z\in S^{\prime}$, there is some $u\in
V(D(N^{\prime},T^{\prime}))$ for which $\iota^{\prime}(u)=z$. To see this,
consider the vertex $u\in V(D(N,T))$ for which $\iota(u)=z$. Since $z\in
S^{\prime}$ we then have $g(\iota(u))=g(z)=z\notin\mathcal{Y}$ and, thus, $u$
cannot become redundant in the construction of $\chi^{\prime}$. Hence, $u$ is
also a vertex of $D(N^{\prime},T^{\prime})$, and
$\iota^{\prime}(u)=g(\iota(u))=z$ as required.

Same degrees in $D(N^{\prime},T^{\prime})$ as in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$.

Let $u\in V(D(N,T))$ with $\iota(u)\in S^{\prime}$. Observe that no arc
incident to $u$ is deleted when constructing $D(N^{\prime},T^{\prime})$ and,
thus, $u$ has the same in-and out-degrees in $D(N^{\prime},T^{\prime})$ as it
does in $D(N,T)$, that is, the same in- and out-degrees as
$\iota(u)=\iota^{\prime}(u)$.

Out-arcs in $D(N^{\prime},T^{\prime})$.

Let $u\in V(T^{\prime})$ with
$\iota^{\prime}(u)\neq\iota^{\prime}(\phi^{\prime}(u))$. In particular, there
is no $y\in\mathcal{Y}$ with
$\iota^{\prime}(u)=\iota^{\prime}(\phi^{\prime}(u))=y$. Then, no arc incident
to $u$ was deleted (as for any such arc $a$ the path $\phi(a)$ contains
$\phi(u)$ by Definition 2(a)) and, so, $u$ has the same out-degree in
$D(N^{\prime},T^{\prime})$ as in $D(N,T)$. Moreover, $u$ has out-degree $2$ in
$D(N,T)$ since $\iota(u)\neq\iota(\phi(u))$ (otherwise
$\iota^{\prime}(u)=\iota^{\prime}(\phi^{\prime}(u))$ by construction of
$\phi^{\prime}$ and $\iota^{\prime}$) and, thus, in
$D(N^{\prime},T^{\prime})$.∎

######  Lemma 4 (transitivity of restrictions).

Let $\chi$ be an $(S,\mathcal{Y})$-containment structure for some $S$ and
$\mathcal{Y}$, let $S^{\prime\prime}\subseteq S^{\prime}\subseteq S$ and let
$g^{\prime}:S\cup\mathcal{Y}\to S^{\prime}\cup\mathcal{Y}$ and
$g^{\prime\prime}:S^{\prime}\cup\mathcal{Y}\to
S^{\prime\prime}\cup\mathcal{Y}$ be restriction functions. Let $\chi^{\prime}$
be the $g^{\prime}$-restriction of $\chi$ and let $\chi^{\prime\prime}$ be the
$g^{\prime\prime}$-restriction of $\chi^{\prime}$. Then, $\chi^{\prime\prime}$
is the $(g^{\prime\prime}\circ g^{\prime})$-restriction of $\chi$.

###### Proof.

First, we show that $g:=g^{\prime\prime}\circ g^{\prime}$ is a restriction
function. To this end, let $v\in S\cup\mathcal{Y}$. If $v\in
S^{\prime\prime}$, then $v\in S^{\prime}\cap S$ and, thus,
$g(v)=g^{\prime\prime}(g^{\prime}(v))=g^{\prime\prime}(v)=v$ since both
$g^{\prime}$ and $g^{\prime\prime}$ are restriction functions. Otherwise,
$v\notin S^{\prime\prime}$ and either $v\in S^{\prime}$, in which case
$g^{\prime}(v)=v\notin S^{\prime\prime}$, or $g^{\prime}(v)\in\mathcal{Y}$. In
either case $g^{\prime}(v)\notin S^{\prime\prime}$ and so
$g(v)=g^{\prime\prime}(g^{\prime}(v))\in\mathcal{Y}$.

In the following, let
$\chi^{\prime}=(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$, let
$\chi^{\prime\prime}=(D(N^{\prime\prime},T^{\prime\prime}),\phi^{\prime\prime},\iota^{\prime\prime})$
and let $\iota_{g^{\prime}}$ be as described in Definition 7, that is,
$\iota_{g^{\prime}}(u)=g^{\prime}(\iota(u))$ for all $u\in V(D(N,T))$ (and
analogously for $\iota^{\prime}_{g^{\prime\prime}}$ and $\iota_{g}$). Then, by
Definition 7, $\iota^{\prime}=\iota_{g^{\prime}}$ and
$\iota^{\prime\prime}=\iota^{\prime}_{g^{\prime\prime}}$. Note that, for any
$u\in V(D(N^{\prime},T^{\prime}))$,

$\iota^{\prime}_{g^{\prime\prime}}(u)=g^{\prime\prime}(\iota^{\prime}(u))=g^{\prime\prime}(\iota_{g^{\prime}}(u))=g^{\prime\prime}(g^{\prime}(\iota(u)))=g(\iota(u))=\iota_{g}(u).$
(1)

Next, we show that $\chi^{\prime\prime}$ equals the $g$-restriction
$\chi^{*}=(D(N^{*},T^{*}),\phi^{*},\iota^{*})$ of $\chi$. To this end, we
first prove that $D(N^{*},T^{*})=D(N^{\prime\prime},T^{\prime\prime})$. As
both display graphs are subgraphs of $D(N,T)$, it is enough to show that any
arc or vertex is deleted in the construction of $D(N^{*},T^{*})$ from $D(N,T)$
if and only if it is deleted in the construction of $D(N^{\prime},T^{\prime})$
from $D(N,T)$ or of $D(N^{\prime\prime},T^{\prime\prime})$ from
$D(N^{\prime},T^{\prime})$.

Arcs:

Let $uv$ be an arc of $D(N,T)$. If $uv\in A(T)$, then let
$Q_{uv}:=\\{u,v\\}\cup V(\phi(uv))$ (that is, $Q_{uv}$ contains $u$, $v$ and
all vertices in the path $\phi(uv)$). If $uv$ is an arc of $N$, then let
$Q_{uv}$ be the set containing $u$ and $v$ together with any $u^{\prime}$ and
$v^{\prime}$ for which $uv$ is in the path $\phi(u^{\prime}v^{\prime})$ (by
Definition 2, there is at most one such arc $u^{\prime}v^{\prime}$). By
Observation 1, $uv$ is deleted in the construction of $D(N^{*},T^{*})$ if and
only if there is some $y\in Y$ with $\iota_{g}(Q_{uv})=\\{y\\}$.

First, assume that $uv$ is in $D(N^{\prime\prime},T^{\prime\prime})$ but not
in $D(N^{*},T^{*})$. Since $D(N^{\prime\prime},T^{\prime\prime})$ is a
subgraph of $D(N^{\prime},T^{\prime})$, we know that $uv$ is also in
$D(N^{\prime},T^{\prime})$. If $uv\in A(T)$, then all vertices of
$\phi^{\prime}(uv)=\phi(uv)$ are still in $D(N^{\prime},T^{\prime})$ as
$\phi^{\prime}$ is an embedding function on $D(N^{\prime},T^{\prime})$. If
$uv\in A(N)$ and $Q_{uv}=\\{u,v,u^{\prime},v^{\prime}\\}$ and any of
$u^{\prime}$ and $v^{\prime}$ is not in $D(N^{\prime},T^{\prime})$, then the
arc $u^{\prime}v^{\prime}\in A(T)$ was deleted in the construction of
$D(N^{\prime},T^{\prime})$ and, by Observation 2, so was $uv$, contradicting
$uv$ being in $D(N^{\prime},T^{\prime})$. Thus, all vertices of $Q_{uv}$ are
in $D(N^{\prime},T^{\prime})$ and, by (1),
$\iota^{\prime}_{g^{\prime\prime}}(Q_{uv})=\iota_{g}(Q_{uv})=\\{y\\}$ for some
$y\in\mathcal{Y}$. Then $uv$ is deleted in the construction of
$D(N^{\prime\prime},T^{\prime\prime})$.

Second, assume that $uv$ is in $D(N^{*},T^{*})$ but not in
$D(N^{\prime\prime},T^{\prime\prime})$. If $uv$ is in
$D(N^{\prime},T^{\prime})$ then $uv$ is redundant with respect to
$(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$, that is,
$Q_{uv}\subseteq V(D(N^{\prime},T^{\prime}))$ and, by Observation 1, there is
some $y\in\mathcal{Y}$ with
$\\{y\\}=\iota^{\prime}_{g^{\prime\prime}}(Q_{uv})=\iota_{g}(Q_{uv})$ (using
(1)). But then, $uv$ is also deleted in the construction of $D(N^{*},T^{*})$.
If $uv$ is not in $D(N^{\prime},T^{\prime})$, then
$\iota_{g^{\prime}}(Q_{uv})=\\{y\\}$ for some $y\in\mathcal{Y}$, implying
$\iota_{g}(Q_{uv})=g(\iota(Q_{uv}))=g^{\prime\prime}(g^{\prime}(\iota(Q_{uv}))=g^{\prime\prime}(\iota_{g^{\prime}}(Q_{uv}))=g^{\prime\prime}(\\{y\\})=\\{g^{\prime\prime}(y)\\}$.
As $y\in\mathcal{Y}$ implies $g^{\prime\prime}(y)\in\mathcal{Y}$, we know that
$uv$ is deleted in the construction of $D(N^{*},T^{*})$.

Vertices:

Since each arc of $D(N,T)$ is in $D(N^{*},T^{*})$ if and only if it is in
$D(N^{\prime\prime},T^{\prime\prime})$, all vertices with at least one
incident arc in $D(N^{*},T^{*})$ are in $D(N^{\prime\prime},T^{\prime\prime})$
and vice versa. It remains to consider the isolated vertices. To this end, let
$v\in V(D(N,T))$ with no incident arcs in $D(N^{*},T^{*})$ and let
$Q_{v}:=\\{v,\phi(v)\\}$ if $v\in V(T)$ and let $Q_{v}$ be the set containing
$v$ and any $u$ such that $v=\phi(u)$ if $v\in V(N)$. By definition of
redundant vertices, either both vertices of $Q_{v}$ are deleted in the
construction of $D(N^{*},T^{*})$ or neither is. As $D(N^{*},T^{*})$ and
$D(N^{\prime\prime},T^{\prime\prime})$ have the same arcs, we may assume
neither element of $Q_{v}$ has any incident arcs. Then, $v$ is deleted in the
construction of $D(N^{*},T^{*})$ if and only if $\iota_{g}(Q_{v})=\\{y\\}$ for
some $y\in\mathcal{Y}$. Now, if $Q_{v}$ intersects
$V(D(N^{\prime},T^{\prime})$, then $Q_{v}\subseteq
V(D(N^{\prime},T^{\prime}))$. Then, by (1),
$\iota^{\prime}_{g^{\prime\prime}}(Q_{v})=\iota_{g}(Q_{v})$ implying that $v$
is in $D(N^{\prime\prime},T^{\prime\prime})$ if and only if it is in
$D(N^{*},T^{*})$. Otherwise, $Q_{v}\cap
V(D(N^{\prime},T^{\prime}))=\varnothing$ (in particular, $v\notin
V(D(N^{\prime},T^{\prime}))$), implying $\iota_{g^{\prime}}(Q_{v})=\\{y\\}$
for some $y\in\mathcal{Y}$. As in the Arc-case,
$\iota_{g}(Q_{v})=\\{g^{\prime\prime}(y)\\}=\\{y^{\prime}\\}$ for some
$y^{\prime}\in\mathcal{Y}$. Thus, $v$ is neither in $D(N^{*},T^{*})$ nor in
$D(N^{\prime\prime},T^{\prime\prime})$.

Since $\phi^{*}$ is the restriction of $\phi$ to $T^{*}$ and
$\phi^{\prime\prime}$ is the restriction of $\phi$ to $T^{\prime\prime}$ (via
$\phi^{\prime}$), we also have $\phi^{*}=\phi^{\prime\prime}$. By (1),
$\iota^{\prime}_{g^{\prime\prime}}(u)=\iota_{g}(u)$ for any vertex $u$ in
$D(N^{\prime},T^{\prime})$ and, thus, $\iota^{\prime\prime}(u)=\iota^{*}(u)$
for any vertex $u$ in $D(N^{\prime\prime},T^{\prime\prime})$ (as
$\iota^{\prime\prime}$ and $\iota^{*}$ are just restrictions of
$\iota^{\prime}_{g^{\prime\prime}}$ and $\iota_{g}$ respectively). Therefore,
$\iota^{*}=\iota^{\prime\prime}$ and we have proved that
$\chi^{*}=\chi^{\prime\prime}$, as required. ∎

###  3.4 Well-behaved containment structures

At this point, we note some additional properties that it will be helpful to
assume for $(S,\mathcal{Y})$-containment structures. These properties are
summarized in the concept of “well-behavedness” and, in what follows, we will
restrict our attention to such containment structures. While not directly
implied by the definition of a containment structure, the properties
effectively ensure that containment structures behave “as expected”. In
particular, our dynamic programming algorithm will work with well-behaved
signatures.

######  Definition 8.

An $(S,\mathcal{Y})$-containment structure $(D(N,T),\phi,\iota)$ is called
_well-behaved_ if

  1. (a)

$D(N,T)$ contains no redundant arcs or vertices;

  2. (b)

For all arcs $uv$ in $D(N,T)$ with $\iota(u),\iota(v)\in\mathcal{Y}$, we have
$\iota(u)=\iota(v)$;

  3. (c)

For all $u,v\in V(D(N,T))$ such that $\iota(u),\iota(v)\in S$ and $D(N,T)$ has
a $u$-$v$-path, $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ has an
$\iota(u)$-$\iota(v)$-path.

Here we prove a number of properties of well-behaved containment structures,
that allow us to focus on them going forward.

######  Lemma 5.

Let $\chi:=(D(N,T),\phi,\iota)$ be a
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-containment
structure with $\iota^{-1}(\mathcal{Y})=\varnothing$. Then, $\chi$ is well-
behaved.

###### Proof.

Since $\iota^{-1}(\mathcal{Y})=\varnothing$ and
$S=V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$, we know that $\iota$
is an isomorphism between $D(N,T)$ and
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$, implying Definition
8(c), while (a) and (b) are direct consequences of
$\iota^{-1}(\mathcal{Y})=\varnothing$. ∎

######  Lemma 6.

Let $\chi=(D(N,T),\phi,\iota)$ be a well-behaved $(S,\mathcal{Y})$-containment
structure and let $g$ be a restriction function such that, for all arcs $uv$
of $D(N,T)$ with $g(\iota(u)),g(\iota(v))\in\mathcal{Y}$, we have
$g(\iota(u))=g(\iota(v))$. Then, the $g$-restriction $\sigma$ of $\chi$ is
also well-behaved.

Essentially, this condition says that relabelling according to $g$ does not
immediately create any arcs $uv$ for which $u$ and $v$ are labelled with
different elements of $\mathcal{Y}$.

###### Proof.

We will show that
$\sigma=(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime}=\iota\circ g)$
satisfies Definition 8(a)-(c).

(a)

follows by Definition 7, as redundant arcs and vertices are deleted when
constructing $\sigma$.

(b):

Let $uv$ be an arc of $D(N^{\prime},T^{\prime})$ with
$\iota^{\prime}(u),\iota^{\prime}(v)\in\mathcal{Y}$. Then, by the condition of
the lemma, $\iota^{\prime}(u)=\iota^{\prime}(v)$.

(c):

Let $u,v\in V(D(N^{\prime},T^{\prime}))$ such that
$\iota^{\prime}(u),\iota^{\prime}(v)\notin\mathcal{Y}$ (that is,
$\iota^{\prime}(u),\iota^{\prime}(v)\in S^{\prime}$ for
$S^{\prime}:=\operatorname{img}(g)\setminus\mathcal{Y}$) and there is a
$u$-$v$-path $p$ in $D(N^{\prime},T^{\prime})$. Then, by Definition 7,
$\iota(u)=g(\iota(u))=\iota^{\prime}(u)$ and, similarly,
$\iota(v)=\iota^{\prime}(v)$. Moreover, as $D(N^{\prime},T^{\prime})$ is a
subgraph of $D(N,T)$, the latter also contains $p$. Finally, since $\chi$ is
well-behaved, there is a path in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ from
$\iota(u)=\iota^{\prime}(u)$ to $\iota(v)=\iota^{\prime}(v)$.∎

###  3.5 Partial solution and valid signatures

As with any dynamic programming algorithm, we need some way to decide which
signatures are “correct” before we have actually found a solution. As such, we
need a notion of a “partial solution”. Much as we may think of a signature for
a bag $(P,S,F)$ as corresponding to the
$(P\to\textsc{past},F\to\textsc{future})$-restriction of some solution, we may
think of a partial solution as the $(F\to\textsc{future})$-restriction of some
solution. That is, a partial solution is a $(P\cup
S,\\{\textsc{future}\\})$-containment structure that roughly corresponds to
what would happen if we took a solution and “forgot” some of the details about
the vertices in $F$. A partial solution is then a “witness” for a given
signature for $(P,S,F)$ if that signature can in turn be derived from the
partial solution by “forgetting” details about the vertices in $P$. In this
case we call the signature “valid”. This is defined precisely below.

######  Definition 9 (partial solution, signature, valid).

Let $(P,S,F)$ be a bag in the tree decomposition of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Then any $(P\cup
S,\\{\textsc{future}\\})$-containment structure is called _$F$ -partial
solution_ (or simply _partial solution_) for $(P,S,F)$. A well-behaved
signature $\sigma$ for $(P,S,F)$ is called _valid_ if $\sigma$ is the
$(P\to\textsc{past})$-restriction of a well-behaved partial solution $\psi$
for $(P,S,F)$. We call $\psi$ a _witness_ for $\sigma$.

######  Lemma 7.

Let $(N_{\textsc{in}},T_{\textsc{in}})$ be a Yes-instance of Tree Containment
and let $(P,S,F)$ be a bag in the tree decomposition of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. Then, there is a well-
behaved $F$-partial solution $\psi$, and a valid signature $\sigma$ for
$(P,S,F)$.

###### Proof.

By Lemma 5, there is a well-behaved
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-containment
structure $\psi^{*}$ with ${\iota}^{-1}(\mathcal{Y})=\varnothing$. Clearly,
$\psi^{*}$ is also a
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\varnothing)$-containment
structure. Now, let $\psi$ be the $(F\to\textsc{future})$-restriction of
$\psi^{*}$ and note that $\psi$ is an $F$-partial solution. Clearly,
$x,y\in\\{\textsc{future}\\}\Rightarrow x=y$ and, so, Lemma 6 applies, showing
that $\psi$ is well-behaved. Finally, let $\sigma$ be the
$(P\to\textsc{past})$-restriction of $\psi$ which is valid since $\psi$ is
well-behaved. ∎

######  Lemma 8.

$(N_{\textsc{in}},T_{\textsc{in}})$ is a Yes-instance of Tree Containment if
and only if there is a valid signature $\sigma:=(D(N,T),\phi,\iota)$ for
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\varnothing,\varnothing)$
with ${\iota}^{-1}(\textsc{future})=\varnothing$.

###### Proof.

By Lemma 2 and Lemma 5, $(N_{\textsc{in}},T_{\textsc{in}})$ is a Yes-instance
if and only if there is a well-behaved
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\mathcal{Y})$-containment
structure $\psi=(D(N,T),\phi,\iota)$ with
${\iota}^{-1}(\\{\mathcal{Y}\\})=\varnothing$, or equivalently a well-behaved
$\varnothing$-partial solution $\psi=(D(N,T),\phi,\iota)$ with
${\iota}^{-1}(\\{\textsc{future}\\})=\varnothing$. First, suppose such a
partial solution exists and let
$\sigma:=((D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$ be the
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))\to\textsc{past})$-restriction
of $\psi$. Then, $\sigma$ is a valid signature for
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\varnothing,\varnothing)$
and, by construction, ${\iota^{\prime}}^{-1}(\textsc{future})=\varnothing$.
(In fact $D(N^{\prime},T^{\prime})$ is the empty graph since all arcs and
vertices of $D(N,T)$ become past-redundant; but we do not use that fact here).

For the converse, consider a valid signature $\sigma:=(D(N,T),\phi,\iota)$ for
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\varnothing,\varnothing)$
with ${\iota}^{-1}(\textsc{future})=\varnothing$. By Definition 9, $\sigma$ is
the
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))\to\textsc{past})$-restriction
of a well-behaved $\varnothing$-partial solution
$\psi:=((D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$. It remains
to show that ${\iota^{\prime}}^{-1}(\textsc{future})=\varnothing$. Towards a
contradiction, assume that $D(N^{\prime},T^{\prime})$ has a vertex $u$ with
$\iota^{\prime}(u)=\textsc{future}$. Since
$u\notin\iota^{-1}(\textsc{future})=\varnothing$, $u$ is future-redundant
after applying
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))\to\textsc{past}$.
However, applying
$V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))\to\textsc{past}$ cannot
make a vertex future-redundant that was not previously future-redundant (as no
new vertex gains the label future). Thus, $u$ is future-redundant in $\psi$,
contradicting Definition 8(a). ∎

Lemma 6, Lemma 7 and Lemma 8 show that an instance
$(N_{\textsc{in}},T_{\textsc{in}})$ of Tree Containment is a Yes-instance if
and only if there is a well-behaved valid signature
$\sigma:=(D(N,T),\phi,\iota)$ for the root bag
$(V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})),\varnothing,\varnothing)$
with ${\iota}^{-1}(\textsc{future})=\varnothing$. Thus in order to solve an
instance of Tree Containment, it is enough to decide for each bag $(P,S,F)$ in
the tree decomposition of $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$,
and for each well-behaved signature $\sigma$ for $(P,S,F)$, whether $\sigma$
is valid.

###  3.6 Determining valid signatures

With the formal definitions of valid signatures and restrictions in place, we
can now show how to determine whether a well-behaved signature for a bag
$(P,S,F)$ is valid, assuming we know this for all signatures on the child
bag(s). As is common in dynamic programming techniques, we take advantage of
the structure of a nice tree decomposition. The following lemmas describe the
exact conditions for Leaf, Forget and Introduce bags while the additional
terminology required for Join bags is deferred to Section 3.7.

######  Lemma 9.

Let $(P,S,F)$ correspond to a Leaf bag in the tree decomposition i.e.
$P=S=\varnothing$, $F=V(D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}}))$ and
$(P,S,F)$ has no children. Let $\sigma:=(D(N,T),\phi,\iota)$ be a well-behaved
signature for $(P,S,F)$. Then, $\sigma$ is valid if and only if
$\iota^{-1}(\textsc{past})=\varnothing$.

###### Proof.

Suppose first that $\sigma$ is valid. By Definition 9, $\sigma$ is the
$(P\to\textsc{past})$-restriction of a well-behaved $F$-partial solution (that
is, $(P\cup S,\\{\textsc{future}\\})$-containment structure)
$\psi:=D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$. Then
$\iota^{\prime}(u)\neq\textsc{past}$ for every vertex $u$ in
$D(N^{\prime},T^{\prime})$ and, as $P=\varnothing$, this remains true after
applying $P\to\textsc{past}$. It follows that $\iota(u)\neq\textsc{past}$ for
every vertex $u\in D(N,T)$, as required.

Conversely, suppose $\iota^{-1}(\textsc{past})=\varnothing$. Since
$P=\varnothing$, the $(S,\\{\textsc{past},\textsc{future}\\})$-containment
structure $\sigma$ is also a $(P\cup S,\\{\textsc{future}\\})$-containment
structure, i.e. $\sigma$ is an $F$-partial solution. To show that $\sigma$ is
valid, we prove that $\sigma$ is the $(P\to\textsc{past})$-restriction of
itself, that is, $\sigma$ is a witness for $\sigma$. To this end, observe that
applying $P\to\textsc{past}$ does not change the isolabelling and, by
Definition 8, $\sigma$ contains no redundant arcs or vertices. Thus, applying
$P\to\textsc{past}$ and removing redundant arcs and vertices does not change
$\sigma$. ∎

######  Lemma 10.

Let $(P,S,F)$ correspond to a Forget bag in the tree decomposition with child
bag $(P^{\prime},S^{\prime},F)$, i.e. $P=P^{\prime}\cup\\{z\\}$ and
$S=S^{\prime}\setminus\\{z\\}$ for some $z\in S^{\prime}$. Let $\sigma$ be a
well-behaved signature for $(P,S,F)$. Then, $\sigma$ is valid if and only if
$\sigma$ is the $(z\to\textsc{past})$-restriction of a valid signature
$\sigma^{\prime}$ for $(P^{\prime},S^{\prime},F)$.

###### Proof.

Suppose first that $\sigma$ is the $(z\to\textsc{past})$-restriction of some
valid signature $\sigma^{\prime}$ for $(P^{\prime},S^{\prime},F)$. By
Definition 9, $\sigma^{\prime}$ has a witness $\psi^{\prime}$ (that is,
$\psi^{\prime}$ is a well-behaved $F$-partial solution for
$(P^{\prime},S^{\prime},F)$ whose $P^{\prime}\to\textsc{past}$-restriction is
$\sigma^{\prime}$). By Lemma 4, $\sigma$ is the
$(P\to\textsc{past})$-restriction of $\psi^{\prime}$, and so $\sigma$ is
valid.

For the converse, suppose that $\sigma$ is valid and let $\psi$ be a witness
of $\sigma$ (that is, $\psi$ is a well-behaved $F$-partial solution for
$(P,S,F)$ and $\sigma$ is the $(P\to\textsc{past})$-restriction of $\psi$).
Then, the $(P^{\prime}\to\textsc{past})$-restriction $\sigma^{\prime}$ of
$\psi$ is a valid signature for $(P^{\prime},S^{\prime},F)$ and, by Lemma 4,
the $(z\to\textsc{past})$-restriction of $\sigma^{\prime}$ is the
$(P\to\textsc{past})$-restriction of $\psi$, that is, $\sigma$. ∎

######  Lemma 11.

Let $(P,S,F)$ correspond to an Introduce bag in the tree decomposition with
child bag $(P,S^{\prime},F^{\prime})$, i.e. $S^{\prime}=S\setminus\\{z\\}$ and
$F^{\prime}=F\cup\\{z\\}$ for some $z\in S$. Let $\sigma$ be a well-behaved
signature for $(P,S,F)$. Then, $\sigma$ is valid if and only if the
$(z\to\textsc{future})$-restriction $\sigma^{\prime}$ of $\sigma$ is a valid
signature for $(P,S^{\prime},F^{\prime})$.

###### Proof.

Suppose first that $\sigma$ is a valid signature and let $\psi$ be a witness
for $\sigma$ (that is, $\psi$ is a well-behaved $F$-partial solution for which
$\sigma$ is the $(P\to\textsc{past})$-restriction). Let $\psi^{\prime}$ be the
$(z\to\textsc{future})$-restriction of $\psi$ which, by Lemma 6, is a well-
behaved $F^{\prime}$-partial solution. Let $\sigma^{*}$ denote the
$(P\to\textsc{past})$-restriction of $\psi^{\prime}$ and note that
$\sigma^{*}$ is a valid signature for $(P,S^{\prime},F^{\prime})$. By Lemma 4,
$\sigma^{*}$ is also the
$(P\to\textsc{past},\\{z\\}\to\textsc{future})$-restriction of $\psi$ and the
$(z\to\textsc{future})$-restriction $\sigma^{\prime}$ of $\sigma$ is also the
$(P\to\textsc{past},\\{z\\}\to\textsc{future})$-restriction of $\psi$. Thus,
$\sigma^{\prime}=\sigma^{*}$ and so $\sigma^{\prime}$ is valid, as required
(see Fig. 5).

Figure 5: Illustration of proof for Introduce bags, validity of $\sigma$
implies validty of $\sigma^{\prime}$. Solid lines are restriction relations
that we may assume; the dashed line shows the construction of $\psi^{\prime}$
from $\psi$; dotted lines are relations we can infer using transitivity.

For the converse, let $\sigma=:(D(N,T),\phi,\iota)$ and let
$\sigma^{\prime}=:(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$ be
a valid signature for $(P,S^{\prime},F^{\prime})$. By Definition 9,
$\sigma^{\prime}$ is the $(P\to\textsc{past})$-restriction of some well-
behaved $F^{\prime}$-partial solution
$\psi^{\prime}:=(D(N_{0}^{\prime},T_{0}^{\prime}),\phi_{0}^{\prime},\iota_{0}^{\prime})$.
In the following, $\sigma$, $\sigma^{\prime}$ and $\psi^{\prime}$ will guide
us in constructing an $F$-partial solution $\psi$ of which $\psi^{\prime}$ is
the $(z\to\textsc{future})$-restriction and, more importantly, of which
$\sigma$ is the $(P\to\textsc{past})$-restriction. Then, this implies that
$\sigma$ is valid.

To begin the construction, let $V_{z}$ and $A_{z}$ denote the the set of
vertices and arcs, respectively, that are in $D(N,T)$ but not in
$D(N^{\prime},T^{\prime})$ (that is, the vertices and arcs that are deleted
when deriving $\sigma^{\prime}$ from $\sigma$). Letting $g$ be the function
$z\to\textsc{future}$, we may assume that $g(\iota(v))=\textsc{future}$ for
all vertices $v$ in $V_{z}$ or $V(A_{z})$ and
$g(\iota(V(\phi(uv))))=\\{\textsc{future}\\}$ for any tree arc $uv$ in $A_{z}$
as well. Similarly, let $V_{p}$ and $A_{p}$ be the vertices and arcs,
respectively, that are deleted from $D(N_{0}^{\prime},T_{0}^{\prime})$ in the
construction of $D(N^{\prime},T^{\prime})$. Letting $h$ be the function
$P\to\textsc{past}$, we may assume that $h(\iota(v))=\textsc{past}$ for all
vertices $v$ in $V_{p}$ or $V(A_{p})$, and
$h(\iota(V(\phi(uv))))=\\{\textsc{past}\\}$ for any tree arc $uv$ in $A_{p}$
as well.

We now construct the $F$-partial solution
$\psi:=(D(N_{0},T_{0}),\phi_{0},\iota_{0})$ as follows. First, let
$D(N_{0},T_{0})$ be the graph derived from $D(N_{0}^{\prime},T_{0}^{\prime})$
by adding all vertices and arcs of $V_{z}$ and $A_{z}$. Equivalently, we may
say we construct $D(N_{0},T_{0})$ by adding the arcs and vertices of $V_{p}$
and $A_{p}$ to $D(N,T)$, or by adding the arcs and vertices of
$V_{z},V_{p},A_{z},A_{p}$ to $D(N^{\prime},T^{\prime})$. Let $\phi_{0}$ be
defined as the ’union’ of $\phi$ and $\phi_{0}^{\prime}$ \- that is,
$\phi_{0}(uv)=\phi(uv)$ if $uv$ is an arc in $T$, and
$\phi_{0}(uv)=\phi_{0}^{\prime}(uv)$ if $uv$ is an arc in $T_{0}^{\prime}$ (if
$uv$ is an arc of both $T$ and $T_{0}^{\prime}$, then these are the same, as
$uv$ is in $T^{\prime}$ and
$\phi(uv)=\phi^{\prime}(uv)=\phi_{0}^{\prime}(uv)$). Similarly
$\phi_{0}(u)=\phi(u)$ if $u$ is a vertex in $T$, and
$\phi_{0}(u)=\phi_{0}^{\prime}(u)$ if $u$ is a vertex in $T_{0}^{\prime}$.
Finally let $\iota_{0}:V(D(N_{0},T_{0}))\to P\cup S\cup\\{\textsc{future}\\}$
be defined as follows: $\iota_{0}(v)=\iota(v)$ if $v\in V_{z}$ or
$\iota^{\prime}(v)=\textsc{future}$, $\iota_{0}(v)=\iota_{0}^{\prime}(v)$ if
$v\in V_{p}$ or $\iota^{\prime}(v)=\textsc{past}$, and
$\iota_{0}(v)=\iota_{0}^{\prime}(v)=\iota^{\prime}(v)=\iota(v)$ otherwise.
(Note that $\iota_{0}(v)=\textsc{future}$ is possible for some vertices, if
$\iota(v)=\textsc{future}$, but $\iota_{0}(v)=\textsc{past}$ is not possible
as $\iota_{0}^{\prime}(v)\neq\textsc{past}$ for any $v$.)

Figure 6: Illustration of proof for Introduce bags, validity of
$\sigma^{\prime}$ implies validty of $\sigma$. Solid lines are restriction
relations that we may assume; the dashed lines show the construction of $\psi$
from $\psi^{\prime}$ or $\sigma$ (we do not describe the construction of
$\phi_{0}$ or $\iota_{0}$ in the figure, only the construction of
$D(N_{0},T_{0})$ by adding arcs and vertices); the dotted line shows the
relation we want to prove, that $\sigma$ is the
$\\{P\to\textsc{past}\\}$-restriction of $\psi$.

We note here that for any vertex $v$ in $D(N_{0},T_{0})$ with $\iota_{0}(v)\in
S\cup\\{\textsc{future}\\}$, $v$ is a vertex of $D(N,T)$ and
$\iota_{0}(v)=\iota(v)$. Indeed, $v$ cannot be in $V_{p}$, nor can it hold
that $\iota^{\prime}(v)=\textsc{past}$ if $v$ is in
$D(N^{\prime},T^{\prime})$, as both cases would imply
$\iota_{0}(v)=\iota_{0}^{\prime}(v)\in P$. By construction, in all other cases
$\iota_{0}(v)=\iota(v)$. Furthermore, for any arc $a$ incident to $v$ in
$D(N_{0},T_{0})$, $a$ is an arc in $D(N,T)$ (since $a\in A_{p}$ would imply
$\iota_{0}^{\prime}(v)\in P$ and hence either $v\in V_{p}$ or
$\iota^{\prime}(v)=\textsc{past}$), and thus $\phi_{0}(a)=\phi(a)$. A similar
argument shows that for any vertex $v$ in $D(N_{0},T_{0})$ with $\iota(u)\in
P$, $v$ is a vertex of $D(N_{0}^{\prime},T_{0}^{\prime})$,
$\iota_{0}(v)=\iota_{0}^{\prime}(v)$, and $\phi_{0}(a)=\phi_{0}^{\prime}(a)$
for any arc $a$ in $D(N_{0},T_{0})$ incident to $v$.

We will now show that $\psi$ is indeed a well-behaved $F$-partial solution;
afterwards we will show that $\sigma$ is the
$\\{P\to\textsc{past}\\}$-restriction of $\psi$, from which it follows that
$\sigma$ is valid. (A similar argument can be used to show that
$\psi^{\prime}$ is the $\\{\\{z\\}\to\textsc{future}\\}$-restriction of
$\psi$, but we will not need this fact so we do not prove it here.)

######  Claim 1.

$\psi$ is a well-behaved $F$-partial solution.

Proof: We first show that $\psi$ satisfies one of the properties of a well-
behaved $(P\cup S,\\{\textsc{future}\\})$-containment structure

  * •

for any $u,v\in V(D(N_{0},T_{0}))$ with $\iota_{0}(u),\iota_{0}(v)\in P\cup
S$, if $D(N_{0},T_{0})$ has a path from $u$ to $v$ then there is a path from
$\iota_{0}(u)$ to $\iota_{0}(v)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$: Suppose for a
contradiction that this is not the case, and let $u,v\in V(D(N_{0},T_{0}))$ be
such that $\iota_{0}(u),\iota_{0}(v)\in P\cup S$ and there is a path from $u$
to $v$ in $D(N_{0},T_{0}))$, but no path from $\iota_{0}(u)$ to $\iota_{0}(v)$
in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, choosing $uv$ such that
the length of the $u-v$ path is minimal. If $uv$ is an arc in
$D(N_{0},T_{0})$, then $uv$ is an arc in $D(N,T)$ or
$D(N_{0}^{\prime},T_{0}^{\prime})$, and the existence of a path from
$\iota(u)$ to $\iota(v)$ in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$
follows from the fact that $\sigma$ or $\sigma_{0}^{\prime}$ is well-behaved.
Otherwise, by choice of $u,v$ we may assume all internal vertices $u^{\prime}$
on the path from $u$ to $v$ satisfy $\iota_{0}(u^{\prime})=\textsc{future}$.
Then every arc on this path is an arc in $D(N,T)$ and so again, we have a path
from $\iota_{0}(u)=\iota(u)$ to $\iota_{0}(v)=\iota(v)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ by the fact that $\sigma$
is well-behaved.

  * •

$D(N_{0},T_{0})$ is a display graph:

    * –

$D(N_{0},T_{0})$ is acyclic:  Suppose for a contradiction that
$D(N_{0},T_{0})$ contains a directed cycle. If $\iota_{0}(u)\in P\cup S$ for
some vertex $u$ in this cycle, then as shown above the existence of a path
from $u$ to $u$ in $D(N_{0},T_{0})$ implies the existence of a path from
$\iota_{0}(u)$ to $\iota_{0}(u)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, contradicting the fact
that $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ is acyclic.

It remains to consider the case that every vertex $z$ in this cycle has
$\iota_{0}(z)=\textsc{future}$. But in this case every arc of the cycle is
also an arc in $D(N,T)$, and so $D(N,T)$ contains a cycle, a contradiction as
$D(N,T)$ is a display graph.

    * –

$T_{0}$ is an out-forest: We first observe that for every vertex $u$ in
$D(N_{0},T_{0})$, either all its incident arcs in $D(N_{0},T_{0})$ are also
arcs of $D(N,T)$, or they are all arcs of $D(N_{0}^{\prime},T_{0}^{\prime})$.
Indeed, suppose for a contradiction that this is not the case, then there
exist arcs $a\in A_{p}$, $a^{\prime}\in A_{z}$ that share a vertex $u$. But by
construction, $a\in A_{p}$ implies that $u\in V_{p}$ or
$\iota^{\prime}(u)=\textsc{past}$ and so $\iota_{0}(u)\in P$, while
$a^{\prime}\in A_{z}$ implies $\iota_{0}(u)\in S\cup\\{\textsc{future}\\}$, a
contradiction.

Now it remains to observe that every vertex in $T_{0}$ has in-degree at most
$1$, as either all its incident arcs are in $T$ or they are all in
$T_{0}^{\prime}$. This, together with the fact that $D(N_{0},T_{0})$ is
acyclic, implies that $T_{0}$ is an out-forest.

    * –

Every vertex in $D(N_{0},T_{0})$ has in- and out-degree at most $2$ and total
degree at most $3$: As argued above, every vertex in $D(N_{0},T_{0})$ has all
its incident arcs in $D(N,T)$ or in $D(N_{0}^{\prime},T_{0}^{\prime})$, and so
this property follows from the fact that it holds for $D(N,T)$ and
$D(N_{0}^{\prime},T_{0}^{\prime})$

    * –

Any vertex in $V(N_{0})\cap V(T_{0})$ has out-degree $0$ and in-degree at most
$1$ in each of $T_{0}$ and $N_{0}$: Again, this follows from the fact that all
incident arcs of a vertex in $D(N_{0},T_{0})$ belong to one of $D(N,T)$,
$D(N_{0}^{\prime},T_{0}^{\prime})$.

  * •

$\phi_{0}$ is an embedding function on $D(N_{0},T_{0})$:

    * –

For each $u\in V(T_{0})$, $\phi_{0}(u)\in V(N_{0})$ and, for each arc $uv\in
A(T_{0})$, $\phi_{0}(uv)$ is a directed $\phi_{0}(u)$-$\phi_{0}(v)$-path in
$N_{0}$: This follows immediately from the construction of $\phi_{0}$ and the
fact that $\phi$ and $\phi_{0}^{\prime}$ are embedding functions.

    * –

for any distinct $u,v\in V(T_{0})$, $\phi_{0}(u)\neq\phi_{0}(v)$: Note that if
a tree vertex $u$ is in $V_{p}$ then, by definition of past-redundant, so is
$\phi_{0}^{\prime}(u)$. Similarly if $u\in V_{z}$ then $\phi(u)\in V_{z}$. So
now for two vertices $u,v\in V(T_{0})$, if $u\in V_{p}$ and $v\in V_{z}$ then
$\phi_{0}(u)=\phi_{0}^{\prime}(u)\in V_{p}$ and $\phi_{0}(v)=\phi(v)\in
V_{z}$, and so $\phi_{0}(u)\neq\phi_{0}(v)$. Otherwise, $u,v$ are either both
in $D(N,T)$ or both in $D(N_{0}^{\prime},T_{0}^{\prime})$, and
$\phi_{0}(u)\neq\phi_{0}(v)$ follows from the fact that $\phi$ and
$\phi_{0}^{\prime}$ are embedding functions.

    * –

for any $u\in V(T_{0})\cap V(N_{0})$, $\phi_{0}(u)=u$: Follows immediately
from the construction of $\phi_{0}$.

    * –

the paths $\\{\phi_{0}(uv)\mid uv\in A(T_{0})\\}$ are arc-disjoint: Observe
that by construction that if a tree arc $uv$ is in $A_{p}$, then so is every
arc in $\phi_{0}(uv)=\phi_{0}^{\prime}(uv)$. Similarly if $uv$ is in $A_{z}$
then so is every arc in $\phi_{0}(uv)=\phi(uv)$. So consider two distinct tree
arcs $uv,u^{\prime}v^{\prime}\in A(T_{0})$. If $uv\in
A_{p},u^{\prime}v^{\prime}\in A_{z}$ then the arcs of the paths
$\phi_{0}(uv),\phi_{0}(u^{\prime}v^{\prime})$ are in $A_{p},A_{z}$
respectively, so $\phi_{0}(uv),\phi_{0}(u^{\prime}v^{\prime})$ are arc-
disjoint. Otherwise, we may assume both $uv$ and $u^{\prime}v^{\prime}$ are
arcs in one of $D(N,T),D(N_{0}^{\prime},T_{0}^{\prime})$, from which the claim
follows by the fact that $\phi$ and $\phi_{0}^{\prime}$ are embedding
functions.

    * –

for any distinct $p,q\in A(T_{0})$, $\phi_{0}(p)$ and $\phi_{0}(q)$ share a
vertex $z^{\prime}$ only if $p$ and $q$ share a vertex $w$ with
$z^{\prime}=\phi_{0}(w)$: Suppose $\phi_{0}(p)$ and $\phi_{0}(q)$ share a
vertex $z^{\prime}$. As argued previously, all incident arcs to $z^{\prime}$
must be in one of $D(N,T),D(N_{0}^{\prime},T_{0}^{\prime})$. Thus in
particular, $z^{\prime}$ cannot have incident arcs from both $A_{p}$ and
$A_{z}$. Then since $\phi_{0}(p)$ and $\phi_{0}(q)$ both contain arcs incident
to $z^{\prime}$, we must have that $p,q\notin A_{p}$ or $p,q\notin A_{z}$.
Then either $\phi_{0}(p)=\phi(p)$ and $\phi_{0}(q)=\phi(q)$, or
$\phi_{0}(p)=\phi_{0}^{\prime}(p)$ and $\phi_{0}^{\prime}(q)$. Then the claim
follows from the fact that $\phi$ and $\phi_{0}^{\prime}$ are embedding
functions.

  * •

$\iota_{0}$ is a $(P\cup S,\\{\textsc{future}\\})$-isolabelling:

    * –

For $u\in V(D(N_{0},T_{0}))$ with $\iota_{0}(u)\neq\textsc{future}$,
$\iota_{0}(u)\in V(N_{\textsc{in}})$ only if $u\in V(N_{0})$ and
$\iota_{0}(u)\in V(T_{\textsc{in}})$ only if $u\in V(T_{0})$ : Follows
immediately from the construction of $\iota_{0}$.

    * –

For $u,v\in V(D(N_{0},T_{0}))$ with
$\iota_{0}(u),\iota_{0}(v)\neq\textsc{future}$, $\iota_{0}(u)=\iota_{0}(v)$
only if $u=v$: Suppose $u\neq v$ and
$\iota_{0}(u),\iota_{0}(v)\neq\textsc{future}$; we will show
$\iota_{0}(u)\neq\iota_{0}(v)$. If $u\in V_{p}$ and $v\in V_{z}$, then by
construction $\iota_{0}(u)=\iota(u)\in\\{z,\textsc{future}\\}$ (and so in fact
$\iota_{0}(u)=z$) and $\iota_{0}(v)=\iota_{0}^{\prime}(v)\in P$. Thus
$\iota_{0}(u)\neq\iota_{0}(v)$. Otherwise, we may assume $u$ and $v$ are both
vertices in $D(N,T)$ or in $D(N_{0}^{\prime},T_{0}^{\prime})$. Then
$\iota_{0}(u)\neq\iota_{0}(v)$ follows from the fact that $\iota$ and
$\iota_{0}^{\prime}$ are isolabellings.

    * –

For $u,v\in V(D(N_{0},T_{0}))$ with
$\iota_{0}(u),\iota_{0}(v)\neq\textsc{future}$, the arc $uv$ is in
$D(N_{0},T_{0})$ if and only if $\iota_{0}(u)\iota_{0}(v)$ is in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ : Follows immediately from
the construction of $\iota_{0}$ and the fact that $\iota,\iota_{0}^{\prime}$
are isolabellings.

    * –

$\iota_{0}$ is surjective onto $P\cup S$: Consider any $w\in P\cup S$. If
$w\in P$, there is $u\in V(D(N_{0}^{\prime},T_{0}^{\prime}))$ with
$\iota_{0}^{\prime}(u)=w$. For such $u$ we have either $u\in V_{p}$ or
$\iota^{\prime}(u)=\textsc{past}$. In either case we have
$\iota_{0}(u)=\iota_{0}^{\prime}(u)=w$. Similarly if $w\in S$, there is $u\in
V(D(N,T))$ with $\iota(u)=w$ and either $\iota^{\prime}(u)=\iota(u)$ (if $w\in
S^{\prime}$) or $u\in V_{z}$ or $\iota^{\prime}(u)=\textsc{future}$ (if
$w=z$), and so $\iota_{0}(u)=\iota(u)=w$.

  * •

Each vertex $u$ with $\iota_{0}(u)\in P\cup S$ has the same in- and out-degree
in $D(N_{0},T_{0})$ as $\iota_{0}(u)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$: As previously shown, all
incident arcs of $u$ in $D(N_{0},T_{0})$ belong to at least one of
$D(N,T),D(N_{0}^{\prime},T_{0}^{\prime})$. Moreover if $\iota_{0}(u)=\iota(u)$
then all incident arcs are in $D(N,T)$ and if
$\iota_{0}(u)=\iota_{0}^{\prime}(u)$ then all incident arcs are in
$D(N_{0}^{\prime},T_{0}^{\prime})$. Then this property follows from the fact
that $\sigma$ and $\sigma_{0}^{\prime}$ are containment structures.

  * •

Each vertex $u$ of $T_{0}$ with $\iota_{0}(u)\neq\iota(\phi_{0}(u))$ has $2$
out-arcs in $D(N_{0},T_{0})$ : In the case that $\iota_{0}(u)\in P\cup S$,
this follows from previously-shown properties. We may assume $u$ is an
internal vertex of $T_{0}$ (as otherwise $u\in V(T_{0})\cap V(N_{0})$ and
$\phi_{0}(u)=u$). Then $\iota_{0}(u)$ is also an internal vertex of
$T_{\textsc{in}}$, and $u$ has the same in-and out-degree as $\iota_{0}(u)$.
Thus in particular $u$ has out-degree $2$, as $T_{0}$ is binary.

For the case that $\iota_{0}(u)=\textsc{future}$, by construction
$\iota_{0}(u)=\iota(u)$. Furthermore $\iota(\phi(u))\neq\textsc{future}$ (as
this would imply
$\iota_{0}(\phi_{0}(u))=\iota(\phi(u)=\textsc{future}=\iota_{0}(u)$, a
contradiction). Then as $\sigma$ is a
$(S,\\{\textsc{past},\textsc{future}\\})$-containment structure, $u$ has out-
degree $2$ in $D(N,T)$, and therefore in $D(N_{0},T_{0})$.

The above conditions show that $\psi$ is a $(P\cup
S,\\{\textsc{future}\\})$-containment structure, i.e. an $F$-partial solution.
Next we show that $\psi$ is well-behaved:

  * •

$D(N_{0},T_{0})$ contains no redundant arcs or vertices: Suppose for a
contradiction that $D(N_{0},T_{0})$ contains a future-redundant arc or vertex
$a$. We will show that such an arc or vertex is also redundant w.r.t $\sigma$,
a contradiction as $\sigma$ is well-behaved. Consider the case that $a$ is an
arc $uv$ Then $\iota_{0}(u)=\iota_{0}(v)=\textsc{future}$. It follows by
construction that $u,v$ are vertices of $D(N,T)$ and
$\iota(u)=\iota(v)=\textsc{future}$. In addition we have that
$\iota_{0}(u^{\prime})=\textsc{future}$ for any vertex $u^{\prime}$ on the
path $\phi_{0}(uv)=\phi(uv)$, and hence $\phi(u^{\prime})=\textsc{future}$ for
such $u^{\prime}$. It follows that $uv$ is future-redundant w.r.t $\sigma$,
the desired contradiction. Essentially the same arguments can also be made for
redundant network arcs and redundant tree or network vertices.

  * •

For any $y,y^{\prime}\in\\{\textsc{future}\\}$ with $y\neq y^{\prime}$, there
is no arc $uv$ in $D(N_{0},T_{0})$ for which $\iota_{0}(u)=y$ and
$\iota_{0}(v)=y^{\prime}$: This follows immediately from the fact that
$|\\{\textsc{future}\\}|=1$ so there are no such $y,y^{\prime}$.

  * •

For any $u,v,$ in $V(D(N_{0},T_{0}))$ with $\iota_{p}(v),\iota_{0}(v)\in P\cup
S$, if $D(N_{0},T_{0})$ has a path from $u$ to $v$ then
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ has a path from
$\iota_{0}(u)$ to $\iota_{0}(v)$: This has already been shown, at the start of
the proof for this claim. $\lrcorner$

We now have that $\psi$ satisfies all the conditions of a well-behaved
$F$-partial solution. Finally we need to show that $\sigma$ is the
$\\{P\to\textsc{past}\\}$-restriction of $D(N_{0},T_{0})$.

######  Claim 2.

$\sigma$ is the $\\{P\to\textsc{past}\\}$-restriction of $D(N_{0},T_{0})$

Proof: Let
$\sigma^{\prime\prime}=(D(N^{\prime\prime},T^{\prime\prime}),\phi^{\prime\prime},\iota^{\prime\prime})$
denote the $\\{P\to\textsc{past}\\}$-restriction of $\psi$. We show
$\sigma=\sigma^{\prime\prime}$ for their three elements individually.

Equality of $D(N^{\prime\prime},T^{\prime\prime})$ and $D(N,T)$: To show this,
it is enough to show that that $D(N^{\prime\prime},T^{\prime\prime})$ is
$D(N_{0},T_{0})$ with the arcs of $A_{p}$ and vertices of $V_{p}$ removed,
i.e. these arcs and vertices are exactly the ones that become redundant when
constructing the $\\{P\to\textsc{past}\\}$-restriction of $\psi$. Since these
were exactly the arcs and vertices that were added to $D(N,T)$ to produce
$D(N_{0},T_{0})$, this is enough to show that
$D(N^{\prime\prime},T^{\prime\prime})=D(N,T)$.

Let $g$ be the restriction function $\\{P\to\textsc{past}\\}$. We claim that
for the isolabelling $\iota_{u}\circ g$, the redundant arcs are exactly those
of $A_{p}$.

Indeed, consider any arc $uv$ in $A_{p}$. Since $uv\in A_{p}$, it must have
been made past-redundant in the construction of $\sigma^{\prime}$ from
$\psi^{\prime}$. So if $uv$ is a tree arc, then $\iota_{0}^{\prime}(z)\in P$
for all $z$ in $\\{u,v\\}\cup V(\phi_{0}^{\prime}(uv))$ (as all these vertices
are labelled past after applying $\\{P\to\textsc{past}\\}$). Then by
construction of $\psi$, we have $\phi_{0}(uv)=\phi_{0}^{\prime}(uv)$, and also
$\iota_{0}(z)=\iota_{0}^{\prime}(z)$ for all $z$ in $\\{u,v\\}\cup
V(\phi_{0}^{\prime}(uv))$ (since either $z\in V_{p}$ or
$\iota^{\prime}(z)=\textsc{past}$). Thus $\iota_{0}(z)\in P$ for all $z$ in
$\\{u,v\\}\cup V(\phi_{0}(uv))$, and so $uv$ becomes past-redundant after
applying $\\{P\to\textsc{past}\\}$. For a network arc $uv$ in $A_{p}$, a
similar argument holds, but we need to be careful if there is a tree arc
$u^{\prime}v^{\prime}$ for which $uv$ is in $\phi(u^{\prime}v^{\prime})$ (in
particular, we would have a problem if $u^{\prime}v^{\prime}$ is not an arc in
$D(N^{\prime},T^{\prime})$, as $u^{\prime}v^{\prime}$ could conceivably
prevent $uv$ from becoming past-redundant). For such an arc
$u^{\prime}v^{\prime}$, note that $u^{\prime}v^{\prime}$ must also be in
$A_{p}$ (otherwise $u^{\prime}v^{\prime}$ is an arc in
$D(N^{\prime},T^{\prime})$ but $\phi^{\prime}(uv)=\phi_{0}(uv)$ is not a path
in $D(N^{\prime},T^{\prime})$, a contradiction). It follows then that
$\iota_{0}^{\prime}(u^{\prime}),\iota_{0}(v^{\prime})\in P$. We also have that
$\iota_{0}^{\prime}(u),\iota_{0}(v)\in P$. So by a similar argument to tree
arcs, we have that $uv$ is redundant after applying $\\{P\to\textsc{past}\\}$
in $\psi$, as required.

Conversely consider any redundant arc $uv$ in $D(N_{0},T_{0})$ after applying
$\\{P\to\textsc{past}\\}$. As $\psi$ is well-behaved, we may assume any such
arc is past-redundant. Then $\iota_{0}(u),\iota_{0}(v)\in P$. This implies
among other things that $uv$ is not in $A_{z}$ (as that would require
$\iota_{0}(u),\iota_{0}(v)\in F\cup\\{\textsc{future}\\}$) so $uv$ is also an
arc in $D(N_{0}^{\prime},T_{0}^{\prime})$. Similarly if $uv$ is a tree arc
then all arcs in $\phi_{0}(uv)$ as also in $D(N_{0}^{\prime},T_{0}^{\prime})$,
and if $uv$ is a network arc that is part of a path
$\phi_{0}(u^{\prime}v^{\prime})$, then $u^{\prime}v^{\prime}$ is also an arc
in $D(N_{0},T_{0}^{\prime})$. Furthermore $\iota_{0}^{\prime}(z)=\iota_{0}(z)$
for any vertex in one of these arcs (as $\iota^{\prime}(z)\neq\textsc{future}$
and $\iota^{\prime}(z)\notin V_{z}$). It is then easy to see that, just as
$uv$ is redundant in $\psi$ after applying $\\{P\to\textsc{past}\\}$, $uv$ is
also redundant in $\psi^{\prime}$ after applying $\\{P\to\textsc{past}\\}$,
and so $uv$ is in $A_{p}$.

We have now shown that $A_{p}$ is exactly the set of arcs in $\psi$ that are
redundant after applying $\\{P\to\textsc{past}\\}$. We now consider the
vertices. First consider a vertex $v\in V_{p}$. Then as $V_{p}$ is in
$D(N_{0}^{\prime},T_{0}^{\prime})$ but not $D(N^{\prime},T^{\prime})$, all
incident arcs of $v$ are in $A_{p}$. Thus $v$ becomes isolated after removing
redundant arcs from $D(N,T)$. As $v\in V_{p}$, by construction
$\iota_{0}(v)=\iota_{0}^{\prime}(v)\in P$. Similarly this holds for any
$v^{\prime}$ such that $\phi_{0}^{\prime}(v^{\prime})=v$ or
$\phi_{0}^{\prime}(v)=v^{\prime}$. As such, $v$ is past-redundant after
applying $\\{P\to\textsc{past}\\}$, as required.

Conversely, suppose $v$ is past-redundant w.r.t.
$(D(N_{0},T_{0}),\phi_{0},\iota_{0}\circ\\{P\to\textsc{past}\\})$. Then $v$ is
isolated after removing $A_{p}$, and $\iota_{0}(v),\iota_{0}(v^{\prime})\in
P$, for $v^{\prime}$ any vertex such that $\phi_{0}(v)=v^{\prime}$ or
$\phi_{0}(v^{\prime})=v$. These vertices are also in
$D(N_{0}^{\prime},T_{0}^{\prime})$ (they cannot be in $V_{z}$ as that would
require them being labelled with something in $\\{z,\textsc{future}\\}$). Then
by construction
$\iota_{0}^{\prime}(v)=\iota_{0}(v),\iota_{0}^{\prime}(v^{\prime})=\iota_{0}(v^{\prime})$
are in $P$ as well, and as such $v$ is past-redundant w.r.t
$(D(N_{0}^{\prime},T_{0}^{\prime}),\phi_{0}^{\prime},\iota_{0}^{\prime}\circ
g)$, and so $v\in V_{p}$, as required.

Equality of $\phi^{\prime\prime}$ and $\phi$: Here we use the fact that
$D(N^{\prime\prime},T^{\prime\prime})=D(N,T)$. Consider any arc $uv$ in
$T^{\prime\prime}=T$. Then by construction,
$\phi^{\prime\prime}(uv)=\phi_{0}(uv)$, and furthermore
$\phi_{0}(uv)=\phi(uv)$ as $uv$ is an arc in $T$. Thus
$\phi^{\prime\prime}(uv)=\phi(uv)$ for all arcs $uv$ in $T^{\prime\prime}=T$,
and so $\phi^{\prime}=\phi$.

Equality of $\iota^{\prime\prime}$ and $\iota$: Consider any vertex $u$ in
$D(N^{\prime\prime},T^{\prime\prime})=D(N,T)$, and suppose first that
$\iota_{0}(u)=\iota(u)$. Then $\iota_{0}(u)\notin P$ (as $\iota(u)\in
S\cup\\{\textsc{past},\textsc{future}\\}$), from which it follows that
$\iota^{\prime\prime}(u)=\iota_{0}(u)=\iota(u)$. If on the other hand
$\iota_{0}(u)\neq\iota(u)$, by construction of $\iota_{0}$ this can only
happen if $\iota^{\prime}(u)=\textsc{past}$ (we do not need to consider the
case $u\in V_{p}$ as we know $u$ is a vertex of $D(N,T)$). In this case
$\iota_{0}(u)=\iota_{0}^{\prime}(u)$, which must be in $P$ (as otherwise
$\iota^{\prime}(u)=\iota_{0}^{\prime}(u)\neq\textsc{past}$.) Then by
construction $\iota^{\prime\prime}(u)=\textsc{past}$, and also
$\iota(u)=\iota^{\prime}(u)=\textsc{past}$. Thus
$\iota^{\prime\prime}(u)=\iota(u)$ for all vertices $u$ in $D(N,T)$.
$\lrcorner$

As we have now shown that $\psi$ is a well-behaved $F$-partial solution and
$\sigma$ is the $\\{P\to\textsc{past}\\}$-restriction of $\sigma$, we have
that $\sigma$ is valid, as required. ∎

###  3.7 Validity for Join bags

In order to characterize validity for Join bags, we need to introduce a third
type of $(S,\mathcal{Y})$-containment structure. In our notation we may think
of a Join bag as being expressed by the tuple $(P,S,F)$ where $P$ can be
decomposed into $L\cup R$, such that the “left” child bag is $(L,S,F\cup R)$
and the “right” child bag is $(R,S,F\cup L)$. We want to characterize the
validity of a signature $\sigma$ for a Join bag in terms of the validity of
signatures for each of the child bags. The main idea is to find two signatures
$\sigma_{L}$ and $\sigma_{R}$ (for different child bags) which are
‘compatible’, in the sense that the two witnesses for these signatures can be
combined, and such that the resulting partial solution is a witness for
$\sigma$. In order to facilitate this characterization, it will be useful to
define a “3-way” analogue of a signature, called a _reconciliation_ , in which
we use the labels $\\{\textsc{left},\textsc{right},\textsc{future}\\}$ instead
of $\\{\textsc{past},\textsc{future}\\}$. This is defined below.

######  Definition 10 (reconciliation).

Let $(L\cup R,S,F)$ be a Join bag in the tree decomposition of
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ with child bags $(L,S,F\cup
R)$ and $(R,S,F\cup L)$. Then, we call an
$(S,\\{\textsc{left},\textsc{right},\textsc{future}\\})$-containment structure
a _reconciliation_ for $(L\cup R,S,F)$. Such a reconciliation $\mu$ for
$(L\cup R,S,F)$ is called _valid_ if it is the
$(L\to\textsc{left},R\to\textsc{right})$-restriction of a well-behaved
$F$-partial solution (i.e. a $(L\cup R\cup
S,\\{\textsc{future}\\})$-containment structure).

######  Lemma 12.

Let $(L\cup R,S,F)$ be a Join bag with child bags $(L,S,F\cup R)$ and
$(R,S,F\cup L)$, and let $\sigma$ be a signature for $(L\cup R,S,F)$. Then,
$\sigma$ is valid if and only if there is a reconciliation $\mu$ for $(L\cup
R,S,F)$ and valid signatures $\sigma_{L}$ and $\sigma_{R}$ for $(L,S,F\cup R)$
and $(R,S,F\cup L)$, respectively, such that

  1. (a)

$\sigma$ is the
$(\\{\textsc{left},\textsc{right}\\}\to\textsc{past})$-restriction of $\mu$,

  2. (b)

$\sigma_{L}$ is the
$(\textsc{left}\to\textsc{past},\textsc{right}\to\textsc{future})$-restriction
of $\mu$, and

  3. (c)

$\sigma_{R}$ is the
$(\textsc{right}\to\textsc{past},\textsc{left}\to\textsc{future})$-restriction
of $\mu$.

To prove this lemma, we first show the following.

######  Lemma 13.

Any valid reconciliation is well-behaved.

###### Proof.

Let $\mu$ be a valid reconciliation for $(L\cup R,S,F)$, and let
$\psi=(D(N,T),\phi,\iota)$ be a well-behaved $F$-partial solution for which
$\mu$ is the $g$-restriction, where $g$ is the function
$\\{L\to\textsc{left},R\to\textsc{right}\\}$. We first show that there is no
arc $uv$ in $D(N,T)$ with $g(\iota(u))=y,g(\iota(v))=y^{\prime}$ for any
$y,y^{\prime}\in\\{\textsc{left},\textsc{right},\textsc{future}\\}$ with
$y\neq y^{\prime}$. Recall that by properties of a tree decomposition, there
are no arcs between $F$ and $L\cup R$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, nor between $L$ and $R$.
So now consider a vertex $u\in V(D(N,T))$; we will show that if
$g(\iota(u))\in\\{\textsc{left},\textsc{right}\\}$ then $u$ has no neighbour
$v$ with
$g(\iota(v))\in\\{\textsc{left},\textsc{right},\textsc{future}\\}\setminus\\{g(\iota(u))\\}$,
which is enough to show the claim. If $\iota(u)\in L$, then all neighbours of
$\iota(u)$ in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ are in $L\cup
S$. Furthermore as $\psi$ is a well-behaved $(L\cup R\cup
S,\\{\textsc{future}\\})$-containment structure, the degree of $u$ in $D(N,T)$
is equal to the degree of $\iota(u)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, and for each neighbour
$v^{\prime}$ of $\iota(u)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, there is a neighbour $v$
of $u$ in $D(N,T)$ with $\iota(v)=v^{\prime}$. It follows that $\iota(v)\in
L\cup S$ and thus $g(\iota(v))\in S\cup\\{\textsc{left}\\}$ for any neighbour
of $u$ in $D(N,T)$, while $g(\iota(u))=\textsc{left}$. A similar argument
shows that if $\iota(u)\in R$, then $g(\iota(v))\in S\cup\\{\textsc{right}\\}$
for any neighbour of $u$ in $D(N,T)$ and $g(\iota(u))=\textsc{right}$. Finally
if $\iota(u)\in S\cup\\{\textsc{future}\\}$, then
$g(\iota(u))=\iota(u)\notin\\{\textsc{left},\textsc{right}\\}$, and we are
done.

As no vertex labelled left or right by $\iota\circ g$ has a neighbour with a
different label from $\\{\textsc{left},\textsc{right},\textsc{future}\\}$,
there are in fact no arcs $uv$ in $D(N,T)$ with
$g(\iota(u))=y,g(\iota(v))=y^{\prime}$ for any
$y,y^{\prime}\in\\{\textsc{left},\textsc{right},\textsc{future}\\}$ with
$y\neq y^{\prime}$. We can therefore apply Lemma 6 to see that $\sigma$ is
well-behaved. ∎

We next motivate the definition of a reconciliation by showing that the
validty of a signature for $(L\cup R,S,F)$ can be characterized by the
validity of reconciliations for $(L\cup R,S,F)$.

######  Lemma 14.

Let $(L\cup R,S,F)$ be a Join bag with child bags $(L,S,F\cup R)$ and
$(R,S,F\cup L)$, and let $\sigma$ be a signature for $(L\cup R,S,F)$. Then
$\sigma$ is valid if and only if there is a valid reconciliation $\mu$ for
$(L\cup R,S,F)$ such that $\sigma$ is the
$\\{\\{\textsc{left},\textsc{right}\\}\to\textsc{past}\\}$-restriction of
$\mu$.

###### Proof.

Suppose first that $\sigma$ is valid. Then there is a well-behaved $(L\cup
R\cup S,\\{\textsc{future}\\})$-containment structure $\psi$ (an $F$-partial
solution) such that $\sigma$ is the $\\{L\cup
R\to\textsc{past}\\}$-restriction of $\psi$. Now let $\mu$ be the
$\\{L\to\textsc{left},R\to\textsc{right}\\}$-restriction of $\psi$. By Lemma
3, $\mu$ is an
$(S,\\{\textsc{left},\textsc{right},\textsc{future}\\})$-containment
structure, and by construction $\mu$ is valid. Now let $\sigma^{\prime}$ be
the $\\{\\{\textsc{left},\textsc{right}\\}\to\textsc{past}\\}$-restriction of
$\mu$. Then transitivity implies that $\sigma^{\prime}$ is also the $\\{L\cup
R\to\textsc{past}\\}$-restriction of $\psi$, that is $\sigma^{\prime}=\sigma$.
Thus $\sigma$ is the
$\\{\\{\textsc{left},\textsc{right}\\}\to\textsc{past}\\}$-restriction of
$\mu$, as required.

Conversely, suppose there is a reconciliation $\mu$ for $(L\cup R,S,F)$ such
that $\sigma$ is the
$\\{\\{\textsc{left},\textsc{right}\\}\to\textsc{past}\\}$-restriction of
$\mu$. Then as $\mu$ is valid, there is a well-behaved $F$-partial solution
$\psi$ such that $\mu$ is the
$\\{L\to\textsc{left},R\to\textsc{right}\\}$-restriction of $\psi$. Then again
by transitivity, $\sigma$ is also the $\\{L\cup
R\to\textsc{past}\\}$-restriction of $\psi$. Thus $\sigma$ is valid. ∎

Now we show how the validity of a reconciliation $\mu$ for $(L\cup R,S,F)$ can
be characterized by the validity of signatures for the child bags.

######  Lemma 15.

Let $(L\cup R,S,F)$ be a Join bag with child bags $(L,S,F\cup R)$ and
$(R,S,F\cup L)$, and let $\mu$ be a well-behaved reconciliation for $(L\cup
R,S,F)$. Let $\sigma_{L}$ be the
$\\{\textsc{left}\to\textsc{past},\textsc{right}\to\textsc{future}\\}$-restriction
of $\mu$, and $\sigma_{R}$ the
$\\{\textsc{right}\to\textsc{past},\textsc{left}\to\textsc{future}\\}$-restriction
of $\mu$. If $\mu$ is valid, then $\sigma_{L}$ is a valid signature for
$(L,S,F\cup R)$ and $\sigma_{R}$ is a valid signature for $(R,S,F\cup L)$.

###### Proof.

Suppose that $\mu$ is valid. Then there is a well-behaved $F$-partial solution
$\psi$ such that $\mu$ is the
$\\{L\to\textsc{left},R\to\textsc{right}\\}$-restriction of $\mu$. By
construction and Lemma 3, $\sigma_{L}$ is an
$(S,\\{\textsc{past},\textsc{future}\\})$-containment structure, and thus a
signature for $(L,S,F\cup R)$. By transitivity, $\sigma_{L}$ is the
$\\{L\to\textsc{past},R\to\textsc{future}\\}$-restriction of $\psi$. We will
show that $\sigma_{L}$ is a valid signature for $(L,S,F\cup R)$.

Let $\psi_{L}$ be the $\\{R\to\textsc{future}\\}$-restriction of $\psi$. By
construction, $\psi_{L}$ is an $F\cup R$-partial solution and by Lemma 6
$\psi_{L}$ is well-behaved. Moreover by transitivity, the
$\\{L\to\textsc{past}\\}$-restriction of $\psi_{L}$ is also the
$\\{L\to\textsc{past},R\to\textsc{future}\\}$-restriction of $\psi$. That is,
the $\\{L\to\textsc{past}\\}$-restriction of $\psi_{L}$ is $\sigma_{L}$, and
so $\sigma_{L}$ is valid for $(L,S,F\cup R)$. (See Fig. 7.)

Figure 7: Illustration of proof for reconciliations on Join bags, validity of
$\mu$ implies validty of $\sigma_{L}$ and $\sigma_{R}$. Solid lines are
restriction relations that we may assume; the dashed lines shows the
construction of $\psi_{L}$ and $\psi_{R}$ from $\psi$; dotted lines are
relations we can infer using (multiple uses of) transitivity.

A similar argument shows that $\sigma_{R}$ is a valid signature for
$(R,S,F\cup R)$. ∎

######  Lemma 16.

Let $(L\cup R,S,F)$ be a Join bag with child bags $(L,S,F\cup R)$ and
$(R,S,F\cup L)$, and let $\mu$ be a well-behaved reconciliation for $(L\cup
R,S,F)$. Let $\sigma_{L}$ be the
$\\{\textsc{left}\to\textsc{past},\textsc{right}\to\textsc{future}\\}$-restriction
of $\mu$, and $\sigma_{R}$ the
$\\{\textsc{right}\to\textsc{past},\textsc{left}\to\textsc{future}\\}$-restriction
of $\mu$. If $\sigma_{L}$ is a valid signature for $(L,S,F\cup R)$ and
$\sigma_{R}$ is a valid signature for $(R,S,F\cup L)$, then $\mu$ is valid.

###### Proof.

Let $\psi_{L}$ be a well-behaved $F\cup R$-partial solution for which
$\sigma_{L}$ is the $(L\to\textsc{past})$-restriction, and similarly let
$\psi_{R}$ be a well-behaved $F\cup L$-partial solution for which $\sigma_{R}$
is the $(R\to\textsc{past})$-restriction. Our strategy is to combine
$\psi_{L}$ and $\psi_{R}$ into an $F$-partial solution $\psi$, and then show
that $\mu$ is the $(L\to\textsc{left},R\to\textsc{right})$-restriction of this
$\psi$.

In what follows, for a given containment structure $\sigma$, we will write the
display graph, embedding function and isolabelling of $\sigma$ as
$D(N_{\sigma},T_{\sigma}),\phi_{\sigma}$ and $\iota_{\sigma}$. Thus we have
$\mu=(D(N_{\mu},T_{\mu}),\phi_{\mu},\iota_{\mu})$,
$\sigma_{L}=(D(N_{\sigma_{L}},T_{\sigma_{L}}),\phi_{\sigma_{L}},\iota_{\sigma_{L}})$,
etc. Recall that by construction, $D(N_{\sigma_{L}},T_{\sigma_{L}})$ is a
subgraph of both $D(N_{\mu},T_{\mu})$ and $D(N_{\psi_{L}},T_{\psi_{L}})$.
Similarly, $D(N_{\sigma_{R}},T_{\sigma_{R}})$ is a subgraph of both
$D(N_{\mu},T_{\mu})$ and $D(N_{\psi_{R}},T_{\psi_{R}})$.

Now let $A_{L}$ be the set of arcs, and $V_{L}$ the set of vertices, that
become redundant and are therefore deleted from $D(N_{\psi_{L}},T_{\psi_{L}})$
when deriving the $\\{L\to\textsc{past}\\}$-restriction $\sigma_{L}$ from
$\psi_{L}$. That is, $A_{L}=A(D(N_{\psi_{L}},T_{\psi_{L}}))\setminus
A(D(N_{\sigma_{L}},T_{\sigma_{L}}))$ and
$V_{L}=V(D(N_{\psi_{L}},T_{\psi_{L}}))\setminus
V(D(N_{\sigma_{L}},T_{\sigma_{L}}))$. We note that by construction,
$\iota_{\psi_{L}}(v)\in L$ for any $v\in V_{L}\cup V(A_{L})$. Similarly, let
$A_{R},V_{R}$ be the sets of arcs and vertices that are deleted from
$D(N_{\psi_{R}},T_{\psi_{R}})$ in the construction of $\sigma_{R}$ from
$\psi_{R}$. Let $A_{R}^{\prime},V_{R}^{\prime}$ be the set of vertices that
are deleted from $D(N_{\mu},T_{\mu})$ in the construction of $\sigma_{L}$ from
$\mu$, and let $A_{L}^{\prime},V_{L}^{\prime}$ be the set of vertices that are
deleted from $D(N_{\mu},T_{\mu})$ in the construction of $\sigma_{R}$ from
$\mu$. (See Fig. 8.)

Finally let $A_{S}$ be the arcs of $D(N_{\mu},T_{\mu})$ that are not in
$A_{L}^{\prime}\cup A_{R}^{\prime}$, and $V_{S}$ the vertices of
$D(N_{\mu},T_{\mu})$ not in $V_{L}^{\prime}\cup V_{R}^{\prime}$. Note that the
arcs and vertices of $V_{S},A_{S}$ appear in all of $D(N_{\mu},T_{\mu})$,
$D(N_{\sigma_{L}},T_{\sigma_{L}})$, $D(N_{\sigma_{R}},T_{\sigma_{R}})$,
$D(N_{\psi_{L}},T_{\psi_{L}})$, $D(N_{\psi_{R}},T_{\psi_{R}})$.

Observe that if $v\in V_{R}^{\prime}\cup V(A_{R}^{\prime})$ then
$\iota_{\mu}(v)\in\\{\textsc{right},\textsc{future}\\}$. Indeed, when deriving
$\sigma_{L}$ the
$\\{\textsc{left}\to\textsc{past},\textsc{right}\to\textsc{future}\\}$-restriction
of $\mu$, no arcs or vertices will become past-redundant, since they would
previously have been left-redundant in $\mu$ (here we use the fact that
$\iota_{\mu}$ did not already label any vertices past, unlike future.) So the
only vertices and arcs that are removed are ones that become future-redundant,
i.e. previously had their vertices labelled right or future. By a similar
argument, if $v\in V_{L}^{\prime}\cup V(A_{L}^{\prime})$ then
$\iota_{\mu}(v)\in\\{\textsc{left},\textsc{future}\\}$. Furthermore, we can
show that $A_{L}^{\prime}\cap A_{R}^{\prime}=\varnothing$ and
$V_{L}^{\prime}\cap V_{R}^{\prime}=\varnothing$. Indeed, recall that for any
arc $a$ in $D(N_{\mu},T_{\mu})$, there is a set of vertices $Q_{a}$ such that
$a$ is $y$-redundant w.r.t $(D(N_{\mu},T_{\mu}),\phi_{\mu},\iota^{\prime})$ if
and only if $\iota(Q_{a})=\\{y\\}$, for any isolabelling $\iota$. Note that we
cannot have $\iota_{\mu}(Q_{a})=\\{\textsc{future}\\}$, as this implies that
$a$ is redundant w.r.t $\mu$, a contradiction as $\mu$ is well-behaved. So if
$a$ is future-redundant after applying
$\\{L\to\textsc{past},R\to\textsc{future}\\}$ (i.e. if $a\in A_{R}^{\prime}$)
then there is at least one $z\in Q_{a}$ with $\iota_{\mu}(z)\in R$. But then
this implies that $a$ is not future-redundant after applying
$\\{R\to\textsc{past},L\to\textsc{future}\\}$, so $a$ is not in
$A_{L}^{\prime}$. A similar argument shows that $V_{L}^{\prime}$ and
$V_{R}^{\prime}$ are disjoint.

Figure 8: Illustration of proof for reconciliations on Join bags, validity of
$\sigma_{L}$ and $\sigma_{R}$ implies validty of $\mu$. Solid lines are
restriction relations that we may assume; the dashed lines show the
construction of $\psi$ from $\psi_{L}$ or $\psi_{R}$ (we do not describe the
construction of $\phi_{0}$ or $\iota_{0}$ in the figure, only the construction
of $D(N_{0},T_{0})$ by adding arcs and vertices); the dotted line shows the
relation we want to prove, that $\mu$ is the
$\\{L\to\textsc{left},R\to\textsc{right}\\}$-restriction of $\psi$.

We now describe the construction of an $F$-partial solution
$\psi=(D(N,T),\phi,\iota)$.

Let $D(N,T)$ be the display graph with vertex set $V_{S}\cup
V_{L}^{\prime}\cup V_{R}^{\prime}\cup V_{L}\cup V_{R}$ and arc set $A_{S}\cup
A_{L}^{\prime}\cup A_{R}^{\prime}\cup A_{L}\cup A_{R}$. (We keep the partition
of these sets into network side and tree side the same as before.) That is,
$D(N,T)$ is $D(N_{\psi_{L}},T_{\psi_{L}})$ with the arcs of $A_{R}\cup
A_{R}^{\prime}$ and vertices of $V_{R}\cup V_{R}^{\prime}$ added; equivalently
we may say $D(N,V)$ is $D(N_{\psi_{R}},T_{\psi_{R}})$ with the arcs of
$A_{L}\cup A_{L}^{\prime}$ and vertices of $V_{L}\cup V_{L}^{\prime}$ added,
or that it is $D(N_{\mu},T_{\mu})$ with the arcs of $A_{L}\cup A_{R}$ and
vertices of $V_{L}\cup V_{R}$ added.

Let the embedding function $\phi$ be defined as follows. For a tree vertex $u$
in $T$, if $u\in V_{L}$ then let $\phi(u)=\phi_{\psi_{L}}(u)$, and similarly
if $u\in V_{R}$ then let $\phi(u)=\phi_{\psi_{R}}(u)$. If $u\in
V_{L}^{\prime}$, let
$\phi(u)=\phi_{\mu}(u)=\phi_{\sigma_{L}}(u)=\phi_{\psi_{L}}(u)$ (note that $u$
is a vertex in $D(N_{\sigma_{L}},T_{\sigma_{L}})$ as $v\notin V_{R}^{\prime}$,
and so these terms are all well-defined and equal by construction). Similarly
if $u\in V_{R}^{\prime}$, let
$\phi(u)=\phi_{\mu}(u)=\phi_{\sigma_{R}}(u)=\phi_{\psi_{R}}(u)$. Finally if
$u\in V_{S}^{\prime}$, let
$\phi(u)=\phi_{\mu}(u)=\phi_{\sigma_{L}}(u)=\phi_{\sigma_{R}}(u)=\phi_{\psi_{L}}(u)=\phi_{\psi_{R}}(u)$.

For a tree arc $uv$ in $A_{L}$, let $\phi(uv)=\phi_{\psi_{L}}(uv)$, and
similarly for $uv\in A_{R}$ let $\phi(uv)=\phi_{\psi_{R}}(uv)$. For $uv\in
A_{L}^{\prime}$, let
$\phi(uv)=\phi_{\mu}(uv)=\phi_{\sigma_{L}}(uv)=\phi_{\psi_{L}}(uv)$ (note that
$uv$ is an arc in $D(N_{\sigma_{L}},T_{\sigma_{L}})$ as $uv\notin
A_{R}^{\prime}$). Similarly for $uv\in A_{R}^{\prime}$, let
$\phi(uv)=\phi_{\mu}(uv)=\phi_{\sigma_{R}}(uv)=\phi_{\psi_{R}}(uv)$. Finally
for $uv\in A_{S}$, let
$\phi(uv)=\phi_{\mu}(uv)=\phi_{\sigma_{L}}(uv)=\phi_{\sigma_{R}}(uv)=\phi_{\psi_{L}}(uv)=\phi_{\psi_{R}}(uv)$.

Let the $(L\cup R\cup S,\\{\textsc{future}\\})$-isolabelling $\iota$ be
defined as follows. For a vertex $v\in V_{L}$, let
$\iota(v)=\iota_{\psi_{L}}(v)$. Similarly if $v\in V_{R}$, let
$\iota(v)=\iota_{\psi_{R}}(v)$. Otherwise, $v$ is a vertex of
$D(N_{\mu},T_{\mu})$. If $\iota_{\mu}(v)=\textsc{left}$ then let
$\iota(v)=\iota_{\psi_{L}}(v)$ (recalling that $v\notin V_{R}^{\prime}$, so
$v$ is a vertex of $D(N_{\sigma_{L}},T_{\sigma_{L}})$ and thus of
$D(N_{\psi_{L}},T_{\psi_{L}})$, with $\iota_{\sigma_{L}}(v)=\textsc{past}$ and
$\iota_{\psi_{L}}(v)\in L$). Similarly if $\iota_{\mu}(v)=\textsc{right}$ then
let $\iota(v)=\iota_{\psi_{R}}(v)$. Finally if $\iota_{\mu}(v)\in
S\cup\\{\textsc{future}\\}$, then set $\iota(v)=\iota_{\mu}(v)$.

We will now show that $\psi$ is indeed a well-behaved $F$-partial solution;
afterwards we will show that $\mu$ is the
$\\{L\to\textsc{left},R\to\textsc{right}\\}$-restriction of $\psi$, from which
it follows that $\mu$ is valid. (A similar argument can be used to show that
$\psi_{L}$ is the $\\{R\to\textsc{future}\\}$-restriction of $\psi$ and
$\psi_{R}$ is the $\\{L\to\textsc{future}\\}$-restriction of $\psi$, but we
will not need these fact so we do not prove them here.)

######  Claim 3.

$\psi$ is a well-behaved $F$-partial solution.

Proof: We first show that $\psi$ satisfies one of the properties of well-
behaved $(L\cup R\cup S,\\{\textsc{future}\\})$-containment structure.

  * •

For any $u,v\in V(D(N,T))$ with $\iota(u),\iota(v)\in L\cup R\cup S$, if
$D(N,T)$ has a path from $u$ to $v$ then there is a path from $\iota(u)$ to
$\iota(v)$ in $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$: To see this
property, first consider the case that $uv$ is an arc in $D(N,T)$. In this
case it is sufficient to show that $\iota(u)=\iota_{\theta}(u)$ and
$\iota(v)=\iota_{\theta}(v)$ for some $\theta\in\\{\mu,\psi_{L},\psi_{R}\\}$,
as the property then follows from the fact that $\mu,\psi_{L},\psi_{R}$ are
all well-behaved.

If $uv\in A_{L}$ then $u\in V(D(N_{\psi_{L}},T_{\psi_{L}}))$ and either $u\in
V_{L}$ or $\iota_{\sigma_{L}}(u)=\textsc{past}$ and
$\iota_{\mu}(u)=\textsc{left}$; in either case $\iota(u)=\iota_{\psi_{L}}(u)$,
and similarly $\iota(v)=\iota_{\psi_{L}}(v)$, so we let $\theta=\psi_{L}$.
Similarly if $uv\in A_{R}$ then $\theta=\psi_{R}$. For any arc $uv$ in
$D(N_{\mu},T_{\mu})$, we can let $\theta=\psi_{L}$ if
$\iota_{\mu}(u)=\iota_{\mu}(v)=\textsc{left}$, $\psi_{R}$ if
$\iota_{\mu}(u)=\iota_{\mu}(v)=\textsc{right}$, and $\mu$ if
$\iota_{\mu}(u),\iota_{\mu}(v)\in P$. If $\iota_{\mu}(u)=\textsc{future}$
(resp. $\iota_{\mu}(v)$ = future) then $\iota(u)=\textsc{future}$
($\iota(v)=\textsc{future}$), so we do not need to consider this case. We also
cannot have
$\\{\iota_{\mu}(u),\iota_{\mu}(v)\\}=\\{\textsc{left},\textsc{right}\\}$ as
$\mu$ is well-behaved. It remains to consider the case that one of
$\iota_{\mu}(u),\iota_{\mu}(v)$ is left or right and the other is in $S$;
suppose w.l.o.g. that $\iota_{\mu}(u)=\textsc{left}$ and $\iota_{\mu}(v)\in
S$. In this case both $u$ and $v$ are vertices of
$D(N_{\sigma_{L}},T_{\sigma_{L}})$ and therefore
$D(N_{\psi_{L}},T_{\psi_{L}})$; moreover $\iota(u)=\iota_{\psi_{L}}(u)$ and
$\iota_{\psi_{L}}(v)=\iota_{\sigma_{L}}(v)=\iota_{\mu}(v)=\iota(v)$. Thus we
can let $\theta=\sigma_{L}$.

Now suppose for a contradiction that there exist $u,v\in V(D(N,T))$ with
$\iota(u),\iota(v)\in L\cup R\cup S$ such that there is a path from $u$ to $v$
in $D(N,T)$, but no path from $\iota(u)$ to $\iota(v)$ exists in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$. By the above discussion
$uv$ cannot be an arc. Moreover every internal vertex $z$ on the shortest
$u-v$ path must have $\iota(z)=\textsc{future}$ (otherwise $\iota(z)\ \in
L\cup R\cup S$ and $u,z$ forms a shorter path). Note that any such $z$ is also
a vertex in $D(N_{\mu},T_{\mu})$ with $\iota_{\mu}(z)=\textsc{future}$ (no
other possibility leads to $\iota(z)=\textsc{future}$; in particular if
$\iota_{\mu}(z)=\textsc{left}$ then $\iota(z)=\iota_{\psi_{L}}(z)\in L$). Any
arc incident to $z$ in $D(N,T)$ is also an arc in $D(N_{\mu},T_{\mu})$ (such
arcs cannot be in $A_{L}$ or $A_{R}$). So it follows that the path from $u$ to
$v$ also exists in $D(N_{\mu},T_{\mu})$. Finally, we must have
$\iota_{\mu}(u),\iota_{\mu}(v)\in S$ (they cannot be in
$\\{\textsc{left},\textsc{right}\\}$ as $u,v$ have neighbours labelled future
by $\iota_{\mu}$ and $\mu$ is well-behaved). So it then follows that there is
a path from $\iota(u)=\iota_{\mu}(u)$ to $\iota(v)=\iota_{\mu}(v)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, as $\mu$ is well-behaved.

  * •

$D(N,T)$ is a display graph:

    * –

$D(N,T)$ is acyclic:  Suppose for a contradiction that $D(N,T)$ contains a
cycle. If $\iota(u)\in L\cup R\cup S$ for some vertex $u$ in this cycle, then
as shown above the existence of a path from $u$ to $u$ in $D(N,T)$ implies the
existence of a path from $\iota(u)$ to $\iota(u)$ in
$D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$, contradicting the fact
that $D_{\textsc{in}}(N_{\textsc{in}},T_{\textsc{in}})$ is acyclic.

It remains to consider the case that every vertex $z$ in this cycle has
$\iota(z)=\textsc{future}$. However as argued previously, any $z$ with
$\iota(z)=\textsc{future}$ is also a vertex in $D(N_{\mu},T_{\mu})$, and all
its incident arcs in $D(N,T)$ are also arcs of $D(N_{\mu},T_{\mu})$. Then we
have that $D(N_{\mu},T_{\mu})$ contains a cycle, a contradiction as
$D(N_{\mu},T_{\mu})$ is a display graph.

    * –

$T$ is an out-forest: As $D(N,T)$ is acyclic, it is remains to show that every
vertex of $T$ has in-degree at most $1$ in $T$. To do this, we will show
something stronger: that for any vertex $v$ in $D(N,T)$, all of its incident
arcs in $D(N,T)$ are arcs in $D(N_{\theta},T_{\theta})$, for some
$\theta\in\\{\mu,\psi_{L},\psi_{R}\\}$. Then the desired property immediately
follows, as every tree vertex has at most one incoming tree-arc in
$D(N_{\theta},T_{\theta})$.

So consider any vertex $v\in D(N,T)$. If $v\in V_{L}$, then the only incident
arcs of $v$ are in $A_{L}$, and therefore all these arcs in
$D(N_{\psi_{L}},T_{\psi_{L}})$. Similarly if $v\in V_{R}$ then all incident
arcs are in $D(N_{\psi_{R}},T_{\psi_{R}})$. So now we may assume $v$ is a
vertex of $D(N_{\mu},T_{\mu})$. If $\iota_{\mu}(v)=\textsc{left}$ then $v$ can
have no incident arcs in $A_{R}^{\prime}$ or $A_{R}$ (as any vertex incident
to such an arc must be in $V_{R}$ or else have
$\iota_{\sigma_{R}}(u)=\textsc{past}$ and so $\iota_{\mu}(v)=\textsc{right}$).
Then all incident arcs of $uv$ in $D(N,T)$ are also in
$D(N_{\psi_{L}},T_{\psi_{L}})$. Similarly if $\iota_{\mu}(v)=\textsc{left}$
then all incident arcs are in $D(N_{\psi_{R}},T_{\psi_{R}})$. Finally if
$\iota_{\mu}(v)\in S\cup\\{\textsc{future}\\}$, then again none of its
incident arcs are in $A_{L}$ or $A_{R}$ (as this would require
$\iota_{\sigma_{L}}(v)=\textsc{past}$ or $\iota_{\sigma_{R}}(v)=\textsc{past}$
and so $\iota_{\mu}(v)\in\\{\textsc{left},\textsc{right}\\}$), and so so all
incident arcs are in $D(N_{\mu},T_{\mu})$.

    * –

Every vertex in $D(N,T)$ has in- and out-degree at most $2$ and total degree
at most $3$: This follows immediately from the previously-shown property that
every vertex in $D(N,T)$ has all its incident arcs in one of
$D(N_{\mu},T_{\mu}),D(N_{\psi_{L}},T_{\psi_{L}}),D(N_{\psi_{R}},T_{\psi_{R}})$,
and the fact that this constraint holds for each of these graphs.

    * –

Any vertex in $V(N)\cap V(T)$ has out-degree $0$ and in-degree at most $1$ in
each of $T_{0}$ and $N_{0}$: Again this follows from the fact that every
vertex in $D(N,T)$ has all its incident arcs in one of
$D(N_{\mu},T_{\mu}),D(N_{\psi_{L}},T_{\psi_{L}}),D(N_{\psi_{R}},T_{\psi_{R}})$.

  * •

$\phi$ is an embedding function on $D(N,T)$:

    * –

For each $u\in V(T)$, $\phi(u)\in V(N)$ and, for each arc $uv\in A(T)$,
$\phi(uv)$ is a directed $\phi(u)$-$\phi(v)$-path in $N$:

The fact that $\phi(u)\in V(N)$ follows immediately from the fact that
$\phi(u)=\phi_{\theta}(u)$ for some $\theta\in\\{\mu,\psi_{L},\psi_{R}\\}$,
and so $\phi(u)$ is a network vertex.

To see that $\phi(uv)$ is a path from $\phi(u)$ to $\phi(v)$, we will show
that there is $\theta\in\\{\mu,\psi_{L},\psi_{R}\\}$ such that
$\phi(uv)=\phi_{\theta}(uv)$, $\phi(u)=\phi_{\theta}(u)$ and
$\phi(v)=\phi_{\theta}(v)$. The result then follows from the fact that
$\phi_{\theta}$ is an embedding function.

If $uv\in A_{L}$, then neither $u$ nor $v$ can be in $V_{R}$, nor can they be
in $V_{R}^{\prime}$ (note that $u\in V_{R}^{\prime}$ requires
$\iota_{\mu}(u)\in\\{\textsc{right},\textsc{future}\\}$, but $uv\in A_{L}$
implies either $u\in V_{L}$ or $\iota_{\sigma_{L}}(u)=\textsc{past}$ and thus
$\iota_{\mu}(u)=\textsc{left}$). It follows by construction of $\phi$ that
$\phi(u)=\phi_{\psi_{L}}(u)$, $\phi(v)=\phi_{\psi_{L}}(u)$, and
$\phi(uv)=\phi_{\psi_{L}}(uv)$, so we can let $\theta=\psi_{L}$. Similarly if
$uv\in A_{R}$ we can let $\theta=\psi_{R}$. For $uv\in A_{L}^{\prime}\cup
A_{R}^{\prime}\cup A_{S}$, we have that $u,v$ are vertices in
$D(N_{\mu},T_{\mu})$, and therefore not in $V_{L}$ or $V_{R}$. It follows by
construction that $\phi(u)=\phi_{\mu}(u)$, $\phi(v)=\phi_{\mu}(u)$, and
$\phi(uv)=\phi_{\mu}(uv)$, so we let $\theta=\mu$.

    * –

for any distinct $u,v\in V(T)$, $\phi(u)\neq\phi(v)$: We first show that for
any $u\in V(T)$, $u\in V_{L}$ if and only if $\phi(u)\in V_{L}$. Recall that
$V_{L}$ is the set of vertices in $D(N_{\psi_{L}},T_{\psi_{L}})$ that become
past-redundant after applying $\\{L\to\textsc{past}\\}$, and observe that by
the definition of $y$-redundancy, a tree vertex $u$ is $y$-redundant with
respect to some containment structure
$(D(N^{\prime},T^{\prime}),\phi^{\prime},\iota^{\prime})$ if and only if
$\phi^{\prime}(u)$ is $y$-redundant. Thus $u\in V_{L}$ if and only if
$\phi(u)\in V_{L}$. By a similar argument, $u\in V_{R}$ if and only if
$\phi(u)\in V_{R}$.

Now suppose for a contradiction that there exist distinct $u,v\in V(T)$ with
$\phi(u)=\phi(v)$. If $\phi(u)=\phi(v)\in V_{L}$, then also $u,v\in V_{L}$.
Thus $u,v$ are distinct vertices in $D(N_{\psi_{L}},T_{\psi_{L}})$ with
$\phi_{\psi_{L}}(u)=\phi(u)=\phi(v)=\phi_{\psi_{R}}(v)$, a contradiction as
$\phi_{\psi_{L}}$ is an embedding function. We get a similar contradiction if
$\phi(u)\in V_{R}$. Finally if $\phi(u)\notin V_{L}\cup V_{R}$, then also
$u,v\notin V_{L}\cup V_{R}$. Thus $u,v$ are distinct vertices in
$D(N_{\mu},T_{\mu})$ with $\phi_{\mu}(u)=\phi(u)=\phi(v)=\phi_{\mu}(v)$, again
a contradiction as $\phi_{\mu}$ is an embedding function.

    * –

for any $u\in V(T)\cap V(N)$, $\phi(u)=u$: This follows immediately from the