Skip to Main content Skip to Navigation
New interface
Journal articles

Revisiting Decomposition by Clique Separators

David Coudert 1 Guillaume Ducoffe 2, 3 
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 : 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.
Complete list of metadata

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/hal-01753324
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 3:37:07 PM
Last modification on : Thursday, August 4, 2022 - 4:58:25 PM

File

decomposition_by_clique_separa...
Files produced by the author(s)

Identifiers

Citation

David Coudert, Guillaume Ducoffe. Revisiting Decomposition by Clique Separators. SIAM Journal on Discrete Mathematics, 2018, 32 (1), pp.682 - 694. ⟨10.1137/16M1059837⟩. ⟨hal-01753324⟩

Share

Metrics

Record views

265

Files downloads

440