Clique-decomposition revisited

Description

The decomposition of graphs by clique-minimal separators is a common algorithmic tool, first introduced by Tarjan. Since it allows to cut a graph into smaller pieces, it can be applied to pre-process the graphs in the computation of many optimization problems. However, the best known clique-decomposition algorithms have respective O(nm)-time and O(n 2.69)-time complexity, that is prohibitive for large graphs. Here we prove that for every graph G, the decomposition can be computed in O T (G) + min{n 2.3729 , ω 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 clique-decomposed iñ O(n 2.3729)-time. Based on prior work from Kratsch et al., we prove in addition that computing the clique-decomposition is at least as hard as triangle detection. Therefore, the existence of any o(n 2.3729)-time clique-decomposition algorithm 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 clique-decomposed in linear or quasi-linear time.

Additional details