I have been trying to solve Maximum clique problem with the algorithm mentioned below and so far not been able to find a case in which it fails.
Algorithm:
For a given graph, each node numbered from 1 to N.
1. Consider a node as permanent node and form a set of nodes such that each node is connected to this permanent node.(the set includes permanent node as well)
2. Now form a subgraph of the original graph such that it contains all the nodes in the set formed and only those edges which are between the nodes present in the set.
3. Find degree of each node.
4. If all the nodes have same degree then we have a clique.
5. Else delete the least degree node from this subgraph and repeat from step 3.
6. Repeat step 1-5 for all the nodes in the graph.
Can anyone point out flaw in this algorithm?
Here is my code http://pastebin.com/tN149P9m.
Here's a family of counterexamples. Start with a k-clique. For each node in this clique, connect it to each node of a fresh copy of K_{k-1,k-1}, i.e., the complete bipartite graph on k-1 plus k-1 nodes. For every permanent node in the clique, the residual graph is its copy of K_{k-1,k-1} and the clique. The nodes in K_{k-1,k-1} have degree k and the other clique nodes have degree k - 1, so the latter get deleted.
Here's a 16-node counterexample, obtained by setting k = 4 and identifying parts of the K_{3,3}s in a ring:
{0: {1, 2, 3, 4, 5, 6, 7, 8, 9},
1: {0, 2, 3, 7, 8, 9, 10, 11, 12},
2: {0, 1, 3, 10, 11, 12, 13, 14, 15},
3: {0, 1, 2, 4, 5, 6, 13, 14, 15},
4: {0, 3, 7, 8, 9, 13, 14, 15},
5: {0, 3, 7, 8, 9, 13, 14, 15},
6: {0, 3, 7, 8, 9, 13, 14, 15},
7: {0, 1, 4, 5, 6, 10, 11, 12},
8: {0, 1, 4, 5, 6, 10, 11, 12},
9: {0, 1, 4, 5, 6, 10, 11, 12},
10: {1, 2, 7, 8, 9, 13, 14, 15},
11: {1, 2, 7, 8, 9, 13, 14, 15},
12: {1, 2, 7, 8, 9, 13, 14, 15},
13: {2, 3, 4, 5, 6, 10, 11, 12},
14: {2, 3, 4, 5, 6, 10, 11, 12},
15: {2, 3, 4, 5, 6, 10, 11, 12}}