[GAP Forum] a graph question

Dmitrii Pasechnik dima at thi.informatik.uni-frankfurt.de
Wed Jun 16 00:37:31 BST 2004

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


More information about the Forum mailing list