Revisiting Decomposition by Clique Separators

David Coudert 1 Guillaume Ducoffe 2, 3
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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 [48 références]  Voir  Masquer  Télécharger
Contributeur : David Coudert <>
Soumis le : jeudi 29 mars 2018 - 15:37:07
Dernière modification le : jeudi 7 février 2019 - 14:28:24


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



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〉



Consultations de la notice


Téléchargements de fichiers