Tag Archives: Difficulty 5

Consecutive Sets

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.

Consecutive Ones Submatrix

This is another problem where the reference is a PhD thesis that they had to ship to the library.  Hopefully I don’t mess the description up, because it’ll be hard to get back.

The problem: Consecutive Ones Submatrix.  This is problem SR14 in the appendix.

The description: Given an mxn matrix A, consisting of only 0’s and 1’s, and a positive integer K, can we find an mxK submatrix B of A such that we can rearrange the columns of B so that in each row, all of the 1’s occur consecutively?  (This is called the “consecutive ones property” and will come up in several problems.)

Example: Suppose this was A:

1 0 0 0
0 1 0 1
0 1 1 1
0 0 1 0

If K=3, we could among other things, choose the last 3 columns of A for B, and rearrange the second and third columns to get:

0 0 0
1 1 0
1 1 1
0 0 1

..which has the property.

The dissertation by Booth which has the reduction gives this example of a matrix that has no permutation when K=N.  (Note in the dissertation, the consecutive ones property applies to columns, not rows, so I transposed the matrix in the paper)

0 1 1 1 1
1 1 1 0 1
0 0 1 1 0
0 1 1 0 0
1 1 0 0 0

The easiest way to see why this won’t work is to realize that the fourth column needs to go last (or first) and the first column needs to go first (or last) to keep the sequences of four 1’s from being split.  So our partial solution is:

0 1 1 1 1
1 1 1 1 0
0 x x x 1
0 y y y 0
1 z z z 0

The x’s are some permutation of “010”, which means the 1 has to go last, so that puts column 3 from the original matrix there:

0 1 1 1 1
1 1 1 1 0
0 0 0 1 1
0 y y 1 0
1 z z 0 0

The y’s need to be a permutation of 01 that has a 1 in the third column, so that means that the second column needs to go into the third spot.  But the z’s need a permutation of 01 that has a 1 in the second column, so that means that the second column needs to stay in the second spot.  So no permutation works.

(While I have the dissertation, he also claims that this matrix can’t be permuted either:

0 0 1 1 0
0 0 0 1 1
0 0 0 0 1
1 1 0 0 0
1 1 1 0 0

..but it seems like this would work:

0 0 1 1 0
0 0 0 1 1
0 0 0 0 1
1 1 0 0 0
1 1 1 0 0

Maybe I’m doing the transposition wrong.  Remember, in his problem definition he permutes rows to keep consecutive ones in the columns, so he actually starts with:

1 0 0 0 1
1 1 0 0 0
1 1 0 0 0
0 0 1 1 0
0 0 0 1 1

..but I can permute rows to get:

1 1 0 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 1
0 0 1 1 0

I bet there is a missing 1 someplace in that matrix.)

Reduction: Is from Hamiltonian Path.  Keeping in mind that Booth’s thesis defines the problem as permuting rows to have 1’s in consecutive columns, he defines the incidence matrix of a graph G=(V,E) to be a |V|x|E| matrix M where mij is 1 if vertex i is in edge j, and 0 otherwise.  Notice that each column has exactly two 1’s in it.

(To solve G&J’s version of the problem, you’d want M=|E|x|V| and mij = 1 iff vertex j is in edge i)

Now all we have to do is take a graph, build an incidence matrix, and see if we can rearrange the rows so that the consecutive 1’s property holds for n-1 of the rows.  (The row we leave out is for the connection from the last vertex in the path back to the first vertex in the path, which we don’t have to take).

Difficulty: 5.  I’ll admit to being a bit confused by trying to use an adjacency matrix instead of an incidence matrix.  And to not really understanding the problem definition (the examples in the thesis really helped).  But really, I should have gotten this without having to make them ship the thesis all the way from California.

Protected: Longest Common Subsequence

This content is password protected. To view it please enter your password below:

Protected: Expected Component Sum

This content is password protected. To view it please enter your password below:

Protected: Comparative Containment

This content is password protected. To view it please enter your password below:

Protected: Maximum Fixed-Length Disjoint Paths

This content is password protected. To view it please enter your password below:

Protected: Minimum Edge-Cost Flow

This content is password protected. To view it please enter your password below:

Protected: Kth Shortest Path

This content is password protected. To view it please enter your password below:

Protected: Shortest Weight-Constrained Path

This content is password protected. To view it please enter your password below:

Protected: Stacker-Crane

This content is password protected. To view it please enter your password below: