0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This one is easy because its graph is a cycle of odd length. $\endgroup$ – coffeemath Apr 4 '16 at 16:53
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.