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.
- 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])$.
- 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.
- 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$.
- 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.