To Approximate Treewidth, Use Treelength!

Description

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 ⌊l(G)/2⌋ · (|S| − 1), with l(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 · (|S| − 1). We use our results to prove that the treelength tl(G) of any graph G is at most ⌊l(G)/2⌋ 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) ≤ c_H · 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 O(l(G))-approximation algorithm for computing the treewidth of n-node apex-minor-free graphs in O(n^2)-time.

Abstract

International audience

Additional details