I have to describe (no pseudocode needed) how to find large cliques in an arbitrary undirected graph. All vertices have to be connected with each other and crossing is allowed. This is one approach:
Given an undirected graph with nodes N and edges E. Let us set K as the size of cliques we want to find. First, locate all the vertices with a degree larger or equal to K-1 and check which subset of K vertices forms a clique. When we add another edge to the list we check if it forms a clique or not.
- Form a recursive function with three parameters starting node, length of the present set of nodes and desired length of nodes.
- The starting index resembles that no node can be added to the present set less than that index. So a loop is run from that index to n.
- If it is found that after adding a node to the present set, the set of nodes remains a clique. If yes, that node is added and the recursive function is called with parameters index of new added node +1, length of current set + 1, and the desired length.
- If the desired length is reached, the nodes are printed.
I wanted to know if this approach could work or not?