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 x_{i}∨ y_{i}∨ z_{i}) over r variables (u_{1}..u_{r}, 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 u_{i}: α_{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 u_{i} is associated with (α_{i}, β_{i}, γ_{i}). The negated version of the variable ~u_{i} 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 u_{i} and ~u_{i} 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.