Dealing with intractability: NP-complete problems

Question

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?

Answer 1

There are a number of well-studied strategies; which is best in your application depends on circumstance.

• Improve worst case runtime
  Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ [1]; this is a huge improvement over the naive $\Omega(2^n)$ and might make instance sizes relevant for you tractable.

• Improve expected runtime
  Using heuristics, you can often devise algorithms that are fast on many instances. If those include most that you meet in practice, you are golden. Examples are SAT for which quite involved solvers exist, and the Simplex algorithm (which solves a polynomial problem, but still). One basic technique that is often helpful is branch and bound.

• Restrict the problem
  If you can make more assumptions on your inputs, the problem may become easy.

  • Structural properties
    Your inputs may have properties that simplify solving the problem, e.g. planarity, bipartiteness or missing a minor for graphs. See here for some examples of graph classes for which CLIQUE is easy.
  • Bounding functions of the input
    Another thing to look at is parameterised complexity; some problems are solvable in time $O(2^kn^m)$ for $k$ some instance parameter (maximum node degree, maximum edge weight, ...) and $m$ constant. If you can bound $k$ by a polylogarithmic function in $n$ in your setting, you get polynomial algorithms. Saeed Amiri gives details in his answer.
  • Bounding input quantities
    Furthermore, some problems admit algorithms that run in pseudo-polynomial time, that is their runtime is bounded by a polynomial function in a number that is part of the input; the naive primality check is an example. This means that if the quantities encoded in your instances have reasonable size, you might have simple algorithms that behave well for you.

• Weaken the result
  This means that you tolerate errorneous or incomplete results. There are two main flavors:

  • Probabilistic algorithms
    You only get the correct result with some probability. There are some variants, most notable Monte-Carlo and Las-Vegas algorithms. A famous example is the Miller-Rabin primality test.
  • Approximation algorithms
    You no longer look for optimal solutions but almost optimal ones. Some algorithms admit relative ("no worse than double the optimum"), others absolute ("no worse than $5$ plus the optimum") bounds on the error. For many problems it is open how well they can be approximated. There are some that can be approximated arbitrarily well in polynomial time, while others are known to not allow that; check the theory of polynomial-time approximation schemes.

Refer to Algorithmics for Hard Problems by Hromkovič for a thorough treatment.

---

1. Simplicity is beauty: Improved upper bounds for vertex cover by Chen Jianer, Iyad A. Kanj, Ge Xia (2005)

Answer 2

Other answers have addressed this from a more theoretical perspective. Here is a more practical approach.

---

For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first:

1. Write a simple program that encodes your problem instance as a SAT instance.

2. Then take a good SAT solver, run it (using the fastest multi-core computer that you happen to have), and see what happens.

Try with smaller instances first to get some idea of how long it might take.

---

Surprisingly often, this approach is much better than trying to implement your own solver specifically for your current problem:

• SAT solvers are very clever and well-optimised. They easily outperform your own implementation of backtracking search (no matter how much time you waste optimising your code). They also easily outperform many off-the-self alternatives such as integer linear programming solvers.

• This requires very little programming. Step 1 is relatively straightforward and it is not performance-critical; you can use scripting languages such as Python. Someone else has already taken care of implementing everything that you need for step 2.

---

For typical NP-hard optimisation problems ("find the smallest thingy that satisfies all these constraints") this approach may or may not work.

If you can easily turn it into a decision problem ("does there exist a thingy of size 4 that satisfies all these constraints?", "what about size 3?"), great, follow the same approach as above with decision problems.

Otherwise, you might want to resort to a heuristic solver that tries to find a small solution (not necessarily the smallest solution). For example:

1. Encode your problem as a (weighted) MAX-SAT instance.

2. Use the heuristic solvers from the UBCSAT package. Heuristic solvers parallelise trivially; try to find a computer cluster with hundreds of computers. You can run the solvers as long as you want, and then take the best solution that you have found so far.

Answer 3

Parametrized Complexity

One way to attack intractability is thinking about the problem in the parametrized complexity context.

In parametrized complexity we solve the problem by fixing some parameter (say $k$). If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is fixed parameter tractable in $k$. Here $f(k)$ is just some computable function. There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP. We believe that XP is not equal to FPT (just as we believe P $\neq$ NP). But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy. In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction. The class W[0] is the class FPT.

These are some samples in different classes of the W hierarchy:

1. Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
2. Independent set and Clique are both W[1]-complete
3. Dominating set is W[2]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at Parameterized Circuit Complexity and the W Hierarchy by Downey et al (1998).

And if you want even more is good to read Flum and Grohe's Parameterized Complexity Theory.

And finally:

Parametrized complexity versus Approximation algorithms:

It's known that if the problem has FPTAS (fully polynomial-time approximation scheme) then it's also FPT (which is obvious) But there is nothing well known in reverse direction, also there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...

Sample practical usages:

May be some people believe that parametrized complexity is useless in practice. But this is wrong. Many of parametrized algorithms are discovered in a real world applications, when you can fix some parameters, here is an example:

1. One of a main theorems in parametrized complexity, is do to the Courcell, he provide an algorithm of running time $2^{.^{.^{.^2}}}O(n)$ for some classes of parametrized problems. The number of towers of $2$ is $O(k)$, which means for $k=10$, is impossible. But, one group implemented his algorithm with some modifications on more special case, and they got extremely fast algorithm for vertex cover, which currently used in some subway stations in Germany.

2. One of a fastest and most accurate heuristic algorithms for TSP is : Tour merging and branch decomposition, which uses parametrization of problem (not directly, but branch decomposition and the dynamic programming approach they used is based on some good assumptions).

Answer 4

NP completeness is about worst case intractability. Depending on which problem you are working on, many classes of instances might be solvable in a reasonable time in practice (although you might need a more specialized algorithm to get the good runtimes).

Consider seeing if there is an efficient reduction from your problem to a problem with good solvers available, such as Boolean Satisfiability or Integer Linear Programming.

Answer 5

You have three options in general: The first one is to consider special cases of your problem. In some special cases, your problem might be solvable polynomially e.g. determining whether there exists a simple path from $v_i$ to $v_j$ to $v_k$ in an arbitrary directed graph $G$ is NP-Complete but it will be polynomial(linear) when $G$ is reducible. The second option is to use a good estimation algorithm to solve your problem. Estimation algorithms provide near-optimal answers to your problem. If you cannot use the previous options, the only remaining way will be: to use a tolerable algorithm to solve your problem in exponential time. Among exponential algorithms, the running time of some of them can be tolerable when the input size of your problem is less than a specific value.

Answer 6

Although touched upon briefly in some of the answers, let me emphasize that in practice, NP-complete problems are solved (or approximated) all the time. The main reason that you can solve NP-complete problems in practice is:

Instances encountered in practice are not "worst-case".

Another reason for the discrepancy is:

It is difficult to analyze heuristic algorithms formally.

In practice, you use heuristic algorithms to solve your NP-complete problems, and hope for the best. The results are often stunning.

Another issue touched upon in other answers is:

Sometimes exponential algorithms are fast enough.

That of course depends on the problem. When big data is involved, we have the opposite maxim:

Sometimes the only feasible algorithms are quasilinear.

---

I'm afraid that the crowd here is rather theoretically inclined. You might get better answers on the main stackexchange site.