Approximating pathwidth for graphs of small treewidth

Carla Groenland, Gwenaël Joret, Wojciech Nadara +1

We describe a polynomial-time algorithm which, given a graph $G$ with treewidth $t$, approximates the pathwidth of $G$ to within a ratio of $O(t\sqrt{\log t})$. This is the first a…