What is inapproximability of NP-hard problems?

Recently I have come across a paper which talks of "(1+ε)-inapproximability" and of "logarithmic approximation".

While I have a basic knowledge of computational complexity (I more or less know what it means to be in P, NP, NP-hard and so on), I tried to study some basic texts on approximability but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean?

If you want to know the paper I was referring to, it was DasGupta & Desai. «On the complexity of Newmanʼs community finding approach for biological and social networks». Journal of Computer and System Sciences 79, n. 1 (2013): 50–67. The found inapproximability is a property of the modularity measure (the so-called Q) related to the Newman-Girvan algorithm for finding community structure in networks, a measure whose maximization has been proved NP-complete by Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, and Wagner in 2008. Thank you in advance.

• What is "ELI10"? Aug 26, 2016 at 16:43
• @DavidRicherby: ELI10 = "explain like I'm 10". There is a large subreddit which is dedicated to ELI5-questions. reddit.com/r/explainlikeimfive The expression ELI5 is more common than ELI10. Aug 26, 2016 at 16:58
• @ChingChong OK, so it's redundant, since any decent explanation should be comprehensible to somebody with the mathematical sophistication to ask the question in the first place. And we're not Reddit. Aug 26, 2016 at 17:17
• You might find Erik Demaine's MIT 6.890 lectures on inapproximability (intro, examples, gap problems) to be useful. (Disclaimer: I was in the audience.) Aug 26, 2016 at 21:19

Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely analogous.

Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following:

If there is a polynomial time approximation algorithm for $\Pi$ whose approximation ratio is better than $c$ then [something bad happens].

Usually the "something bad" is $\mathsf{P} = \mathsf{NP}$, but sometimes we can only prove that, say $\mathsf{NP} \subseteq \mathsf{DTime}(n^{\log \log n})$ (that is, SAT can be solved in time $O(n^{ \log \log n})$). Since we believe that the "something bad" is wrong, it follows that probably no polynomial time approximation algorithm for $\Pi$ has an approximation ratio better than $c$.

Why this form of result? If $\mathsf{P} = \mathsf{NP}$, then all NP optimization problems (that is, all optimization problems whose decision version is in NP) can be solved in polynomial time. Therefore in order to prove that a certain problem cannot be approximated well we need to make some complexity assumption such as $\mathsf{P} \neq \mathsf{NP}$.

The best one can hope for is to prove that is an NP-hard to approximate $\Pi$ better than $c$. What this means is that for each $\epsilon > 0$ there is a polynomial reduction $A$ from SAT to $\Pi$ with the following properties:

1. If the input formula $\varphi$ is satisfiable than the optimal value of $A(\varphi)$ is at most $x$, for some value $x$ which the reduction explicitly calculates (in polynomial time).

2. If $\varphi$ is not satisfiable than the optimal value of $A(\varphi)$ is more than $(c+\epsilon)x$.

In particular, any polynomial time $(c+\epsilon)$-approximation algorithm would be able to distinguish the two cases, and thus to solve SAT in polynomial time.

Technically, what we have described is known as a promise problem: decide whether an instance of $\Pi$ has value at most $x$ or more than $(c+\epsilon)x$; or stated differently, find the optimal value of an instance of $\Pi$ (or at least distinguish the two cases) under the promise that the optimal value is either at most $x$ or more than $(c+\epsilon)x$.

In some cases we are able to prove that a certain problem $\Pi$ is $c$-hard to approximate, and also show that a polynomial time $c$-approximation algorithm exists. In this case we say that the inapproximability threshold of $\Pi$ is $c$. For example, Håstad shows that the threshold of inapproximability for 3SAT is $7/8$.

Our definition above of $c$-inapproximability states that in polynomial time it is impossible to approximate a certain problem better than $c$, but allows an approximation ratio of $c$. Sometimes we also want to disallow an approximation ratio of $c$. The terminology doesn't reflect this fine point, and formal statements of theorems have to be consulted.

Finally, $(1+\epsilon)$-inapproximability means that (under some complexity assumptions) it is impossible (in polynomial time) to approximate the problem to within $1+\epsilon$ for some $\epsilon > 0$ (in terms of our notation above, the problem is $1$-hard to approximate). We also say that the problem is APX-hard.

Logarithmic inapproximability means that it is impossible to approximate the problem to within $O(\log n)$, where $n$ is some natural parameter inherent in the problem, usually the number of vertices in the input graph.

• Thank you very much for your lengthy and accurate response. Do you have any advice about reasonably clear textx, books or papers, which explain the above notions? Aug 26, 2016 at 18:30
• You can try Wikipedia and the references therein, such as Luca Trevisan's survey. Aug 26, 2016 at 18:33

There are some NP-complete problems where you can get good approximations to an optimal solution, and some where you can't. Take colouring of a planar graph: Deciding whether a planar graph can be coloured in 3 colours is NP complete. On the other hand, every planar graph can be coloured in 4 colours. But there is no graph that would take say 3.01 colours. So if you try to colour a 3 colourable graph, you either solve the problem, or your solution is at least 33.3333% worse than the optimal solution. No (1 + eps) approximation if eps < 1/3.

Other problems allow arbitrarily good approximations that get harder to find as you try to improve the approximation.

• So, basically, you're saying that there's no sense in which approximating the chromatic number of a planar graph makes much sense. But what does this have to do with the question? Aug 26, 2016 at 17:21
• @DavidRicherby: Seriously? "but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean" Aug 26, 2016 at 19:41