Skip to Main content Skip to Navigation
New interface
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

https://hal.inria.fr/hal-01348965
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2016 - 1:54:04 PM
Last modification on : Thursday, August 4, 2022 - 4:58:24 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, 2016, 30 (3), pp.13. ⟨10.1137/15M1034039⟩. ⟨hal-01348965⟩

Share

Metrics

Record views

190

Files downloads

600