Hint for problem 7.23:
First, note that the subsequences need not be contiguous!
I.e., "ace" is a substring of "abcde".
Instead of using vertex cover, use (the closely related problem)
independent set.
Given an undirected graph G = (V,E), V = {v1, v2, ..., vn},
transform it into the following set of |E|+1 strings:
* v1, v2, ..., vn
* for each edge (vi, vj) in E (i > j), (*CORRECTION! First leave out
the larger endpoint, then leave out the smaller endpoint*)
v1, ..., v(i-1), v(i+1), ..., vn, v1, ..., v(j-1), v(j+1), ..., vn
Now show that v(i1), v(i2), ..., v(ik) is a vertex cover of G
iff it is a common substring of these strings.