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 metadatas

Cited literature [48 references]  Display  Hide  Download

https://hal.inria.fr/hal-01753324
Contributor : David Coudert <>
Submitted on : Thursday, March 29, 2018 - 3:37:07 PM
Last modification on : Monday, September 9, 2019 - 1:42:01 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, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.682 - 694. ⟨10.1137/16M1059837⟩. ⟨hal-01753324⟩

Share

Metrics

Record views

613

Files downloads

206