These next two problems are very similar to the “consecutive ones” problems we’ve been looking at lately.
The problem: Consecutive Block Minimization. This is problem SR17 in the appendix.
The description: Given an m x n matrix A consisting of 0’s and 1’s and a positive integer K, can we permute the columns of A so that the permuted matrix (B) has K or less blocks of consecutive 1’s. G&J define a “block” as an entry bij =1 where bi,j+1 = 0 or j = n. So a “block” is one-dimensional, going across a row.
Example: Here’s a matrix:
Right now, this has 9 blocks (3 on the first row, 2 on the second and fifth, 1 on the third and fourth).
But we can permute the columns to get:
..for a total of 6 blocks.
Reduction: The paper by Kou has several reductions in it, we’ll be using this paper next week too. This problem is “Problem 3” in the paper. The problem uses Hamiltonian Path, but with costs for edges, so it’s really more like “Traveling Salesman on Paths”. His “Problem 2” takes an instance of regular Hamiltonian Path and shows that this “Traveling Salesman on Paths” problem is NP-Complete on “cost graphs”.
Kou defines a “cost graph” of a matrix as a complete graph that has one vertex for each row and an edge cost of edge (i,j) as the number of columns in A that have a 1 in row i and a 0 in row j. He proves in the paper that a Hamiltonian Path on the cost graph has cost k iff there are k+c blocks of 1’s in the matrix, where c is the number of 1’s in the last row in the matrix.
So, the full reduction takes an instance of HP, creates an incidence matrix (as we defined in the Consecutive Ones Matrix Augmentation problem), builds a cost graph of that, and uses that cost graph as the input to the Consecutive Block minimization problem.
Difficulty: 7. The cost graph construction is pretty hard to grasp, and you need to prove some extra lemmas along the way to show that the transformation works.