Not All Equal 2-Sat Problem

Question

I'm going over past papers for my exam and I came across this question. The only time I have heard of "Not-All-Equal" was as a 3-Sat problem, so I'm wondering if this question does actually mean 2-Sat and if so, could you possibly explain?

I dont really want an answer, I'd much rather an explaination so that I can work it out for myself.

Question: We consider a special case of the Not-All-Equal 2-SAT problem where no literal contains a negation. The task is to decide if it i s possible to assign truth values to the variables such that each clause has one literal that is true and one that is false. Recall that 2-COL (or 2-Colourability) is the decision problem where the input is a graph and the task is to determine if the vertices can be coloured by 2 colours such that neighbouring vertices (vertices joint with an edge) have different colours.

a) Consider the Not-All-Equal 2-SAT problem given by the clauses

{x1, x2}, {x2, x3}, {x3, x4}, {x4, x5}, {x5, x1}

Are these clauses Not-All-Equal satisfiable? Explain why this problem is equivalent to a 2- COL problem.

Draw the graph for this 2-COL problem and explain why the graph not is 2-Colourable.

Answer 1

I assume your notation $\{x_i,x_j\}$ which you call a clause is just a set of two propositions $x_i$ and $x_j$ and that clause is called "not-all-equal" satisfiable provided one may assign truth values such that one of $x_i,x_j$ is T (true) and the other F (false).

Since it doesn't matter which is a true, it makes sense to draw this particular clause as a line segment connecting nodes $x_i$ and $x_j.$ In any given situation we make nodes for each proposition and connect any two that appear in the same clause. This is the connection to 2-colorability since if A,B colors denote T,F then the clause is not-all-equal satisfiable iff there is a two coloring such that no two nodes connected by a segment should be the same color.

In your specific problem mentioned, after drawing the five nodes and connecting the pairs which are in the same clause you get a cycle of length 5. The reason that can't be 2 colorable is that if you start out with say color B, the colors must alternate and you have B,A,B,A,B with B at the fifth node, but this node connects to the first node already colored B making it impossible to finish the coloring.

In general I guess any graph not having an odd length loop as a subgraph anywhere could be 2-colored, but that's just an initial intuition. Probably a proof could be found using a google on "two colored graphs" or the like.

Answer 2

Create an undirected graph. For each variable, and its negation, create a vertex. Add an edge to each vertex and negation. (By definition A cannot equal not A.) For each variable pair that cannot be equal, add an undirected edge to the corresponding vertices.

Finding values for the variables so that they're not equal is equivalent to finding a 2-coloring in the graph.

"Cannot be equal" is equivalent to the boolean operator "XOR". Thus this is also "XOR-SAT."

This is L-complete I believe.

---

The only time I have heard of "Not-All-Equal" was as a 3-Sat problem

"Not all equal" with 3 or more variables is equivalent to hypergraph coloring.

Regular SAT is all true okay, but all false not okay. Hyper graph coloring is "all true not okay" and "all false not okay", "everything else is fine". Hypergraph coloring and 3-SAT coloring are both NP-complete.