# Approximating NP-complete problems

Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it.

Could we get around this by finding an algorithm which approximates the solution to a certain accuracy?

That is, would the result above bar the existence of an algorithm which finds a maximum independent set to an accuracy of 0.5? I.e., it is guaranteed to be less than 0.5 away from the size of a maximum set? (And hence implying that it actually is a maximum independent set.)

It seems to me that the latter wouldn't violate our proofs of non-tractability, which are discrete in nature, while still giving an answer that satisfies the problem from a practical perspective.

-
There is a class of problems called APX Hard, such that unless NP=P, there are exist no polynomial time approximation schemes. –  Tim Seguine Mar 30 '14 at 19:04

We do not know for certain that independent set cannot be solved exactly in polynomial time. However, it is considered unlikely, and this is the famous P$\neq$NP conjecture.

In cases where exact optimal solutions cannot (probably) be found in polynomial time, it is natural to look for approximately optimal solutions. Algorithms tackling this are known as approximation algorithms. If an algorithm always returns a solution whose value is within $\rho$ of the optimum, then we call it a $\rho$-approximation algorithm, and say that its approximation ratio is $\rho$.

A good example is MAX-3SAT, in which we are given a 3CNF formula, and our goal is to find an assignment maximizing the number of satisfied clauses. The corresponding decision version is a generalization of 3SAT, and so it is NP-complete. However, if we choose an assignment at random, it satisfies $7/8$th of the clauses in expectation, and we can in fact deterministically find such an assignment. Since the optimal solution satisfies at most a $1$-fraction of the clauses, this algorithm has an approximation ratio of $7/8$. It is a consequence of the PCP theorem that it is NP-hard to do any better (this is a result of Håstad). We say that MAX-3SAT is NP-hard to approximate within $7/8+\epsilon$ for any $\epsilon > 0$.

The independent set problem is much harder than MAX-3SAT. Indeed, it is NP-hard to approximate within $n^{1-\epsilon}$ for any $\epsilon > 0$. The best approximation algorithm known has approximation ratio $O(n(\log\log n)^2/\log^3 n)$ (as per Wikipedia).

In practice, independent set can probably be approximated better, but this is different to formalize, since it is not clear what properties real-world graphs satisfy. For random $G(n,1/2)$ graphs (in which each edge is chosen with probability $1/2$ independently), there is a $1/2$-approximation algorithm (the approximation ratio is with high probability over the choice of the graph).

Sometimes one considers smooth analysis of algorithms to model real-world instances. The idea is that real-world instances are noisy, and so instead of being interested in a specific graph $G$, we should be looking at a "neighborhood" of $G$ formed from graphs close to $G$ (differing by a relatively small number of edges). It could be the case that some algorithm has good approximation ratio on most of the graphs in the neighborhood of any graph $G$. I am not aware of any such analysis for independent set.

-
Great answer, thank you. Is there any book you would recommend that deals with approximation algorithms in general? I would guess CLRS might touch on it. –  AmadeusDrZaius Mar 30 '14 at 2:25
There are many books, which are easy enough to find on the web. Since I haven't read any of them, I can't recommend any one in particular. –  Yuval Filmus Mar 30 '14 at 2:29
@AmadeusDrZaius At least two nice ones come to mind. There's one by Vazirani and another one by Williamson and Shmoys. –  Juho Mar 30 '14 at 16:08
@Juho Thanks, it seems like a really good one. amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/… –  AmadeusDrZaius Mar 30 '14 at 18:59

If we assume a proof exists showing NP-complete problems cannot be solved in polynomial time (a very important corollary for such a proof would be that $P \neq NP$), such a proof would not invalidate any of the existing methods we have for coping with NP-complete problems:

• A brute force algorithm may be fine if instances of the problem are small.
• Sometimes the structure of problem instances can be used to solve it more quickly (2SAT vs. SAT).
• Sometimes certain parameters of problem instances can be used to solve the problem faster (CLIQUE with $k=10$ is solvable in ${\binom{n}{k}}$ ~ $n^k$).
• Heuristics can be used to find a good enough solution: Backtracking, genetic algos, local search...
• Approximation algorithms (like your suggestion) can be used to find sub-optimal but good enough solutions.

An example of an approximation algorithm can be given for MAX-2SAT. MAX-2SAT is the problem of finding the maximum number of clauses that can be simultaneously satisfied by an assignment to the variables of a 2-CNF (a boolean formula in conjunctive normal form with clauses that contain 2 literals). Each variable in a boolean formula can either be $0$ or $1$, so we just flip a coin to decide whether we assign $0$ or $1$ to each variable. With this approach, we can easily find an assignment to each variable that satisfies up to 75% of the clauses!

None of these techniques contradict our assumption that NP-complete problems have been proven to be unsolvable in polynomial time.

-
Thanks for your answer! I had no idea about 2SAT -- I was under the (false) impression that the problem was unsolved. –  AmadeusDrZaius Mar 30 '14 at 3:01
I think it's important to make a distinction here: A probabilistic polynomial time algorithm that approximates solutions to MAX-2SAT is not a solution to MAX-2SAT. Another very important observation is that all NP-hard problems have solutions. This means MAX-2SAT has a solution, but it does not have polynomial running time (which renders the solution impractical). We say "2SAT has a polynomial time algorithm." We don't say "2SAT is solved." Finally, it is true that $2SAT \in P$, but I am not sure how you deduced that given my example of MAX-2SAT. Something to think about. –  baffld Mar 30 '14 at 3:24
When I said "the problem [is solved]", I meant "the problem of finding a polynomial-time algorithm for 2SAT is/was solved". Pardon my abbreviation. –  AmadeusDrZaius Mar 30 '14 at 4:04
MAX-2SAT can be approximated much better, to within $0.943\ldots$ (see en.wikipedia.org/wiki/2-satisfiability#Maximum-2-satisfiability for the number). Assuming UGC, this is best possible. –  Yuval Filmus Mar 30 '14 at 5:05

Here's an example: Take a graph with n nodes. Determining whether there is a cycle of length n is NP-complete. Now take "travelling salesman without triangular equation". Set the distance to 1 if two nodes are connected, and n^2 if they are not connected. If there was a cycle then the shortest tour has length n, otherwise it has length at least > n^2. Our inability to find an approximation comes from the fact that if there was a cycle, then there just isn't any near-optimal solution.

Or take "minimum number of colors required to color a planar graph". This is trivially solved if 0, 1 or 2 colors are needed, NP-complete to determine that the solution is 3, and there is always a way to color a graph with four colours. If the solution is 3, there is no approximation less than 33 percent away.

-
You could of course claim that 3 3/7th colours are required when two are not enough, and stay within 1/7th or 14.29% of the correct answer, but that's a bit like cheating :-) –  gnasher729 Mar 30 '14 at 18:02

There are some NP-complete problems for which it has been shown that even getting an approximation to the solution is already NP-complete. I don't remember details now. It does depend on the problem, others are amenable to getting approximations efficiently.

-