To Approximate Treewidth, Use Treelength!

Abstract

Tree-likeness parameters have proven their utility in the design of efficient algorithms on graphs. In this paper, we relate the structural tree-likeness of graphs with their metric tree-likeness. To this end, we establish new upper bounds on the diameter of minimal separators in graphs. We prove that in any graph $G$, the diameter of any minimal separator $S$ in $G$ is at most $\lfloor \ell(G) / 2\rfloor \cdot (|S|-1)$, with $\ell(G)$ the length of a longest isometric cycle in $G$. Our result relies on algebraic methods and on the cycle basis of graphs. We improve our bound for the graphs admitting a distance preserving elimination ordering, for which we prove that any minimal separator $S$ has diameter at most $2 \cdot (|S|-1)$. We use our results to prove that the treelength $tl(G)$ of any graph $G$ is at most $\lfloor \ell(G) / {2}\rfloor$ times its treewidth $tw(G)$. In addition, we prove that, for any graph $G$ that excludes an apex graph $H$ as a minor, $tw(G) \leq c_H \cdot tl(G)$ for some constant $c_H$ only depending on $H$. We refine this constant when $G$ has bounded genus. Altogether, we obtain a simple $\mathcal{O} (\ell(G))$-approximation algorithm for computing the treewidth of $n$-node apex-minor-free graphs in $\mathcal{O}(n^2)$-time.