2
$\begingroup$

Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. the algorithm returns an incorrect result.

Consider an undirected graph $G$ represented by an adjacency matrix $A$. If there exists an edge directly connecting node $i$ and node $j$ then $A[i][j] = 1$, $A[i][j] = 0$ otherwise.

  1. Construct a hashtable $H$ where the keys are nodes in $G$ and the values are lists of nodes directly connected to the given node. For example a simple triangle graph with nodes $a$, $b$ and $c$ would have $H$ with key-values pairs $(a, [b, c])$, $(b, [a, c])$ and $(c, [b, a])$.
  2. Traverse all keys in $H$. For each key traverse the corresponding value and check if every node in the list is connected to every other node in the list. If a node $i$ is not connected to any single node $j$ then remove $i$ from the list.
  3. Traverse the keys in $H$ again. Keep track of the maximum count $m$ of all values. $m$ will be the size of the maximum clique(s) in $G$.
  4. Traverse the keys in $H$ again. This time print the contents of the value for a given key if value.count equals $m$.

I've tried a variety of graphs as inputs and so far I haven't found a good counter example.

Regarding the algorithm's runtime:

  • step one can be done in $O(N^2)$ time. This requires visiting every entry of the $NxN$ adjacency matrix $A$. Inserting an entry into $H$ can be done in amortized constant time.
  • step two takes $O(N^3)$ time. Traverse every key in $O(N)$ time. For a given key $k$ checking all the directly connected nodes takes $O(N^2)$ time.
  • step three runs in linear time
  • step four runs in $O(N^2)$ time (when accounting for printing the nodes)

So the overall runtime is $O(N^3)$ where $N$ is the number of nodes in $G$.

From some research it doesn't sound like finding maximum cliques in an undirected graph (without any constraints on the graph) can be done in polynomial time. Hence there's probably some nice corner cases for the above algorithm. Please help find some.

Improve this question
$\endgroup$
5
  • $\begingroup$ IMO you should ask on some forums where people learn about algorithms, such as apps.topcoder.com/forums/?module=ThreadList&forumID=505803 . Also, instead of step 1 just say you start with adjacency lists, and don't bother describing steps 3 and 4. $\endgroup$
    – Radu GRIGore
    Jan 4, 2012 at 16:22
  • 2
    $\begingroup$ I think the problem lies in the removal of nodes in step 2. It may seem that the node you remove does not belong to the maximum clique, but in fact it may be (at least that's my intuition). Nevertheless this may be a good greedy approach in practice. $\endgroup$
    – George
    Jan 4, 2012 at 17:46
  • $\begingroup$ Thanks for the clarification; however, what happens if we rewrite step 2 to the following: Traverse all keys in $H$. For each key traverse the corresponding value and check if every node in the list is connected to every other node in the list. If a node i is not connected to any single node j then remove the key from the list Then, I seem unable to find a counterexample on which the algorithm does not find a maximum clique. Any suggestions? $\endgroup$
    – anonymous
    Jan 5, 2012 at 9:06
  • $\begingroup$ @anonymous I think the counter-example provided by Ricky Demer below will do. Using this graph as input to your modified algorithm will result in zero maximum cliques being found (every node in the maximum clique will have its corresponding entry inappropriately removed from H since every node in the max clique is directly connected to a node not in the max clique). However a maximum clique of size three exists. $\endgroup$
    – SundayMonday
    Jan 6, 2012 at 23:22
  • $\begingroup$ Also I'm not sure if you need to consider all $N!$ permutations of the nodes in step 2. Could you perhaps just consider all $2^N$ subsets? This seems to work for Ricky Demer's counter example. If this does work then it's complexity would be $N*2^N$. $\endgroup$
    – SundayMonday
    Jan 6, 2012 at 23:37

1 Answer 1

Reset to default
5
$\begingroup$

$A \; = \; \begin{bmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}$

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Indeed! I thought of this graph this morning. I thought of it as a triangle with three spikes. Anyways this graph shows that the order of the nodes in step 2 matters. Hence all N! permutations must be considered and nothing is gained over a brute force method. Afterthought: wonder if the nodes in step 2 could be ordered by increasing degree? $\endgroup$
    – MrDatabase
    Jan 4, 2012 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.