On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of $14\mathrm{/}15+ϵ$ and $1\mathrm{/}2+ϵ$. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-$m$ approximation-resistant OCSPs accepting only a fraction $1\mathrm{/}(m\mathrm{/}2)!$ of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P $\mathrm{\ne }$ \NP.