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.