Clique problem algorithm design

Question

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.

Bridging

You meant complete subgraph of size k right? Also, I think k isn't used in your pseudocode. – Beisel

Yup, you're correct on both counts. :-) – Bridging

@Jason: There are n vertices right, i.e. A[1,...,n]? – Beisel

Arghhh... I got it wrong in the above. I meant A[0,...,n-1] though I suppose A[1,...,n] would work as well. – Bridging

@Jason: Suggestion: Could you document what the two functions are suppose to do? – Beisel

Answer 1

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.

Beisel

Answer 2

I once implemented an algorithm to find all maximal cliques in a graph, which is a similar problem to yours. The way I did it was based on this paper: http://portal.acm.org/citation.cfm?doid=362342.362367 - it described a backtracking solution which I found very useful as a guide, although I changed quite a lot from that paper. You'd need a subscription to get at that though, but I presume your University would have one available.

One thing about that paper though is I really think they should have named the "not set" the "already considered set" because it's just too confusing otherwise.

Gimp

Answer 3

The algorithm "for each k-tuple of vertices, if it is a clique, then return true" works for sure. However, it's brute force, which is probably not what an algorithms course is searching for. Instead, consider the following:

1. Every vertex is a 1-clique.
2. For every 1-clique, every vertex that connects to the vertex in the 1-clique contributes to a 2-clique.
3. For every 2-clique, every vertex that connects to each vertex in the 2-clique contributes to a 3-clique.
4. ...
5. For every (k-1)-clique, every vertex that connects to each vertex in the (k-1) clique contributes to a k-clique.

This idea might lead to a better approach.

Broker

Answer 4

It's amazing what typing things down as a question will show you about what you've just written. This line:

P = A x A x A  //Cartesian product

should be this:

P = A ^k //Cartesian product

What do you mean by A^k? Are you taking a matrix product? If so, is A the adjacency matrix (you said it was an array of n+1 elements)?

In setbuilder notation, it would look something like this:

P = {(x0, x1, ... xk) | x0 ∈ A and x1 ∈ A ... and xk ∈ A}

It's basically just a Cartesian product of A taken k times. On paper, I wrote it down as k being a superscript of A (I just now figured out how to do that using markdown).

Plus, A is just an array of each individual vertex without regard for adjacency.

Bridging

What do you mean by A^k? Are you taking a matrix product? If so, is A the adjacency matrix (you said it was an array of n+1 elements)? – Beisel

I believe A is an unordered list of nodes, ie 1, 2, 3, ... ,n. A^k gives every possible length-k combination of them. Then he checks whether any given combination is connected, ie, a clique. – Pseudonymous

@Zach: A^k is just the Cartesian product A×A×…A (k times), as the comment and the answer says. [It consists of k-tuples (u,v,w,...) where each of the elements is in A.] – Seise

Thank you Paul. You said it better than I could. :-) I'll take this as a prompt that I might need to reconsider a more readable way of doing this. – Bridging

Ah I see. So the edges in the graph are not explicit in your code right? – Beisel