Skip to Main content Skip to Navigation
Journal articles

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.
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 : Monday, November 22, 2021 - 3:54:10 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

810

Files downloads

668