1
$\begingroup$

This problem's been stumping me for the better part of a week:

You're given a set of triplets of variables. The variables are all distinct and ordered. Each triplet $a,b,c$ means that either $a<b<c$ or $c<b<a$. The problem is to find an ordering of the variables satisfying all constraints.

For example, the set $\\{(a,b,c),(d,c,b),(b,d,e)\\}$ is solvable by assigning $a<b<c<d<e$. By symmetry you can assume $a<b<c$ to start, and the rest of the sequence is derivable by finding triplets where a pair has been seen already. In contrast, a set like $\\{(a,b,c),(a,c,b)\\}$ is unsatisfiable, as if $a<b<c$ then the second triplet implies either $b>c$ or $a>b$.


The natural solution to me is do directly model this as integer linear programming, where all values are distinct integers in $[0, |\text{Variables}|)$ and the triplets are directly encoded as an equation and solved. This works (and is performant), but it may be suboptimal for the special case.

Most of my attention has been looking at whether you can build a directed (acyclic) graph where the variables can be topologically sorted: $a > b$ if the DAG has a path from $a$ to $b$, and if at any point an unavoidable cycle occurs then it's UNSAT. This also works, but I can't find a clever way avoid doing backtracking at some point, as there are many problem instances where guessing orderings becomes necessary.

I suspect the problem is NP, but I can't prove it. This also seems like the type of problem that would have been heavily researched due to its simplicity, but I can't find any references.

$\endgroup$
3
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Betweenness ? $\endgroup$
    – Dmitry
    Dec 5, 2022 at 22:11
  • $\begingroup$ Evidently it seems like the problem has been studied, I just had the wrong terms. $\endgroup$ Dec 5, 2022 at 22:57
  • 1
    $\begingroup$ The problem is trivially in NP. A certificate is an ordering of the variables, and you can check in polynomial-time whether it is indeed a permutation of the variables and that the constraints are satisfied. $\endgroup$
    – Steven
    Dec 6, 2022 at 8:13

1 Answer 1

1
$\begingroup$

This is known as the betweenness problem. It is in NP (you can easily check the correctness of any proposed solution in polynomial time), and is NP-hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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