Skip to Main content Skip to Navigation
Journal articles

To Approximate Treewidth, Use Treelength!

David Coudert 1 Guillaume Ducoffe 1 Nicolas Nisse 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 ⌊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.
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2016 - 1:54:04 PM
Last modification on : Tuesday, June 22, 2021 - 8:14:03 PM


Files produced by the author(s)




David Coudert, Guillaume Ducoffe, Nicolas Nisse. To Approximate Treewidth, Use Treelength!. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.13. ⟨10.1137/15M1034039⟩. ⟨hal-01348965⟩



Record views


Files downloads