2

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

Improve this question

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

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).
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.
NP-Hard, does that mean there is no pseudo P solution either?
@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.
0

Found this on the web, probably from a class" To accompany the text ``Introduction to Parallel Computing'', Addison Wesley, 2003

Finding a Maximal Independent Set (MIS)

parallel MIS algorithms use randimization to gain concurrency (Luby's algorithm for graph coloring). Initially, each node is in the candidate set C. Each node generates a (unique) random number and communicates it to its neighbors. If a nodes number exceeds that of all its neighbors, it joins set I. All of its neighbors are removed from C. This process continues until C is empty. On average, this algorithm converges after O(log|V|) such steps.
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.