Effect of constraints Density on the hardness of Betweness problem Betweeness problem is well known NP-complete permutation problem. Given a family $M$ of triples $(a_i, a_j, a_k)$, the problem is to decide whether a permutation $\Phi$ of elements $a_1, a_2, ..., a_n$ exists which satisfies all betweeness constraints.  For each triple $(a,b,c)$ in $M$, it holds that either $\Phi(a) \lt \Phi(b) \lt \Phi(c)$ or $\Phi(c) \lt \Phi(b) \lt \Phi(a)$.

Motivated partialy by this CS Theory post, I am interested in the relation between density of constraints and hardness of betweeness problem. I am looking for for a classification of problem's hardness based on the number of triples $|M|$ for these cases:

1-$|M|=O(\log n)$, 2-$|M|=o(n)$ , 3-$|M|=\Theta(n)$,  4-$|M|=\Omega(n^2)$, 5-$|M|=\Omega(n^3)$.

Please classify it to PTIME solvable, Quasi-polynomial solvable, Subexponential time solvable, and NP-complete.
As mentioned in the comments, the case with $\Theta(\log n)$ clauses is in PTIME. The other cases are NP complete.

From Chor&amp;Sudan, we know that solving Betweenness instances with $m\in\Theta(n)$ clauses is NP complete (as they present a gadget reduction from gap-E3SAT instances with a linear number of clauses). We also know that there are trivially-satisfiable instances with up to $\Theta(n^3)$ constraints. We can therefore reduce the hard language of Betweenness instances with $m \in \Theta(n)$ to the language with $m \in \Theta(n^c)$ clauses, for any rational $0 &lt; c \le 3$, simply by composing the hard instances with trivially-satisfiable instances of suitable density.


Chor and Sudan, 1998, A Geometric Approach to Betweenness.