# Recognizing $k$-leaf powers in polynomial time, for constant $k$

Manuel Lafond111Université de Sherbrooke

###### Abstract

A graph $G$ is a $k$-leaf power if there exists a tree $T$ whose leaf set is
$V(G)$, and such that $uv\in E(G)$ if and only if the distance between $u$ and
$v$ in $T$ is at most $k$. The graph classes of $k$-leaf powers have several
applications in computational biology, but recognizing them has remained a
challenging algorithmic problem for the past two decades. The best known
result is that $6$-leaf powers can be recognized in polynomial time. In this
paper, we present an algorithm that decides whether a graph $G$ is a $k$-leaf
power in time $O(n^{f(k)})$ for some function $f$ that depends only on $k$
(but has the growth rate of a power tower function).

Our techniques are based on the fact that either a $k$-leaf power has a
corresponding tree of low maximum degree, in which case finding it is easy, or
every corresponding tree has large maximum degree. In the latter case, large
degree vertices in the tree imply that $G$ has redundant substructures which
can be pruned from the graph. In addition to solving a longstanding open
problem, we hope that the structural results presented in this work can lead
to further results on $k$-leaf powers.

##  1 Introduction

In computational biology, it is commonplace to use dissimilarity information
between species to reconstruct a phylogenetic tree, in which the leaves are
the species and the internal nodes represent common ancestors. Sequence
distances can be used for this task, but are known to be unreliable [17, 24].
In 2002, Nishimura et al. [23] proposed that each pair of species should
simply be considered as either _close_ or _far_. There should then be a
threshold $k$ such that in the phylogeny, close species are at distance at
most $k$ and far species at distance more than $k$. The $k$-leaf power problem
arises when we model species as the vertices of a graph $G$ in which edges
represent closeness.

More specifically, we say that a graph $G$ is a _$k$ -leaf power_ if there
exists a tree $T$ such that the set of leaves of $T$ is $V(G)$, and such that
$uv\in E(G)$ if and only if $dist_{T}(u,v)\leq k$, where $dist_{T}(u,v)$ is
the distance between $u$ and $v$ in $T$ and $u,v$ are distinct. The tree $T$
is called a _$k$ -leaf root_ of $G$. The $G$ graph is a _leaf power_ if it is
a $k$-leaf power for some $k$.

Since their introduction, these graph classes have attracted the attention of
both algorithm designers and graph theoreticians. Two important problems have
remained open for the last two decades. The first is to obtain a precise
graph-theoretical characterization of $k$-leaf powers in terms of $k$. A
fundamental question asks whether, for all $k$, $k$-leaf powers can be
characterized as chordal graphs that forbid a finite set of induced subgraphs.
This is known to be true for $k=2,3,4$, but unknown for higher $k$ [3, 6].

The second open problem is whether one can decide in polynomial time whether a
graph $G$ is a $k$-leaf power, where $k$ could be fixed or given. This has
been a longstanding problem even in the case $k\in O(1)$. Polynomial-time
recognition is possible for $k\leq 6$ [11, 15], and the technical feats
required to solve the case $k=6$ show that extending these results is far from
trivial. In this work, we tackle the latter question and show that polynomial-
time recognition is indeed possible for any constant $k$.

###  1.1 Related work

It is well-known that all $k$-leaf powers are chordal, and they are also
strongly chordal (see e.g. [5]). The $2$-leaf powers are collections of
disjoint cliques and the $3$-leaf powers are exactly the chordal graphs that
are bull, dart and gem-free [3, 25]. This can be used to recognize them in
linear time. For $k=4$, a characterization of twin-free $4$-leaf powers in
terms of chordality and a small set of forbidden induced subgraphs is
established, again leading to a linear time algorithm [6]. For $k\geq 5$, a
characterization still escapes us, except for distance-hereditary $5$-leaf
powers [2]. It is known that all $k$-leaf powers are also $(k+2)$-leaf powers,
but that they are not all $(k+1)$-leaf powers [8].

Chang and Ko [10] have developed a linear time recognition algorithm for
$5$-leaf powers, using a reduction from a similar problem known as the
$3$-Steiner root, in which members of $V(G)$ can also be in internal nodes in
the desired tree. Recently, Ducoffe showed that $6$-leaf powers were
polynomial-time recognizable [15], this time using a reduction from the
$4$-Steiner root problem and an elaborate dynamic programming approach. The
case $k=6$ is the farthest that could be achieved so far. Let us mention that
$k$-leaf powers have bounded clique-width [18], and that in [13, 14], the
problem of editing a graph to a $k$-leaf power is studied.

A recent result of Eppstein and Havvaei [16] states that recognizing $k$-leaf
powers is fixed parameter tractable (FPT) in $k+\delta(G)$, where $\delta(G)$
is the degeneracy of the graph. Note that since a $k$-leaf power $G$ is
chordal, it is known that $tw(G)=\omega(G)-1\leq\delta(G)\leq tw(G)$, where
$tw(G)$ and $\omega(G)$ are the treewidth and clique number, respectively,
showing that the problem is also FPT in $tw(G)+k$. We also mention that in
[12], Chen et al. show that if we require each node of the $k$-leaf root to
have degree between $3$ and $d$ (except leaves), then finding such a $k$-leaf
root, if any, is FPT in $k+d$.

Recognizing the larger class of leaf powers is also a challenging open
problem. Subclasses of strongly chordal graphs have been shown to be leaf
powers [20, 4, 22], but not all strongly chordal graphs are leaf powers [5,
21, 19]. Other variants and generalizations of $k$-leaf powers have also been
proposed [7, 9].

###  1.2 Our contributions

In this work, we show that for any constant $k\geq 2$, one can decide whether
a graph $G$ is a $k$-leaf power in time $O(n^{f(k)})$. Here, the function $f$
depends only on $k$, and thus $k$-leaf powers can be recognized in polynomial
time for any constant $k$. We must reckon that $f(k)$ grows faster than a
power tower function with base $k$ and height $3k$, i.e.
$f(k)\in\Omega(k\uparrow\uparrow(3k))$, using Knuth’s up arrow notation. We
did not attempt to optimize $f(k)$, and it is possible that the techniques
presented here can be refined in the future to attain a more reasonable $f(k)$
exponent, or even to obtain an FPT algorithm in parameter $k$.

To the best of our knowledge, several tools developed for this result have not
been applied before. The main idea is that if $G$ is a $k$-leaf power, then
either $G$ admits a $k$-leaf root of low maximum degree, in which case it can
be found “easily”, or all $k$-leaf roots have large maximum degree, in which
case it contains redundant substructures. By this, we mean that $G$ has a
large number of vertex-disjoint subgraphs that are easy to solve individually
and admit the “same kind” of $k$-leaf roots. We can then argue that we can
simply remove one of those redundant subsets from $G$, obtain an equivalent
instance, and repeat the process. We do borrow ideas from [12, 16], since we
handle the “easy” instances mentioned above using dynamic programming on a
tree decomposition.

Although the above ideas are used for algorithmic purposes, they may shed
light on the graph theoretical characterization of $k$-leaf powers. Indeed,
our collection of similar subgraphs satisfy a number of graph properties of
interest (see next subsection). Combined with the knowledge gained from prior
work, our side results may thus help understanding the structure of $k$-leaf
powers. It is also plausible that our techniques can be applied to solve open
problems on the larger class of pairwise compatibility graphs [9] and their
variants, where edges represent a distance in an interval $[d_{1},d_{2}]$ and
non-edges represent a distance not in that interval.

###  1.3 Overview of our algorithm

Our approach requires a bit of a setup in terms of definitions, so here we
first provide the main intuitions.

Assume for the moment that $G$ admits a $k$-leaf root $T$ of maximum degree
$d:=d(k)$, some quantity that depends only on $k$. Then for any leaf $v$ in
$T$, there are at most $d^{k}$ other leaves of $T$ at distance at most $k$
from $v$. This implies that in $G$, $v$ has at most $d^{k}$ neighbors, and so
the maximum degree of $G$ is at most $d^{k}$. This bounds the maximum clique
number and, since $G$ is chordal, also bounds the treewidth by $d^{k}$.
Eppstein and Havvaei [16] have shown that in this setting, one can decide
whether $G$ is a $k$-leaf power in time $O((kd^{k})^{cd^{k}}n)$ for some
constant $c$.

The difficult cases therefore arise when every $k$-leaf root of $G$ has
maximum degree above $d$. At a very high level, our approach for this case can
be described in four essential steps.

  1. 1.

Find a large collection $\\{C_{1}\cup Y_{1},\ldots,C_{d}\cup Y_{d}\\}$ of
disjoint subsets of $V(G)$ that have a “similar” neighborhood structure and
that are easy to solve. Each $C_{i}$ is small and cuts $Y_{i}$ from the rest
of the graph, and each subgraph induced by $C_{i}\cup Y_{i}$ has maximum
degree at most $d^{k}$.

  2. 2.

Consider the set of _all_ $k$-leaf roots of each subgraph of $G$ induced by
the $C_{i}\cup Y_{i}$ subsets, and ensure that many of these sets of $k$-leaf
roots are “similar”. If $d$ is large enough, this will be the case.

  3. 3.

Check whether $G-(C_{1}\cup Y_{1})$ admits a $k$-leaf root. If not, we are
done, but if so, let $T$ be such a $k$-leaf root.

  4. 4.

Look at how the $C_{i}\cup Y_{i}$ subsets are organized within $T$, for $i>1$.
Since they have a similar structure as $C_{1}\cup Y_{1}$ and admit the same
type of $k$-leaf roots, we can find a $k$-leaf root $T_{1}$ of $G[C_{1}\cup
Y_{1}]$ that we can embed into $T$, while mimicking the organization of the
$C_{i}\cup Y_{i}$’s.

Of course, we need to be precise about what is meant by a “similar”
neighborhood structure, and a “similar” set of $k$-leaf roots. We need two
ingredients: the notion of a _similar structure of $G$_, and the notion of the
_signature_ of a tree.

Figure 1: On the left: a $k$-leaf root $T$ with a node $v$ with more than $d$
children. We have chosen $d$ of them, namely $v_{1},\ldots,v_{d}$. The leaf
$z$ is chosen to be at minimum distance from $v$ in $T$. The $C_{i}$ labels
represent the leaves descending from $v_{i}$ at distance at most $k$ from $z$.
Each $C_{i}$ is organized into at most $k$ layers, where layer $j$ consists of
the vertices at distance exactly $j$ from $v$. The $Y_{i}$ labels represent
the deeper leaves below $v_{i}$. On the right: the structure of $G$ implied by
$z$ and the $C_{i}\cup Y_{i}$ leaves of $T$. In $G$, vertices from the same
layer have the same neighbors outside their respective $C_{i}\cup Y_{i}$.

##### Similar structures.

Let $T$ be a $k$-leaf root of $G$ of maximum degree above some large enough
$d$, and suppose that $T$ is rooted. We look at the leaves below a deepest
high degree node of $T$, and want to understand how their structure is
reflected in $G$. This is represented in Figure 1. More specifically, $T$ has
some deepest node $v$ with _at least_ $d+1$ children and whose descendants all
have _at most_ $d$ children. Let $v_{1},\ldots,v_{d}$ be $d$ arbitrary
children of $v$. Let $T_{1},\ldots,T_{d}$ denote the subtrees rooted at the
$v_{i}$’s. Take a leaf $z$ of $T$ that is as close as possible to $v$, but
that does not belong to a $T_{i}$ subtree (such a $z$ exists because $v$ has
more than $d$ children). Then the leaves at distance at most $k$ from $z$ in a
$T_{i}$ subtree form a subset $C_{i}\subseteq V(G)$ of neighbors of $z$. Since
$T_{i}$ has maximum degree $d$, one can argue that $|C_{i}|\leq d^{k}$.
Moreover, if we assume that $G$ is connected, it can be argued that
$C_{i}\neq\emptyset$. In fact in $G$, each $C_{i}$ separates the other leaves
contained in $T_{i}$ from the rest of $G$. Let us call these other leaves
$Y_{i}$. Note that $Y_{i}$ might be empty, so $C_{i}$ might not exactly be a
separator, and even if it is, it might not be minimal. Nevertheless, the
degree bound on $v_{i}$ and its descendants implies that in $G$, the induced
subgraph $G[C_{i}\cup Y_{i}]$ has maximum degree $d^{k}$. In other words, a
high-degree $k$-leaf root of $G$ implies the existence of a large number of
disjoint $C_{i}\cup Y_{i}$ subsets of vertices that are each “easy” to solve,
and such that there is a vertex $z$ that is a neighbor of each member of each
$C_{i}$.

There is yet another property of the $C_{i}$’s that is useful. If we look at
the leaves in $C_{i}$ at distance $j$ from $v$ for some $j\in[k]$, and the
leaves in some other $C_{j}$ also at distance exactly $j$ from $v$, all these
leaves share the same distance to the leaves “outside” of $T_{i}$ and $T_{j}$.
In terms of $G$, the $C_{i}$ vertices can be “layered” so that vertices in the
same layer have the same outside neighborhood in $G$, where the layer of a
vertex is an integer between $1$ and $k$. This is what is meant by a similar
neighborhood structure.

##### Exploiting similar structures.

Obviously, we do not have access to such a $k$-leaf root to find the structure
as we just did, even though we know it exists. However, it can be found in $G$
by brute force, and our ultimate goal is to show that $G$ is a $k$-leaf power
if and only if $G-(C_{1}\cup Y_{1})$ is a $k$-leaf power (where the choice of
$C_{1}\cup Y_{1}$ is arbitrary).

So, imagine that we have found $z$ and the $C_{i}\cup Y_{i}$’s as in Figure 1
on the right, along with a layering of the $C_{i}$’s, but that we do not have
the tree $T$ on the left. In fact, the actual $k$-leaf root might not look
like $T$ at all, and it might intertwine its $C_{i}\cup Y_{i}$ leaf sets.
Nevertheless, if $d$ is large enough, we show that many of the $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ subgraphs admit a “similar” set of $k$-leaf roots. To make
this notion clearer, suppose that we take _every_ $k$-leaf root of a
$G[C_{i}\cup Y_{i}\cup\\{z\\}]$ subgraph, look at their restriction to
$C_{i}\cup\\{z\\}$, and replace each leaf of $C_{i}$ by its layer (see Figure
2.c). By “similar” sets of $k$-leaf roots, we mean that these sets of
restricted $k$-leaf roots are exactly the same for many of the $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ subgraphs. These can be computed using dynamic programming
on a tree decomposition of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$.

This is an oversimplification, but let us go with it for a moment. Assuming
the above is feasible, we could first find a $k$-leaf root $T$ of
$G-(C_{1}\cup Y_{1})$ (if none exists, then $G$ is not a $k$-leaf power). If
$d$ is large enough, several of the $C_{i}\cup\\{z\\}$ subsets will be
organized in the same manner in $T$, i.e. restricting $T$ to these
$C_{i}\cup\\{z\\}$ subsets and replacing $C_{i}$ leaves by their layer will
yield the same tree. We can then find a $k$-leaf root $T_{1}$ of $G[C_{1}\cup
Y_{1}\cup\\{z\\}]$ with the same structure as these, and embed $T_{1}$ with
the same organization as the others in $T$. Because $C_{1}$ is layered in the
same manner as the other $C_{i}$’s, mimicking their structure in $T$ ensures
that the distance relationships with the other vertices are satisfied. The $z$
vertex is important, since it serve as a common point between all the
$C_{i}$’s and indicates where to start embedding. At this point, it becomes
difficult to describe how this embedding is performed more concretely, and the
interested reader is redirected to the proof of Theorem 3.1 for more details.

##### Tree signatures.

As we mentioned, expecting the $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ subgraphs to
admit exactly the same sets of $k$-leaf roots, even if we restrict them to
$C_{i}\cup\\{z\\}$ and replace the leaves by their layer, does not quite work.
First, each restricted subtree must also remember how far the $Y_{i}$ vertices
are from the nodes of the restricted subtree, to ensure that we do not make
the $Y_{1}$ nodes too close to other nodes during the embedding. This can be
done by labeling the internal nodes of our restricted trees with the distance
to the closest $Y_{i}$ leaf, as in Figure 2.c. Note that a similar trick was
done by Chen et al. in [12].

Figure 2: (a) A subgraph of $G$ induced by $C_{i}\cup Y_{i}\cup\\{z\\}$.
Vertices in black are those of $C_{i}$, and in gray those of $Y_{i}$. The
$\ell_{1},\ell_{2},\ell_{3}$ represent the layer assigned to each vertex of
$C_{i}$ (several vertices can have the same layer). (b) A $4$-leaf root $T$
for this subgraph. The leaves of $C_{i}$ are labeled by their layer. (c) The
restriction of $T$ to $C_{i}\cup\\{z\\}$, but in which each internal node
remembers the distance to the closest pruned leaf that it led to (if any). (d)
A tree representing the signature of the restricted $4$-leaf root. Each time a
node has three identical subtrees, one of them is considered redundant and is
pruned.

Second, we cannot guarantee that enough of the $G[C_{i}\cup Y_{i}\cup\\{z\\}]$
will admit _exactly_ the same set of restricted $k$-leaf roots, since the
number of possibilities is too large. The solution is to define a compact
representation of $k$-leaf roots restricted to some $C_{i}\cup\\{z\\}$, which
we call its _signature_. This representation prunes information from the tree
that is not necessary for our embedding. Conceptually, to obtain the signature
of a tree, we look at each node and if we find a node that has three or more
child subtrees that are identical, we remove one of these subtrees. This is
fine for our embedding, since the identical subtree can be inserted along the
others that are identical. We repeat until this is not possible. This is
illustrated in Figure 2. From (a) a $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ subgraph,
we look at (b) each $k$-leaf root with leaves of the $C_{i}$’s replaced by
their layer, then (c) restrict to $C_{i}\cup\\{z\\}$ and remember the
distances to the removed leaves, and finally (d) prune redundant subtrees.
This gives the compact representation of one $k$-leaf root, and we must obtain
them all.

This compact representation allows much less possibilities, and then we can
guarantee with a pigeonhole argument that with large enough $d$, many
$G[C_{i}\cup Y_{i}\cup\\{z\\}]$ will admit the exact same set of signatures.
This works because the number of possible signatures does not depend on $d$,
only on $k$. Therefore, we can make $d$ as large as desired for our argument.
Note that concretely, signatures are represented as vectors of integers that
encode the same information, since it allows for simpler proofs (see Section
3).

We now proceed with the details.

##  2 Preliminary notions

For an integer $n$, we use the notation $[n]=\\{1,2,\ldots,n\\}$. All graphs
in this paper are finite, simple and undirected. For a graph $G$ and $v\in
V(G)$, we denote by $N_{G}(v)$ the set of neighbors of $v$ in $G$, and we
write $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. For $X\subseteq V(G)$, we denote by
$N_{G}(X)=\bigcup_{x\in X}(N_{G}(x)\setminus X)$ the neighbors of members of
$X$ that are outside of $X$. Also, we write $N_{G}[X]=N_{G}(X)\cup X$. We may
drop the subscript $G$ if it is clear from the context. For $X\subseteq V(G)$,
we denote by $G[X]$ the subgraph of $G$ induced by $X$. We define a _connected
component_ as a maximal _set_ of vertices $X$ such that $G[X]$ is connected.

Unless stated otherwise, all trees in this paper are _rooted_. Hence we will
usually say _tree_ instead of _rooted tree_. We denote the root of a tree $T$
by $r(T)$. For a node $v\in V(T)$, we write $ch_{T}(v)$ for the set of
children of $v$ in $T$. The _arity_ of $T$ is $\max_{v\in V(G)}|ch_{T}(v)|$.
We say that $v$ is a _leaf_ if it is has no children. We write $L(T)$ to
denote the set of leaves of $T$. It is important to note that leaves are
sometimes defined as nodes with a single neighbor in $T$. This slightly
differs from our definition, since if $r(T)$ has a single child in $T$, it is
not treated as a leaf here. The only case in which the root is also a leaf is
when $T$ has a single vertex (which has no children). A node $u\in V(T)$ is a
_descendant_ of another node $v\in V(T)$ if $v$ is on the path from $r(T)$ to
$u$. In this case, $v$ is an _ancestor_ of $u$. Note that $v$ is a descendant
and ancestor of itself. Given a tree $T$ and some $v\in V(T)$, we let $T(v)$
denote the subtree rooted at $v$, i.e. the subgraph of $T$ induced by $v$ and
all its descendants. The distance between two nodes $u$ and $v$ of $T$ is
denoted $dist_{T}(u,v)$. We define $height(T)=1+\max_{l\in
L(T)}dist_{T}(r(T),l)$.

Two trees $T_{1}$ and $T_{2}$ are _equal_ if $r(T_{1})=r(T_{2})$ and
$(V(T_{1}),E(T_{1}))=(V(T_{2}),E(T_{2}))$, in which case we write
$T_{1}=T_{2}$. Two trees $T_{1}$ and $T_{2}$ are called _leaf-isomorphic_ ,
denoted $T_{1}\simeq_{L}T_{2}$, if $L(T_{1})=L(T_{2})$, and there exists a
bijection $\mu:V(T_{1})\rightarrow V(T_{2})$ such that $\mu(u)=u$ for every
$u\in L(T_{1})$, $\mu(r(T_{1}))=r(T_{2})$, and such that $uv\in E(T_{1})$ if
and only if $\mu(u)\mu(v)\in E(T_{2})$. We call $\mu$ a leaf-isomorphism. Note
that this is stronger than the usual notion of isomorphism, since we require
$T_{1}$ and $T_{2}$ to be built with the same set of leaves. Also observe that
since leaves must be matched, the $\mu$ function is unique222To see this,
observe that $\mu$ is forced for the leaves of $T_{1}$. Then, $\mu$ is forced
for the parent of those leaves, and then $\mu$ is forced for the grand-
parents, and so on..

Let $X\subseteq V(T)$. The _restriction_ of $T$ to $X$, denoted $T|X$, is the
subgraph of $T$ induced by $X$ and every vertex of $T$ on the shortest path
between two elements of $X$. We shall repeatedly use the fact that for $u,v\in
X$, $dist_{T|X}(u,v)=dist_{T}(u,v)$, and that $V(T|X)\subseteq V(T)$. Note
that for $v\in V(T|X)$, $ch_{T}(v)\setminus ch_{T|X}(v)$ denotes the set of
children of $v$ that were “removed” by the restriction.

### Leaf powers and their properties

The main definition of interest in this paper is the following.

###### Definition 1

Let $G$ be a graph and let $k$ be a positive integer. A _$k$ -leaf root_ of
$G$ is a tree $T$ such that $L(T)=V(G)$, and such that for all distinct
$u,v\in V(G)$, $uv\in E(G)$ if and only if $dist_{T}(u,v)\leq k$.

The graph $G$ is a _$k$ -leaf power_ if there exists a $k$-leaf root of $G$.

Note that according to our definitions, the tree $T$ is implicitly rooted.
This is not required in the usual definition of leaf powers, although this is
inconsequential for $k\geq 2$. This is because if an unrooted $k$-leaf root
$T$ has an internal node or has a single node, we may use it as the root. If
not, $T$ has two vertices $u$ and $v$, which are both of degree $1$. This
implies that $uv\in E(G)$, but since $k\geq 2$, we may add an internal node
between $u$ and $v$ in $T$. Also observe that the $k$-leaf power property is
hereditary. That is, if $G$ is a $k$-leaf power and $X\subseteq V(G)$, then
$G[X]$ is a $k$-leaf power. This is because if $T$ is a $k$-leaf root of $G$,
then $T|X$ is a $k$-leaf root of $G[X]$, since restrictions preserve
distances.

A graph is _chordal_ if it has no induced cycle of length $4$ or more. The
treewidth of $G$ is denoted $tw(G)$ (we defer the definition of treewidth to
Section 4). The following is a well-known property of $k$-leaf powers, for any
$k$ (see [23, 5]).

###### Lemma 2.1

Let $G$ be a $k$-leaf power. Then $G$ is chordal.

We will be interested in $k$-leaf roots that have high arity. In [16, section
7], Eppstein and Havvaei have shown that if $G$ is a graph of bounded
treewidth, then deciding if $G$ is a $k$-leaf power is fixed-parameter
tractable in $k+tw(G)$. As we show, this implies that low-arity $k$-leaf
roots, if any, can be found using this result.

###### Lemma 2.2

Let $G$ be a graph with $n$ vertices. If there exists a $k$-leaf root of $G$
of arity at most $d$, then $G$ has maximum degree $d^{k}$. Moreover, one can
decide in time $O(n(d^{k}k)^{cd^{k}})$ whether such a $k$-leaf root exists,
where $c$ is a constant.

  * Proof.

Assume that $T$ is a $k$-leaf root of $G$ of arity at most $d$. Let $v\in
V(G)$. Then in $T$, the number of leaves at distance at most $k$ from $v$ is
bounded by $d^{k}$ (since if we imagine rerooting $T$ at $v$, each node will
still have at most $d$ children — the astute reader will see that we could
optimize to $d^{k-1}$, but let us not bother). This implies that $v$ has at
most $d^{k}$ neighbors in $G$. Since this holds for every vertex, $G$ has
maximum degree $d^{k}$.

As for the second part of the lemma, we know by [16] that deciding if $G$ is a
$k$-leaf power can be done in time $O(n\cdot(tw(G)k)^{c\cdot tw(G)})$ for some
constant $c$. To use this, we can first check whether $G$ is chordal in linear
time, and if not reject it. Since $G$ is chordal, it is well-known that
$tw(G)=\omega(G)-1$, where $\omega(G)$ is the size of a maximum clique in $G$.
In any graph, $\omega(G)$ is at most the maximum degree plus one. In our case,
this implies that $tw(G)=\omega(G)-1\leq d^{k}$. Using the algorithm of [16],
we can check whether $G$ is a $k$-leaf power in time $O(n(d^{k}k)^{cd^{k}})$.

##  3 Finding redundant structures in $k$-leaf powers

Let us fix a positive integer $k$ and an arbitrary graph $G$ for the rest of
the paper. We assume that $G$ is connected, as otherwise, each connected
component can be treated separately (if a $k$-leaf root is found for each
component, we can join their roots under a new root at distance more than $k$
from them). As we mentioned, an important difficulty is when $G$ does admit
$k$-leaf roots, but they all have large arity. We now define our similar
structures precisely. We then introduce the notion of a _signature_ for their
$k$-leaf roots. After that, we argue that many subsets admit the same $k$-leaf
root signatures, and that we can prune one. In Section 4, we show how the set
of $k$-leaf root signatures can be found.

###  3.1 Similar structures

A _similar structure_ of a graph $G$ is a tuple
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ where:

  * •

$\mathcal{C}=\\{C_{1},\ldots,C_{d}\\}$ is a collection of $d\geq 2$ pairwise
disjoint, non-empty subsets of vertices of $G$;

  * •

$\mathcal{Y}=\\{Y_{1},\ldots,Y_{d}\\}$ is a collection of pairwise disjoint
subsets of vertices of $G$, some of which are possibly empty. Also, $C_{i}\cap
Y_{j}=\emptyset$ for any $i,j\in[d]$;

  * •

$z\in V(G)$ and does not belong to any subset of $\mathcal{C}$ or
$\mathcal{Y}$;

  * •

$\mathcal{L}=\\{\ell_{1},\ldots,\ell_{d}\\}$ is a set of functions where, for
each $i\in[d]$, we have
$\ell_{i}:C_{i}\cup\\{z\\}\rightarrow\\{0,1,\ldots,k\\}$. The functions in
$\mathcal{L}$ are called _layering functions_.

Additionally, $\mathcal{S}$ must satisfy several conditions. Let us denote
$C^{*}=\bigcup_{i\in[d]}C_{i}$. Let $X=\\{X_{1},\ldots,X_{t}\\}$ be the
connected components of $G-C^{*}$. For each $i\in[d]$, denote
$X^{(i)}=\\{X_{j}\in X:N_{G}(X_{j})\subseteq C_{i}\\}$, i.e. the components
that have neighbors only in $C_{i}$.

Then all the following conditions must hold:

  1. 1.

for each $i\in[d]$, $Y_{i}=\bigcup_{X_{j}\in X^{(i)}}X_{j}$ ($Y_{i}=\emptyset$
is possible);

  2. 2.

there is exactly one connected component $X_{z}\in X$ such that for all
$i\in[d]$, ${N_{G}(X_{z})\cap C_{i}\neq\emptyset}$. Moreover, $z\in X_{z}$ and
$C^{*}\subseteq N_{G}(z)$;

  3. 3.

for all $X_{j}\in X\setminus\\{X_{z}\\}$, $X_{j}\subseteq Y_{i}$ for some
$i\in[d]$. In particular, $X_{z}$ is the only connected component of $G-C^{*}$
with neighbors in two or more $C_{i}$’s;

  4. 4.

the layering functions $\mathcal{L}$ satisfy the following:

    1. (a)

for each $i\in[d]$, $\ell_{i}(z)=0$. Moreover, $\ell_{i}(x)>0$ for any $x\in
C_{i}$;

    2. (b)

for any $i,j\in[d]$ and any $x\in C_{i},y\in C_{j}$, $\ell_{i}(x)=\ell_{j}(y)$
implies $N_{G}(x)\setminus(C_{i}\cup Y_{i}\cup C_{j}\cup
Y_{j})=N_{G}(y)\setminus(C_{i}\cup Y_{i}\cup C_{j}\cup Y_{j})$. Note that this
includes the case $i=j$;

    3. (c)

for any $i,j\in[d]$ and any $x\in C_{i},y\in C_{j}$,
$\ell_{i}(x)+\ell_{j}(y)\leq k$ implies $xy\in E(G)$. Note that this includes
the case $i=j$.

    4. (d)

for any _two distinct_ $i,j\in[d]$ and any $x\in C_{i},y\in C_{j}$,
$\ell_{i}(x)+\ell_{j}(y)>k$ implies $xy\notin E(G)$. Note that this does _not_
include the case $i=j$

We will refer to the value of $d$ as the _size_ of $\mathcal{S}$.

Although somewhat burdensome, the properties of a similar structure occur
naturally when we look at the subtrees under a given node of a $k$-leaf root.
The similar structure is the one that is described in Figure 1, but in a more
precise manner. The properties of similar structures essentially say that
after removing each $C_{i}\in\mathcal{C}$ from $G$, there is one connected
component $X_{z}$ that touches every $C_{i}$, with a $z\in X_{z}$ that is a
neighbor of each $C_{i}$. All the other connected components are separated
from the rest of the graph by exactly one $C_{i}$, and these form the
$Y_{i}$’s. As for the layering functions, they state that $z$ is a special
vertex with layer $0$. For the $C_{i}$ vertices, the layers represent how the
neighborhoods of the $C_{i}$ members are organized. One can imagine that $G$
has a $k$-leaf root and that the layer of $x\in C_{i}$ is the distance from
$x$ to the lowest common ancestor of $C_{i}$ (of course, this is conceptual
since we don’t have this $k$-leaf root). Any two vertices at the same layer
must have the same neighborhood outside of their $C_{i}$’s. Vertices from
“close” layers, i.e. with sum at most $k$, must be neighbors. If the layers
are “far”, i.e. with sum more than $k$, then the vertices should not be
neighbors (unless they are in the same $C_{i}$).

We first show that similar structures can always be found on graphs with
$k$-leaf roots of high arity. This is essentially a formalization of Figure 1.

###### Lemma 3.1

Let $d\geq 2$ and let $G$ be a connected graph that admits a $k$-leaf root of
arity at least $d+1$. Then there exists a similar structure
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ of $G$ such that
$|\mathcal{C}|=d$. Moreover, for each $C_{i}\in\mathcal{C}$, $|C_{i}|\leq
d^{k}$ and $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ has maximum degree at most $d^{k}$.

  * Proof.

Let $T$ be a $k$-leaf root of $G$ of arity at least $d+1$. We show how to
construct $\mathcal{C}=\\{C_{1},\ldots,C_{d}\\}$,
$\mathcal{Y}=\\{Y_{1},\ldots,Y_{d}\\},z$, and
$\mathcal{L}=\\{\ell_{1},\ldots,\ell_{d}\\}$ using the relationship between
$T$ and $G$. Let $v$ be a deepest node of $T$ with $d+1$ or more children
(such a node must exist). By the choice of $v$, all the descendants of $v$
have at most $d$ children.

Let $z\in L(T)$ be a leaf of $T$ at minimum distance from $v$, i.e. $z$
minimizes $dist_{T}(z,v)$ among all leaves of $T$. Note that $z$ may or may
not be a descendant of $v$. Let $v_{1},\ldots,v_{d}$ be $d$ children of $v$,
none of which is an ancestor of $z$ (such a choice of $d$ children exists
since $v$ has at least $d+1$ children). For each $i\in[d]$, define
$C_{i}=L(T(v_{i}))\cap N_{G}(z)$. Note that since $z$ is not a descendant of
$v_{i}$, the vertices of $L(T(v_{i}))\cap N_{G}(z)$ must be at distance at
most $k$ from $v$ (actually, $k-1$, but we shall not bother). Since the
$T(v_{i})$ subtree has arity at most $d$, there are at most $d^{k}$ leaves in
$T(v_{i})$ at distance at most $k$ from $v$. It follows that $|C_{i}|\leq
d^{k}$, for each $i\in[d]$. Note that by construction, the $C_{i}$ subsets are
pairwise disjoint. To see that the $C_{i}$’s are non-empty, assume that
$C_{i}$ is empty for some $i\in[d]$. Since $z$ is the closest leaf to $v$, and
since every path from a member of $L(T(v_{i}))$ to a member of $V(G)\setminus
L(T(v_{i}))$ passes through $v$, no element of $L(T(v_{i}))$ is at distance
$k$ or less in $T$ from and element of $V(G)\setminus L(T(v_{i}))$. Since
$L(T(v_{i}))\neq\emptyset$, this implies that $G$ is disconnected, a
contradiction. We may thus assume that $C_{i}\neq\emptyset$.

Now, for convenience, define $C^{*}=\bigcup_{i\in[d]}C_{i}$. Also define
$G^{\prime}=G-C^{*}$.

Let $X_{z}$ be the connected component of $G^{\prime}$ that contains $z$. By
construction, $z$ is a neighbor of every vertex in each $C_{i}$. We must show
that only $X_{z}$ intersects with every $C_{i}$. Let
$Z=L(T)\setminus\left(\bigcup_{i\in[d]}L(T(v_{i})))\right)$, and notice that
$z\in Z$. We argue that $G^{\prime}[Z]$ is connected. Assume otherwise. Then
$G^{\prime}[Z]$ has at least two connected components, one of them being
$X_{z}$, and the other some other component $X_{q}$. Since $G$ is connected
and removing $C^{*}$ separates $X_{z}$ from $X_{q}$, there is some $q\in
X_{q}$ such that $N_{G}(q)\cap C^{*}\neq\emptyset$. Let $c\in N_{G}(q)\cap
C^{*}$. Consider the location of $q$ in $T$. Because $q\in Z$, $q$ is not a
descendant of any $v_{i}$, and thus the path from $q$ to $c$ in $T$ passes
through $v$. But the choice of $z$ implies

$\displaystyle k\geq dist_{T}(q,c)=dist_{T}(q,v)+dist_{T}(v,c)\geq
dist_{T}(q,v)+dist_{T}(v,z)\geq dist_{T}(q,z)$

Since $T$ is a $k$-leaf root of $G$, we have $qz\in E(G)$, contradicting that
they belong to different connected components of $G^{\prime}$. Thus
$G^{\prime}[Z]$ is connected.

Now for $i\in[d]$, consider a leaf $x\in L(T(v_{i}))\setminus C_{i}$. We argue
that all neighbors of $x$ are in $L(T(v_{i}))$. Suppose that $x$ has a
neighbor $q\in L(T)\setminus L(T(v_{i}))$. Then $dist_{T}(x,q)\leq k$, and the
path from $x$ to $q$ goes through $v$. But again, by the choice of $z$,

$k\geq dist_{T}(x,q)=dist_{T}(x,v)+dist_{T}(v,q)\geq
dist_{T}(x,v)+dist_{T}(v,z)=dist_{T}(x,z)$

But then, $x$ should be in $C_{i}$ (by its definition), which is a
contradiction. It follows that $x$ has no neighbor outside of $L(T(v_{i}))$.
In particular, $x\notin Z$.

It follows that $Z$ is a connected component of $G^{\prime}$, that it is equal
to $X_{z}$, and that it satisfies Property 2 of similar structures. Moreover,
as we argued any other connected component $X_{j}$ of $G^{\prime}$ contains
vertices that appear as leaves of some $T(v_{i})$ subtree, and $N_{G}(X_{j})$
must be a subset of $C_{i}$ since $X_{j}$ vertices have no neighbor outside
$T(v_{i})$. We may then define $Y_{i}=L(T(v_{i}))\setminus C_{i}$ for each
$i\in[d]$ and it follows that $Y_{i}$ regroups all connected components of
$G^{\prime}$ that have neighbors only in $C_{i}$, which satisfies Property 1.
Property 3 is easily seen to be satisfied, since the elements in
$\\{X_{z},Y_{1},\ldots,Y_{d}\\}$ are disjoint and cover all of $L(T)\setminus
C^{*}$.

It remains to describe our layering functions $\mathcal{L}$. For $i\in[d]$,
put $\ell_{i}(z)=0$ and for $x\in C_{i}$, define

$\ell_{i}(x)=dist_{T}(x,v)$

Note that $\ell_{i}(x)>0$, and that $\ell_{i}(x)=1$ is possible if $C_{i}$
only contains a leaf of $T$. Also note that $\ell_{i}(x)\leq k$ since each $x$
is a neighbor of $z$. Property 4a is thus satisfied. We show that each
remaining property is satisfied.

_Property 4b_. Let $i,j\in[d]$ and let $x\in C_{i},y\in C_{j}$ such that
$\ell_{i}(x)=\ell_{j}(y)$. Note that $q\in N_{G}(x)\setminus(C_{i}\cup
Y_{i}\cup C_{j}\cup Y_{j})$ only if $q$ is a leaf of $T$ at distance at most
$k$ from $x$, and $q$ does not descend from $v_{i}$ or $v_{j}$. Therefore, the
path from $x$ to $q$ goes through $v$. Since $dist_{T}(x,v)=dist_{T}(y,v)$
(because they have the same layer), we have $dist_{T}(x,q)=dist_{T}(y,q)$, and
thus $q\in N_{G}(y)\setminus(C_{i}\cup Y_{i}\cup C_{j}\cup Y_{j})$ as well.
Thus $N_{G}(x)\setminus(C_{i}\cup Y_{i}\cup C_{j}\cup Y_{j})\subseteq
N_{G}(y)\setminus(C_{i}\cup Y_{i}\cup C_{j}\cup Y_{j})$, and the other
containment direction can be argued symmetrically. Thus $\mathcal{S}$
satisfies Property 4b.

_Property 4c_. Let $i,j\in[d]$ and let $x\in C_{i},y\in C_{j}$ with
$\ell_{i}(x)+\ell_{j}(y)\leq k$. We see that $dist_{T}(x,y)\leq
dist_{T}(x,v)+dist_{T}(y,v)=\ell_{i}(x)+\ell_{j}(y)\leq k$, implying that
$xy\in E(G)$. Thus Property 4c is satisfied.

_Property 4d_. Let $i,j\in[d]$, $i\neq j$, and let $x\in C_{i},y\in C_{j}$
with $\ell_{i}(x)+\ell_{j}(y)>k$. Since $x$ and $y$ descend from distinct
$v_{i}$ and $v_{j}$,
$dist_{T}(x,y)=dist_{T}(x,v)+dist_{T}(v,y)=\ell_{i}(x)+\ell_{j}(y)>k$, and
thus $xy\notin E(G)$. Thus Property 4d is satisfied.

We have therefore shown that $\mathcal{S}$ satisfies all requirements to be a
similar structure, and that $|C_{i}|\leq d^{k}$ for each $i\in[d]$.

To finish the proof, recall that the lemma requires that each $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ has maximum degree at most $d^{k}$. First note that $z$ has
at most $d^{k}$ neighbors in this subgraph. Now let $x\in C_{i}\cup Y_{i}$.
Any neighbor of $x$ in $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ is at distance at most
$k-1$ from the parent $p$ of $x$ in $T$. Since $T_{i}$ has arity at most $d$,
the number of other leaves of $C_{i}\cup Y_{i}$ at distance at most $k-1$ from
$p$ is at most $d^{k-1}$, and thus $x$ has at most $d^{k-1}$ neighbors in
$C_{i}\cup Y_{i}$ (this also counts the leaves that do not descend from $p$).
Note that $x$ could also have $z$ as a neighbor, so its degree in $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ is at most $d^{k-1}+1\leq d^{k}$, as desired.

###  3.2 Valued trees and signatures

We now know that similar structures exist in difficult $k$-leaf powers. This
is not enough though. We would like to say that the $G[C_{i}\cup
Y_{i}\cup\\{z\\}]$ subgraphs each admit “similar” sets of $k$-leaf roots, so
that pruning one $C_{i}\cup Y_{i}$ does not matter. In fact, we are only
interested in how the $C_{i}\cup\\{z\\}$ subsets behave in these $k$-leaf
roots, so we develop the notion of a _valued restriction_ to remove the
$Y_{i}$’s, while retaining the essential distance information to these
$Y_{i}$’s. This is still not enough though, since the sets of such restricted
$k$-leaf roots may still differ. We introduce the notion of a _signature_ for
these pruned trees, which is a compact representation that retains the essence
of the structure of the trees.

A _valued tree_ $\mathcal{T}$ is a pair $(T,\sigma)$ where $T$ is a tree and
$\sigma:V(T)\setminus L(T)\rightarrow\mathbb{N}\cup\\{\infty\\}$ assigns each
internal node of $T$ an integer, or possibly the special value $\infty$. We
say that $\mathcal{T}$ is _$s$ -bounded_ if $\sigma(v)\leq s$ or
$\sigma(v)=\infty$ for each $v\in V(T)\setminus L(T)$. We define
$height(\mathcal{T})=height(T)$. For $v\in V(T)$,
$\mathcal{T}(v)=(T^{\prime},\sigma^{\prime})$ denotes the valued tree in which
$T^{\prime}=T(v)$ and $\sigma^{\prime}(w)=\sigma(w)$ for $w\in
V(T(v))\setminus L(T)$. We say that two valued trees $(T_{1},\sigma_{1})$ and
$(T_{2},\sigma_{2})$ are _value-isomorphic_ if $T_{1}\simeq_{L}T_{2}$, with
leaf-isomorphism $\mu$, and $\sigma_{1}(w)=\sigma_{2}(\mu(w))$ for all $w\in
V(T_{1})\setminus L(T_{1})$. The notion of valued restrictions will be
fundamental for the rest of this paper.

###### Definition 2

Let $T$ be a tree and let $X\subseteq L(T)$. We say that $(T^{\prime},\sigma)$
is the _valued restriction of $T$ to $X$_ if it satisfies the following:

  * •

$T^{\prime}=T|X$;

  * •

for each $v\in V(T^{\prime})\setminus L(T^{\prime})$, let
$L^{*}(v)=\bigcup_{x\in ch_{T}(v)\setminus ch_{T^{\prime}}(v)}L(T(x))$. Then

    * –

if $L^{*}(v)=\emptyset$, $\sigma(v)=\infty$;

    * –

otherwise, $\sigma(v)=\min_{l\in L^{*}(v)}dist_{T}(v,l)$.

See Figure 3.b for an illustration. Intuitively, the valued restriction of $T$
to $X$ takes $T^{\prime}=T|X$ as a tree. By doing so, each remaining $v\in
V(T^{\prime})$ might have lost some children that were in $T$. We want $v$ to
remember how far it is from a “hidden” leaf, i.e. descending from one of these
lost children, and $\sigma(v)$ stores this information. The point of this is
that $T$ represents a $k$-leaf root in which the leaves not in $X$ should be
at distance more than $k$ from any leaf not in $T$ (concretely, these will be
the $Y_{i}$ leaves). The tree $T^{\prime}$ is a compressed version of $T$, and
we will embed $T^{\prime}$ into a larger $k$-leaf root instead of $T$. During
this embedding we want to know how far the hidden leaves are to ensure that
outside leaves remain at distance more than $k$ from them.

Figure 3: (a) A tree $T$. The set of leaves $v$ with a label $\ell(v)$ in
$\\{0,1,\ldots,4\\}$ forms a set $X$, and the leaves in gray are those not in
$X$. Note that these labels do not take part of the definition of a valued
restriction, but are needed for signatures. (b) The valued restriction
$\mathcal{T}$ of $T$ to $X$, with the leaves of $X$ preserving their labels.
(c) An illustration of the signature of each rooted subtree of the valued
restriction. For each leaf $v$, the signature of $\mathcal{T}(v)$ is
$(\ell(v))$. We only give the full signature for one internal node. We chose
to order its entries such that for $i\in 1,\ldots,5$, the $i$-th coordinate is
the number of children of that node that have signature $(i-1)$, or $2$ if
this value is above $2$. The last entry is the $\sigma$ value of the node (as
for every other node). The parent of that node would then have one entry for
each possible signature for a tree of height $2$, and only one of those
entries would be set to $1$.

#### Valued tree signatures

Let $\mathcal{T}=(T,\sigma)$ be a valued tree that is $s$-bounded for some
$s$. Furthermore, let $\ell$ be a layering function that maps each leaf in
$L(T)$ to an integer in $\\{0,1,\ldots,k\\}$. We now define the _signature of
$\mathcal{T}$ with respect to $\ell$_, denoted $sig_{\ell}(\mathcal{T})$,
which encodes some properties of $\mathcal{T}$ in a vector of integers. The
signature is defined recursively and depends on the height of $\mathcal{T}$,
as illustrated in Figure 3.c.

If $height(\mathcal{T})=1$, then $T$ has a single node $v$, which is a leaf.
In this case, define $sig_{\ell}(\mathcal{T})=(\ell(v))$.

Now, assume that $height(\mathcal{T})=h>1$. Let
$S(s,h-1)=\\{s_{1},\ldots,s_{m}\\}$ denote the set of all possible signatures
for an $s$-bounded valued tree of height $h-1$ _or less_ , with respect to any
layering function that assigns leaves to $\\{0,1,\ldots,k\\}$. We will later
show that $m$ is finite. We may assume that the $s_{i}$ subscripts order the
the signatures lexicographically (but this is merely for concreteness, the
ordering does not matter). Then $sig_{\ell}(\mathcal{T})$ is a vector or
dimension $m+1$ in which, for $i\in[m]$, the $i$-th coordinate of
$sig_{\ell}(\mathcal{T})$ is defined as

$sig_{\ell}(\mathcal{T})[i]=\min(2,|\\{v\in
ch_{T}(r(T)):sig_{\ell}(\mathcal{T}(v))=s_{i}\\}|)$

Moreover, $sig_{\ell}(\mathcal{T})[m+1]=\sigma(r(T))$.

It should be obvious that if $\mathcal{T}$ has height $h$, then
$sig_{\ell}(\mathcal{T}(v))\in S(s,h-1)$ for each $v\in ch_{T}(r(T))$, and
hence the signature summarizes every child subtree of $r(T)$. Two signatures
are _equal_ in the usual sense of vector equality, i.e. if they have the same
length and, at every position, the values of the two vectors are equal.

In words, one may think of each integer $i\in[m]$ as a code for the $i$-th
signature $s_{i}$, and $sig_{\ell}(\mathcal{T})[i]$ is the number of children
of $r(T)$ whose subtree has signature $s_{i}$, except that we only bother
remembering whether there are $0,1$ or more of those (which we encode by $2$).
We also reserve the last coordinate of $sig_{\ell}(\mathcal{T})$ for
$\sigma(r(T))$. For valued trees with one node, we only need to remember the
layer of the leaf.

We list the basic properties of signatures that will be needed, and then we
will proceed with our $k$-leaf power algorithm.

###### Lemma 3.2

Let $\mathcal{T}_{1}=(T_{1},\sigma_{1})$ and
$\mathcal{T}_{2}=(T_{2},\sigma_{2})$ be valued trees satisfying
$sig_{\ell_{1}}(\mathcal{T}_{1})=sig_{\ell_{2}}(\mathcal{T}_{2})$ for some
layering functions $\ell_{1}$ and $\ell_{2}$. Then the following holds:

  1. 1.

if $r(T_{1})$ has a child $u$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))\neq sig_{\ell_{1}}(\mathcal{T}_{1}(v))$
for every $v\in ch_{T_{1}}(r(T_{1}))\setminus\\{u\\}$, then $r(T_{2})$ has
exactly one child $u^{\prime}$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{2}}(\mathcal{T}_{2}(u^{\prime}))$;

  2. 2.

if $r(T_{1})$ has two distinct children $u,v$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{1}}(\mathcal{T}_{1}(v))$, then
$r(T_{2})$ has at least two distinct children $u^{\prime},v^{\prime}$ such
that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{2}}(\mathcal{T}_{2}(u^{\prime}))=sig_{\ell_{2}}(\mathcal{T}_{2}(v^{\prime}))$;

  3. 3.

for any $x\in V(T_{1})$, there exists $y\in V(T_{2})$ such that
$dist_{T_{1}}(x,r(T_{1}))=dist_{T_{2}}(y,r(T_{2}))$ and
$sig_{\ell_{1}}(\mathcal{T}_{1}(x))=sig_{\ell_{2}}(\mathcal{T}_{2}(y))$. In
particular, this includes the case $x\in L(T_{1})$.

  * Proof.

Property 1 is due to the fact that the entry corresponding to
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))$ must be equal to $1$ in both the
$sig_{\ell_{1}}(\mathcal{T}_{1})$ and $sig_{\ell_{2}}(\mathcal{T}_{2})$
vectors. Property 2 is because the entry corresponding to
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{1}}(\mathcal{T}_{1}(v))$ must
be equal to $2$ in both the $sig_{\ell_{1}}(\mathcal{T}_{1})$ and
$sig_{\ell_{2}}(\mathcal{T}_{2})$ vectors.

Property 3 can be argued inductively on $dist_{T_{1}}(x,r(T_{1}))$. If the
distance is $0$, then $x=r(T_{1})$ and $y=r(T_{2})$ shows that the property
holds. If $dist_{T_{1}}(x,r(T_{1}))>0$, let $x^{\prime}$ be the child of
$r(T_{1})$ on the path between $x$ and $r(T_{1})$. By the previous properties,
$r(T_{2})$ has a child $y^{\prime}$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(x^{\prime}))=sig_{\ell_{2}}(\mathcal{T}_{2}(y^{\prime}))$.
By induction, there is $y\in V(T_{2}(y^{\prime}))$ such that
$dist_{T_{1}(x^{\prime})}(x,x^{\prime})=dist_{T_{2}(y^{\prime})}(y,y^{\prime})$
and
$sig_{\ell_{1}}(\mathcal{T}_{1}(x^{\prime}))=sig_{\ell_{2}}(\mathcal{T}_{2}(y^{\prime}))$.
The distance from $x$ to $r(T_{1})$ is thus the same as the distance from $y$
to $r(T_{2})$, and therefore $y$ show that the property holds.

Importantly, we can argue that the number of possible signatures depends only
on height and $s$-boundedness.

###### Lemma 3.3

Let $S(s,h)$ denote the set of all possible signatures for $s$-bounded valued
trees of height $h$ or less, for any layering function that map leaves to
$\\{0,1,\ldots,k\\}$. Then

$\displaystyle|S(s,h)|\leq\begin{cases}k+1&\mbox{if $h=1$}\\\ (s+2)\cdot
3^{|S(s,h-1)|}+|S(s,h-1)|&\mbox{otherwise}\end{cases}$

  * Proof.

All valued trees with $h=1$ have a signature of the form $(\ell(v))$, and
$\ell(v)$ can take up to $k+1$ values. For $h>1$, consider an $s$-bounded
valued tree of height $h$. For each of the $S(s,h-1)$ possible signatures of
valued trees of height $h-1$ or less, the signature vector has an entry in
$\\{0,1,2\\}$, i.e. $3$ possible values for each element of $S(s,h-1)$.
Moreover, the last entry is $\sigma(r(T))$, which can take up to $s+2$ values
in $\\{0,1,\ldots,s,\infty\\}$. This counts the number of signatures for a
valued tree of height exactly $h$. Since $S(s,h)$ includes signatures for
valued trees of height $h$ _or less_ , we must add the term $|S(s,h-1)|$ to
count the valued trees of height $h-1$ or less.

We note that the upper bound on $|S(s,h)|$ can be computed in time
proportional to $h$ (omitting the bit manipulations required to handle the
memory required to represent the large value of $|S(s,h)|$), since for each
$h\geq 2$, it suffices to store $|S(s,h-1)|$ after computing it, and use it to
compute $|S(s,h)|$ in constant time, and repeat.

We now come back to $k$-leaf powers, and show that in all the cases that will
be of interest to us, $s$ and $h$ are bounded by a function of $k$.

###### Lemma 3.4

Assume that $G$ is a connected $k$-leaf power and let $X\subseteq V(G)$.
Assume that there is $C\subseteq X$ such that $C$ is a clique and $X\setminus
C\subseteq N_{G}(C)$. Let $T^{*}$ be a $k$-leaf root of $G$, and let
$(T,\sigma)$ be the valued restriction of $T^{*}$ to $X$. Then $\mathcal{T}$
is $k$-bounded and $height(\mathcal{T})\leq 3k$.

  * Proof.

Let us first argue that $\mathcal{T}$ has height at most $3k$. Consider the
tree $T|C$. Then $T|C$ has height at most $k$, as otherwise the members of the
$C$ clique cannot be at distance at most $k$ from each other. Moreover, any
$x\in X\setminus C$ is at distance at most $k$ from some node of $T|C$, as
otherwise $x$ cannot be at distance at most $k$ from any member of $C$. Thus
in $T$, $r(T)$ is at distance at most $k$ from $r(T|C)$, and any leaf in
$X\setminus C$ is at distance at most $2k$ from $r(T|C)$, since the farthest
possible leaf is at distance $k$ below the deepest node of $T|C$. Hence
$height(\mathcal{T})\leq 3k$.

As for $k$-boundedness, suppose that $\mathcal{T}$ is not $k$-bounded. Then
there is some $v\in V(T)\setminus L(T)$ such that $\sigma(v)>k$ but
$\sigma(v)\neq\infty$. Let

$L^{*}_{v}=\bigcup_{v^{\prime}\in ch_{T^{*}}(v)\setminus
ch_{T}(v)}L(T^{*}(v^{\prime}))$

Since $(T,\sigma)$ is the valued restriction of $T^{*}$ to $X$, each leaf
$w\in L^{*}_{v}$ is in $V(G)\setminus X$ and is at distance greater than $k$
from $v$. Moreover, we know that at least one such $w$ exists, as otherwise we
would have $\sigma(v)=\infty$. Then $w$ only has neighbors in $L^{*}_{v}$,
since any other neighbor would require a path of length at most $k$ that
passes through $v$, which is not possible. It follows that every member of
$L^{*}_{v}$ only has neighbors in $L^{*}_{v}$. In other words, $L^{*}_{v}$ is
disconnected from the rest of the graph, a contradiction since $G$ is
connected. Therefore, $\mathcal{T}$ is $k$-bounded.

Note that the $k$ and $3k$ bounds could be slightly improved with a more
detailed analysis, but we would still obtain a power tower behavior for the
number of possible signatures.

###  3.3 Pruning subsets with redundant $k$-leaf root signatures

We now establish the connections between similar structures and signatures.
Let $\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ be a similar
structure of $G$. Unless mentioned otherwise, we will always assume that
$\mathcal{C}=\\{C_{1},\ldots,C_{d}\\},\mathcal{Y}=\\{Y_{1},\ldots,Y_{d}\\}$
and $\mathcal{L}=\\{\ell_{1},\ldots,\ell_{d}\\}$ for some $d$. We will mainly
look at the $k$-leaf roots of the $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ subgraphs.
For $i\in[d]$, let $LR_{z}(C_{i}\cup Y_{i}\cup\\{z\\})$ be the set of all
$k$-leaf roots of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ whose root is the unique
neighbor of $z$ in the tree. Note that $LR_{z}(C_{i}\cup Y_{i}\cup\\{z\\})$
captures every possible $k$-leaf root, except that a specific node is chosen
as the root.

###### Lemma 3.5

Assume that $G$ is a connected $k$-leaf power and let
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ be a similar structure
of $G$. For $i\in[d]$, let $T^{*}\in LR_{z}(C_{i}\cup Y_{i}\cup\\{z\\})$, and
let $\mathcal{T}=(T,\sigma)$ be the valued restriction of $T^{*}$ to
$C_{i}\cup\\{z\\}$. Then $\mathcal{T}$ is $k$-bounded and
$height(\mathcal{T})\leq 3k$.

  * Proof.

Note that $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ is connected, since $Y_{i}$ consists
of connected components that have neighbors in $C_{i}$, and all vertices in
$C_{i}$ have $z$ as a neighbor. Thus, we can apply Lemma 3.4, since $\\{z\\}$
is a clique and $C_{i}\subseteq N_{G}(z)$.

Together, Lemma 3.3 and Lemma 3.5 allow us to bound the number of possible
signatures of $k$-leaf roots of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ subgraphs by
$|S(k,3k)|$, which grows quickly but is a function of $k$ only. The last piece
we need is that all the $(C_{i}\cup Y_{i}\cup\\{z\\})$’s have $k$-leaf roots
with the same signatures.

Let $s\in S(k,3k)$ be a possible signature for a $k$-bounded valued tree of
height at most $3k$, for any layering function. We say that $C_{i}\cup
Y_{i}\cup\\{z\\}$ _accepts_ $s$ if there exists $T^{*}\in LR_{z}(C_{i}\cup
Y_{i}\cup\\{z\\})$ such that $sig_{\ell_{i}}(\mathcal{T})=s$, where
$\mathcal{T}$ is the valued restriction of $T^{*}$ to $C_{i}\cup\\{z\\}$.

We then define

$accept(\mathcal{S},C_{i})=\\{s\in S(k,3k):C_{i}\cup Y_{i}\cup\\{z\\}\mbox{
accepts }s\\}$

It is important to note that by Lemma 3.5, for any $T^{*}\in LR_{z}(C_{i}\cup
Y_{i}\cup\\{z\\})$, $sig_{\ell_{i}}(\mathcal{T})\in S(k,3k)$, and therefore
$sig_{\ell_{i}}(\mathcal{T})\in accept(\mathcal{S},C_{i})$, where
$\mathcal{T}$ is the valued restriction of $T^{*}$ to $C_{i}\cup\\{z\\}$. In
other words, $accept(\mathcal{S},C_{i})$ captures the signature of _every_
$k$-leaf root of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$.

We need one last definition.

###### Definition 3

A similar structure $\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ of
$G$ is called _homogeneous_ if, for each $C_{i},C_{j}\in\mathcal{C}$,
$accept(C_{i})=accept(C_{j})\neq\emptyset$.

For our purposes, we need a homogeneous similar structure of size at least
$3|S(k,3k)|$. If all $k$-leaf roots have large enough arity, this is
guaranteed to exist.

###### Lemma 3.6

Let $G$ be a connected $k$-leaf power. Let $d=3|S(k,3k)|\cdot 2^{|S(k,3k)|}$,
and assume that $G$ admits a $k$-leaf root of arity at least $d+1$. Then there
is a _homogeneous_ similar structure
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ of $G$ such that
$|\mathcal{C}|=3|S(k,3k)|$. Moreover, for each $C_{i}\in\mathcal{C}$,
$|C_{i}|\leq d^{k}$ and $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ has maximum degree at
most $d^{k}$.

  * Proof.

By Lemma 3.1, there exists a similar structure
$\mathcal{S}^{\prime}=(\mathcal{C}^{\prime},\mathcal{Y}^{\prime},z,\mathcal{L}^{\prime})$
of $G$ with $|\mathcal{C}^{\prime}|=d$, with each
$C^{\prime}_{i}\in\mathcal{C}^{\prime}$ having $|C^{\prime}_{i}|\leq d^{k}$
and $G[C^{\prime}_{i}\cup Y^{\prime}_{i}\cup\\{z\\}]$ having maximum degree
$d^{k}$ or less. Denote
$\mathcal{C}^{\prime}=\\{C^{\prime}_{1},\ldots,C^{\prime}_{d}\\}$,
$\mathcal{Y}^{\prime}=\\{Y^{\prime}_{1},\ldots,Y^{\prime}_{d}\\}$ and
$\mathcal{L}^{\prime}=\\{\ell^{\prime}_{1},\ldots,\ell^{\prime}_{d}\\}$. The
problem is that $\mathcal{S}^{\prime}$ might not be homogeneous.

Notice that by Lemma 3.5, for any $C^{\prime}_{i}\in\mathcal{C}$,
$accept(\mathcal{S}^{\prime},C^{\prime}_{i})$ is a subset of $S(k,3k)$. Thus
the number of possible distinct $accept(\mathcal{S},C^{\prime}_{i})$ sets is
$2^{|S(k,3k)|}$. By the pigeonhole principle, the fact that
$|\mathcal{C}^{\prime}|=d=3|S(k,3k)|2^{|S(k,3k)|}$ implies that there is some
$\mathcal{C}\subseteq\mathcal{C}^{\prime}$ such that
$|\mathcal{C}|=3|S(k,3k)|$ and such that
$accept(\mathcal{S}^{\prime},C^{\prime}_{i})=accept(\mathcal{S}^{\prime},C^{\prime}_{j})$
for every $C^{\prime}_{i},C^{\prime}_{j}\in\mathcal{C}$. Note that since $G$
is a $k$-leaf power, none of these $accept$ sets is empty, since each
$G[C_{i}\cup Y_{i}\cup\\{z\\}]$ is a $k$-leaf power.

We thus know that there exists a set of indices $h_{1},\ldots,h_{3|S(k,3k)|}$
such that
$\mathcal{C}=\\{C^{\prime}_{h_{1}},C^{\prime}_{h_{2}},\ldots,C^{\prime}_{h_{3|S(k,3k)|}}\\}$.
Let
$\mathcal{Y}=\\{Y^{\prime}_{h_{1}},Y^{\prime}_{h_{2}},\ldots,Y^{\prime}_{h_{3|S(k,3k)|}}\\}$,
and similarly let
$\mathcal{L}=\\{\ell^{\prime}_{h_{1}},\ell^{\prime}_{h_{2}},\ldots,\ell^{\prime}_{h_{3|S(k,3k)|}}\\}$.
One can easily verify that all properties of a similar structure hold for
$\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ (in particular, all the
$C^{\prime}_{i}\cup Y^{\prime}_{i}$ that were not kept in $\mathcal{C}$ now
join the same connected component as $z$). We have $|\mathcal{C}|=3|S(k,3k)|$.
This similar structure is homogeneous. Finally, the bounds for
$|C_{h_{i}}|\leq d^{k}$ and the maximum degree at most $d^{k}$ for
$G[C_{h_{i}}\cup Y_{h_{i}}\cup\\{z\\}]$ still hold for every $h_{i}$.

We can finally present the main result of this section.

###### Theorem 3.1

Let $G$ be a connected graph. Let
$\mathcal{S}=(\mathcal{C},\mathcal{S},z,\mathcal{L})$ be a homogeneous similar
structure of $G$, with
$\mathcal{C}=\\{C_{1},\ldots,C_{l}\\},\mathcal{Y}=\\{Y_{1},\ldots,Y_{l}\\}$
and $l=3|S(k,3k)|$. Then $G$ is a $k$-leaf power if and only if $G-(C_{1}\cup
Y_{1})$ is a $k$-leaf-power.

  * Proof.

First, note that if $G-(C_{1}\cup Y_{1})$ is not a $k$-leaf-power, then by
heredity, $G$ is not a $k$-leaf-power. We now focus on the other direction of
the statement.

Suppose that $G-(C_{1}\cup Y_{1})$ is a leaf power, and let $R$ be a $k$-leaf
root of $G-(C_{1}\cup Y_{1})$. Assume without loss of generality that $R$ is
rooted at the single neighbor of $z$. The proof is constructive: we show
algorithmically how to insert $C_{1}\cup Y_{1}$ into $R$ to obtain a $k$-leaf
root of $G$.

For $i\in\\{2,\ldots,l\\}$, let $T^{*}_{i}=R|(C_{i}\cup Y_{i}\cup\\{z\\})$,
which is a $k$-leaf root of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$. Furthermore let
$\mathcal{T}_{i}=(T_{i},\sigma_{i})$ be the valued restriction of $T^{*}_{i}$
to $C_{i}\cup\\{z\\}$. Note that $V(T_{i})\subseteq V(T^{*}_{i})\subseteq
V(R)$.

Since $l-1>|S(k,3k)|$, there must be distinct $i,j\in\\{2,\ldots,l\\}$ such
that $sig_{\ell_{i}}(\mathcal{T}_{i})=sig_{\ell_{j}}(\mathcal{T}_{j})$, by the
pigeonhole principle. Assume, without loss of generality, that $i=2$ and $j=3$
(otherwise, simply rename the $C_{i}$’s). Note that since $V(T_{2})\subseteq
V(T_{2}^{*})\subseteq V(R)$, each node of $T_{2}$ and $T^{*}_{2}$ is in $R$.
The same holds for $T_{3}$ and $T^{*}_{3}$. Moreover, all of
$T_{2},T^{*}_{2},T_{3}$ and $T^{*}_{3}$ contain $z$ and hence also contain the
root of $R$. It follows that
$r(T_{2})=r(T^{*}_{2})=r(T_{3})=r(T^{*}_{3})=r(R)$.

Since $accept(\mathcal{S},C_{1}\cup
Y_{1}\cup\\{z\\})=accept(\mathcal{S},C_{2}\cup
Y_{2}\cup\\{z\\})=accept(\mathcal{S},C_{3}\cup Y_{3}\cup\\{z\\})$ by
homogeneity, there exists a $k$-leaf root $T^{*}_{1}$ of $G[C_{1}\cup
Y_{1}\cup\\{z\\}]$, with $r(T^{*}_{1})$ being the parent of $z$, such that
$sig_{\ell_{1}}(\mathcal{T}_{1})=sig_{\ell_{2}}(\mathcal{T}_{2})=sig_{\ell_{3}}(\mathcal{T}_{3})$,
where $\mathcal{T}_{1}=(T_{1},\sigma_{1})$ is the valued restriction of
$T^{*}_{1}$ to $C_{1}\cup\\{z\\}$. Note that $r(T_{1})=r(T^{*}_{1})$, again
because of $z$. We now describe how to insert $T^{*}_{1}$ into $R$, based on
the signature of $\mathcal{T}_{1}$. This is shown in Algorithm 1. By inserting
a subtree $T^{*}_{1}(u)$ as a child of $r$, we mean to add all the nodes and
edges of the $T^{*}_{1}(u)$ tree to $R$, and to add an edge between $r$ and
$r(T^{*}_{1}(u))$.

1

2$insert(r(T^{*}_{1}),r(R))$ //initial call

3

4 Function  _insert( $t,r$)_

5 //$t\in V(T^{*}_{1})$ is the node of $T^{*}_{1}$ we are inserting

6 //$r\in V(R)$ is the node of $R$ we are inserting on

7 foreach  _child $u\in ch_{T^{*}_{1}}(t)\setminus ch_{T_{1}}(t)$_ do

8 Insert the $T^{*}_{1}(u)$ subtree as a child of $r$

9

10 end foreach

11

12 foreach  _child $u\in ch_{T_{1}}(t)$_ do

13 if  _$\exists w\in ch_{T_{1}}(t)\setminus\\{u\\}$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(w))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$_ then

14 Insert the $T^{*}_{1}(u)$ subtree as a child of $r$

15

16 else

17 Let $u_{2}\in ch_{T_{2}}(r)$ such that
$sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$

18 Let $u_{3}\in ch_{T_{3}}(r)$ such that
$sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$

19 if  _$u_{2}\neq u_{3}$_ then

20 Insert the $T^{*}_{1}(u)$ subtree as a child of $r$

21

22 else

23 if  _$u_{2}\neq z$_ then

24 Recursively call $insert(u,u_{2})$

25

26

27

28

29 end foreach

30

31 end

Algorithm 1 Insertion of $T_{1}^{*}$ into $R$.

Let us begin with a bit of intuition on this algorithm. The idea is that
$insert(t,r)$ embeds $T_{1}^{*}(t)$ into $R(r)$, where $t$ should be a node of
$T_{1}$ and $r$ a node of $R$. The initial call says that
$r(T^{*}_{1})=r(T_{1})$ should correspond to $r(R)$ after $T^{*}_{1}$ is
inserted, and the recursive calls make similar correspondences with children
of $r(T^{*}_{1})$ and $r(R)$, recursively. We will maintain the invariant that
at any point, $r\in V(R)\cap V(T_{2})\cap V(T_{3})$, such that
$\mathcal{T}_{2}(r),\mathcal{T}_{3}(r)$ have the same signature as
$\mathcal{T}_{1}(t)$ (we prove this below). Then in any recursion, when $t$
has children $u$ in $T_{1}^{*}$ but not in $T_{1}$, we know that
$T_{1}^{*}(u)$ only has leaves in $Y_{1}$ (line 1). In this case, we just
insert the $T_{1}^{*}(u)$ subtree. The $Y_{i}$ leaves to insert must be at
distance more than $k$ to all of $L(R)$, and the fact that
$\mathcal{T}_{2}(r)$ and $\mathcal{T}_{3}(r)$ have similar subtrees at the $r$
location helps us guarantee it. That is, $\mathcal{T}_{2}(r)$ lets us argue on
the distance relationships between $Y_{1}$ and the leaves in $L(R)\setminus
L(\mathcal{T}_{2}(r))$, and $\mathcal{T}_{3}(r)$ helps us with all
relationships with leaves in $L(\mathcal{T}_{2}(r))$. This idea of
complementarity is the reason we need both $\mathcal{T}_{2}$ and
$\mathcal{T}_{3}$. A similar idea applies when $T_{1}^{*}(u)$ is inserted on
lines 1 and 1. A recursion is needed for each $u\in ch_{T_{1}}(t)$ such that
the node of $T_{2}$ and $T_{3}$ corresponding to $u$ is the same in
$ch_{R}(r)$, since the complementarity trick cannot be applied. Let us proceed
with the details.

Since the algorithm only inserts subtrees as children of nodes of $R$, it is
not hard to see that the modified $R$ will also be a tree. For the rest of the
proof, let $R^{\prime}$ be the tree obtained after the algorithm has
terminated, assuming that the initial call is $insert(r(T^{*}_{1}),r(R))$. The
rest of the proof is dedicated to showing that $R^{\prime}$ is a $k$-leaf root
of $G$. The proof is divided in a series of claims.

###### Claim 1

At any point that $insert(t,r)$ is called and arguments $t$ and $r$ are
received, the following holds:

  * –

$t\in V(T_{1})\setminus L(T_{1})$;

  * –

$r\in V(T_{2})\cap V(T_{3})$;

  * –

$sig_{\ell_{1}}(\mathcal{T}_{1}(t))=sig_{\ell_{2}}(\mathcal{T}_{2}(r))=sig_{\ell_{3}}(\mathcal{T}_{3}(r))$.

  * Proof.

We argue this by induction on the depth of the recursion. As a base case,
consider the initial call with $t=r(T^{*}_{1})$ and $r=r(R)$. We have $t\in
V(T_{1})$ since $r(T^{*}_{1})=r(T_{1})$. To see that $t\notin L(T_{1})$, note
that $|L(T_{1})|=|C_{1}\cup\\{z\\}|\geq 2$ implies that $r(T_{1})$ is not a
leaf itself, since leaves have $0$ children. Thus initially, $t\in
V(T_{1})\setminus L(T_{1})$. Also, we have already argued that
$r=r(R)=r(T_{2})=r(T_{3})$. Moreover, in this initial case,
$sig_{\ell_{1}}(\mathcal{T}_{1}(t))=sig_{\ell_{1}}(\mathcal{T}_{1})=sig_{\ell_{2}}(\mathcal{T}_{2})=sig_{\ell_{2}}(\mathcal{T}_{2}(r))$
and the same holds for $\mathcal{T}_{3}$.

Now, assume that the statement holds for any recursive call of depth $\delta$.
We argue that it also holds for recursive calls at depth $\delta+1$. When a
call at recursion depth $\delta$ with parameters $t$ and $r$ is made, the only
way a deeper recursive call could be made is when line 1 is reached. This
happens when $t$ has a child $u$ in $T_{1}$ such that no other child of $t$ in
$T_{1}$ has the same signature. Since we assume by induction that
$sig_{\ell_{1}}(\mathcal{T}_{1}(t))=sig_{\ell_{2}}(\mathcal{T}_{2}(r))$, by
Lemma 3.2.1, $r$ must also have exactly one child $u_{2}$ in $T_{2}$ such that
$sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$.
By the same argument, $r$ has exactly one child $u_{3}$ in $T_{3}$ such that
$sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$.
In particular, $u_{2}$ and $u_{3}$ as used in the algorithm always exist.

A recursive call is only made if $u_{2}=u_{3}$ and $u_{2}\neq z$, in which
case $u$ and $u_{2}$ are passed to a recursive call. We know that $u\in
V(T_{1})$, and must argue that $u\notin L(T_{1})$. Assume instead that $u$ is
a leaf of $T_{1}$. Since
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))$,
$u_{2}$ would also be a leaf of $T_{2}$ and $u_{3}$ a leaf of $T_{3}$. We have
$L(T_{2})=C_{2}\cup\\{z\\}$ and $L(T_{3})=C_{3}\cup\\{z\\}$. Since $C_{2}$ and
$C_{3}$ are disjoint, only $u_{2}=u_{3}=z$ is possible, but this is a
contradiction since the algorithm explicitly states that line 1 could not be
reached in this case. Hence, $u\notin L(T_{1})$, which proves the first
property of the claim.

The second and third properties of the claim hold for the recursive call
because $u_{2}=u_{3}$, and because they are explicitly chosen to have the same
signature.

We show that to create $R^{\prime}$, the algorithm inserts a subtree that is
leaf-isomorphic to $T^{*}_{1}$. This ensures that distance relationships
between leaves of $T^{*}_{1}$ are the same in $R^{\prime}$.

###### Claim 2

$R^{\prime}|(C_{1}\cup Y_{1}\cup\\{z\\})\simeq_{L}T^{*}_{1}$.

  * Proof.

We prove the claim by induction on the height of $T_{1}(t)$. That is, we show
that for any $t$ and $r$ passed to the algorithm, $R^{\prime}$ contains a
subtree $R^{\prime}_{t}$ that is leaf-isomorphic to $T_{1}^{*}(t)$, and that
the leaf-isomorphism from $T_{1}^{*}(t)$ to $R^{\prime}_{t}$ maps $t$ to $r$.

By Claim 1, $t$ is in $T_{1}$ but not a leaf of $T_{1}$. So as a base case,
consider that the algorithm receives arguments $t$ and $r$, such that
$T_{1}(t)$ is a subtree of $T_{1}$ of height $2$. That is, all the children of
$t$ in $T_{1}$ are leaves (but not necessarily all the children of $t$ in
$T^{*}_{1}$). Consider a child $u\in ch_{T^{*}_{1}}(t)\setminus
ch_{T_{1}}(t)$. Then line 1 ensures that $T_{1}^{*}(u)$ is inserted as a child
subtree of $r$ in $R^{\prime}$. Consider now a child $u\in ch_{T_{1}}(t)$,
which is a leaf by assumption. If some other child $w$ of $T_{1}$ has the same
signature (i.e.
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{1}}(\mathcal{T}_{1}(w))$), line
1 ensures that $u$ is inserted as a child of $r$. Otherwise, there are
$u_{2}\in ch_{T_{2}}(r)$ and $u_{3}\in ch_{T_{3}}(r)$ with the same signature
as $u$, i.e.
$sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))=sig_{\ell_{1}}(\mathcal{T}_{1}(u))$.
As in the previous claim, $u_{2}$ and $u_{3}$ must also be leaves and one of
$u_{2}\neq u_{3}$ or $u_{2}=u_{3}=z$ must hold, because $C_{2}$ and $C_{3}$
are disjoint. If $u_{2}=u_{3}=z$, then $u=z$ as well, since this is the only
leaf with signature $(0)$. In this case, $t=r(T_{1})$ and $r=r(R)$, and the
check that $u_{2}\neq z$ in the algorithm ensures that nothing happens (which
is correct, since $z$ is already a child of $r$). If $u_{2}\neq u_{3}$, $u$ is
added as a child of $r$ on line 1 (which is correct since $u\neq z$). It
follows that all children of $t$ in $T^{*}_{1}$ are children of $r$ in
$R^{\prime}$. Therefore, $R^{\prime}$ contains a subtree leaf-isomorphic to
$T^{*}_{1}(t)$ with $t$ mapped to $r$.

Now assume that $T_{1}(t)$ is a subtree of height greater than $2$. Notice
that for each child $u\in ch_{T^{*}_{1}}(t)$, $T_{1}^{*}(u)$ is inserted as a
child subtree of $r$ in $R^{\prime}$, unless $t$ has no other child with the
same signature as $u$, and there are $u_{2}\in ch_{T_{2}}(r)$ and $u_{3}\in
ch_{T_{3}}(r)$, with $u_{2}=u_{3}$, with the same signature as $u$. As before,
if $u=z$, then $u_{2}=u_{3}=z$ and nothing happens, which is correct.
Otherwise, line 1 is reached and the algorithm is called recursively with
arguments $u$ and $u_{2}$. In this case, we may assume by induction that
$R^{\prime}$ contains a subtree leaf-isomorphic to $T^{*}_{1}(u)$, with the
leaf-isomorphism mapping $u$ to $u_{2}$. Let $U$ be the set of children of $t$
in $T_{1}$ for which line 1 is reached. Notice that for each distinct
$u,u^{\prime}\in U$, $sig_{\ell_{1}}(\mathcal{T}_{1}(u))\neq
sig_{\ell_{1}}(\mathcal{T}_{1}(u^{\prime}))$, since children with a non-unique
signature are inserted on line 1. Moreover, each $u\in U$ is put in
correspondence with a child $u_{2}$ of $r$ with the same signature as $u$,
implying that every $u\in U$ has a distinct correspondent among the children
of $r$. We can therefore conclude that for each $u\in ch_{T^{*}_{1}}(t)$
(other than $z$), either $T^{*}_{1}(u)$ is inserted as a child subtree of $r$,
or $T^{*}_{1}(u)$ is inserted recursively with $u$ being mapped to a unique
child $u_{2}$ or $r$. It follows that $R^{\prime}$ contains a subtree
isomorphic to $T_{1}^{*}(t)$ with $t$ mapped to $r$.

To finish the proof, we observe that the above statement holds for
$t=r(T_{1})=r(T^{*}_{1})$ and $r=r(R)$. Thus $R^{\prime}$ contains a subtree
leaf-isomorphic to $T^{*}_{1}$ with a leaf-isomorphism that maps
$r(T^{*}_{1})$ to $r(R)$.

It remains to argue that distance relationships in $R^{\prime}$ are also
correct for pairs of leaves with one in $C_{1}\cup Y_{1}\cup\\{z\\}$ and the
other in $V(G)\setminus(C_{1}\cup Y_{1}\cup\\{z\\})=L(R)\setminus\\{z\\}$.

###### Claim 3

Let $x\in L(T^{*}_{1})$ and $y\in L(R)\setminus\\{z\\}$. If $xy\in E(G)$, then
$dist_{R^{\prime}}(x,y)\leq k$, and otherwise, $dist_{R^{\prime}}(x,y)>k$.

  * Proof.

We argue that anytime that a leaf of $T^{*}_{1}$ is inserted, the conditions
of the claim are satisfied. Consider any recursion of the algorithm where
parameters $t$ and $r$ are given, and let us focus on the set of leaves of
$T^{*}_{1}$ inserted during that recursion.

Let $u\in ch_{T^{*}_{1}}(t)$ and assume that $T^{*}_{1}(u)$ is inserted as a
child of $r$ in the current recursion. Let $x\in L(T^{*}_{1}(u))$ be an
inserted leaf. We consider two possible cases.

Case 1: $x\in L(T^{*}_{1}(u))\setminus L(T_{1})$. Observe that $x\in
L(T^{*}_{1})\setminus L(T_{1})=(C_{1}\cup
Y_{1}\cup\\{z\\})\setminus(C_{1}\cup\\{z\\})=Y_{1}$, and thus $x$ has no
neighbors in $L(R)$. Thus we must argue that $x$ is at distance more than $k$
to any leaf $y$ of $R$. Let $x^{\prime}$ be the lowest ancestor of $x$ in
$T^{*}_{1}$ (i.e. farthest from the root) such that $x^{\prime}\in V(T_{1})$.
Note that if $T_{1}^{*}(u)$ was inserted on line 1, then $x^{\prime}=t$ since
$u\notin V(T_{1})$ but $t\in V(T_{1})$ by Claim 1, and otherwise, $x^{\prime}$
is a descendant of $u$. In any case, $x^{\prime}$ is in $V(T_{1}(t))$. Recall
that $\mathcal{T}_{1}=(T_{1},\sigma_{1})$, and that $\sigma_{1}(x^{\prime})$
is the minimum distance from $x^{\prime}$ to a leaf descending from a node in
$ch_{T^{*}_{1}}(x^{\prime})\setminus ch_{T_{1}}(x^{\prime})$. We note that $x$
is such a leaf, and thus
$dist_{T^{*}_{1}}(x,x^{\prime})\geq\sigma_{1}(x^{\prime})$.

Also recall that by Claim 1, $r\in V(T_{2})\cap V(T_{3})$ and
$sig_{\ell_{1}}(\mathcal{T}_{1}(t))=sig_{\ell_{2}}(\mathcal{T}_{2}(r))=sig_{\ell_{3}}(\mathcal{T}_{3}(r))$.
By Lemma 3.2.3, there is $x_{2}^{\prime}\in V(T_{2}(r))$ such that
$dist_{T_{1}}(x^{\prime},t)=dist_{T_{2}}(x_{2}^{\prime},r)$ and
$sig_{\ell_{1}}(\mathcal{T}_{1}(x^{\prime}))=sig_{\ell_{2}}(\mathcal{T}_{2}(x_{2}^{\prime}))$.
In particular, $\sigma_{1}(x^{\prime})=\sigma_{2}(x_{2}^{\prime})$. Since
$\mathcal{T}_{2}$ is the valued restriction of $T^{*}_{2}$ to
$C_{2}\cup\\{z\\}$, this implies that there exists $x_{2}\in
L(T_{2}^{*})\setminus L(T_{2})=Y_{2}$, descending from a node in
$ch_{T^{*}_{2}}(x_{2}^{\prime})\setminus ch_{T_{2}}(x_{2}^{\prime})$, such
that
$dist_{T^{*}_{2}}(x_{2},x_{2}^{\prime})=dist_{R}(x_{2},x_{2}^{\prime})=\sigma_{2}(x_{2}^{\prime})=\sigma_{1}(x_{1}^{\prime})\leq
dist_{T^{*}_{1}}(x,x^{\prime})$. Since the distance from $x_{2}^{\prime}$ to
$r$ is the same as the distance from $x^{\prime}$ to $t$, this also implies
that $dist_{R}(x_{2},r)\leq dist_{T_{1}^{*}}(x,t)$. Now, let $y\in
L(R)\setminus(C_{2}\cup Y_{2})$. We have $x_{2}y\notin E(G)$ and obtain

$\displaystyle k<dist_{R}(x_{2},y)$ $\displaystyle\leq
dist_{R}(x_{2},r)+dist_{R}(r,y)$ $\displaystyle\leq
dist_{T_{1}^{*}}(x,t)+dist_{R}(r,y)$
$\displaystyle=dist_{R^{\prime}}(x,r)+dist_{R^{\prime}}(r,y)$
$\displaystyle=dist_{R^{\prime}}(x,y)$

where, for the last two equalities, we used the fact that $T^{*}_{1}(u)$ was
inserted as a child subtree of $r$, and thus that the path from $x$ to $y$ in
$R^{\prime}$ must first go to $r$, and then to $y$. This shows that $x$ has
the correct distance to all $y\in L(R)\setminus(C_{2}\cup Y_{2})$. It remains
to handle the vertices in $C_{2}\cup Y_{2}$. For the moment, let us instead
consider $y\in L(R)\setminus(C_{3}\cup Y_{3})$. We can apply the same argument
as above, but using $T_{3}$ instead. That is, by the equality of the
signatures, there is some $x_{3}\in Y_{3}$ such that
$dist_{T^{*}_{3}}(x_{3},r)=dist_{R}(x_{3},r)\leq dist_{T^{*}_{1}}(x,t)$. By
repeating the above argument, we deduce that for any $y\in
L(R)\setminus(C_{3}\cup Y_{3})$, $dist_{R}(x_{3},y)>k$, which in turn implies
$dist_{R^{\prime}}(x,y)>k$. In particular, this holds for any $y\in C_{2}\cup
Y_{2}$. We have therefore shown that $dist_{R^{\prime}}(x,y)>k$ for any $y\in
L(R)$, and thus that $x$ is correctly inserted.

Case 2: $x\in L(T_{1})$. In this case, $u\in ch_{T_{1}}(t)$ and $T_{1}^{*}(u)$
must have been inserted as a child of $r$ on line 1 or on line 1. Note that
$x\in C_{1}$ ($x=z$ is not possible since $z$ is not reinserted in
$R^{\prime}$).

Let us define $u_{2}\in ch_{T_{2}}(r)$ and $u_{3}\in ch_{T_{3}}(r)$ to handle
both cases. If $T^{*}_{1}(u)$ is inserted on line 1, then define $u_{2}$ and
$u_{3}$ as in the algorithm. In this case, we must have $u_{2}\neq u_{3}$. If
instead $T^{*}_{1}(u)$ is inserted on line 1, then there is $w\in
ch_{T_{1}}(t)$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{1}}(\mathcal{T}_{1}(w))$ and
$w\neq u$. By Lemma 3.2.2, there exist distinct $u_{2},u_{2}^{\prime}\in
ch_{T_{2}}(r)$ and $u_{3},u_{3}^{\prime}\in ch_{T_{3}}(r)$ such that
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}^{\prime}))=sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))=sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}^{\prime}))$.
Observe that at least one of $u_{2}\neq u_{3}$ or $u_{2}\neq u^{\prime}_{3}$
holds. Assume without loss of generality that $u_{2}\neq u_{3}$.

In either case, note that $u_{2}$ and $u_{3}$ are defined so that $u_{2}\neq
u_{3}$, $u_{2}\in ch_{T_{2}}(r)$, $u_{3}\in ch_{T_{3}}(r)$,
$sig_{\ell_{1}}(\mathcal{T}_{1}(u))=sig_{\ell_{2}}(\mathcal{T}_{2}(u_{2}))=sig_{\ell_{3}}(\mathcal{T}_{3}(u_{3}))$.

By Lemma 3.2.3, there exist $x_{2}\in L(T_{2}(u_{2}))$ such that
$dist_{T_{2}^{*}}(x_{2},u_{2})=dist_{T_{1}}(x,u)$ and
$sig_{\ell_{1}}(\mathcal{T}_{1}(x))=sig_{\ell_{2}}(\mathcal{T}_{2}(x_{2}))$.
Since the signature of a leaf is just its layer, this implies that
$\ell_{1}(x)=\ell_{2}(x_{2})$. Also note that
$dist_{R^{\prime}}(x,r)=dist_{R^{\prime}}(x_{2},r)$. Similarly, there exists
$x_{3}\in L(T_{3})$ such that $\ell_{1}(x)=\ell_{3}(x_{3})$ and such that
$dist_{T_{3}^{*}}(x_{3},u_{3})=dist_{T_{1}}(x,u)$, i.e. that
$dist_{R^{\prime}}(x,r)=dist_{R^{\prime}}(x_{3},r)$. Also note that the paths
from $x$ to $r$, $x_{2}$ to $r$ and $x_{3}$ to $r$ only intersect at $r$,
since $u,u_{2}$ and $u_{3}$ are all distinct nodes of $R^{\prime}$.

First consider $y\in L(R)\setminus(C_{2}\cup Y_{2}\cup C_{3}\cup Y_{3})$.
Since the layers are all equal, by Property 4b of similar structures, $xy\in
E(G)\Leftrightarrow x_{2}y\in E(G)\Leftrightarrow x_{3}y\in E(G)$. If $y$ is
not a descendant of $u_{2}$, then the path from $x_{2}$ to $y$ goes through
$r$, implying $dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{2},y)$. If $y$ is
not a descendant of $u_{3}$, then the path from $x_{3}$ to $y$ goes through
$r$, implying $dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{3},y)$. Since
$u_{2}\neq u_{3}$, $y$ cannot be a descendant of both $u_{2}$ and $u_{3}$, and
so at least one of $dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{2},y)$ or
$dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{3},y)$ must hold. If $xy\in
E(G)$, then $x_{2}y,x_{3}y\in E(G)$ and $dist_{R^{\prime}}(x_{2},y)\leq k$,
$dist_{R^{\prime}}(x_{3},y)\leq k$ both hold, implying
$dist_{R^{\prime}}(x,y)\leq k$. Similarly, if $xy\notin E(G)$, then
$x_{2}y,x_{3}y\notin E(G)$ and, in the same manner, and
$dist_{R^{\prime}}(x_{2},y)>k$, $dist_{R^{\prime}}(x_{3},y)>k$ both hold,
implying $dist_{R^{\prime}}(x,y)>k$.

Now consider $y\in C_{2}\cup Y_{2}$. Assume that $xy\notin E(G)$. Then by
Property 4b, $x_{3}y\notin E(G)$. If $y$ is not a descendant of $u_{3}$, then
the path from $x_{3}$ to $y$ goes through $r$ and
$dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{3},y)>k$. If $y$ is a descendant
of $u_{3}$, then we have

$k<dist_{R^{\prime}}(x_{3},y)\leq
dist_{R^{\prime}}(x_{3},r)+dist_{R^{\prime}}(r,y)=dist_{R^{\prime}}(x,r)+dist_{R^{\prime}}(r,y)$

and, since
$dist_{R^{\prime}}(x,r)+dist_{R^{\prime}}(r,y)=dist_{R^{\prime}}(x,y)$, the
distance from $x$ to $y$ is correctly above $k$.

Assume that $xy\in E(G)$. Again by Property 4b, $x_{3}y\in E(G)$. Note that
$y\in Y_{2}$ is not possible since $Y_{2}$ only has neighbors in $C_{2}\cup
Y_{2}$. So we know that $y\in C_{2}$, and hence $\ell_{2}(y)$ is defined. If
$y$ is not a descendant of $u_{3}$, the usual argument applies, since the path
from $x_{3}$ to $y$ goes through $r$, implying
$dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{3},y)\leq k$. Suppose that $y$ is
a descendant of $u_{3}$. By Property 4d of similar structures, we must have
$\ell_{1}(x)+\ell_{2}(y)\leq k$ (because if $\ell_{1}(x)+\ell_{2}(y)>k$, $xy$
could not be an edge). As $\ell_{1}(x)=\ell_{2}(x_{2})$, we have
$\ell_{2}(x_{2})+\ell_{2}(y)\leq k$ as well. Luckily, Property 4c is
applicable to vertices in the same $C_{i}$, and so $x_{2}y\in E(G)$. The path
from $x_{2}$ to $y$ goes through $r$, and thus
$dist_{R^{\prime}}(x,y)=dist_{R^{\prime}}(x_{2},y)\leq k$. This covers the
case $y\in C_{2}\cup Y_{2}$.

The last remaining case is $y\in C_{3}\cup Y_{3}$. This can be handled exactly
as the previous case, but swapping the roles of $x_{2}$ and $x_{3}$. This
completes the proof, as we have covered every possible case for a leaf
inserted by the algorithm, at any point.

To conclude the proof, we can argue that $R^{\prime}$ is a $k$-leaf-power of
$G$ by looking at every pair of vertices of $G$. First note that by Claim 2,
all the leaves of $T^{*}_{1}$ are present in $R^{\prime}$, and so
$V(G)=L(R^{\prime})$. Let $x,y\in V(G)$, with $x\neq y$. If $x,y\in
V(G)\setminus(C_{1}\cup Y_{1})$, then $x,y\in L(R)$ and, since
$dist_{R}(x,y)=dist_{R^{\prime}}(x,y)$, we know that $xy\in
E(G)\Leftrightarrow dist_{R^{\prime}}(x,y)\leq k$. If $x,y\in C_{1}\cup
Y_{1}\cup\\{z\\}$, then by Claim 2, $R^{\prime}|(C_{1}\cup Y_{1}\cup\\{z\\})$
is leaf-isomorphic to $T^{*}_{1}$. Since $T^{*}_{1}$ is a $k$-leaf root of
$G[C_{1}\cup Y_{1}\cup\\{z\\}]$, we know that $xy\in E(G)\Leftrightarrow
dist_{R^{\prime}}(x,y)\leq k$. Finally, if $x\in C_{1}\cup Y_{1}$ and $y\in
V(G)\setminus(C_{1}\cup Y_{1})$, Claim 3 ensures that $xy\in
E(G)\Leftrightarrow dist_{R^{\prime}}(x,y)\leq k$. Therefore, $R^{\prime}$ is
a $k$-leaf-power of $G$.

##  4 Computing the set of accepted signatures

We have not yet discussed how to find an homogeneous similar structure
$\mathcal{S}$. Since $k$ is fixed, it is not too hard to find a similar
structure of $G$ with the properties of Lemma 3.6, if one exists. It suffices
to brute-force every combination of $3|S(k,3k)|$ subsets of $V(G)$ of size at
most $d^{k}$ in $G$ to find the $C_{i}$’s, and check that all similar
structure properties hold. In particular, each $G[C_{i}\cup Y_{i}\cup\\{z\\}]$
has maximum degree at most $d^{k}$, so using Lemma 2.2, we can check whether
this is a $k$-leaf power. However, this is not enough, since homogeneity
requires enumerating all accepted signatures for the found $C_{i}\cup
Y_{i}\cup\\{z\\}$, in order to construct $accept(\mathcal{S},C_{i}\cup
Y_{i}\cup\\{z\\})$ and ensure that they are all equal. We will achieve this
through a tree decomposition of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$.

Let us assume that $\mathcal{S}=(\mathcal{C},\mathcal{Y},z,\mathcal{L})$ is a
similar structure satisfying $|\mathcal{C}|=3|S(k,3k)|$, with each
$|C_{i}|\leq d^{k}$ such that $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ has maximum
degree at most $d^{k}$. We want to compute $accept(\mathcal{S},C_{i})$ for
each $i\in[d]$. This can be achieved using a slightly more general result.

###### Lemma 4.1

Let $G$ be a connected graph of maximum degree at most $d^{k}$ and let $z\in
V(G)$. Then in time $O(n\cdot d^{8k}\cdot f(k)^{3})$, where $n=|V(G)|$ and
$f(k)=d^{4kd^{4k}}\cdot(k+2)^{d^{4k}}$, one can enumerate the set of all
valued trees $\mathbb{T}=\\{\mathcal{T}_{1},\ldots,\mathcal{T}_{l}\\}$, up to
value-isomorphism, such that $\mathcal{T}_{i}\in\mathbb{T}$ if and only if
there exists a $k$-leaf root $T^{*}$ of $G$ such that (1) $T^{*}$ is rooted at
the parent of $z$; and (2) $\mathcal{T}_{i}$ is the valued restriction of
$T^{*}$ to $N_{G}[z]$.

To see why Lemma 4.1 allows us to compute $accept(\mathcal{S},C_{i})$, recall
that the latter contains the signature of every $\mathcal{T}$ that is the
valued restriction of $T^{*}$ to $C_{i}\cup\\{z\\}$, where $T^{*}$ is a
$k$-leaf root of $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ with the root as the parent
of $z$. Since $N_{G[C_{i}\cup Y_{i}\cup\\{z\\}]}[z]=C_{i}\cup\\{z\\}$, we can
pass $G[C_{i}\cup Y_{i}\cup\\{z\\}]$ and $z$ to the above lemma. By taking the
signature of every $\mathcal{T}_{i}$ returned, we obtain
$accept(\mathcal{S},C_{i})$. Note that the lemma does not deal with layers, so
the leaf sets of the desired $\mathcal{T}_{i}$’s are $N_{G}[z]$ (instead of
integers representing layers as in the previous section).

The rest of this section is dedicated to the proof of Lemma 4.1. We will write
$N(v)$ and $N[v]$ instead of $N_{G}(v)$ and $N_{G}[v]$, respectively, with the
understanding that $G$ is the graph stated in Lemma 4.1. Likewise, for
$X\subseteq V(G)$, we write $N(X)$ and $N[X]$ instead of $N_{G}(X)$ and
$N_{G}[X]$, respectively. The proof is based on the tree decomposition of $G$
and uses a relatively standard dynamic programming algorithm. Recall that
given a graph $G$, a nice tree decomposition of $G$ is a tree
$B=(V_{B},E_{B})$ in which (1) $B_{i}\subseteq V(G)$ for each $B_{i}\in
V_{B}$; (2) for each $uv\in E(G)$, there is some $B_{i}\in V_{B}$ with $u,v\in
B_{i}$; (3) for each $u\in V(G)$, the set of $B_{i}$’s that contain $u$ form a
connected subgraph of $B$. Moreover, each $B_{i}\in V_{B}$ can be one of four
types: $B_{i}\in L(B)$, in which case $B_{i}=\\{v\\}$ for some $v\in V(G)$;
$B_{i}$ is an introduce node, in which case $B_{i}$ has a single child $B_{j}$
with $B_{j}=B_{i}\setminus\\{v\\}$ for some $v\in V(G)$; $B_{i}$ is a forget
node, in which case $B_{i}$ has a single child $B_{j}$ with
$B_{i}=B_{j}\setminus\\{v\\}$ for some $v\in B_{j}$; $B_{i}$ is a join node,
in which case $B_{i}$ has two children $B_{l},B_{r}$ and $B_{i}=B_{l}=B_{r}$.
The width of $B$ is $max_{B_{i}\in V_{B}}(|B_{i}|-1)$, and the treewidth of
$G$ is the minimum width of a nice tree decomposition of $G$.

We note that [16] also use a tree decomposition based algorithm. However, it
does not seem adaptable directly for our purposes, since it is not guaranteed
to return every structure of every $k$-leaf root of the given graph, and it
does not maintain the $\sigma$ information that we need.

For our algorithm, we first check whether $G$ is chordal: if not, we know by
Lemma 2.1 that $G$ is not a $k$-leaf power and we can return
$\mathbb{T}=\emptyset$. Otherwise, since $G$ has maximum degree at most
$d^{k}$ and is chordal, $G$ has clique number at most $d^{k}+1$ and thus
treewidth at most $d^{k}$. The properties of the tree decomposition that we
will need are summarized here.

###### Lemma 4.2

Let $G$ be a connected chordal graph of maximum degree at most $d^{k}$, and
let $z\in V(G)$. Then there exists a nice tree decomposition $B=(V_{B},E_{B})$
of $G$ with $O(|V(G)|)$ nodes and of width at most $d^{k}$, such that
$r(B)=\\{z\\}$ and such that each $B_{i}\in V_{B}$ is a non-empty clique.

We omit the proof, which uses standard arguments. The idea is that connected
chordal graphs admit a tree decomposition in which every bag is a non-empty
clique (see e.g. [1]). We can take such a decomposition, root it at a bag
containing $z$, and apply the standard transformation to make it nice (if the
root is not exactly $\\{z\\}$, it can be made $\\{z\\}$ by adding enough
forget nodes above).

Let $B=(V_{B},E_{B})$ be a nice tree decomposition that satisfies all the
properties of Lemma 4.2. For $B_{i}\in V_{B}$, we will denote by
$V_{i}=\bigcup_{B_{j}\in B(B_{i})}B_{j}$ the set of vertices of $G$ found in
the bags at $B_{i}$ or its descendants. Note that for each $V_{i}$, $G[V_{i}]$
is connected. This can be seen inductively. First, it is true for leaves. At
introduce nodes, we introduce a vertex $v$ connected to the rest of $B_{i}$,
so $G[V_{i}]$ remains connected. At forget nodes, $V_{i}$ is the same as
$V_{j}$ and remains connected. At join nodes, $V_{i}$ is the union of the
vertices of two connected graphs that intersect at $B_{i}$, and thus remains
connected.

Let $B_{i}$ be a bag of $B$ and let $(T,\sigma)$ be a valued tree. We say that
$(T,\sigma)$ is _valid for_ $B_{i}$ if it satisfies the following conditions:

  * •

$L(T)=N[B_{i}]\cap V_{i}$;

  * •

there exists a $k$-leaf root $T^{*}$ of $G[V_{i}]$ such that $(T,\sigma)$ is
the valued restriction of $T^{*}$ to $N[B_{i}]\cap V_{i}$, and such that
$r(T)=r(T^{*})$.

Since $r(B)=\\{z\\}$, our goal is to obtain the set _all_ of valued trees that
are valid for $r(B)$, as this will yield the valued restrictions to $N[z]$
required by Lemma 4.1. Note that unlike in the previous section, there is no
requirement on the root of $T$ or $T^{*}$ being the parent of $z$. The
requirement that $r(T)=r(T^{*})$ is there to ensure that the root we see in
the restricted $T$ is also the root in $T^{*}$ (since otherwise, the
restriction could hide nodes of $T^{*}$ above the root of $T$). This is
important for our purposes, since it allows us to safely look at the valid
valued trees for $r(B)=\\{z\\}$ whose root is the parent of $z$. Also note
that it is tempting to define $(T,\sigma)$ as the valued restriction of
$T^{*}$ to $B_{i}$, and not bother with $N[B_{i}]\cap V_{i}$. This does not
quite work — the inclusion of the neighborhood is necessary to retain enough
information to update the $\sigma(w)$ values accurately (see proof for
details).

For the rest of this section, we shall slightly abuse notation and treat two
valued trees that are value-isomorphic as _the same_. In other words, we
assume the understanding that two valued trees are _distinct_ only if they are
not value-isomorphic.

We first show that the number of distinct $(T,\sigma)$ valued trees to
consider is bounded (with a crude estimate), meaning that we can enumerate all
candidates.

###### Lemma 4.3

Let $B_{i}\in V(B)$ and let $(T,\sigma)$ be a valid valued tree for $B_{i}$.
Then $T$ has at most $d^{4k}$ nodes and is $k$-bounded. Consequently, there
are at most $d^{4kd^{4k}}\cdot(k+2)^{d^{4k}}$ possible valid valued trees for
$B_{i}$ (up to value-isomorphism).

  * Proof.

Let $T$ be a valid valued tree for $B_{i}$. Then $L(T)=N[B_{i}]\cap V_{i}$.
First recall that $|B_{i}|\leq d^{k}+1$. Since $G$ has maximum degree at most
$d^{k}$, $N[B_{i}]\leq d^{k}+1+(d^{k}+1)\cdot d^{k}\leq 2d^{2k}$, assuming
$d\geq 2$. Let $T^{\prime}$ be the unique tree such that $T^{\prime}$ has no
node with only one child, and such that $T$ is a subdivision of $T^{\prime}$.
In other words, $T^{\prime}$ is obtained from $T$ by contracting every node of
degree $2$ (except the root). Then $T^{\prime}$ has at most
$|L(T^{\prime})|\leq 2d^{2k}$ internal nodes and at most $4d^{2k}$ edges.
Moreover, each edge $uv$ of $T^{\prime}$ represents a path
$(u,x_{1},\ldots,x_{l},v)$ in $T$, where $u,x_{1},\ldots,x_{l}$ have one
child. Note that $l\leq k$, as otherwise, the leaves in $T(v)$ would be at
distance more than $k$ from the other leaves, whereas $N[B_{i}]\cap V_{i}$ is
a connected subgraph of $G$. We may thus assume that each edge of $T^{\prime}$
corresponds to at most $k$ additional nodes in $T$. Therefore, $T$ has at most
$2d^{2k}$ leaves and at most $4kd^{2k}$ internal nodes, for a total of at most
$(4k+2)d^{2k}\leq d^{4k}$ nodes (assuming $d\geq 2$).

The number of trees with at most $d^{4k}$ nodes is bounded by
$(d^{4k})^{d^{4k}}=d^{4kd^{4k}}$. We know that $(T,\sigma)$ is $k$-bounded by
Lemma 3.4 (since $N[B_{i}]\cap V_{i}$ consists of a clique $B_{i}$ and a
subset of $N[B_{i}]$). Thus, for each possible tree, each of the at most
$d^{4k}$ internal nodes can receive a value in $\\{0,1,\ldots,k,\infty\\}$,
i.e. $k+2$ possibilities. Thus the number of valued trees is bounded by
$d^{4kd^{4k}}\cdot(k+2)^{d^{4k}}$.

We now describe a dynamic programming recurrence over $B$ that constructs a
set $Q[B_{i}]$ for each $B_{i}$. The set $Q[B_{i}]$ must contain _every_ valid
valued tree for $B_{i}$, i.e. $\mathcal{T}\in Q[B_{i}]$ if and only if
$\mathcal{T}$ is valid for $B_{i}$. We assume that we are enumerating each
candidate valued tree from the above lemma, and must decide whether to put it
in $Q[B_{i}]$ or not. For convenience, denote
$\mathcal{N}[B_{i}]:=N[B_{i}]\cap V_{i}$ for the rest of this section.

  * •

_Leaf node_. Let $B_{i}=\\{v\\}$ be a leaf of $B$. Then $(T,\sigma)\in
Q[B_{i}]$ if and only if $T$ is the single node $v$ (and $\sigma$ has an empty
domain).

  * •

_Introduce node_. Let $B_{i}$ be an introduce node with child
$B_{j}=B_{i}\setminus\\{v\\}$. Then put $(T,\sigma)\in Q[B_{i}]$ if and only
if there exists $(T_{j},\sigma_{j})\in Q[B_{j}]$ such that all the following
conditions are satisfied:

    * –

$T|\mathcal{N}[B_{j}]\simeq_{L}T_{j}$. Let $\mu$ be the leaf-isomorphism from
$T|\mathcal{N}[B_{j}]$ to $T_{j}$;

    * –

for every internal node $w\in V(T|\mathcal{N}[B_{j}])$,
$\sigma(w)=\sigma_{j}(\mu(w))$ and for every internal node $w\in V(T)\setminus
V(T|\mathcal{N}[B_{j}])$, $\sigma(w)=\infty$;

    * –

for each $w\in L(T)\setminus\\{v\\}$, $vw\in E(G)$ if and only if
$dist_{T}(v,w)\leq k$;

    * –

for each internal node $w\in V(T)$, $dist_{T}(v,w)+\sigma(w)>k$.

  * •

_Forget node_. Let $B_{i}$ be a forget node with child
$B_{j}=B_{i}\cup\\{v\\}$. Then put $(T,\sigma)\in Q[B_{i}]$ if and only if
there exists $(T_{j},\sigma_{j})\in Q[B_{j}]$ such that

    * –

$r(T_{j})$ has at least two distinct children $u,v$ such that $T_{j}(u)$ and
$T_{j}(v)$ both have a leaf in $\mathcal{N}[B_{i}]$;

    * –

$T\simeq_{L}T_{j}|\mathcal{N}[B_{i}]$. Let $\mu$ be the leaf-isomorphism from
$T$ to $T_{j}|\mathcal{N}[B_{i}]$;

    * –

for each $w\in V(T)\setminus L(T)$, let $C(w)=\\{c\in
ch_{T_{j}}(\mu(w)):\mu^{-1}(c)=\emptyset\\}$, and let

$\displaystyle\hat{L}=\bigcup_{c\in C(w)}L(T_{j}(c))\quad\mbox{ and
}\quad\hat{I}=\\{w\\}\cup\bigcup_{c\in C(w)}V(T_{j}(c))\setminus\hat{L}$

Then

$\displaystyle\sigma(w)=\min\begin{cases}\min_{v\in\hat{I}}\sigma_{j}(\mu(v))+dist_{T_{j}}(\mu(w),\mu(v))\\\
\min_{l\in\hat{L}}dist_{T_{j}}(\mu(w),l)\end{cases}$

  * •

_Join node_. Let $B_{i}$ be a join node of $B$ with children $B_{l}$ and
$B_{r}$, where $B_{i}=B_{l}=B_{r}$. Then $(T,\sigma)\in Q[B_{i}]$ if and only
if there exists $(T_{l},\sigma_{l})\in Q[B_{l}]$ and $(T_{r},\sigma_{r})\in
Q[B_{r}]$ that satisfy:

    * –

$T|\mathcal{N}[B_{l}]\simeq_{L}T_{l}$. Let $\mu_{l}$ be the leaf-isomorphism
from $T|\mathcal{N}[B_{l}]$ to $T_{l}$;

    * –

$T|\mathcal{N}[B_{r}]\simeq_{L}T_{r}$. Let $\mu_{r}$ be the leaf-isomorphism
from $T|\mathcal{N}[B_{r}]$ to $T_{r}$;

    * –

for each $w\in V(T)\setminus L(T)$, we have
$\sigma(w)=\min(\sigma_{l}(\mu_{l}(w)),\sigma_{r}(\mu_{r}(w)))$ if $w$ is in
both $T|\mathcal{N}[B_{l}]$ and $T|\mathcal{N}[B_{r}]$,
$\sigma(w)=\sigma_{l}(\mu_{l}(w))$ if $w$ is only in $T|\mathcal{N}[B_{l}]$,
and $\sigma(w)=\sigma_{r}(\mu_{r}(w))$ otherwise;

    * –

for each distinct $u,v\in L(T)$, $uv\in E(G)$ if and only if
$dist_{T}(u,v)\leq k$;

    * –

for each $u\in\mathcal{N}[B_{l}]\setminus B_{i}$ and each internal node $w\in
V(T|\mathcal{N}[B_{r}])$, $dist_{T}(u,w)+\sigma_{r}(\mu_{r}(w))>k$. Likewise,
for each $u\in\mathcal{N}[B_{r}]\setminus B_{i}$ and each $w\in
V(T|\mathcal{N}[B_{l}])$, $dist_{T}(u,w)+\sigma_{l}(\mu_{l}(w))>k$;

    * –

for each internal node $w_{l}\in V(T|\mathcal{N}[B_{l}])$ and each internal
node $w_{r}\in V(T|\mathcal{N}[B_{r}])$,
$\sigma_{l}(\mu_{l}(w_{l}))+dist_{T}(w_{l},w_{r})+\sigma_{r}(\mu_{r}(w_{r}))>k$.

###### Lemma 4.4

Consider the recurrence given above. For any bag $B_{i}$, $(T,\sigma)$ is a
valid valued restriction for $B_{i}$ if and only if $(T,\sigma)\in Q[B_{i}]$
(up to value-isomorphism).

  * Proof.

The proof is by induction on the depth of $B_{i}$. As a base case, assume that
$B_{i}$ is a leaf. Then $B_{i}=\\{v\\}$, $\mathcal{N}[B_{i}]=\\{v\\}$, and
$(T,\sigma)$ with $T$ containing $v$ only is the only possible valid valued
tree. Hence the leaf case is correct.

Now consider the induction step. Let $B_{i}\in V(B)\setminus L(B)$ and assume
that the statement is correct for all descendants of $B_{i}$. We prove the two
directions of the statement separately.

($\Rightarrow$) : suppose that $(T,\sigma)$ is a valid valued restriction for
$B_{i}$. Then there exists a $k$-leaf-power $T^{*}$ of $G[V_{i}]$ such that
$(T,\sigma)$ is the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$, and
such that $r(T)=r(T^{*})$. We must argue that $(T,\sigma)$ is in $Q[B_{i}]$.

##### Introduce node.

Suppose that $B_{i}$ is an introduce node, with child
$B_{j}=B_{i}\setminus\\{v\\}$. Notice that by the properties of tree
decompositions, $N(v)\cap V_{i}=B_{i}\setminus\\{v\\}$ (since $B_{i}$ is a
clique).

Let $T^{*}_{j}=T^{*}|V_{j}$, noting that $V_{j}=V_{i}\setminus\\{v\\}$.
Moreover, $T^{*}_{j}$ is a $k$-leaf root of $G[V_{j}]$, since distances
between leaves do not change when taking a restriction. Let
$(T_{j},\sigma_{j})$ be the valued restriction of $T^{*}_{j}$ to
$\mathcal{N}[B_{j}]$.

We would like to use induction and argue that $(T_{j},\sigma_{j})\in
Q[B_{j}]$, but for that we need $r(T_{j})=r(T^{*}_{j})$, which is not
immediate. Indeed, it is possible that $r(T_{j})\neq r(T^{*}_{j})$, which
happens if and only if in $T^{*}_{j}$, some ancestor of $r(T_{j})$ (other than
itself) has descending leaves of $V_{j}$ not in $\mathcal{N}[B_{j}]$. We argue
that this does not occur. Let $L^{\prime}=V_{j}\setminus
L(T^{*}_{j}(r(T_{j})))$, and assume that $L^{\prime}$ is non-empty. For that
to happen, observe that $v\notin L(T^{*}(r(T_{j})))$. This is because
$r(T)=r(T^{*})$, and if $v$ was a descendant of $r(T_{j})$ in $T^{*}$, then
the root of $T=T^{*}|\mathcal{N}[B_{i}]$ would still be $r(T_{j})\neq
r(T^{*})$. Thus in $T^{*}$, the path from $r(T_{j})$ to $v$ goes “above”
$r(T_{j})$. Also note that no member of $L^{\prime}$ has a neighbor in
$B_{j}$, as otherwise this member of $L^{\prime}$ would be included in
$T_{j}=T^{*}_{j}|\mathcal{N}[B_{j}]$. Moreover, members of $L^{\prime}$ are
not neighbors of $v$. Let $u\in L^{\prime}$ be at minimum distance from
$r(T_{j})$ in $T^{*}_{j}$. Then $u$ is also at minimum distance from
$r(T_{j})$ in $T^{*}$, among all leaves in $L^{\prime}$. Let
$d_{u}=dist_{T^{*}}(u,r(T_{j}))$ and $d_{v}=dist_{T^{*}}(v,r(T_{j}))$. First
assume that $d_{u}\leq d_{v}$. We know that $B_{j}\neq\emptyset$ and that
$B_{i}$ is a clique, implying that there is $v^{\prime}\in B_{j}$ such that
$vv^{\prime}\in E(G)$ and that $dist_{T^{*}}(v,v^{\prime})\leq k$. Since
$v^{\prime}\in B_{j}$, $v^{\prime}$ descends from $r(T_{j})$ and thus the path
from $v$ to $v^{\prime}$ passes through $r(T_{j})$ in $T^{*}$. Then $d_{u}\leq
d_{v}$ implies $dist_{T^{*}}(u,v^{\prime})\leq k$. This is not possible since
$u$ has no neighbor in $B_{j}$. Suppose instead that $d_{u}>d_{v}$. Note that
$u$ must have at least one neighbor $u^{\prime}$ in $L(T^{*}(r(T_{j})))$
(otherwise, since $u$ is at minimum distance from $r(T_{j})$, this would imply
that no member of $L^{\prime}$ has a neighbor outside of $L^{\prime}$, and
thus contradict that $G[V_{i}]$ is connected). Note that $u^{\prime}\notin
B_{j}$ because $u$ has no neighbor in $B_{j}$. The path from $u$ to
$u^{\prime}$ in $T^{*}$ goes through $r(T_{j})$, and $u^{\prime}$ is at
distance at most $k$ from $u$. Since $d_{v}<d_{u}$, $u^{\prime}v\in E(G)$, a
contradiction since all the neighbors of $v$ are in $B_{j}$. We deduce that
$L^{\prime}$ is empty. Hence, we can safely assume that
$r(T^{*}_{j})=r(T_{j})$. Therefore, by induction, $(T_{j},\sigma_{j})\in
Q[B_{j}]$. It remains to show that $(T_{j},\sigma_{j})$ satisfies all
conditions of introduce nodes.

Let us argue that $T|\mathcal{N}[B_{j}]=T_{j}$. Note that
$V(T|\mathcal{N}[B_{j}])$ is the set of all vertices of $T^{*}$ on the path
between two leaves in $\mathcal{N}[B_{j}]$, and $V(T_{j})$ the set of all
vertices of $T^{*}_{j}$ between two leaves in $\mathcal{N}[B_{j}]$. This makes
it clear that $T|\mathcal{N}[B_{j}]=T_{j}$, but let us argue this for
completeness. Consider two vertices $x,y\in\mathcal{N}[B_{j}]$, and let
$P_{xy}$ be the path of $T^{*}$ from $x$ to $y$. All vertices of $P_{xy}$ must
be in $T$ since $x,y\in\mathcal{N}[B_{i}]$, and all vertices of $P_{xy}$ are
in $T|\mathcal{N}[B_{j}]$ since $x,y\in\mathcal{N}[B_{j}]$. All vertices of
$P_{xy}$ must be in $T^{*}_{j}$ since $x,y\in V_{j}$, and must also all be in
$T_{j}$ since $x,y\in\mathcal{N}[B_{j}]$. Since this holds for every
$x,y\in\mathcal{N}[B_{j}]$, we obtain $T|\mathcal{N}[B_{j}]=T_{j}$. We also
have the leaf-isomorphism $\mu(w)=w$ for all $w\in V(T|\mathcal{N}[B_{j}])$
since $T|\mathcal{N}[B_{j}]$ and $T_{j}$ share the same set of vertices of
$T^{*}$. We shall use $w$ and $\mu(w)$ interchangeably, since they represent
the same node.

We next justify $\sigma(w)=\infty$ for every internal node $w\in V(T)\setminus
V(T_{j})$. There are two possible cases. First suppose that $r(T)\neq
r(T_{j})$. Recall that $T$ and $T_{j}$ differ only by the $v$ leaf. Thus,
$r(T)\neq r(T_{j})$ happens if and only if $r(T^{*})$ has at least two
distinct two children, such that one leads to $v$ and the other leads to
$r(T_{j})$. In this situation, $w\in V(T)\setminus V(T_{j})$ must be a node on
one of these two paths (excluding $r(T_{j})$ and $v$). As we have already
argued, all leaves of $T^{*}_{j}$ are descendants of $r(T_{j})$ in $T^{*}$.
Therefore, $w$ cannot have a descendant from $T^{*}_{i}$ that is not in
$V_{i}\setminus\mathcal{N}[B_{i}]$. If follows that $\sigma(w)=\infty$
represents the correct distance information for $w$.

The second case is when $r(T)=r(T_{j})$. In this case, the only difference
between $T_{j}$ and $T$ is that there is some vertex $x\in V(T_{j})$ and a
path $P=(x_{1},\ldots,x_{l}=v)$ such that $x_{1}\in ch_{T}(x)$ and
$x_{1}\notin V(T_{j})$. In other words, $T$ was obtained from $T_{j}$ by
appending the path leading to $v$ under some node $x$. It follows that only
the nodes $x_{1},\ldots,x_{l-1}$ are internal nodes in $T$ but not in $T_{j}$.
The recurrence assumes that $\sigma(x_{i})=\infty$ for each $x_{i}$. Again, we
must argue that in $T^{*}$, no such $x_{i}$ has a descending leaf in
$L(T^{*})\setminus\mathcal{N}[B_{i}]$, i.e. that $L(T^{*}(x_{1}))=\\{v\\}$.
Assume that this is not the case. Let $u=\neq v$ be a leaf of $T^{*}(x_{1})$
at minimum distance from $x$. This is similar to the previous situation. We
have that $u\notin\mathcal{N}[B_{j}]$ since $x_{1}$ is not in $T_{j}$. Let
$d_{u}=dist_{T^{*}}(u,x)$ and $d_{v}=dist_{T^{*}}(v,x)$. Assume that
$d_{u}\leq d_{v}$. Then the path from $v$ to any $v^{\prime}\in B_{j}$ (which
exists) passes through $x$, implying that $uv^{\prime}\in E(G)$, a
contradiction. Assume instead that $d_{u}>d_{v}$. There must exist
$u^{\prime}\in N(u)$ such that $u^{\prime}\notin L(T^{*}(x_{1}))$ (otherwise,
no leaf in $L(T^{*}(x_{1}))$ has a neighbor in $G$ outside of
$L(T^{*}(x_{1}))$ and $G[V_{i}]$ is not connected). Note that
$u^{\prime}\notin B_{j}$. The path from $u$ to $u^{\prime}$ goes through $x$,
implying that $vu^{\prime}\in E(G)$, a contradiction. Thus in $T^{*}$, each
$x_{i}$ only has $v$ has a leaf descendant. This justifies putting
$\sigma(x_{i})=\infty$ for each $x_{i}$.

Let $w\in V(T|\mathcal{N}[B_{j}])$ be an internal node that is in both $T$ and
$T_{j}$. Let $w^{\prime}\in ch_{T^{*}}(w)\setminus ch_{T}(w)$. Then
$w^{\prime}$ only leads to leaves in
$V_{i}\setminus\mathcal{N}[B_{i}]=V_{j}\setminus\mathcal{N}[B_{j}]$ and must
also be in $ch_{T^{*}_{j}}(w)\setminus ch_{T_{j}}(w)$. Conversely, let
$w^{\prime\prime}\in ch_{T^{*}_{j}}(w)\setminus ch_{T_{j}}(w)$. Then in
$T^{*}_{j}$, $w^{\prime\prime}$ only leads to leaves in
$V_{j}\setminus\mathcal{N}[B_{j}]$. We have a problem if $w^{\prime\prime}\in
ch_{T}(w)$. Again, since $T$ and $T_{j}$ differ only by $v$, this is only
possible if $w^{\prime\prime}$ has $v$ as a descendant. But as we argued in
the previous paragraph, $w^{\prime\prime}$ would not have descendants in
$V_{j}\setminus\mathcal{N}[B_{j}]$ (here, $w^{\prime\prime}$ plays the same
role as $x_{1}$). Therefore, we may assume that $w^{\prime\prime}\in
ch_{T^{*}}(w)\setminus ch_{T}(w)$. Since the set of hidden children of $w$ is
the same in either $T$ and $T_{j}$, we deduce that $\sigma(w)=\sigma_{j}(w)$
represents the correct distance information.

Also, since $T=T^{*}|\mathcal{N}[B_{i}]$ and $T^{*}$ is a $k$-leaf root of
$G$, it is clear that for all $w\in L(T)\setminus\\{v\\}$, $vw\in
E(G)\Leftrightarrow dist_{T}(v,w)\leq k$. Moreover, since we have argued that
$\sigma(w)$ is correct for each $w\in V(T)\setminus L(T)$, we must have
$dist_{T}(v,w)+\sigma(w)>k$, as otherwise $v$ would have a neighbor outside of
$\mathcal{N}[B_{i}]$. This agrees with the recurrence, and it will therefore
put $(T,\sigma)$ in $Q[B_{i}]$.

##### Forget node.

Suppose that $B_{i}$ is a forget node, with child $B_{j}=B_{i}\cup\\{v\\}$.
Note that $T^{*}$ is a $k$-leaf root of $G[V_{j}]$. Let $(T_{j},\sigma_{j})$
be the valued restriction of $T^{*}$ to $\mathcal{N}[B_{j}]$. Because
$\mathcal{N}[B_{i}]\subseteq\mathcal{N}[B_{j}]$, the root of $T_{j}$ satisfies
$r(T_{j})=r(T)=r(T^{*})$. Then by induction, $(T_{j},\sigma_{j})\in Q[B_{j}]$.

Note that $r(T)$ must have two distinct children with descendants in
$\mathcal{N}[B_{i}]$, and thus the same holds for $T_{j}$, as in the
recurrence. Because $T=T^{*}|\mathcal{N}[B_{i}]$ and
$T_{j}=T^{*}|\mathcal{N}[B_{j}]$, it is not hard to see that
$T=T_{j}|\mathcal{N}[B_{i}]$. The leaf-isomorphism is $\mu(w)=w$ for all $w\in
V(T)$ because $T$ and $T_{j}|\mathcal{N}[B_{i}]$ use the same set of vertices.

Now let $w\in V(T)\setminus L(T)$. Let $L^{*}=\bigcup_{c\in
ch_{T^{*}}(w)\setminus ch_{T}(w)}L(T^{*}(c))$. To find the minimum distance
from $w$ to a leaf $u\in L^{*}$, we must first consider all leaves of
$L(T_{j})$ that descend from a child $c\in ch_{T_{j}}(w)\setminus ch_{T}(w)$,
in which case $\mu^{-1}(c)=\emptyset$. The minimum distance to such a leaf is
given by $\min_{l\in\hat{L}}dist_{T_{j}}(\mu(w),l)$ in the recurrence. We must
also consider all leaves of $V_{j}\setminus L(T_{j})$ that descend from a
child $c\in ch_{T^{*}}(w)\setminus ch_{T}(w)$. Consider such a leaf $u$ at
minimum distance from $w$, and let $w^{\prime}$ be the lowest ancestor of $u$
that is in $V(T_{j})$ (which exists, since $w$ is an ancestor of $u$). Then
either $w^{\prime}=w$ if $u$ descends from some child $c\in
ch_{T^{*}}(w)\setminus ch_{T_{j}}(w)$, in which case the distance is
$\sigma_{j}(w)$, or $w^{\prime}$ is a descendant of some child of $w$ in
$ch_{T_{j}}(w)\setminus ch_{T}(w)$, in which case this distance is
$\sigma_{j}(w^{\prime})+dist_{T_{j}}(w,w^{\prime})$. In any case, the distance
to such a $u$ is given by the expression
$\min_{v\in\hat{I}}\sigma_{j}(\mu(v))+dist_{T_{j}}(\mu(v),\mu(w))$ in the
recurrence. Since the recurrence takes the minimum over all possibilities, it
will take the minimum possible distance, and thus $\sigma(w)$ describes the
same distance as in the recurrence.

##### Join node.

Suppose that $B_{i}$ is a join node, with children $B_{l}=B_{r}=B_{i}$. In
this part of the proof, we will use $B_{i},B_{l}$ and $B_{r}$ interchangeably,
but use $B_{l}$ and $B_{r}$ when we want to emphasize that we are dealing with
the “left” or “right” side of the decomposition. Let $T^{*}_{l}=T^{*}|V_{l}$
and $T^{*}_{r}=T^{*}|V_{r}$. Let $(T_{l},\sigma_{l})$ be the valued
restriction of $T^{*}_{l}$ to $\mathcal{N}[B_{l}]$. Similarly, let
$(T_{r},\sigma_{r})$ be the valued restriction of $T^{*}_{r}$ to
$\mathcal{N}[B_{r}]$.

As in the introduce case, we would like to argue that $r(T_{l})=r(T^{*}_{l})$.
Assume that this is not the case, and that $r(T_{l})\neq r(T^{*}_{l})$. Then
$L(T^{*}(r(T^{*}_{l})))\setminus L(T^{*}(r(T_{l})))$ is non-empty. Let $u\in
V_{l}$ be one of those leaves, and choose $u$ that has minimum distance to
$r(T_{l})$. Notice that $u\notin\mathcal{N}[B_{l}]$, and thus $u\in
V_{l}\setminus\mathcal{N}[B_{l}]$. Moreover, since $r(T^{*})=r(T)$, $r(T^{*})$
has at least two distinct children with a descendant in $\mathcal{N}[B_{i}]$.
Let $w$ be such a child, chosen so that $w$ does not have $r(T_{l})$ as a
descendant. Let $v\in L(T^{*}(w))\cap\mathcal{N}[B_{i}]$. Note that
$v\notin\mathcal{N}[B_{l}]$ by the choice of $w$. Thus,
$v\in\mathcal{N}[B_{i}]\setminus\mathcal{N}[B_{l}]=N(B_{r})\cap V_{r}$. In
particular, $v\in V_{r}\setminus B_{i}$, and it is not hard to see that by the
properties of tree decompositions, this implies $u\neq v$.

Now, let $d_{v}=dist_{T^{*}}(v,r(T_{l}))$ and
$d_{u}=dist_{T^{*}}(u,r(T_{l}))$. Assume that $d_{u}\leq d_{v}$. We know that
$v$ has a neighbor $v^{\prime}$ in $B_{i}$, and that all of $B_{i}$ descend
from $r(T_{l})$ in $T^{*}$. Thus the path from $v$ to $v^{\prime}$ passes
through $r(T_{l})$. Since $dist_{T^{*}}(v,v^{\prime})\leq k$, the assumption
$d_{u}\leq d_{v}$ means that $dist_{T^{*}}(u,v^{\prime})\leq k$, and thus
$uv^{\prime}\in E(G)$. This is a contradiction since
$u\notin\mathcal{N}[B_{i}]$. Assume that $d_{u}>d_{v}$. One can see that $u$
must have a neighbor $u^{\prime}$ in $L(T^{*}(r(T_{l})))$ (if not, by the
choice of $u$, all the leaves in $L(T^{*}(r(T^{*}_{l})))\setminus
L(T(r(T_{l})))$ have only neighbors in $L(T^{*}(r(T^{*}_{l})))\setminus
L(T(r(T_{l})))$, contradicting that $G[V_{i}]$ is connected). Recall that
$u\in V_{l}\setminus\mathcal{N}[B_{l}]$, and so $u^{\prime}$ must be in
$V_{l}\setminus B_{l}$. Moreover, $d_{u}>d_{v}$ implies that $vu^{\prime}\in
E(G)$. But $v\in V_{r}\setminus B_{i}$ and $u^{\prime}\in V_{l}\setminus
B_{l}$, which is not allowed by the properties of tree decompositions.

We deduce that $r(T_{l})=r(T^{*}_{l})$. By a symmetric argument,
$r(T_{r})=r(T^{*}_{r})$. By induction, $(T_{l},\sigma_{l})\in Q[B_{l}]$ and
$(T_{r},\sigma_{r})\in Q[B_{r}]$.

Since $T=T^{*}|\mathcal{N}[B_{i}]$ and
$\mathcal{N}[B_{l}]\subseteq\mathcal{N}[B_{i}]$, it is not hard to see that
$T|\mathcal{N}[B_{l}]=T_{l}$, with the leaf-isomorphism $\mu_{l}(w)=w$ for
$w\in V(T|\mathcal{N}[B_{l}])$. Likewise, $T|\mathcal{N}[B_{r}]=T_{r}$, with
the leaf-isomorphism $\mu_{r}(w)=w$ for $w\in V(T|\mathcal{N}[B_{r}])$. We
shall not distinguish $w$ and $\mu_{l}(w),\mu_{r}(w)$ since they refer to the
same node.

Let $w\in V(T)\setminus L(T)$. Note that $w$ is in at least one of
$T|\mathcal{N}[B_{l}]$ or $T|\mathcal{N}[B_{r}]$ since $w$ has a descendant in
at least one of $\mathcal{N}[B_{l}]$ or $\mathcal{N}[B_{r}]$. If $w$ is in
both $T|\mathcal{N}[B_{l}]$ and $T|\mathcal{N}[B_{r}]$, then
$\sigma(w)=\min(\sigma_{l}(w),\sigma_{r}(w))$ holds because all leaves of
$V_{i}\setminus\mathcal{N}[B_{i}]$ that have $w$ as their first ancestor in
$T$ are either leaves of $V_{l}\setminus\mathcal{N}[B_{l}]$ or
$V_{r}\setminus\mathcal{N}[B_{r}]$, and $\sigma_{l}(w)$, $\sigma_{r}(w)$ cover
both cases.

Suppose that $w$ is in $T|\mathcal{N}[B_{l}]$ but not in
$T|\mathcal{N}[B_{r}]$. If all leaves in $T^{*}(w)$ are in $V_{l}$, having
$\sigma(w)=\sigma_{l}(w)$ as in the recurrence is correct. Suppose that
$L(T^{*}(w))\setminus V_{l}$ is non-empty, and choose $u$ among those of
minimum distance to $w$. Note that $u\notin\mathcal{N}[B_{r}]$, as otherwise
$w$ would be in $T|\mathcal{N}[B_{r}]$. Thus $u\in
V_{r}\setminus\mathcal{N}[B_{r}]$. We repeat the same type of argument one
last time (this is a tedious endeavor, but unfortunately, the cases appear to
be not similar enough to handle them with a reusable claim). Let $v\in
L(T(w))$. We note that $v\in\mathcal{N}[B_{l}]\setminus B_{l}=N(B_{l})\cap
V_{l}$, since otherwise $w$ would be in $T|\mathcal{N}[B_{r}]$. In particular,
$uv\notin E(G)$, by the properties of tree decompositions. Let
$d_{u}=dist_{T^{*}}(u,w)$ and $d_{v}=dist_{T^{*}}(v,w)$. Assume that
$d_{u}\leq d_{v}$. Let $v^{\prime}\in N(v)\cap B_{l}$, which we know exists.
Note that $v^{\prime}\in B_{r}$ as well. Thus, the path from $v$ to
$v^{\prime}$ in $T^{*}$ must go through $w$, since otherwise
$T|\mathcal{N}[B_{r}]$ would contain $w$. Then, $d_{u}\leq d_{v}$ implies that
$dist_{T^{*}}(u,v^{\prime})\leq k$, a contradiction since $u$ has no neighbor
in $B_{l}$. Assume instead that $d_{u}>d_{v}$. By the choice of $u$, there
must exist $u^{\prime}\in V_{r}\setminus B_{r}$ such that $uu^{\prime}\in
E(G)$, and such that $u^{\prime}\notin L(T^{*}(w))$ (otherwise, $u$ cannot be
connected to the rest of the graph). This implies that $vu^{\prime}\in E(G)$.
This is not possible by the properties of tree decompositions, since $v\in
N(B_{l})\subseteq V_{l}\setminus B_{i}$, and $u^{\prime}\in V_{r}\setminus
B_{i}$. We deduce that $w$ has no descending leaf in
$V_{r}\setminus\mathcal{N}[B_{r}]$, and that $\sigma(w)=\sigma_{l}(w)$ is
correct.

Suppose that $w$ is in $T|\mathcal{N}[B_{r}]$ but not in
$T|\mathcal{N}[B_{l}]$. A symmetric argument justifies that
$\sigma(w)=\sigma_{r}(w)$.

The fact that for $u,v\in L(T)$, $uv\in E(G)\Leftrightarrow dist_{T}(u,v)\leq
k$ follows from the fact that $T=T^{*}|\mathcal{N}[B_{i}]$ and that $T^{*}$ is
a $k$-leaf root of $G[V_{i}]$.

Now let $u\in\mathcal{N}[B_{l}]\setminus B_{i}$ and take an internal node
$w\in V(T|\mathcal{N}[B_{r}])$. We note that $u\in V_{l}\setminus B_{i}$.
Moreover in $T^{*}(w)$, there is a leaf $v$ of
$V_{r}\setminus\mathcal{N}[B_{r}]$ at distance $\sigma_{r}(w)$ from $w$. It
follows that $uv\notin E(G)$, and thus that
$dist_{T^{*}}(u,w)+\sigma_{r}(w)>k$. This implies that
$dist_{T}(u,w)+\sigma_{r}(w)>k$. A symmetric argument justifies the same
property for $u\in\mathcal{N}[B_{r}]\setminus B_{i}$.

Finally, let $w_{l}\in V(T|\mathcal{N}[B_{l}])$ and $w_{r}\in
V(T|\mathcal{N}[B_{r}])$. Then any leaf of
$T^{*}(w_{l})\setminus\mathcal{N}[B_{i}]$ must be at distance more than $k$ to
any leaf of $T^{*}(w_{r})\setminus\mathcal{N}[B_{i}]$. This justifies
$\sigma_{l}(w_{l})+dist_{T}(w_{l},w_{r})+\sigma_{r}(w_{r})>k$.

($\Leftarrow$) Suppose that $(T,\sigma)\in Q[B_{i}]$. We must argue that there
is a $k$-leaf root $T^{*}$ of $G[V_{i}]$, with $r(T^{*})=r(T)$, such that
$(T,\sigma)$ is the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$.

##### Introduce node.

Let $B_{i}$ be an introduce node with child $B_{j}=B_{i}\setminus\\{v\\}$.
Then there exists $(T_{j},\sigma_{j})\in Q[B_{j}]$ that satisfies the
properties of the recurrence. Let $\mu$ be the leaf-isomorphism from
$T|\mathcal{N}[B_{j}]$ to $T_{j}$. By induction, there is a $k$-leaf power
$T^{*}_{j}$ of $G[V_{j}]=G[V_{i}\setminus\\{v\\}]$ such that
$(T_{j},\sigma_{j})$ is the valued restriction of $T^{*}_{j}$ to
$\mathcal{N}[B_{j}]$, and such that $r(T^{*}_{j})=r(T_{j})$.

We can construct a $k$-leaf root $T^{*}$ of $G[V_{i}]$ as follows. For each
$w\in V(T|\mathcal{N}[B_{j}])$, let $U(w)=ch_{T^{*}_{j}}(\mu(w))\setminus
ch_{T_{j}}(\mu_{j}(w))$. Then for each $u\in U(w)$, add the $T^{*}_{j}(u)$
subtree as a child of $w$ in $T$. Because $r(T^{*}_{j})=r(T_{j})$, every leaf
in $V_{j}\setminus\mathcal{N}[B_{j}]$ gets inserted. In essence, we simply add
the subtrees of $T^{*}_{j}$ that $T$ is missing at the locations indicated by
$T_{j}$.

We claim that $T^{*}$ meets all the requirements for $(T,\sigma)$ to be valid.
We note that $r(T^{*})=r(T)$ since in our construction, we started with $T$,
and only added subtrees under some of its internal nodes (thus, we have not
accidentally “raised” the root in $T^{*}$). Let us argue that $(T,\sigma)$ is
the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$. Notice that
$T=T^{*}|\mathcal{N}[B_{i}]$, since $L(T)=\mathcal{N}[B_{i}]$, and to obtain
$T^{*}$ we took $T$ and only added extra subtrees under its existing nodes.
Moreover, it is not hard to see that $T^{*}|V_{j}\simeq_{L}T^{*}_{j}$. This is
because we started with $T$ such that $T|\mathcal{N}[B_{j}]\simeq_{L}T_{j}$,
and we added the missing subtrees of $T^{*}_{j}$ on the vertices of
$T|\mathcal{N}[B_{j}]$ at the appropriate locations.

Consider $w\in V(T)\setminus L(T)$ and let us argue that $\sigma(w)$
represents the correct distance to a hidden leaf under $w$. First assume that
$w\notin V(T|\mathcal{N}[B_{j}])$. Then one can see from the construction that
we never insert subtrees under $w$, and hence $\sigma(w)=\infty$ represents
the correct distance. Assume instead that $w\in V(T|\mathcal{N}[B_{j}])$. Then
our insertion procedure only adds the leaves descending from children in
$ch_{T^{*}_{j}}(\mu(w))\setminus ch_{T_{j}}(\mu(w))$ under $w$. The
$\sigma_{j}(\mu(w))$ quantity gives the minimum distance from $\mu(w)$ to such
an inserted leaf and in this case, the recurrence specifies that
$\sigma(w)=\sigma_{j}(\mu(w))$, which is correct.

Let us now argue that $T^{*}$ is a $k$-leaf root of $G[V_{i}]$. Because
$T^{*}|V_{j}\simeq_{L}T^{*}_{j}$, for each $x,y\in V_{j}$, $xy\in
E(G)\Leftrightarrow dist_{T^{*}}(x,y)\leq k$. As for $v$, we know by the
recurrence that for each $w\in\mathcal{N}[B_{i}]$, $vw\in E(G)\Leftrightarrow
dist_{T}(v,w)=dist_{T^{*}}(v,w)\leq k$. For any $w\in
V_{i}\setminus\mathcal{N}[B_{i}]$, let $w^{\prime}$ be the lowest ancestor of
$w$ in $T^{*}$ such that $w^{\prime}\in V(T)$, which exists since
$r(T)=r(T^{*})$. The recurrence ensures that
$dist_{T}(v,w^{\prime})+\sigma(w^{\prime})>k$, and thus that
$dist_{T^{*}}(v,w)=dist_{T}(v,w^{\prime})+dist_{T^{*}}(w^{\prime},w)>k$. It
follows that $T^{*}$ is a $k$-leaf root of $G[V_{i}]$.

##### Forget node.

Let $B_{i}$ be a forget node with child $B_{j}=B_{i}\cup\\{v\\}$. Then there
exists $(T_{j},\sigma_{j})\in Q[B_{j}]$ that satisfies the properties of the
recurrence. Let $\mu$ be the leaf-isomorphism from $T$ to
$T_{j}|\mathcal{N}[B_{i}]$.

By induction, there is a $k$-leaf-power $T^{*}_{j}$ of $G[V_{j}]$ such that
$(T_{j},\sigma_{j})$ is the valued restriction of $T^{*}_{j}$ to
$\mathcal{N}[B_{j}]$, and whose root is $r(T^{*}_{j})=r(T_{j})$. Since
$V_{j}=V_{i}$, $T^{*}_{j}$ is also a $k$-leaf root of $G[V_{i}]$. Let us note
that since the recurrence requires $r(T_{j})$ to have two children with
descending leaves in $\mathcal{N}[B_{i}]$, we have
$\mu(r(T))=r(T_{j})=r(T_{j}^{*})$. We want to argue that $T$ is the valued
restriction of $T^{*}_{j}$ to $\mathcal{N}[B_{i}]$. Strictly speaking, $V(T)$
is not a subset of $V(T^{*}_{j})$, so we cannot say that $T$ is the valued
restriction of $T^{*}_{j}$ to $\mathcal{N}[B_{i}]$ (recall that valued
restrictions require usage of same set of nodes). The simplest solution is to
construct a new $k$-leaf root $T^{*}$ “around” $T$.

For each $w\in V(T)$, let $C(w)=\\{c\in
ch_{T_{j}}(\mu(w)):\mu^{-1}(w)=\emptyset\\}$. Moreover, let $C^{*}(w)=\\{c\in
ch_{T^{*}_{j}}(\mu(w))\setminus ch_{T_{j}}(\mu(w))\\}$. Then for each $u\in
C(w)\cup C^{*}(w)$, add the $T^{*}_{j}(u)$ subtree as a child of $w$ in $T$.
Because $\mu(r(T))=r(T_{j})=r(T^{*}_{j})$, we know that every leaf of
$V_{j}\setminus\mathcal{N}[B_{i}]$ is inserted by this procedure. Moreover, it
is not hard to see that $T^{*}\simeq_{L}T^{*}_{j}$, since we add all the
missing subtrees to $T$ at the appropriate locations specified by $T_{j}$.
Hence, $T^{*}$ is a $k$-leaf root of $G[V_{i}]$. It remains to argue that
$(T,\sigma)$ is the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$.

Since $T^{*}$ is obtained from $T$ by inserting child subtrees under the nodes
of $T$, we have $T=T^{*}|\mathcal{N}[B_{i}]$ and $r(T)=r(T^{*})$. Now let
$w\in V(T)\setminus L(T)$. Then in $T^{*}$, consider the minimum distance from
$w$ to a leaf in $u\in V_{i}\setminus\mathcal{N}[B_{i}]$ that descends from a
node in $ch_{T^{*}}(w)\setminus ch_{T}(w)$. Because
$T^{*}\simeq_{L}T^{*}_{j}$, this is identical to the $\Rightarrow$ direction
of forget nodes. That is, the $u$ leaf is either in $L(T_{j})\setminus L(T)$,
in which case $dist_{T^{*}}(w)=\min_{l\in\hat{L}}dist_{T_{j}}(\mu(w),l)$ as in
the recurrence, or this leaf is not in $T_{j}$. In the latter case, $u$ has
some $w^{\prime}$ as its lowest ancestor in $T_{j}$, and the distance to $u$
is given by $dist_{T_{j}}(\mu(w),w^{\prime})+\sigma_{j}(w^{\prime})$. The
value of $\sigma(w)$ should be the minimum of all possibilities, as in the
recurrence. Thus $(T,\sigma)$ is indeed the valued restriction of $T^{*}$ to
$\mathcal{N}[B_{i}]$.

##### Join node.

Let $B_{i}$ be a join node with children $B_{l},B_{r}$, with
$B_{i}=B_{l}=B_{r}$. Then there exist $(T_{l},\sigma_{l})\in Q[B_{l}]$ and
$(T_{r},\sigma_{r})\in Q[B_{r}]$ that satisfy the properties of the
recurrence. Let $\mu_{l}$ and $\mu_{r}$ be the leaf-isomorphisms from
$T|\mathcal{N}[B_{l}]$ to $T_{l}$, and from $T|\mathcal{N}[B_{r}]$ to $T_{r}$,
respectively. By induction, there is a $k$-leaf root $T^{*}_{l}$ of $G[V_{l}]$
such that $(T_{l},\sigma_{l})$ is the valued restriction of $T^{*}_{l}$ to
$\mathcal{N}[B_{l}]$, with $r(T^{*}_{l})=r(T_{l})$. Likewise, there is a
$k$-leaf root $T^{*}_{r}$ of $G[V_{r}]$ such that $(T_{r},\sigma_{r})$ is the
valued restriction of $T^{*}_{r}$ to $\mathcal{N}[B_{r}]$, with
$r(T^{*}_{r})=r(T_{r})$.

We can construct $T^{*}$ as follows. For each $w\in V(T|\mathcal{N}[B_{l}])$,
let $U_{l}(w)=ch_{T^{*}_{l}}(\mu_{l}(w))\setminus ch_{T_{l}}(\mu_{l}(w))$.
Then for each $u\in U_{l}(w)$, add the $T^{*}_{l}(u)$ subtree as a child of
$w$ in $T$. Because $r(T^{*}_{l})=r(T_{l})$, every leaf in
$V_{l}\setminus\mathcal{N}[B_{l}]$ gets inserted. Similarly, for each $w\in
V(T|\mathcal{N}[B_{l}])$, let $U_{r}(w)=ch_{T^{*}_{r}}(\mu_{r}(w))\setminus
ch_{T_{r}}(\mu_{r}(w))$. Then for each $u\in U_{r}(w)$, add the $T^{*}_{r}(u)$
subtree as a child of $w$ in $T$. Again, every leaf in
$V_{r}\setminus\mathcal{N}[B_{r}]$ gets inserted.

We claim that $T^{*}$ meets all the requirements for $(T,\sigma)$ to be valid.
We note that $r(T^{*})=r(T)$ since in our construction, we started with $T$,
and only added subtrees under some of its internal nodes. Let us argue that
$(T,\sigma)$ is the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$.
Notice that $T=T^{*}|\mathcal{N}[B_{i}]$, since $L(T)=\mathcal{N}[B_{i}]$, and
to obtain $T^{*}$ we took $T$ and only added extra subtrees under its existing
nodes. Moreover, it is not hard to see that $T^{*}|V_{l}\simeq_{L}T^{*}_{l}$.
This is because we started with $T$ such that
$T|\mathcal{N}[B_{l}]\simeq_{L}T_{l}$, and we added the missing subtrees of
$T^{*}_{l}$ on the vertices of $T|\mathcal{N}[B_{l}]$ at the appropriate
locations. Similarly, $T^{*}|V_{r}\simeq_{L}T^{*}_{r}$.

Consider $w\in V(T)\setminus L(T)$ and let us argue that $\sigma(w)$
represents the correct distance to a hidden leaf under $w$. If $w\in
V(T|\mathcal{N}[B_{l}])$ but is not is $V(T|\mathcal{N}[B_{r}])$, then our
insertion procedure only adds the leaves descending from children in
$ch_{T^{*}_{l}}(\mu_{l}(w))\setminus ch_{T_{l}}(\mu_{l}(w))$ under $w$. The
$\sigma_{l}(\mu_{l}(w))$ quantity gives the minimum distance from $\mu_{l}(w)$
to such an inserted leaf and in this case, the recurrence specifies that
$\sigma(w)=\sigma_{l}(\mu_{l}(w))$, which is correct. The same argument
applies if $w\in V(T|\mathcal{N}[B_{r}])$ but is not is
$V(T|\mathcal{N}[B_{l}])$. If $w\in V(T|\mathcal{N}[B_{l}])\cap
V(T|\mathcal{N}[B_{r}])$, we have inserted both leaves under $\mu_{l}(w)$ from
$T^{*}_{l}$ and leaves under $\mu_{r}(w)$ from $T^{*}_{r}$. In this case,
$\sigma(w)=\min(\sigma_{l}(\mu_{l}(w)),\sigma_{r}(\mu_{r}(w)))$ correctly
represent the minimum distance from $w$ to such a leaf. It follows that
$(T,\sigma)$ is the valued restriction of $T^{*}$ to $\mathcal{N}[B_{i}]$.

Let us now argue that $T^{*}$ is a $k$-leaf root of $G[V_{i}]$. Because
$T^{*}|V_{l}\simeq_{L}T^{*}_{l}$, for each $u,v\in V_{l}$, $uv\in
E(G)\Leftrightarrow dist_{T^{*}}(u,v)\leq k$. Similarly,
$T^{*}|V_{r}\simeq_{L}T^{*}_{r}$ implies that for each $u,v\in V_{r}$, $uv\in
E(G)\Leftrightarrow dist_{T^{*}}(u,v)\leq k$.

Now, consider $u\in\mathcal{N}[B_{l}]$ and $v\in\mathcal{N}[B_{r}]$. The fact
that $uv\in E(G)\Leftrightarrow dist_{T^{*}}(u,v)\leq k$ is explicitly stated
in the recurrence, using the fact that $T^{*}|\mathcal{N}[B_{i}]=T$.

Next, consider $u\in\mathcal{N}[B_{l}]$ and $v\in
V_{r}\setminus\mathcal{N}[B_{r}]$. Then $uv\notin E(G)$, by the properties of
tree decompositions. Let $w$ be the lowest ancestor of $v$ in $T^{*}$ such
that $w\in V(T|\mathcal{N}[B_{r}])$ (which must exist, by the construction of
$T^{*}$, since the subtree containing $v$ was appended under a node of
$T|\mathcal{N}[B_{r}]$ at some point). In $T^{*}$, the path from $u$ to $v$
must pass through $w$. We have
$dist_{T^{*}}(u,v)=dist_{T}(u,w)+dist_{T^{*}}(w,v)\geq
dist_{T}(u,w)+\sigma_{r}(w)$, which is strictly greater than $k$, by the
properties of the recurrence. The symmetric argument holds for
$u\in\mathcal{N}[B_{r}]$ and $v\in V_{l}\setminus\mathcal{N}[B_{l}]$.

Finally, consider $u\in V_{l}\setminus\mathcal{N}[B_{i}]$ and $v\in
V_{r}\setminus\mathcal{N}[B_{i}]$. Then $uv\notin E(G)$. Let $w_{u}$ (resp.
$w_{v}$) be the lowest ancestor of $u$ (resp. $v$) in $T^{*}$ such that
$w_{u}\in V(T|\mathcal{N}[B_{l}])$ (resp. $w_{v}\in V(T|\mathcal{N}[B_{r}])$).
Then
$dist_{T^{*}}(u,v)=dist_{T^{*}}(u,w_{u})+dist_{T^{*}}(w_{u},w_{v})+dist_{T^{*}}(w_{v},v)\geq\sigma_{l}(w_{u})+dist_{T}(w_{u},w_{v})+\sigma_{r}(w_{v})$,
which is strictly greater than $k$, by the properties of the recurrence. We
have handled every possible pair of leaves and deduce that $T^{*}$ is indeed a
$k$-leaf root of $G[V_{i}]$. This concludes the proof.

We conclude this section with the proof of the main lemma.

  * Proof.

[Proof of Lemma 4.1] We first need to show that the dynamic programming
procedure above can be used to enumerate
$\mathbb{T}=\\{\mathcal{T}_{1},\ldots,\mathcal{T}_{l}\\}$. Recall that
$\mathcal{T}_{i}\in\mathbb{T}$ if and only if there is a $k$-leaf root $T^{*}$
of $G$ such that the root of $T^{*}$ is the parent of $z$, and
$\mathcal{T}_{i}=(T_{i},\sigma_{i})$ is the valued restriction of $T^{*}$ to
$N[z]$. Let $B_{z}=\\{z\\}$ be the root of the tree decomposition from above.

Let $\mathcal{T}_{i}=(T_{i},\sigma_{i})\in\mathbb{T}$ and let $T^{*}$ be a
corresponding $k$-leaf root. Then $L(T_{i})=N[z]=N[B_{z}]=N[B_{z}]\cap V_{z}$
(since $V_{z}=V(G)$). Moreover, $(T_{i},\sigma_{i})$ is the valued restriction
of $T^{*}=T^{*}[V_{z}]$ to $N[z]=N[B_{z}]\cap V_{z}$, and $r(T_{i})=r(T^{*})$
since both roots must be the parent of $z$. Thus $(T_{i},\sigma_{i})$ is valid
for $B_{z}$, and it follows from Lemma 4.4 that $(T_{i},\sigma_{i})\in
Q[B_{z}]$.

Now let $(T,\sigma)\in Q[B_{z}]$ such that $r(T)$ is the parent of $z$. Then
by Lemma 4.4, $(T,\sigma)$ is valid for $B_{z}$ and there is a $k$-leaf root
$T^{*}$ of $G[V_{z}]=G$ such that $(T,\sigma)$ is the valued restriction of
$T^{*}$ to $N[B_{z}]\cap V_{z}=N_{G}[z]$. Moreover, $r(T^{*})=r(T)$ is the
parent of $z$. Therefore, $(T,\sigma)$ must belong to $\mathbb{T}$.

We have thus shown that by enumerating all the valued trees in the computed
$Q[B_{z}]$ and keeping only those whose root is the parent of $z$, we
reconstruct exactly $\mathbb{T}$.

Let us discuss the complexity. Note that $B$ has $O(n)$ nodes. For each bag
$B_{i}\in V(B)$, by Lemma 4.3, we must enumerate $O(f(k))$ possible valued
trees and test each of them for membership in $Q[B_{i}]$, where
$f(k)=d^{4kd^{4k}}\cdot(k+2)^{d^{4k}}$. Join nodes take the longest to test,
since they require to check every combination of valued trees in $Q[B_{l}]$
and $Q[B_{r}]$, which amounts to $f(k)^{2}$ tests. It is not hard to see that
for each combination, checking whether the recurrence holds can be done in
time $O(d^{4k}\cdot d^{4k})$ (the longest condition to check is to test each
$w_{l},w_{r}$ pairs). Therefore, each $B_{i}$ can be computed in time
$O(d^{8k}\cdot f(k)^{3})$. Since there are $O(n)$ such $B_{i}$ bags, the
complexity is $O(n\cdot d^{8k}\cdot f(k)^{3})$.

##  5 Putting it all together

The results accumulated above lead to an immediate algorithm. First, we check
whether $G$ admits a $k$-leaf root of arity at most by $d^{k}$, where
$d=3|S(k,3k)|2^{|S(k,3k)|}$. This can only happen if $G$ has maximum degree at
most $d^{k}$, in which case we can use the algorithm of Eppstein and Havvaei
[16] (or even our algorithm from Section 4 would work). If there is no such
$k$-leaf root but that $G$ is a $k$-leaf power, by Lemma 3.6, we must be able
to find a homogeneous similar structure $\mathcal{S}$ of size $3|S(k,3k)|$.

To find $\mathcal{S}$, we begin by searching for $\mathcal{C}$. We brute-force
every $3|S(k,3k)|$ disjoint subsets of at most $d^{k}$ vertices from $G$,
which is the only reason our algorithm takes time $O(n^{f(k)})$ instead of
$O(f(k)n^{c})$. Assuming a suitable $\mathcal{C}$ has been identified, we look
at the connected components obtained after removing the $C_{i}$’s. At this
point, it is easy to verify that the properties of similar structures hold and
to find $z$ and the $Y_{i}$’s. As for the layering functions, we brute-force
them all, but since the size of the $C_{i}$’s is bounded, this adds little
complexity compared to the gargantuan time taken to enumerate the possible
$\mathcal{C}$’s. Once a suitable set of layering functions is found, we use
the algorithm from Section 4 to compute all the $accept(\mathcal{S},C_{i})$
sets, and it remains to check that they are equal. If so, we have found a
redundant substructure of $G$. By Theorem 3.1, we may remove $C_{1}\cup Y_{1}$
from $G$ to obtain an equivalent instance. We then repeat with $G-(C_{1}\cup
Y_{1})$. The algorithm ends when it either reaches a graph of maximum degree
at most $d^{k}$, which is “easy” to verify, or when no homogeneous similar
structure can be found. In the latter case, we know by Lemma 3.6 that $G$
cannot be a $k$-leaf power.

1 Function  _isLeafPower( $G,k$)_

2 $d\leftarrow 3|S(k,3k)|2^{|S(k,3k)|}$

3 if  _$G$ has maximum degree at most $d^{k}$_ then

4 Check if $G$ is a $k$-leaf power and return the result

5

6 foreach  _collection $\mathcal{C}=\\{C_{1},\ldots,C_{l}\\}$ of disjoint
subsets of $V(G)$, with $l=3|S(k,3k)|$ and each $|C_{i}|\leq d^{k}$_ do

7 Let $G^{\prime}=G-\bigcup_{i\in[l]}C_{i}$

8 Let $X=\\{X_{1},\ldots,X_{t}\\}$ be the connected components of $G^{\prime}$

9 Let $z\in V(G^{\prime})$ such that $\bigcup_{i\in[l]}C_{i}\subseteq
N_{G}(z)$

10 if  _$z$ does not exist_ then

11 continue to the next $\mathcal{C}$

12

13 Let $X_{z}\in X$ such that $z\in X_{z}$

14 if  _some $X_{j}\in X\setminus\\{X_{z}\\}$ has neighbors in two distinct
$C_{i},C_{j}$_ then

15 continue to the next $\mathcal{C}$

16

17 For $i\in[l]$, let $Y_{i}$ be the union of every $X_{j}\in X\setminus
X_{z}$ such that $N_{G}(X_{j})\subseteq C_{i}\\}$

18 if  _$\exists i\in[l],G[C_{i}\cup Y_{i}\cup\\{z\\}]$ has maximum degree
above $d^{k}$ _ then

19 continue to the next $\mathcal{C}$

20

21 foreach  _set of layering functions
$\mathcal{L}=\\{\ell_{1},\ldots,\ell_{l}\\}$_ do

22 if
_$\mathcal{S}=(\mathcal{C},\mathcal{Y}=\\{Y_{1},\ldots,Y_{d}\\},z,\mathcal{L})$
is a similar structure_ then

23 foreach  _$i\in[l]$_ do

24 Compute $accept(\mathcal{S},C_{i})$

25