Menu
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?
261
Given an undirected graph with N nodes and E edges and a value K, the task is to print all set of nodes which form a K size clique. A clique is a complete subgraph of a graph. Explanation: Clearly from the image, 1->2->3 and 3->4->5 are the two complete subgraphs.
A complete subgraph is a set of nodes for which all the nodes are connected to each other. Maximal complete subgraph is are then the largest (i.e. those containing most objects) of these complete subgraphs.
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.
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.
125
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.
26
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
