This problem is very similar to the Betweenness problem from last time, with a slightly different ordering rule.
The problem: Cyclic Ordering. This is problem MS2 in the appendix.
The description: Given a set C of triples (a,b,c) from some universal set A, can we find an ordering f of the elements of A, so that for each triple in C, either:
- f(a) < f(b ) < f(c)
- f(b) < f(c) < f(a)
- f(c) < f(a) < f(b)?
Example: Like last time, let’s say A = {a,b,c,d,e,f}. Here are some triples:
(a,b,c)
(e,b,c)
(a,e,f)
(e,f,a)
(d,f,c)
The usual lexicographic ordering of elements of A will satisfy these triples.
A triple that won’t work with that ordering is (a,e,b). But an ordering {a,e,b,c,d,f} would satisfy all triples including this new one.
Reduction: Galil and Megiddo use 3SAT. So we start with a formula with p clauses (each clause is xi∨ yi∨ zi) over r variables (u1..ur, and their negations). Order each clause so that the variables in it are in increasing order of their subscript. Our set A will have 3 elements for each variable ui: αi, βi and γi. It will also have 5 additional elements for each clause (these will be the j through n described below)
Each variable is “associated” with a triple from these elements of A. The positive version of the variable ui is associated with (αi, βi, γi). The negated version of the variable ~ui is associated with the triple (αi,γi, βi). These triples won’t get added to C, but will be the basis of the triples each clause adds to C.
So suppose we have a clause x∨y∨z. Each of these literals has a triple associated with it as defined above. Let’s call those triples (a,b,c), (d,e,f), and (g,h,i). Using those 9 symbols plus the “extra” symbols for this clause j,k,l,m, and n, create the following triples, called Δ0: {(a,c,j), (b,j,k}, (c,k,l), (d,f,j), (e,j,l), (f,l,m), (g,i,k), (h,k,m), (i,m,n), (n,m,l). These triples, for each clause, create our set of triples C.
Now, suppose we have an assignment of variables- a set S of ui and ~ui that has exactly one choice for each i. For each clause, build a set of triples Δ out of Δ0 and the triples associated with the literals not in S. Then if S includes a literal that makes the clause true, there is a way to satisfy every ordering in Δ. They show this with a table giving the possible assignments. Here are 2 examples:
- If S has just x in it (and not y and z), then Δ adds the triples (a,c,b), (d,e,f), and (g,h,i) and the ordering ackmbdefjlnghi will satisfy all triples.
- If S has y and z in it (and not z), then Δ adds the triples (a,b,c), (d,f,e), and (g,i,h) to Δ0, and the ordering abcjkdmflnegih will satisfy all triples.
In the other direction, if a clause is not satisfied by this assignment, then none of its literals are in S, and so we form Δ by adding the triples (a,b,c), (d,e,f), and (g,h,i) to Δ0. But if we had an ordering of the elements of A that satisfied the triple (a,b,c), it must also satisfy the triple (a,c,j) from Δ0. This means that (b,c,j) is effectively a triple as well (the ordering has to satisfy that triple as well). Since (b,j,k) is in Δ0, then (c,j,k) is effectively a triple, and since (c,k,l) is in Δ0, we can conclude that (j,k,l) must also satisfy the ordering.
We can perform a similar analysis to eventually conclude that (l,m,n) must also satisfy the ordering. But we have the triple (n,m,l) in Δ0, and there is no way to satisfy both consistently. Thus, if a clause is not satisfied, there is no legal ordering to satisfy all of the triples in Δ.
Taking this analysis and applying it to all clauses completes the reduction.
Difficulty: 8. It’s not obvious, at all, even looking at the problem, how you can come up with these different triples. I can (mostly) follow the logic and see that it works, but wow, coming up with this must have been a huge pain.