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 , 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016, 30 (3), pp.13. <10.1137/15M1034039>
Liste complète des métadonnées

https://hal.inria.fr/hal-01348965
Contributeur : David Coudert <>
Soumis le : mardi 26 juillet 2016 - 13:54:04
Dernière modification le : mercredi 27 juillet 2016 - 01:04:23

Fichier

treewidth-treelength.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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>

Partager

Métriques

Consultations de
la notice

137

Téléchargements du document

95