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.