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?

Spleenwort

@bummi you are joking right? Not only is StackOverflow originally built for algorithm design questions, software algorithms are the second topic covered for "things I can ask about" in the help center. stackoverflow.com/help/on-topic – Spleenwort

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

Indigested

our viewers at home should note that the full text of this paper is behind the ACM membership wall – Spleenwort

Hi, by NP-hard, do you mean that there is no algorithm which runs in polynomial time? – Primalia

Yes, NP-Hard means there is no algorithm which can solve this problem in asymptotically polynomial time. Even more, it implies that the correction of the algorithm can also NOT be checked in polynomial time. – Tomtit

Nitpick: This is not the clique problem. It's related, and is at least as hard as the clique problem, but it's not the same problem. The question asks to find all cliques. The clique problem means to test whether there exists a clique of a certain size (roughly), which is not the same. As a result, the problem in the question is not in NP (it is not a decision problem) and is not NP-complete. It's NP-hard, though. – Evaporation

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.

Ludovika

Nitpick: Finding all cliques is not NP-complete. It's not a decision problem, so it's not in NP. It's NP-hard, though. – Evaporation