[GAP Forum] a graph question

[Dmitrii Pasechnik]

Dear GAP forum,

On Tue, Jun 15, 2004 at 12:48:07PM +0100, Petra Holmes wrote:
> I have a graph on about 25000 points.  I would like to find the size of a
> maximal set of pairwise non-adjacent points.  Is there a way to do this in
> GAP?
> 
that's an NP-hard problem, moreover, a
one that is hard to approximate. Unless the graph is very dence, you might be 
seriously out of luck, no matter what software you're using.

You might have to combine information about co-cliques you know
with upper bounds on their size, such as one can obtain from
the information on the graph spectrum, etc...

HTH,
Dmitrii