<p>As mentioned in the comments, the case with $\Theta(\log n)$ clauses is in PTIME. The other cases are NP complete.</p>

<p>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.</p>

<ul>
<li>Chor and Sudan, 1998, A Geometric Approach to Betweenness.</li>
</ul>

CC BY-SA 3.0
2013-10-12T15:23:10.117Z
For case 2, we already know that it is in subexponential time. Therefore, it can not be NP-complete unless ETH is false. Also, cases 4 and 5 are over constrained and my intuition is that at least one of the cases can not be NP-complete.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-10-12T21:10:43.453Z
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.
c.lorenz
CC BY-SA 3.0
2013-10-12T21:39:15.797Z
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$.
c.lorenz
CC BY-SA 3.0
2013-10-12T21:45:27.263Z
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.
c.lorenz
CC BY-SA 3.0
2013-10-12T01:12:12.600Z
2013-10-12T01:12:12.600Z
c.lorenz
<p>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)$.</p>

<p>Motivated partialy by this <a href="https://cstheory.stackexchange.com/questions/1699/is-gap-3sat-np-complete-even-for-3cnf-formulas-where-no-pair-of-variables-appear">CS Theory post</a>, 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:</p>

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

<p>Please classify it to PTIME solvable, Quasi-polynomial solvable, Subexponential time solvable, and NP-complete.</p>

CC BY-SA 3.0
2013-10-11T22:59:27.663Z
Thanks for the quick response :) Is there a hope for PTIME algorithm for this case?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-10-12T00:11:57.117Z
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
CC BY-SA 3.0
2013-10-12T00:26:11.930Z
Thanks Yury. So, Is this algorithm the best known? Also, I guess this algorithm puts case 2 in Subexponential time?.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-10-12T00:39:51.823Z
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
<cc.complexity-theory><permutations>
Effect of constraints Density on the hardness of Betweness problem
Mohammad Al-Turkistany
# Effect of constraints Density on the hardness of Betweness problem

(Asked by: username_0 on 2013-10-11)

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](https://cstheory.stackexchange.com/questions/1699/is-gap-3sat-np-complete-even-for-3cnf-formulas-where-no-pair-of-variables-appear), 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.

**Tags:** cc.complexity-theory, permutations
> **Comments:**
> **username_0**: Thanks for the quick response :) Is there a hope for PTIME algorithm for this case?  
> **username_1**: 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.  
> **username_0**: Thanks Yury. So, Is this algorithm the best known? Also, I guess this algorithm puts case 2 in Subexponential time?.  
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2013-10-12. Score: 2

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.

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

> **Comments:**
> **username_0**: For case 2, we already know that it is in subexponential time. Therefore, it can not be NP-complete unless ETH is false. Also, cases 4 and 5 are over constrained and my intuition is that at least one of the cases can not be NP-complete.  
> **username_2**: 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.  
> **username_2**: 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$.  
> **username_2**: 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.  

---

