[Solved]: Approximating NP-complete problems

Problem Detail: 

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.

Asked By : AmadeusDrZaius

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23236