Algorithm to find 'maximal' independent set in a simple graph

views:

154

answers:

Algorithm to find 'maximal' independent set in a simple graph

Hi,

in words, can someone post directions towards finding the 'maximal' independent set in a simple graph?

I read up something from ETH site which said one can find such in O(n) by simply picking a random vertex v and than scanning the rest and attempting to find if there's an edge from v to the rest.

Thanks

+4 A:

Yes, by definition, a maximal indpendent set is an independent set to which no more vertices can be added without violating the 'independence' condition.

So just picking vertices till you can pick no more would give you a maximal independent set, can be done in linear time (i.e. linear in |V| + |E|).

Note, this is different from maximum independent set, which is an independent set of the largest possible size and finding that is NP-Hard.

Moron 2010-06-03 02:29:51

But that's O(m^2), where m is the size of the independent set you find. For a graph with very few edges, that is close to O(n^2).

Artelius 2010-06-03 02:52:43

It is linear in number of edges. In graph problems, the representation matters and linear usually means |V| + |E|. Technically speaking, size of input could be larger than |V| + |E|. Sorry if that was not clear. I will edit the answer.

Moron 2010-06-03 03:10:23

NP-Hard, does that mean there is no pseudo P solution either?

Thomas Ahle 2010-06-03 13:59:32

@Thomas. No, even subset sum problem is NP-Hard which has pseudo P solutions. NP-Hard = at least as hard as any problem in NP. It has got nothing to do with pseudo P solutions. If that problem is also in NP, then it becomes NP-Complete. I wasn't sure if this was in NP, so didn't mention it.

Moron 2010-06-03 14:27:53

ansaurus

tags:

views:

answers:

Algorithm to find 'maximal' independent set in a simple graph

related questions