Next: MAXIMUM INDUCED SUBGRAPH WITH Up: Subgraphs and Supergraphs Previous: MAXIMUM INDEPENDENT SET Index

### MAXIMUM INDEPENDENT SEQUENCE

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