26

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?

Mantas Vidutis
  • 16,376
  • 20
  • 76
  • 92
  • 3
    @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. http://stackoverflow.com/help/on-topic – Mantas Vidutis Feb 10 '15 at 21:16

2 Answers2

24

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

Community
  • 1
  • 1
polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
  • 1
    our viewers at home should note that the full text of this paper is behind the ACM membership wall – Mantas Vidutis May 10 '10 at 08:22
  • 1
    Hi, by NP-hard, do you mean that there is no algorithm which runs in polynomial time? – SexyBeast Jun 04 '13 at 15:37
  • 1
    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. – divanshu Jun 11 '13 at 18:05
  • 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. – D.W. Sep 27 '22 at 17:48
3

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.

Pradeep Banavara
  • 983
  • 2
  • 11
  • 33
  • 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. – D.W. Sep 27 '22 at 17:46