Volume 11 (2015) Article 10 pp. 257-283
APPROX-RANDOM 2013 Special Issue
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
Revised: May 18, 2014
Published: June 18, 2015
[PDF (334K)]    [PS (1434K)]    [PS.GZ (381K)]
[Source ZIP]
Keywords: acyclic subgraph, APPROX, approximation, approximation resistance, betweenness, constraint satisfaction, CSPs, feedback arc set, hypercontractivity, NP-completeness, orderings, PCP, probabilistically checkable proofs
ACM Classification: F.2.2
AMS Classification: 68Q17, 68W25

Abstract: [Plain Text Version]

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

An extended abstract of this paper appeared in the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2013).