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.
But if we break it into two matrices, for example:
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.