[SOLVED] Counting all cliques of k vertices in a graph sequentially

Counting all cliques of k vertices in a graph sequentially

Does exist a sequential algorithm for counting all k-cliques in an undirected graph?

With k-cliques I mean this: the number of sets of vertices that are all connected one another by edges in an undirected graph.

Here's where to find a more detailed description of a clique. https://en.wikipedia.org/wiki/Clique_(graph_theory)

Solution

You can use Bron–Kerbosch algorithm to list all cliques in graph. Consider its siplest implementation (pseudocode from wikipedia):

BronKerbosch1(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    for each vertex v in P:
        BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        P := P \ {v}
        X := X ⋃ {v}

In each recursive call, the set R contains a clique, while iterating through all the cliques in the graph. Therefore you can alter the algorithm to print the clique whenever its size is k and cut the recursion, since any recursive call would only produce larger cliques.

BronKerbosch1(R, P, X, k):
    if |R| = k:
        report R as a k-clique
    else
        for each vertex v in P:
            BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
            P := P \ {v}
            X := X ⋃ {v}

You can use the same idea when implementing optimized versions with pivoting and vertex ordering.