This problem is apparently one of the more famous “unpublished manuscript” problems. The reference in G&J is an unpublished manuscript by William Masek. David Johnson mentioned in one of his NP-Completeness columns that Masek had “disappeared from the theory community”, but Johnson had the manuscript, and put out a call to Masek for permission to publish it as an article. I guess that he never resurfaced, since I can’t find anything. I did find a different paper that explains the reduction though, so we’ll use that.
The problem: Rectilinear Picture Compression. This is problem SR25 in the appendix.
Description: Given an NxN matrix M, consisting of 0’s and 1’s, and a positive integer K, can we find K or fewer rectangles in M that cover precisely all of the 1’s in M?
Example: Suppose M was:
Here is what I think the best way to draw rectangles is:
Notice that 1×1 rectangles are allowed, and by the way I read the problem definition you can have a cell that is in multiple rectangles. (What you can’t have is a 0 inside a rectangle, or a 1 outside of a rectangle).
Reduction: The good news about Johnson’s NP-Competeness column is that it led me to a technical report by Conn and O’Rourke that explains most of the details of Masek’s reduction. Which is a good thing, because it’s very complicated. He basically defines shapes of 1’s as “wires” running through the matrix. Here are the examples in the Conn and O’Rourke paper:
These wires will be used to represent boolean expressions (truth values are expressed as rectangles of 1’s: True is a 2×1 rectangle, false is a 1×2) Masek then proves several lemmas about how many rectangles it takes to cover each figure, and gives an algorithm to show how to build a figure with the wire components for any boolean expression. From the “how many rectangles does it take to cover each figure” lemmas, we know how many rectangles it will take to cover the figure if it is satisfiable, which becomes the K for the problem.
Difficulty: 9, maybe 10. The Conn and O’Rourke paper doesn’t actually show the proofs of any of these lemmas, but I believe I could follow the reduction if I had access to the lemmas and the construction algorithm.