This one moves slightly away from the matrix stuff we’ve been doing, but results in a pretty cool reduction.

**The problem: **Consecutive Sets. This is problem SR18 in the appendix.

**The description: **Given a collection C of subsets of a finite alphabet Σ, and a positive integer K, can I find a string w from ∑* with K symbols or less, such that each element in C has its characters occur sequentially in w?

**Example: **Let ∑ = {a,b,c,d,e} and C = {{a,b,c}, {a,d,e}, {b,e}, {c,d}}

Then I can choose w to be dcbadeb, which is length 7, which is the best I could find. Notice how positions 2-4 contain {a,b,c}, positions 4-6 contain {a,d,e}, positions 6-7 contain {b,e}, and positions 1-2 contain {c,d}.

**Reduction: **This is “Problem 4” in the paper by Kou from last week. He reduces from Hamiltonian Path. So we start with a graph G=(V,E). Our alphabet Σ (he uses “R” in the paper) has one symbol for each vertex in V and one symbol for each edge in E. Our C set (he uses F in the paper) will have one set for each vertex. The symbols in the set for a vertex i will consist of the edge symbols for the edges incident on i, and the vertex symbol for i itself. K will be 2*|E|+1.

Notice that no two sets in C are subsets of each other (because they each hold a separate symbol from V), and that the intersection of 2 sets from C is a single edge (the edge connecting the two vertices corresponding to the sets), if that edge exists, and the intersection is empty otherwise. A string w that we make will be based on a sequence of vertices (and their C sets). Since each edge appears in two C sets, the “initial” size of w is 2|E| + |V|, if we have no overlap between C sets in w. The question is how small can it get?

Since each C set can have at most one symbol of overlap with another C set, and that only happens if an edge exists between the vertices that define the C sets, the only way to create an overlap to reduce the size of w is to order the vertices such that there are edges between consecutive pairs of vertices. G has a Hamiltonian Path if and only if we can order the vertices in such a way that there is an edge bewteen each part of consecutive vertices. In w, that means we can overlap 1 symbol from each pair of consecutive C sets. Since there are |V|-1 pairs of vertices in a path, the minimum size of w is 2|E| + |V| – (|V|-1) = 2|E| + 1 = K.

**Difficulty: **5. I think this is a neat reduction that students can get, though it might take a bit of work to make sure they understand the problem.