Is this a viable and correct method for finding all maximal cliques in a graph

algorithmsgraph theory

I am a sociology student and have taken "Introduction the Graph Theory" and "Graph Theory and Algorithms" courses from the mathematics faculty some time ago. In my free time I was thinking about a method/algorithm about how to find all unique maximal cliques in any graph. This would be pretty cool to know for sociology analysis of social networks. So I came up with the following method and I was curious if this is a viable and correct method to use. I do not know how to use mathematical writing on this website so I will try to explain it in words:

Step 0)

Write down the set of vertices and set of edges of the graph G.

Step 1)

Pick any vertex v_i in the graph.

Step 2)

Take the maximal star of that vertex v_i (thus a subgraph of graph G in which vertex v_i is connected to all of its neighbours). Write down this subset of vertices.

Step 3)

Check if the edges of the set of vertices of this maximal star of v_i are all connected to each other vertex of this subset of vertices. In other words, check if this subset of vertices is complete.

If yes: then this specific subset of vertices is a unique maximal clique. Write down this subset of vertices as a unique subset.

If no: then go back to step 1 and choose another vertex that has not been chosen before.

Additionally:

If another vertex is chosen to go through all of the steps and there has been found a maximal clique, then check whether this new subset of vertices is unique to the already written down subsets of vertices that represented a unique maximal clique:

If yes: then this specific subset of vertices is a unique maximal clique. Write down this subset of vertices as a unique subset.

If no: then its the same maximal clique that has already been found from a different vertex start. Thus disregard this and go back to step 1 with another vertex that has not been chosen before.

Continue till you have checked the steps for all vertices in the graph G. The output will thus give you all unique subset of vertices of graph G that are an unique maximal clique.

To do this by hand for large graphs it would be a lot of work. But since a computer can note the set of vertices and edges I would believe a computer could perform these steps easy and quickly (depending on how large the graph is) and give you an output of all the unique maximal cliques in any graph G.

Is this a correct and viable method to use? Are there any known other methods to find a solution to this question?

English is not my mother tongue so I might have made some mistakes with the terminology used. I would like to hear your perspectives on it or perhaps spot some mistakes or anything.

Thank you for your attention! 🙂

Best Answer

You might miss many maximal cliques with this approach; in fact, you might very well find none of them.

Consider a cycle graph on at least $4$ vertices. In this graph, the maximal cliques are just the edges (there is no clique on $3$ or more vertices). But for each vertex, your approach will try to take both neighbors of that vertex and see if they form a clique; they don't, so your approach will not find any cliques.

Finding maximal cliques in a graph is going to take a long time, even for a computer, for several reasons:

  • The maximum clique problem is a well-known NP complete problem, and listing all the maximal cliques would let you know which is the largest.
  • Also, there are sometimes exponentially many maximal cliques. For instance, take a graph on $2n$ vertices $v_1, \dots, v_n, w_1, \dots, w_n$ and all edges between them except the $n$ edges $v_1w_1, \dots, v_nw_n$. This graph has $2^n$ maximal cliques: for each $i$, choose either $v_i$ or $w_i$ to add to the clique.

One possible algorithm for listing all maximal cliques is the Bron–Kerbosch algorithm.

Related Question