Talk:Independent set problem
From Wikipedia, the free encyclopedia
"A much easier problem to solve is that of finding a maximal independent set, which is an independent set not contained in any other independent set. We begin with a single vertex. We find a vertex not adjacent to it and add it, then find a vertex adjacent to neither of these and add it, and so on until we can find no more vertices to add. At this time the set is maximal independent."
This seems to be incorrect. Consider the set a--b--c, which has three nodes (a, b, c) and two edges (a-b, b-c). According to this description, we first pick an arbitrary single vertex. For this example, we pick b. There are no non-adjacent nodes left in the set, and so we conclude that the set (b) is maximally independent. However, the set (a, c) is really maximally independent.
- {b} is a maximal independent set, since it is not contained in any other independent set. It is not a maximum independent set (which is probably what you mean by "maximally independent"), but that wasn't claimed. --Mellum 22:32, 27 October 2006 (UTC)
