The quadratic-logarithmic lower-bound conjecture for pebble motion on trees

Consider the \textsc{Pebble Motion Problem on Trees}: a tree $G$ with $N$ vertices, a set of pebbles, and initial and goal configurations satisfying the problem's feasibility conditions. The length of a solution sequence is the number of individual moves transforming the initial configuration into the goal configuration.

Quadratic-logarithmic lower-bound conjecture. There exist instances of the \textsc{Pebble Motion Problem on Trees} for which the length of the shortest solution sequences is

$$\Theta(N^2\log N).$$

The paper's main results give an upper bound of order $\widetilde{\mathrm{O}}(N^2)$ and improve previously known bounds, while the conjecture predicts instances attaining a quadratic-logarithmic shortest-solution length. The source provides no resolution of this conjecture.