Exact Algorithms

Assuming that PNP, NP-complete problems can not be solved in polynomial time. On the other hand, they can (trivially) be solved in exponential time. A natural question is therefore: Can we solve (some) NP-complete problems in sub-exponential time? For example, if the trivial time bound is O(2n), can we reduce it to, say, O(2n) or at least O(2n/log log n )? There is some evidence that this might be impossible, at least for certain types of problems. The notion of sub-exponential time, however, has to be interpreted with some care below.

If the best we can hope for are exponential running times of order $O(αn), then what is the best possible (smallest) value of α? Questions of this type have seen increasing interest during the last years. For example, the well-known 3-colorability problem (decide whether a graph can be colored with 3 colors) can trivially be solved in time O(3n), where n is the number of vertices. In a series of papers this has been brought down to O(1.3289n). The proposed project primarily aims at developing fast exponential time algorithms in this sense. Such algorithms are also known as exact algorithms (as opposed to approximation algorithms for solving NP-hard problems). There are numerous interesting open problems mostly related to certain ``threshold'' values for α.