Re: maximum clique algorithm

In article <[email protected]>,
 David Hysom <[email protected]> wrote:

> I'm working on a bioinformatics problem, in the course of which I found 
> I needed
> an algorithm to enumerate all cliques in a series of graphs.  Since I 
> couldn't find
> any algorithm/implementation I liked, I designed an algorithm from 
> scratch (computes
> exact answer, not heuristic).  I later realized the algorithm is 
> amenable to parallelization.
> 
> I've looked around the web a bit, and haven't found an algorithm that's 
> similar to what
> I came up with.  If any of you have expertise in this area to the extent 
> that you can
> judge the novelty of my design, please write and I'll furnish further 
> details.
> 
> - thanks David Hysom
> Center for Applied Scientific Computing (CASC)
> Lawrence Livermore Nat. Lab.

What size graphs and what size cliques are you searching for?
By clique you mean maximal complete subgraph, not just complete 
subgraph, right?  The problem is equivalent to searching for all maximal 
independent sets in the complement graph, of course.

I have a recent paper on the subject at 
http://arxiv.org/abs/cs.DS/0407036
and a Python implementation of one of the algorithms from that paper 
which I'd be happy to email you.

But (from the point of view of listing cliques) that algorithm is tuned 
for relatively small but dense graphs. You can do better for sparse 
graphs e.g. by removing vertices one at a time, lowest degree vertex 
first, and finding cliques in the neighborhood of each removed vertex.

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/