To Approximate Treewidth, Use Treelength! - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2016

To Approximate Treewidth, Use Treelength!

Résumé

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.
Fichier principal
Vignette du fichier
treewidth-treelength.pdf (312.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01348965 , version 1 (26-07-2016)

Identifiants

Citer

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⟩
197 Consultations
700 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More