Tag Archives: Simple Max-Cut

Simply Deviated Disjunction

Posted on January 19, 2024 | Leave a comment

This problem also uses Max-Cut, but is much harder, even to explain.

The problem: Simply Deviated Disjunction. This is problem MS14 in the appendix.

The description: I’ve gone back and forth a lot between G&J and the paper by Pudlak and Springsteel that has the reduction, and this is my best guess at what we’re trying to do: Let’s break this down into pieces:

We’re given a collection M of n tuples, each tuple has length m. Each element of a tuple (M_i[j] is the jth element in tuple i) has either the value 0 (meaning “false”), 1 (meaning “true”), or x (meaning “no information”). You can think of these as attribute values in a set of data. We’ll be doing logic operations on them, and we’ll be propogating the x’s when it potentially “matters” in the output. So, for example, 1∨x 1, because no matter what x really is the output is 1, but 1 ∧ x = x, because the output depends on what x is.

We then want to partition the tuples into two groups of tuples, I and J. We can order the tuples in I and J however we want. For each tuple, we want to know if the disjunction of all of the truth values is true or not. (So we “or” them all together- G&J’s definition allows us to pick whether we want each row to be true or false, but the paper only cares about whether we get true values or not). We are interested in 4 variables:

a: The number of rows k where the disjunction of the tuple at row k in I is true and the disjunction of the tuple at row k in J is true.
b: The number of rows k where the disjunction of the tuple at row k in I is true, and the disjunction of the tuple at row k in J is false.
c: The number of tows k where the disjunction of the tuple at row k in I is false, and the disjunction of the tuple at row k in J is true.
d: The number of rows k where the disjunction of the tuple at row k in I is false, and the disjunction of the tuple at row k in J is false.

It’s unclear what you do for a row that is in one of the two sets, since the sizes of the sets don’t have to be equal. I’m assuming that will never count towards the total, but maybe it’s meant to count as false.

Anyway, the problem asks: Can we set up I and J so that ad > bc? (This inequality is what “simply deviated” means).

Example: Suppose I have 6 tuples, each of length 3:

(1,1,1)
(1,0,+)
(0,0,1)
(+,0,0)
(0,0,0)

I set up my two lists like this:

I	J
(1,0,+)	(1,1,1)
(0,0,1)	(1,0,0)
(0,0,0)	(+,0,0)

Now we calculate the letters:

a=2 (rows 1 and 2 are true in both I and J)
d = 1 (row 3 is not true in both I and J)
b and c are 0 (no row is true in one set but not true in the other)

So a*d = 2, and b*c = 0, so ad > bc

Reduction: The paper again uses the general “Max Cut” problem, which is our Bipartite Subgraph problem but where the edges have weights. I think they would have been better off with our unweighted “Simple Max Cut” problem, as we’ll see. So we start with a weighted graph, and a K. Let’s call the sum of all of the weights (an edge that is not present has weight 0) w_h. Here are the tuples we make:

m₁ tuples of all zeros (we’ll figure out how many we’ll need soon)
m₂ tuples of all x’s (we’ll figure out how many we’ll need soon)
Then, for each pair of vertices (v,w) in the graph, if the weight of the edge is c, then c copies of a row of all 0’s except for a 1 corresponding to positions i and j. (So c copies of a tuple representing the edge).

I’ll stop here to point out that this third component creates w_h tuples, and since the weights of the edges are not necessarily polynomially bounded in the size of the graph, this won’t necessarily give us a polynomial time reduction. I could be misunderstanding what they are saying. But I also think if you use Simple Max Cut, all of the edge weights are 1 (and so w_h is |E|), and we avoid this issue.

Suppose we have a cut of the vertices into two sets A and B. We would like to set up I and J so that a is the total weight of the edges that cross the cut. (The paper says this is a “natural correspondence”, but I’m having trouble seeing it). If we do that, then d = m₁ (the rows of all 0’s), and b+c = m₂+w_h -a. I don’t exactly see where these results are coming from. But from there, we can compute that m₁ should be 1/4*w_h²*(K-2) and m₂ should be w_h*(k-2)-w_h+K-2. This is only positive when the weight of all edges across the cut is >= K

Difficulty: 10. I got pretty far following this, but some of the steps of the reduction I just don’t get. I’ll say that I’m pretty sure that I’m doing something wrong, possibly with the definition of the problem, because the paper says that the two-valued problem (with no +’s) is open, and I don’t know that I’m doing anything here that isn’t the same as treating x as 0.

Matrix Cover

Posted on January 8, 2024 | Leave a comment

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

$\sum_{1\leq i,j \leq n} (a_{ij}*f(i)*f(j)) \leq K$ ?

Example: Here’s a simple matrix:

$\begin{bmatrix} 5&0&2\\ 1&2&0\\ 0&3&4 \\ \end{bmatrix}$

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.