The minimum feedback arc set problem is APX-hard, which means that (assuming P ≠ NP) there is a hard limit on its approximation quality, a constant "c" > 1 such that every polynomial-time approximation algorithm will sometimes return an edge set larger than "c" times the optimal size. The proof involves approximation-preserving reductions from vertex cover to feedback vertex set, and from feedback vertex set to feedback arc set. More specifically, because vertex cover has no approximation better than 1.3606 unless P ≠ NP, the same is true for feedback arc set. That is, it is possible to take . If the unique games conjecture is true, this inapproximability threshold could be increased to arbitrarily close to 2.