10
$\begingroup$

Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$ find an algorithm which either finds a permutation $\pi$ of the set $\{1, 2, \dots, n\}$ such that $$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$$ or correctly determines that no such permutation exists. Less formally, we want to reorder the numbers 1 through $n$; each triple $(i,j,k)$ in $S$ indicates that $i$ must appear before $k$ in the new order, but $j$ must not appear between $i$ and $k$.

Example 1

Suppose $n=5$ and $S = \{(1,2,3), (2,3,4)\}$. Then

  • $\pi = (5, 4, 3, 2, 1)$ is not a valid permutation, because $(1, 2, 3)\in S$, but $\pi(1) > \pi(3)$.

  • $\pi = (1, 2, 4, 5, 3)$ is not a valid permutation, because $(1, 2, 3) \in S$ but $\pi(1) < \pi(3) < \pi(5)$.

  • $(2, 4, 1, 3, 5)$ is a valid permutation.

Example 2

If $n=5$ and $S = \{(1, 2, 3), (2, 1, 3)\}$, there is no valid permutation. Similarly, there is no valid permutation if $n=5$ and $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$ (I think; may have made a mistake here).

Bonus: What properties of $S$ determine whether a feasible solution exists?

$\endgroup$
  • $\begingroup$ Why not rephrase the second condition as $(\sigma_{m_i},\sigma_{m_j},\sigma_{m_k})\in S\Longrightarrow (i>j \vee j>k)$? Then you have a straightforward, more-or-less, constraint satisfaction problem. (Note that I've simplified the condition based on the other assumptions.) $\endgroup$ – Dave Clarke Apr 13 '12 at 19:38
  • $\begingroup$ BTW: What is the motivation for this problem? $\endgroup$ – Dave Clarke Apr 13 '12 at 19:41
  • $\begingroup$ @DaveClarke See my edit. This problem has been abstracted out of a discussion surrounding a scheduling problem I was discussing with some other students in the lab. Basically, the idea is that you have lots of jobs, some of which have to execute in a certain order. However, you don't want some jobs being scheduled between jobs in a sequence, possibly for very subtle reasons. $\endgroup$ – Patrick87 Apr 13 '12 at 19:47
  • 3
    $\begingroup$ Why the sigmas? Just define $\Sigma = \{1,2,\dots,n\}$. Nested subscripts make the baby Jesus cry. $\endgroup$ – JeffE Apr 15 '12 at 8:43
  • $\begingroup$ @JeffE Honestly, I just like the excuse to play with the equation thing. There's something just viscerally satisfying about writing code that compiles to those little $\sigma$'s. Don't take that from me, man. $\endgroup$ – Patrick87 Apr 15 '12 at 11:23
3
$\begingroup$

Here's a naive algorithm. It relies ultimately on brute force, but may perform okay sometimes.

Each constraint $(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ consists of two conjuncts; let's call them type-$A$, $i < k$, and type-$B$, $\neg(i < j < k)$. Each type-$B$ constraint can be equivalently written as a disjunction $i>j \vee j>k$, relying on the fact that $i\neq j,j\neq k$.

  1. Collect all type-$A$ constraints. Call this $\Theta$. Check whether they are consistent, namely that this is a linearization of the ordering. This takes $O(|S|)$-time in the number of constraints using topological sorting.
  2. For each of the disjuncts in the type-$B$ constraint, check whether it is consistent with partial order $\Theta$. If it is not consistent, remove the disjunct. If both disjuncts are inconsistent with $\Theta$, then fail. Whenever just one type-$B$ constraint is removed, add the remaining one to $\Theta$. This step is $O(|S|^2)$.
  3. Now there's an obvious algorithm for finding a solution, namely to consider all combinations of the type-$B$ disjunction pairs and test their consistency with $\Theta$, but this is clearly exponential in $|S|$.
    One heuristic to improve performance would be to treat the type-$B$ disjunction pairs as the branches of a tree---one pair forms the root, it's children are given by the second pair, their children by the third and so forth. Using this data structure, a solution is found by traversing the tree in a depth-first fashion. Each time a new constraint is added (using the label on a branch), consistency can be checked. Inconsistent subtrees can be pruned.
  4. If a leaf of the tree is reached, then we have a consistent set of constraints consisting of all of the type-$A$ constraints and one disjunct of the type-$B$ constraints. Linearise the result to obtain the desired ordering.

My preferred approach would actually be to encode it into a set of constraints and use a constraint solver such as Choco. I would introduce $n$ integer variables $x_i$ in the range $[0,n-1]$ and require that they were all distinct. Then I would encode each of the constraints above directly as constraints and then let Choco do it's business.

$\endgroup$
1
$\begingroup$

Here is a partial answer:

If you remove the constraint $ i \lt k$ on each triple then your problem becomes the Non-Betweeness problem which is $NP$-complete and there are no known efficient algorithms for such problems. But with $i \lt k$ constraint, it may force some nice structure which can be exploited to find a polynomial time algorithm for your problem.

$\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.