Let $\mathcal{T}_h$ be the set of trees with pathwidth $h$. What is the minimum,$|V(T)|$ over all $T \in \mathcal{T}_h$.

I'm guessing this is a fairly easy question. We know that a complete binary tree of height $2h$ has pathwidth $h$. This gives an upper bound of $2^{2h}-1$. Is this tight? Or could there be trees with pathwidth $h$ and size polynomial in $h$.

  • $\begingroup$ It seems not, here is a possible pointer $\endgroup$
    – codeR
    Commented Apr 18 at 14:27
  • 1
    $\begingroup$ Intuitively, I would believe a ternary tree would be better. $\endgroup$
    – Pål GD
    Commented Apr 18 at 17:17
  • $\begingroup$ @PålGD Good point. A complete ternary tree of height $h$ has pathwidth $h$ (or at least in this paper arxiv.org/pdf/2008.00779.pdf they say it is well known). So this slightly improves the exponent. But is $2^{\Theta(h)}$ the correct answer or is an improvement possible? $\endgroup$ Commented Apr 19 at 8:22
  • $\begingroup$ @codeR I had a look but couldn't work out the relevance, maybe I'm missing something. $\endgroup$ Commented Apr 19 at 8:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.