Next: MAXIMUM INDUCED SUBGRAPH WITH
Up: Subgraphs and Supergraphs
Previous: MAXIMUM INDEPENDENT SET
  Index
- INSTANCE:
Graph
.
- SOLUTION:
An independent sequence for G, i.e., a sequence
of
independent vertices of G such that, for all i < m, a vertex
exists which is adjacent to vi+1 but is not adjacent to any vj for
.
- MEASURE:
Length of the sequence, i.e., m.
- Good News:
Approximable within
[211].
- Bad News:
As hard as MAXIMUM INDEPENDENT SET [211].
Viggo Kann
1999-04-22