MAXIMUM INDEPENDENT SEQUENCE

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: An independent sequence for G, i.e., a sequence $v_1, \ldots, v_m$ of independent vertices of G such that, for all i < m, a vertex $\bar v_i \in V$ exists which is adjacent to $v_{i+1}$ but is not adjacent to any $v_j$ for $j \leq i$.
• MEASURE: Length of the sequence, i.e., m.

  
  

• Good News: Approximable within $O(\vert V\vert (\log\log \vert V\vert/\log \vert V\vert)^2)$ [224].
• Bad News: As hard as MAXIMUM INDEPENDENT SET [224].