I found this problem’s in Bernard Moret’s Theory of Computation Textbook, and got the reduction from the solution manual.  It was nice to see a different problem in one of those books.

The problem: Matric Cover.  This is problem MS13 in the appendix.

The description: Given an NxN matrix A, where every entry is non-negative,  and an integer K, is there a function f that maps the set {1..n} to either 1 or -1, such that

?

Example: Here’s a simple matrix:

We’re trying to keep the sum of a_ij*f(i)*f(j) low.  My first impression was to make the function return -1 for all values. But that means we’re just adding all the a_ij values together (and multiplying by -1x-1=1) for a large sum.  This also means that no matter what we choose for f, all elements on the diagonal will count positively (this won’t be a problem once we use A to represent the adjacency matrix of a graph, since our graphs don’t have self-loops).  So the best we can do in this example is something like f(1)=1, f(2)=1, f(3) = -1, which gives us a sum of 5+0-2+1+2-0-0-3+4=7

Reduction: G&J and Moret both say to use Max-Cut, but since all we need is the adjacency matrix of the graph, and no weights, we can use Simple Max Cut (which we’ve been calling “Bipartite Subpgrah“).  We’re given a graph G, and an integer K, and want to know if we can find a partition of the vertices of G into two sets such that at least K edges cross between the sets.  So we’ll use the adjacency matrix of that graph as our A for Matrix Cover. We’ll set our K’ for Matrix cover to be 2(|E|-2K).  We’ll consider a function f that maps all vertices in one side of the partition as 1, and all vertices on the other side as -1.  This means that all edges that stay on the same side of the partition will contribute 1 to the sum, and all edges that cross the partition will contribute -1 to the sum.

If the Max-Cut instance is true, then there is a partition that has at least K edges cross, and so at least -K will be contributed to our sum.  At most |E|-K edges will not be cut in that case, so our total is (|E|-K)-K = |E|-2K.  We need to double this sum because the matrix is symmetric, and so edge (i,j) appears twice in the matrix.

Difficulty: 5.  I should have gotten this myself. It’s a bit tricky for a homework problem for students because of all of the details- it’s easy for example to miss the need to multiply by 2.  The fact that you don’t _make_ the f function, you just say it has to exist and have certain properties will confuse some students.     But if they know about Simple Max Cut, this is a good non-trivial one for good students.