One of the assignments in my algorithms class is to design an exhaustive search algorithm to solve the clique problem. That is, given a graph of size n, the algorithm is supposed to determine if there is a complete sub-graph of size k. I think I've gotten the answer, but I can't help but think it could be improved. Here's what I have:

Version 1

input: A graph represented by an array A[0,...n-1], the size k of the subgraph to find.

output: True if a subgraph exists, False otherwise

Algorithm (in python-like pseudocode):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

Version 2

input: An adjacency matrix of size n by n, and k the size of the subgraph to find

output: All complete subgraphs in A of size k.

Algorithm (this time in functional/Python pseudocode):

//Base case:  return all vertices in a list since each
//one is a 1-clique
def clique(A, 1):
    S = new list
    for i in range(0 to n-1):
        add i to S
    return S

//Get a tuple representing all the cliques where
//k = k - 1, then find any cliques for k
def clique(A,k):
    C = clique(A, k-1)
    S = new list
    for tuple in C:
        for i in range(0 to n-1):
            //make sure the ith vertex is linked to each
            //vertex in tuple
            for j in tuple:
                if A[i,j] != 1:
                    break
            //This means that vertex i makes a clique
            if j is the last element:
                newtuple = (i | tuple) //make a new tuple with i added
                add newtuple to S
    //Return the list of k-cliques
    return S

Does anybody have any thoughts, comments, or suggestions? This includes bugs I might have missed as well as ways to make this more readable (I'm not used to using much pseudocode).

Version 3

Fortunately, I talked to my professor before submitting the assignment. When I showed him the pseudo-code I had written, he smiled and told me that I did way too much work. For one, I didn't have to submit pseudo-code; I just had to demonstrate that I understood the problem. And two, he was wanting the brute force solution. So what I turned in looked something like this:

input: A graph G = (V,E), the size of the clique to find k

output: True if a clique does exist, false otherwise

Algorithm:

1. Find the Cartesian Product V^k.
2. For each tuple in the result, test whether each vertex is connected to every other. If all are connected, return true and exit.
3. Return false and exit.

UPDATE: Added second version. I think this is getting better although I haven't added any fancy dynamic programming (that I know of).

UPDATE 2: Added some more commenting and documentation to make version 2 more readable. This will probably be the version I turn in today. Thanks for everyone's help! I wish I could accept more than one answer, but I accepted the answer by the person that's helped me out the most. I'll let you guys know what my professor thinks.

Some comments:

• You only need to consider n-choose-k combinations of vertices, not all k-tuples (n^k of them).
• connected(tuple) doesn't look right. Don't you need to reset unconnected inside the loop?
• As the others have suggested, there are better ways of brute-forcing this. Consider the following recursive relation: A (k+1)-subgraph is a clique if the first k vertices form a clique and vertex (k+1) is adjacent to each of the first k vertices. You can apply this in two directions:
  • Start with a 1-clique and gradually expand the clique until you get the desired size. For example, if m is the largest vertex in the current clique, try to add vertex {m+1, m+2, ..., n-1} to get a clique that is one vertex larger. (This is similar to a depth-first tree traversal, where the children of a tree node are the vertices larger than the largest vertex in the current clique.)
  • Start with a subgraph of the desired size and check if it is a clique, using the recursive relation. Set up a memoization table to store results along the way.
• (implementation suggestion) Use an adjacency matrix (0-1) to represent edges in the graph.
• (initial pruning) Throw away all vertices with degree less than k.