2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Thanks for the quick response :) Is there a hope for PTIME algorithm for this case? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Oct 11, 2013 at 22:59
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yury
    Commented Oct 12, 2013 at 0:11
  • $\begingroup$ Thanks Yury. So, Is this algorithm the best known? Also, I guess this algorithm puts case 2 in Subexponential time?. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Oct 12, 2013 at 0:26
  • 1
    $\begingroup$ 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). $\endgroup$
    – Yury
    Commented Oct 12, 2013 at 0:39

1 Answer 1

Reset to default
2
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Oct 12, 2013 at 15:23
  • $\begingroup$ 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. $\endgroup$
    – c.lorenz
    Commented Oct 12, 2013 at 21:10
  • $\begingroup$ 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$. $\endgroup$
    – c.lorenz
    Commented Oct 12, 2013 at 21:39
  • $\begingroup$ 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. $\endgroup$
    – c.lorenz
    Commented Oct 12, 2013 at 21:45

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.