December | 2022 | Discussions of NP-Complete Problems

Monthly Archives: December 2022

Cyclic Ordering

Posted on December 21, 2022 | Leave a comment

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₁..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 Δ⁰: {(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 Δ⁰ 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 Δ⁰, 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 Δ⁰. 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 Δ⁰. 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 Δ⁰, then (c,j,k) is effectively a triple, and since (c,k,l) is in Δ⁰, 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 Δ⁰, 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.

Betweenness

Posted on December 7, 2022 | Leave a comment

The last section is on “Miscellaneous” problems. There are some weird ones in here, but we start with a pretty straightforward number problem.

The problem: Betweenness. This is problem MS1 in the appendix.

The description: Given a set C of triples (a,b,c), where each element of each triple comes from a superset A, can we find an ordering of the elements of A such that according to that ordering, each triple is in either increasing or decreasing order?

Example: It’s actually hard to do a good example for this because most groups of symbols (digits, letters, subscripts, …) have an implicit ordering of elements, and to go against that would be confusing. Having random symbols without connotations of meaning gets pretty confusing pretty quickly as well.

So let’s lean in and say A = {a,b,c,d,e,f} and our triples are:

(a,d,f)
(f,d,b)
(h,d,a)
(f,g,h)
(d,f,h)

We’re allowed any ordering of the elements of A, and the “normal” lexicographical one with ‘a’ first and ‘f’ last satisfies the betweenness rules.

But now suppose we add the new triple: (b,a,d). That is an illegal triple in our normal order, but if we change our ordering so that ‘b’ is first and ‘a’ is second, we can still satisfy all of the triples.

Reduction: The paper by Opatrny uses Hypergraph 2-Colorability (which we called “Set Splitting”). Recall that our reduction only made sets of size 3, so we can start with an instance where each set has at most 3 elements (or, each hyperedge connects at most 3 vertices).

So, suppose we have a set of N vertices s₁..s_n, a set of J 3-vertex hyperedges (a_i, b_i, c_i), as well as M 2-vertex “regular” edges (d_i, e_i).

Our first job is to build superset A. It has:

One symbol for each vertex,
A new symbol X.
A set of J new symbols Y_k, one for each 3-vertex hyperedge.

Now we build C.

Each hyperedge (a_k, b_k, c_k) generates two triples: (a_k, Y_k, b_k) and (Y_k, X, c_k)
Each two-vertex edge (d_k, e_k) generates the triple (d_k, X, e_k)

Suppose the graph had a 2-coloring. Recall that meant that each vertex had a color (the paper uses red and blue) so that each edge and hyperedge touches vertices of both colors. We need to make an ordering of A that satisfies all triples. The ordering will have positive, negative, and rational ranks.

X has rank of 0.
If vertex s_i is red, its rank is i. If it’s blue, its rank is -i.
Each Y_i was associated with a hyperedge (a_i, b_i, c_i).
- If a_i and b_i have the same color (and so the same sign), Y_i‘s rank is min(rank(a_i), rank(b_i)) + $\frac{1}{i+1}$ .
- If they have different colors, the rank is $\frac{1}{i+1}$ if c_i is blue, and $-\frac{1}{i+1}$ if c_i is red

So, suppose every edge had 2 colors. We know:

If a_i and b_i are the same color, they are the same sign, and Y_i is between them, satisfying the (a_k, Y_k, b_k) triple.
If a_i and b_i are the same color, c_i must be the other color (and the other sign from Y_i), satisfying the (Y_k, X, c_k) triple.
If a_i and b_i are different colors, they are different signs. Setting Y_i to a value between 1 and -1 satisfies the (a_k, Y_k, b_k) triple.
If a_i and b_i are different colors, c_i can be either color, so making Y_i the opposite sign as c_i satisfies the (Y_k, X, c_k) triple.
An edge with just 2 vertices needs both vertices opposite colors, and thus opposite signs, so the (d_k, X, e_k) triple is satisfied.

So far, so good. In the opposite direction, suppose we have a solution to the betweenness instance. We’ll assign colors to vertices such that a vertex’s color is red if its rank is > X’s rank. Otherwise, it will be assigned blue. Our triples will now allow any set of a_i, b_i, and c_i to all be greater than or less than X (or for both d_i and e_i to be greater than or less than X), which means that every edge in the hypergraph has both a red and a blue vertex.

Difficulty: 7. It’s relatively easy to see what you need to do. It’s harder to make the numbers actually work. Even this paper has to resort to using rational numbers for the ranks, which is a fixable problem, but certainly not obvious.

Monthly Archives: December 2022

Cyclic Ordering

Betweenness

Recent Posts

Recent Comments

Archives

Categories