<p>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. <strong>I'd just like some help constructing a graph s.t. the algorithm returns an incorrect result.</strong></p>

<p>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. </p>

<ol>
<li>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])$.</li>
<li>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.</li>
<li>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$.</li>
<li>Traverse the keys in $H$ again. This time print the contents of the value for a given key if value.count equals $m$.</li>
</ol>

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

<p>Regarding the algorithm's runtime: </p>

<ul>
<li>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.</li>
<li>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.</li>
<li>step three runs in linear time</li>
<li>step four runs in $O(N^2)$ time (when accounting for printing the nodes)</li>
</ul>

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

<p>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. <strong>Please help find some.</strong></p>

CC BY-SA 3.0
2012-01-04T16:22:43.903Z
IMO you should ask on some forums where people learn about algorithms, such as http://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.
Radu GRIGore
CC BY-SA 3.0
2012-01-04T17:46:07.417Z
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.
George
CC BY-SA 3.0
2012-01-05T09:06:09.477Z
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?
anonymous
CC BY-SA 3.0
2012-01-06T23:22:40.477Z
@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.
SundayMonday
CC BY-SA 3.0
2012-01-06T23:37:59.373Z
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$.
SundayMonday
<ds.algorithms><graph-algorithms><clique><examples>
Maximum clique algorithm on undirected graph
MrDatabase
# Maximum clique algorithm on undirected graph

(Asked by: username_0 on 2012-01-04)

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.**

**Tags:** ds.algorithms, graph-algorithms, clique, examples

> **Comments:**
> **username_1**: IMO you should ask on some forums where people learn about algorithms, such as http://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.  
> **username_2**: 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.  
> **username_3**: 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?  
> **username_4**: @username_3 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.  
> **username_4**: 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$.  

---

## 0 answers

