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.