Maximal Cliques as a Normal Form in the Algebra of Graphs: Compression by Modular Decomposition and an Enumeration Algorithm

Source abstract

The finite simple graphs with vertices in a set S form an algebra G(S) under union and join, generated by the one-vertex graphs. We show that this algebra has a canonical normal form whose data are exactly the maximal cliques of the graph. Precisely, every g∈G(S) admits a unique maximal-clique decompositionμ(g), characterized equivalently as the unique clique decomposition that is an antichain and as the unique normal form of a terminating rewriting system generated by the axioms. The normal form is compositional: μ(g+h)=μ(g)+μ(h) and μ(g·h)=μ(g)·μ(h) for vertex-disjoint g,h, and more generally μ commutes with modular substitution. Consequently, μ(g) may be stored in factored form, whose length is governed by the modular structure of g rather than by the number of maximal cliques: we prove that a graph of modular width w has a factored decomposition of length O(w3w/3n), computable in time O(w3w/3n+m), however many maximal cliques it has, and that the number of maximal cliques and the clique number are then read off in linear time by evaluating the same expression in two different semirings. For the cocktail-party graph, this compresses 2n/2 maximal cliques into n symbols. For arbitrary graphs, we prove a localization identity that expresses μ(g) as a sum over vertices of the decompositions of their forward neighborhoods, and derive from it an enumeration algorithm running in time O(d2n3d/3) on graphs of degeneracy d, with working representation provably within a factor d+1 of the output size, and supporting vertex insertion. We report experiments on 13 real-world networks and on families of bounded modular width. These confirm the space bound and show the enumeration algorithm to be within a small constant factor of tuned classical implementations; they also show that the compression is realized on the bounded-width families, by factors up to 1017, but not on the real-world networks, whose modular width is close to their order.