# 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.

• Thanks for the quick response :) Is there a hope for PTIME algorithm for this case? Oct 11, 2013 at 22:59
• There is an exact algorithm with running time $2^{|M|} poly(n)$. For every constraint $(a,b,c)$, we “guess” whether $\Phi(a) < \Phi(b) < \Phi(c)$ or $\Phi(c) < \Phi(b) < \Phi(a)$ (i.e. try all possibilities). We obtain a partial order on the set of vertices. Then we find a complete order using topological sorting. So we can solve instances with $|M| = O(\log n)$ in polynomial time.
– Yury
Oct 12, 2013 at 0:11
• Thanks Yury. So, Is this algorithm the best known? Also, I guess this algorithm puts case 2 in Subexponential time?. Oct 12, 2013 at 0:26
• I don't know if this is the best known algorithm. Indeed, there is an algorithm with running speed $2^{o(n)}$ for case (2) (“subexponential algorithm” means different things for different people).
– Yury
Oct 12, 2013 at 0:39

As mentioned in the comments, the case with $\Theta(\log n)$ clauses is in PTIME. The other cases are NP complete.
From Chor&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 < c \le 3$, simply by composing the hard instances with trivially-satisfiable instances of suitable density.
• Defining "subexponential" as $2^{o(n)}$ can be misleading. Since we have polynomial-time reductions from SAT, the ETH only implies that the time to solve an NP-complete problem is $2^{n^{\Omega(1)}}$. For the Betweenness problem, the running time could for instance be $O(2^{n^{0.001}})$ which is $2^{o(n)}$. In the same sense, the "subexponential" algorithm for Unique Games does not disprove the UGC. Oct 12, 2013 at 21:10
• It can be overconstrained on some vars, where it is easy, and hard on a constant fraction. Given a BTW instance $x$ on $n$ variables and $\Theta(n)$ clauses, we construct a dense BTW instance $y$ by introducing three sets of $n$ new variables: $A, B, C$; and for each $a, b, c \in A, B, C$, introducing a constraint $(a, b, c)$. If $x$ had $cn$ clauses, then $y$ will have $cn + n^3 = \Theta(n'^3)$ clauses where $n'$ is the number of vars in $y$. Finally, $y$ is satisfiable iff $x$ is since the new constraints are on indep vars and we can augment any ordering of $x$ with $A \prec B \prec C$. Oct 12, 2013 at 21:39
• One might imagine that the intuition corresponds to the case when every variable partakes in a large number - order $\Theta(n^2)$ - of constraints. However, this case is still NP hard since one can let the variables in $x$ take the place of the set $A$ in the above reduction. Oct 12, 2013 at 21:45