Complexity of finding a path visiting all leaves on a tree while respecting a distance bound

Question

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.

Answer 1

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).