Tag Archives: Difficulty 6

Consecutive Ones Matrix Partition

This is the problem I skipped over last week to get the two problems from Booth’s dissertation done together.

The problem: Consecutive Ones Matrix Partition.  This is problem SR15 in the appendix.

The description: Given an mxn matrix A consisting of 0’s and 1’s, can we partition the rows of A into two groups m1 and m2 such that the matrices A1 = m1x n and A2 = m2x n both have the consecutive ones property?

Example: Here’s the matrix that does not have the consecutive ones property.

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

But if we break it into two matrices, for example:

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


0 0 1 1 0
1 1 0 0 0

The two matrices have the consecutive ones property (the second matrix already has it, the top matrix has it if you exchange the 4th and 5th columns.)

Reduction: G&J point to a “private communication”, but I found a technical report by Lipski that explains the reduction.  The reduction is from Hamiltonian Path on cubic graphs (each vertex has degree at most 3).  So we start with a graph G=(V,E) where each vertex is degree 3 or less.  We construct a new graph G’=(V’,E’) where G’ adds new vertices and edges so that each vertex in V has degree 4.  Each new vertex has degree 1 (and so the new edges we add to V always connect to distinct new vertices).  Take the incidence matrix of this graph (as defined in the Consecutive Ones Submatrix problem) and use it as A.

If G has a Hamiltonian Path, then we can split A into two parts: the vertices in the path (thus, all of V) and everything else.  The Hamiltonian Path has the consecutive ones property, just like we saw in the Consecutive Ones Submatrix problem.  The other rows just map to disjoint paths of length 2 (two degree one edges connected by some vertex in V) so will be able to be rearranged.

If A has a partition that works, then choose some vertex v in V.  Suppose it ends up in A1.  We know that this vertex has degree 4.  We also know that to satisfy the consecutive ones property, v needs to be adjacent to exactly 2 things in A1 and 2 things in A2 for the consecutive ones property to work out.  The vertices in A1 need to form a chain of vertices all in V to make the consecutive ones property hold, so will form a Hamiltonian Path.

Difficulty: 6.  The paper glosses over a lot of detail, and I did to.  For example, the paper says “Without loss of generality we may assume that V ∈ M1” (the paper’s version of A1.  I don’t think it’s obvious at all that the entirety of V will end up all in one partition or the other.  I think it’s true, but I think it needs more work from a student to explain why it works.

Consecutive Ones Matrix Augmentation

While I had the dissertation I needed for the last problem, and before I had to send it back (without making copies), I skipped ahead to another problem that used it as a reference.

The problem: Consecutive Ones Matrix Augmentation.  This is problem SR16 in the appendix.

The description: Given an mxn matrix of 0’s and 1’s and a positive integer K, can we change K or fewer 0’s into 1’s to give the matrix the consecutive ones property.  See the Consecutive Ones Submatrix problem for more detail on this property.

Example: Here is the matrix that did not have the property from last week:

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

Recall that we’re looking for a way to  permute the columns so that there are no gaps in the 1’s in each row.  The easy solution here is to add a 1 in the second row (making it all 1’s).  In that case, the matrix has the consecutive ones property without needing any column permutations.

Reduction: Again, it is found in the dissertation by Booth, but this time uses Optimal Linear Arrangement.  Recall in that problem we were given a graph and needed to find an ordering of vertices to minimize the “score” of the differences of the ordering values.

The corresponding idea here is to start with the graph and build an incidence matrix, just like in the Consecutive Ones Submatrix problem.  We notice that any permutation of the rows (in the dissertation, you permute the rows to find consecutive ones in each column) corresponds to a permutation of the vertices in the OLA problem.  If we took a permutation of the vertices, each edge (column) of the incidence matrix has exactly two 1’s in it.  There may or may not be any 0’s between those ones, but if there are, we can convert those 0’s into 1’s (this is the augmentation).

The way these problems relate is that if an edge exists between two vertices, vi and vj, located at positions i and j in the final permutation, that edge adds j-i to the cost (assuming j > i).  In our matrix, if we permute the row corresponding to vertex vi to row i, and permute the row corresponding to vertex vj to row j, then there are j-i-1 o’s between the two rows.  So we could set them all to 1, and that column would have the consecutive ones property.

Thus, a solution of cost K to the OLA problem corresponds to a solution to the Consecutive Ones Matrix Augmentation problem of cost K-|E|, since there are |E| columns in the incidence matrix, and each one differs by 1 from the OLA cost of the edge.

Difficulty: 6, mainly because of the incidence matrix/adjacency matrix difficulty I talked about last time, but also because OLA is not easy to get.  If you’ve already shown them incidence matrices (for example, because you’ve gone over the Consecutive Ones Submatrix problem), then this is probably a 4.

Sparse Matrix Compression

Here’s the problem I’ve been dreading for months.  I haven’t been able to track down the reference, and I haven’t been able to come up with a full reduction on my own.  I’ve decided that I fundamentally don’t understand the way G&J are explaining the problem and have come up with an alternate problem statement that I think meets the same goals.

The problem: Sparse Matrix Compression.  This is problem SR13 in the appendix.

G&J’s description: Given an mxn matrix A where each entry in the matrix is either 0 or 1, and an integer K ≤ m*n.  Can we find a sequence B of n+K integers, each of which is between 0 and m (inclusive), and a function s mapping the numbers from 1 to m to the numbers 1 to K, such that aij = 1 if and only if bs(i)+j-1 = i?

Example: So what does this have to do with compression, you may be asking? The idea is that the b sequence will tell us how to find runs of 1’s in various rows, and the s function tells us where each row’s sequence begins.

So, suppose this is our matrix:

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

The first row implies that the B sequence needs to have 1x1x in it (the x’s can be anything that’s not a 1)

The second row implies that the B sequence needs xx22 in it.

The third row implies that the B sequence needs xxx3

The fourth row implies that the B sequence needs 44xx

The shortest way I can make all of that happen is 4413122X.  In this case, s(1) = 2,  (the sequence starting at position 2: 4131 is the sequence for the first row), s(2) = 4, s(3)=1, s(4) = 1.  The X at the end can be any number, but needs to be there because the sequence needs to be of size n+K, and  the s values need to map from 1-K, and we have s(2) = 4.

(Non-)Reduction: G&J’s reference is to an “unpublished manuscript”, and they say to use graph 3- coloring, and to set K=3 (presumably related to the number of colors).  I’ve been thinking about this for months, and I think I just misunderstand the problem.   I have a real problem trying to understand the use of the K values- setting K=3 means that each row can only map to 1,2, or 3 via the s function.  And if two (or more!) rows have the same s value that means they can have no 1’s in common.  So since there are only 3 s values, if the graph is colorable, that means every row in the matrix needs to map into 3 groups of rows, where for each row they have no 1’s in common.

Which seems like the start of a good idea (the three groups are the three colors of vertices, two rows go into the same group if they can be colored the same and don’t share an edge), except that then you have to come up with a way to eventually get a number in the sequence for each 1 in each row and you need to worry about the fact that the groups that map to the other colors are starting right next to where your group starts (since every s(i) has to map to 1,2,or 3, they all have to start at one of the first 3 positions in the sequence, so for example b4 is the 4th thing in sequence 1, the 3rd thing in sequence 2, and the third thing in sequence 3.  So there needs to be at most one 1 out of all of those overlapping rows), and I couldn’t make this all work out.

Instead, I started thinking about how this problem looks an awful lot like Shortest Common Superstring– We need a common string that holds all of the strings corresponding to each row.

So, let me rewrite the problem as follows: Can we come up with a sequence B of 0’s and 1’s, and a function s such that bs(i)+j-1 = aij? Using this formulation, the best solution I could come up with for my example above was 1100011010.  s(1) = 7, s(2) = 4, s(3) = 3, s(4) = 1.  But on more sparse (or more similar) matrices, the string can get much shorter: If the matrix was 4 copies of the same row 0011, then 0011 can be the result string and s(i) = 1 for all i.  The 4×4 identity matrix can have the b sequence 0001000 and s(1) = 4, s(2) = 3, s(3)=2, s(1) = 1

This is “equivalent” to G&J’s description in the sense that it captures the same desires of the original problem- take a two-dimensional matrix that consists of 0’s and 1’s, and generate a (preferably short) one-dimensional representation with an index function that tells you where each row starts.  In this new formulation, the s function points to the start of each string, and now aij = 1 if and only if the corresponding element in the sequence is 1 (instead of i).  What isn’t so obvious to make equivalent is the K in the original problem (the number of “starting positions” you need to add to N to make the sequence) and the K here (the size of the resulting sequence).  I think it has to do with the structure of the underlying pattern of 0’s and 1’s in each row.  If there is a way to make those K’s translate in polynomial time, then this formulation is truly equivalent to G&J’s.

So now what we need is an instance of SCS where all strings are in the alphabet {0,1} (the problem is still NP-Complete in this case), make them be the rows of our matrix, and set the K’ of the Sparse Matrix Compression problem to be the K of the SCS problem, and it should work out.  I’m not 100% convinced this works, but it seems like it should.

Difficulty: 6.  Mainly because it’s so hard for me to understand the problem, but also seeing how it maps to SCS is not trivial.  But the problem as written by G&J is still unsolved.  Hopefully someone out there can explain how to solve that problem.

Protected: Rooted Tree Storage Assignment

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

Protected: Kth Largest m-Tuple

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

Protected: Numerical 3-Dimensional Matching

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

Protected: Minimum Broadcast Time

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

Protected: Edge Embedding On A Grid

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

Protected: Undirected Flow With Lower Bounds

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

Protected: Minimum Cut Into Bounded Sets

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