Efficient Algorithms For Hard Problems

For many important problems no polynomial time algorithms are known. Many of them are NP-complete and therefore there is currently little hope that a polynomial time algorithm can be found in the near future (or ever). On the other hand, the problems are important and have to be solved in practice. Theoretical computer science provides a lot of possibilities to deal with hard problems:

A good example for a hard problem is vertex cover. The input is a graph and the task is to find a set of vertices that cover all edges. In the following picture, the nodes of a vertex cover are highlighted in red.

A graph and its vertex cover


Peter Rossmanith