<p>As the comments have suggested, you are looking for a Ham Path through a set nodes in the <span class="math-container">$k$</span>-leaf power graph of this tree. That is, given your tree <span class="math-container">$T$</span> and a distance <span class="math-container">$k$</span>, form a graph <span class="math-container">$G$</span> where <span class="math-container">$V(G)$</span> are all the leaf nodes of <span class="math-container">$T$</span> and <span class="math-container">$E(G)$</span> is the set of edges <span class="math-container">$\{u,v\}$</span> if <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are within distance <span class="math-container">$k$</span> in <span class="math-container">$T$</span>. You are looking for a Ham Path in <span class="math-container">$G$</span>. For each particular <span class="math-container">$k$</span>, these graphs obtained from all trees are called <span class="math-container">$k$</span>-leaf powers.</p>
<p>You mention you are not sure about the complexity of this problem when <span class="math-container">$k=2$</span>: Well, we know that when <span class="math-container">$k=2$</span>, no matter what <span class="math-container">$T$</span> you started with, <span class="math-container">$G$</span> will always be a disjoint collection of cliques. So if <span class="math-container">$G$</span> is disconnected, there is no Ham Path and if <span class="math-container">$G$</span> is connected, it must be a clique and finding a Ham Path is trivial.</p>
<p>Similarly, structural characterizations are known for <span class="math-container">$G$</span> when <span class="math-container">$k=3$</span> (3-leaf powers) and Ham Path can be solved in linear time on that graph: <a href="https://www.graphclasses.org/classes/gc_651.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/gc_651.html</a></p>
<p>Structural characterization are somewhat known for <span class="math-container">$k=4$</span> and <span class="math-container">$k=5$</span>. Ham Path is polytime solvable on 4-leaf powers: <a href="https://www.graphclasses.org/classes/gc_650.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/gc_650.html</a> and also polytime solvable on 5-leaf powers: <a href="https://www.graphclasses.org/classes/gc_825.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/gc_825.html</a></p>
<p>While there is still some structure that can be said about a general leaf power graphs (that <span class="math-container">$G$</span> will be chordal, for one), Ham Path is NP-complete on these:
<a href="https://www.graphclasses.org/classes/gc_649.html" rel="nofollow noreferrer">https://www.graphclasses.org/classes/gc_649.html</a></p>
<p>Despite it being NP-complete for general leaf power graphs, it can still be the case that Ham Path will be polytime solvable for any fixed <span class="math-container">$k$</span>, but I have no intuition on whether this is the case. (Edit: A comment from @Laakeri above says that Ham Path should be polytime solvable for each <span class="math-container">$k$</span> due to the cliquewidth parameter)</p>
<p>There are some subclasses of leaf power graphs where the complexity status of HAM PATH remains unknown, but I don't know of any graph class that has been studied between the leaf power graphs and the 5-leaf power graphs (i.e. a subclass of leaf powers which is a superclass of 5-leaf powers).</p>

CC BY-SA 4.0
2022-12-29T08:46:24.187Z
Thanks for the answer! indeed the bounded-cliquewidth argument shows that Hamiltonian Path is solvable for any fixed $k$, not just the ones you mention.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2022-12-27T20:48:04.607Z
2022-12-27T20:48:04.607Z
JimN
<p>I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, unrooted, unranked) tree <span class="math-container">$T$</span>, the <em>distance</em> <span class="math-container">$d(l, l')$</span> between two leaves <span class="math-container">$l$</span> and <span class="math-container">$l'$</span> is simply the length of the unique shortest path between then. Given <span class="math-container">$k &gt; 0$</span>, a <em>distance-<span class="math-container">$k$</span> leaf enumeration</em> of the leaves of <span class="math-container">$T$</span> is a sequence <span class="math-container">$l_1, \ldots, l_n$</span> enumerating all leaves such that the distance between any two consecutive leaves is less than <span class="math-container">$k$</span>, i.e., for all <span class="math-container">$1 \leq i &lt; n$</span>, we have <span class="math-container">$d(l_i, l_{i+1}) \leq k$</span>.</p>
<p>Consider the problem, given a tree <span class="math-container">$T$</span> and a threshold <span class="math-container">$k$</span>, of determining if <span class="math-container">$T$</span> has a distance-<span class="math-container">$k$</span> leaf enumeration. <strong>Is this problem in PTIME, or NP-complete?</strong></p>
<p>Note that this problem is clearly in NP, but I couldn't find a PTIME algorithm or hardness proofs. Some thoughts:</p>
<ul>
<li>I was not able to find a PTIME divide-and-conquer algorithm, because a distance-<span class="math-container">$k$</span> sequence may need to &quot;jump&quot; back and forth, e.g., in this tree if <span class="math-container">$k$</span> is 150 and the edges &quot;--100--&quot; have length 100, we need to alternate jumping left and right of the middle element in the following graph -- this can easily be generalized to more complex examples.</li>
</ul>
<pre><code>x --100--\   /- x
          \ /
x ---100---+--- x
          / \
x --100--/   \- x
</code></pre>
<ul>
<li>I found some works about the complexity of finding an optimal ordering of the children of internal tree nodes to optimize some functions on the sequence of leaves of the tree (e.g., <a href="https://www.sciencedirect.com/science/article/pii/S1570866706000839" rel="nofollow noreferrer">this</a>), but could not see a connection to my problem.</li>
<li>If we considered instead the problem of visiting all tree nodes (not just leaves), it would always be feasible for <span class="math-container">$k=3$</span> (because the cube of a connected graph always has a Hamiltonian path), only feasible for paths if <span class="math-container">$k=1$</span>, and I am not sure of the complexity of determining if <span class="math-container">$k=2$</span> is feasible: on arbitrary graphs it is NP-hard to determine if the square of the graph has a Hamiltonian cycle (<a href="https://www.sciencedirect.com/science/article/pii/0012365X78901644" rel="nofollow noreferrer">source</a>).</li>
<li>Maybe I am also missing the understanding of what is a distance function on elements (leaves) which can be defined by a tree structure.</li>
</ul>

CC BY-SA 4.0
2022-12-24T09:32:26.173Z
I think this is equivalent to the Hamiltonian path problem on $k$-leaf powers. By bounded clique-width this should imply polynomial-time algorithm when $k$ is constant.
Laakeri
CC BY-SA 4.0
2022-12-24T21:42:03.303Z
Not sure if I'm reading it right, but maybe [this site](https://www.graphclasses.org/classes/gc_649.html) suggests it is NP-hard by a result in [this paper](https://doi.org/10.1016/0020-0190(89)90038-0)?
Neal Young
CC BY-SA 4.0
2022-12-29T08:45:38.257Z
Thanks a lot to you both, indeed this completely addresses my question. Somehow I didn't find the notion of $k$-leaf powers.
Antoine Amarilli 'a3nm'
<np-hardness><tree><hamiltonian-paths>
Complexity of finding a path visiting all leaves on a tree while respecting a distance bound
Antoine Amarilli 'a3nm'
# Complexity of finding a path visiting all leaves on a tree while respecting a distance bound

(Asked by: username_0 on 2022-12-24)

I am interested in the complexity of a specific variant of the Hamiltonian path problem where we want to visit all leaves of a tree while respecting a distance bound. Formally, given an (undirected, unrooted, unranked) tree $T$, the distance $d(l, l')$ between two leaves $l$ and $l'$ is simply the length of the unique shortest path between then. Given $k > 0$, a distance-$k$ leaf enumeration of the leaves of $T$ is a sequence $l_1, \ldots, l_n$ enumerating all leaves such that the distance between any two consecutive leaves is less than $k$, i.e., for all $1 \leq i < n$, we have $d(l_i, l_{i+1}) \leq k$.
Consider the problem, given a tree $T$ and a threshold $k$, of determining if $T$ has a distance-$k$ leaf enumeration. Is this problem in PTIME, or NP-complete?
Note that this problem is clearly in NP, but I couldn't find a PTIME algorithm or hardness proofs. Some thoughts:

I was not able to find a PTIME divide-and-conquer algorithm, because a distance-$k$ sequence may need to "jump" back and forth, e.g., in this tree if $k$ is 150 and the edges "--100--" have length 100, we need to alternate jumping left and right of the middle element in the following graph -- this can easily be generalized to more complex examples.

x --100--\   /- x
          \ /
x ---100---+--- x
          / \
x --100--/   \- x


I found some works about the complexity of finding an optimal ordering of the children of internal tree nodes to optimize some functions on the sequence of leaves of the tree (e.g., this), but could not see a connection to my problem.
If we considered instead the problem of visiting all tree nodes (not just leaves), it would always be feasible for $k=3$ (because the cube of a connected graph always has a Hamiltonian path), only feasible for paths if $k=1$, and I am not sure of the complexity of determining if $k=2$ is feasible: on arbitrary graphs it is NP-hard to determine if the square of the graph has a Hamiltonian cycle (source).
Maybe I am also missing the understanding of what is a distance function on elements (leaves) which can be defined by a tree structure.

**Tags:** np-hardness, tree, hamiltonian-paths
> **Comments:**
> **username_1**: I think this is equivalent to the Hamiltonian path problem on $k$-leaf powers. By bounded clique-width this should imply polynomial-time algorithm when $k$ is constant.  
> **username_2**: Not sure if I'm reading it right, but maybe [this site](https://www.graphclasses.org/classes/gc_649.html) suggests it is NP-hard by a result in [this paper](https://doi.org/10.1016/0020-0190(89)90038-0)?  
> **username_0**: Thanks a lot to you both, indeed this completely addresses my question. Somehow I didn't find the notion of $k$-leaf powers.  

---

## 1 answers

### Answer by username_3 on 2022-12-27. Score: 2 | Accepted answer

As the comments have suggested, you are looking for a Ham Path through a set nodes in the $k$-leaf power graph of this tree. That is, given your tree $T$ and a distance $k$, form a graph $G$ where $V(G)$ are all the leaf nodes of $T$ and $E(G)$ is the set of edges $\{u,v\}$ if $u$ and $v$ are within distance $k$ in $T$. You are looking for a Ham Path in $G$. For each particular $k$, these graphs obtained from all trees are called $k$-leaf powers.

You mention you are not sure about the complexity of this problem when $k=2$: Well, we know that when $k=2$, no matter what $T$ you started with, $G$ will always be a disjoint collection of cliques. So if $G$ is disconnected, there is no Ham Path and if $G$ is connected, it must be a clique and finding a Ham Path is trivial.

Similarly, structural characterizations are known for $G$ when $k=3$ (3-leaf powers) and Ham Path can be solved in linear time on that graph: <https://www.graphclasses.org/classes/gc_651.html>

Structural characterization are somewhat known for $k=4$ and $k=5$. Ham Path is polytime solvable on 4-leaf powers: <https://www.graphclasses.org/classes/gc_650.html> and also polytime solvable on 5-leaf powers: <https://www.graphclasses.org/classes/gc_825.html>

While there is still some structure that can be said about a general leaf power graphs (that $G$ will be chordal, for one), Ham Path is NP-complete on these:
<https://www.graphclasses.org/classes/gc_649.html>

Despite it being NP-complete for general leaf power graphs, it can still be the case that Ham Path will be polytime solvable for any fixed $k$, but I have no intuition on whether this is the case. (Edit: A comment from @Laakeri above says that Ham Path should be polytime solvable for each $k$ due to the cliquewidth parameter)

There are some subclasses of leaf power graphs where the complexity status of HAM PATH remains unknown, but I don't know of any graph class that has been studied between the leaf power graphs and the 5-leaf power graphs (i.e. a subclass of leaf powers which is a superclass of 5-leaf powers).

> **Comments:**
> **username_0**: Thanks for the answer! indeed the bounded-cliquewidth argument shows that Hamiltonian Path is solvable for any fixed $k$, not just the ones you mention.  

---

