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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01348965
Contributor : David Coudert <>
Submitted on : Tuesday, July 26, 2016 - 1:54:04 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM

File

treewidth-treelength.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

594

Files downloads

332