Revisiting Decomposition by Clique Separators

Abstract : We study the complexity of decomposing a graph by means of clique separators. This common algorithmic tool, first introduced by Tarjan, allows to cut a graph into smaller pieces, and so, it can be applied to preprocess the graph in the computation of optimization problems. However, the best-known algorithms for computing a decomposition have respective O(nm)-time and O(n^{(3+α)/2}) = o(n^2.69)-time complexity, with α < 2.3729 being the exponent for matrix multiplication. Such running times are prohibitive for large graphs. Here we prove that for every graph G, a decomposition can be computed in O(T (G) + min{n^α , ω^2 n})-time with T (G) and ω being respectively the time needed to compute a minimal triangulation of G and the clique-number of G. In particular, it implies that every graph can be decomposed by clique separators in O(n^α log n)-time. Based on prior work from Kratsch et al., we prove in addition that decomposing a graph by clique-separators is as least as hard as triangle detection. Therefore, the existence of any o(n^α)-time algorithm for this problem would be a significant breakthrough in the field of algorithmic. Finally, our main result implies that planar graphs, bounded-treewidth graphs and bounded-degree graphs can be decomposed by clique separators in linear or quasi-linear time.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.682 - 694. 〈10.1137/16M1059837〉
Liste complète des métadonnées

Littérature citée [52 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01753324
Contributeur : David Coudert <>
Soumis le : jeudi 29 mars 2018 - 15:37:07
Dernière modification le : lundi 30 avril 2018 - 14:30:02

Fichier

decomposition_by_clique_separa...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Guillaume Ducoffe. Revisiting Decomposition by Clique Separators. Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.682 - 694. 〈10.1137/16M1059837〉. 〈hal-01753324〉

Partager

Métriques

Consultations de la notice

79

Téléchargements de fichiers

54