From: Jeff Hoffman <Jeff.Hoffman@aud.alcatel.com>
Subject: Re: Graphs : Finding largest complete subgraph.
Date: Fri, 18 Feb 2000 13:16:17 -0600
Newsgroups: alt.sci.math.combinatorics,sci.math

Robert Israel wrote:

> I believe the problem of existence of a complete subgraph of order k is
> NP-complete, so yes, your algorithm will be exponential in general.  One
> idea: pick a vertex x, look (recursively) at
> a) complete subgraphs containing x (note that these will consist of x plus
> a complete subgraph of the neighbours of x)
> b) complete subgraphs of the graph obtained by deleting x.
>
> Robert Israel                                israel@math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel
> University of British Columbia
> Vancouver, BC, Canada V6T 1Z2

Wow.  I would have used gobs of arrays to find all K(3) then all K(4)....
Yours is much more elegant.  Why is it that the good solutions only seem
obvious *after* you see them? :-)

I was wondering if this would run significantly faster if the max subgraph
was stored somewhere.  The b) branch could be skipped if there weren't enough
points left to get a bigger subgraph.  I know it would depend on the type of
input data, but what about the general case, like half of all possible
edges?  Would it decrease only by a linear amount of time or would it reduce
the exponential term (or not enough to notice)?

Just curious,
Jeff H