I am confused whether $\mathsf{APX-hard} \subseteq \mathsf{NP-hard}$. My confusion stems from a result on graph pricing from this paper which says the following : "Unlike the general case of the graph pricing problem, the bipartite case was not even known to be NP-hard. We show that it is in fact APX-hard by a reduction from MAX CUT". It seems like the authors are implying that APX-hardness is a stronger property than NP-hardness

Since $\textsf{APX} \subseteq \textsf{NP}$ by definition, the above statement is true for MAXCUT as it is in $\textsf{APX}$ and also in $\textsf{APX-hard}$ but I am not sure if $\mathsf{APX-hard} \subseteq \mathsf{NP-hard}$ in general. Any pointers/counter example problem is appreciated!

  • 3
    $\begingroup$ What the authors mean is the following. Previously optimization problem X was not known to be NP-Hard; it could in fact be in P. So the first step is to prove NP-Hardness. If a problem is NP-Hard it could have a PTAS or even an FPTAS. The authors rule this out by showing that there is a constant c > 1 such that approximating to within a factor of c is also NP-Hard. That is all they are saying. $\endgroup$ – Chandra Chekuri Jan 22 '18 at 2:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.