Effect of constraints Density on the hardness of Betweness problem
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.