Find all complete sub-graphs within a graph

Question

Is there a known algorithm or method to find all complete sub-graphs within a graph? I have an undirected, unweighted graph and I need to find all subgraphs within it where each node in the subgraph is connected to each other node in the subgraph.

Is there an existing algorithm for this?

Answer 1

This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.

If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time, but otherwise it's very hard, and is completely solvable only for small graphs.

From Wikipedia

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected.

Clique problems include:

• finding the maximum clique (a clique with the largest number of vertices),
• finding a maximum weight clique in a weighted graph,
• listing all maximal cliques (cliques that cannot be enlarged)
• solving the decision problem of testing whether a graph contains a clique larger than a given size.

These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems), the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.

See also

• Bron–Kerbosch algorithm

Answer 2

Well the problem of finding a k-vertex subgraph in a graph of size n is of complexity

O(n^k k^2)

Since there are n^k subgraphs to check and each of them have k^2 edges.

What you are asking for, finding all subgraphs in a graph is a NP-complete problem and is explained in the Bron-Kerbosch algorithm listed above.