[GAP Forum] a graph question

[Steve Linton]

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

On Wed, 16 Jun 2004 01:37:31 +0200, Dmitrii Pasechnik
<dima at thi.informatik.uni-frankfurt.de> wrote:

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

Dima is correct, of course, that this is a very hard problem in general. It is,
however, also worth mentioning the facilities of Len Soicher's GRAPE package,
which include a function CompleteSubgraphs, which (up to taking the complement
of your graph) does what you want. The effectiveness of the GRAPE function
(and indeed of the whole of GRAPE) depends greatly on whether you know or can
find a sizable subgroup of the automorphism group of your graph. While 25000 is
pretty large, you might be able to get somewhere if there is a big group
acting. See the GRAPE manual for details.

	Steve


-- 
Steve Linton	School of Computer Science  &
      Centre for Interdisciplinary Research in Computational Algebra
	     University of St Andrews 	 Tel   +44 (1334) 463269
http://www.dcs.st-and.ac.uk/~sal	 Fax   +44 (1334) 463278