Flaw in this maximum clique polynomial time approach?

Question

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.

Answer 1

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}}

Answer 2

What you propose looks very much like the following sorting algorithm combined with a greedy clique search:

Consider a simple undirected graph G=(V,E)

Initial sorting

Pick the vertex with minimum degree and place it first in the new list L. From the remaining vertices pick the vertex with minimum degree and place it in the second position in L. Repeat the operations until all vertices in V are in L.

Find cliques greedily

Start from the last vertex in L and move in reverse order. For each vertex v in L compute cliques like this:

1. Add v to the new clique C
2. Compute the neighbor set of v in L: N(v)
3. Pick the last vertex in N(v)
4. v=w; L=L intersection with N(v);
5. Repeat steps 1 to 4

Actually the proposed initial sorting is called a degeneracy ordering and decomposes G in k-cores (see Batagelj et al. 2002 ) A k-core is a maximal subgraph such that all its vertices have at least degree k. The initial sorting leaves the highest cores (with largest k) at the end. When vertices are picked in reverse order you are picking vertices in the highest cores first(similar to your step 4) and trying to find cliques there. There are a number of other possibilities to find cliques greedily based on k-cores but you can never guarantee an optimum unless you do full enumeration.

The proposed initial sorting is used, for example, when searching for exact maximum clique and has been described in many research papers, such as [Carraghan and Pardalos 90]