Why are NP-complete problems so different in terms of their approximation?

Question

I'd like to begin the question by saying I'm a programmer, and I don't have a lot of background in complexity theory.

One thing that I've noticed is that while many problems are NP-complete, when extended to optimization problems, some are far more difficult to approximate than others.

A good example is TSP. Although all kinds of TSP are NP-complete, the corresponding optimization problems get easier and easier to approximate with successive simplifications. The general case is NPO-complete, the metric case is APX-complete, and the Euclidean case actually has a PTAS.

This seems counter-intuitive to me, and I'm wondering whether there is a reason for this.

Answer 1

One reason that we see different approximation complexities for NP-complete problems is that the necessary conditions for NP-complete constitute a very coarse grained measure of a problem's complexity. You may be familiar with the basic definition of a problem $\Pi$ being NP-complete:

1. $\Pi$ is in NP, and
2. For every other problem $\Xi$ in NP, we can turn an instance $x$ of $\Xi$ into an instance $y$ of $\Pi$ in polynomial time such that $y$ is a yes-instance of $\Pi$ if and only if $x$ is a yes-instance of $\Xi$.

Consider condition 2: all that is required is that we can take $x$ and turn it into some $y$ that preserves the "single-bit" yes/no answer. There's no conditions about, for example, the relative size of the witnesses to the yes or no (that is, the size of the solution in the optimization context). So the only measure that's used is the total size of the input which only gives a very weak condition on the size of the solution. So it's pretty "easy" to turn a $\Xi$ into a $\Pi$.

We can see the difference in various NP-complete problems by looking at the complexity of the some simple algorithms. $k$-Coloring has a brute force $O(k^{n})$ (where $n$ is the input size). For $k$-Dominating Set, a brute force approach take $O(n^{k})$. These are, in essence the best exact algorithms we have. $k$-Vertex Cover however has a very simple $O(2^{k}n^{c})$ algorithm (pick an edge, branch on which endpoint to include, mark all covered, keep going until you have no edges unmarked or you hit your budget of $k$ and bactrack). Under polynomial-time many-one reductions (Karp reductions, i.e. what we're doing in condition 2 above), these problems are equivalent.

When we start to approach complexity with even slightly more delicate tools (approximation complexity, parameterized complexity, any others I can't think of), the reductions we use become more strict, or rather, more sensitive to the structure of the solution, and the differences start to appear; $k$-Vertex Cover (as Yuval mentioned) has a simple 2-approximation (but doesn't have an FPTAS unless some complexity classes collapse), $k$-Dominating Set has a $(1+\log n)$-approximation algorithm (but no $(c\log n)$-approximation for some $c>0$), and approximation doesn't really make sense at all for the straight forward version of $k$-Coloring.

Answer 2

One way to consider the difference between decision version and optimization version is by considering different optimization versions of the same decision version. Take for example the MAX-CLIQUE problem, which is very hard to approximate in terms of the usual parameter – the size of the clique. If we change the optimization parameter to the logarithm of the size of the clique, we obtain a problem with an $O(\log n)$ approximation algorithm. If we change the optimization parameter to $1/2 + k/n$, where $k$ is the size of the clique, then we can get an $O(1)$ approximation algorithm.

These examples are not completely made up. The problems of MAX-INDEPENDENT-SET (equivalent to MAX-CLIQUE) and MIN-VERTEX-COVER are closely related – the complement of an independent set is a vertex cover. But while the former is hard to approximate, the latter has a simple 2-approximation.

Reductions showing the NP-hardness of a given problem can sometimes be used to also show hardness of approximation, but this is not always the case – it depends on the reduction. For example, the reduction from MAX-INDEPENDENT-SET to MIN-VERTEX-COVER does not imply hardness of approximation of the latter problem, which is much easier to approximate than the former.

Summarizing, NP-hardness is just one aspect of a problem. Hardness of approximation is a different aspect, and it strongly depends on the notion of approximation.

Answer 3

As an intuitive approach, consider that instantiations of NP-complete problems are not always as hard as the general case. Binary satisifiability (SAT) is NP-complete, but it's trivial to find the solution to A v B v C v D v ... The complexity algorithms just bound the worst-case, not the average case, or even the 90% case.

The easiest way to reduce a NP-complete problem to something simpler is to simply exclude the hard parts. It's cheating, yes. But often the remaining parts are still useful for solving real world problems. In some cases, the line between "easy" and "hard is easy to draw. As you pointed out for TSP, there is a strong reduction in difficulty as you constrain the problem around "normal" directions one might think of. For other problems, it is harder to find real-life useful ways to segregate the easy and hard parts.

To totally leave the realm of CS and mathematics, consider an old car. Your friend wants to drive it. If you have to tell him, "hey, the car works perfect. Just don't take it above 95mph. There's a nasty wobble that'll knock you off the road," it's probably not a big deal. Your friend probably only wanted to take it around town anyway. However, if you have to tell him, "you have to feather the clutch just right to go from 1st to 2nd, or the engine will stall," it might be harder for your friend to use the car around town without some minor training.

Likewise, if an NP-complete problem happens to only get difficult in exotic cases, it reduces complexity rather quickly when you look at subdomains. However, if it gets difficult in commonly occuring cases, there aren't so many useful subdomains which avoid the hard part.