Revisiting Decomposition by Clique Separators
David Coudert, Guillaume Ducoffe · SIAM Journal on Discrete Mathematics · 2018
We study the complexity of decomposing a graph by means of clique separators. This common algorithmic tool, first introduced by Tarjan, allows one 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 ${\cal O}(nm)$-time and ${\cal O}(n^{(3+\alpha)/2}) = o(n^{2.69})$-time complexity with $\alpha < 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 ${\cal O}(T(G) + \min\{n^{\alpha},\omega^2 n\})$-time with $T(G)$ and $\omega$ 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 ${\cal O}(n^{\alpha}\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^{\alpha})$-time algorithm for this problem would be a significant breakthrough in the algorithmic field. 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.