Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches

Abstract

Exponential algorithms, whose time complexity is O(c n ) for some constant c > 1, are inevitable when exactly solving NP-complete problems unless P=NP . This chapter presents recently emerged combinatorial and algebraic techniques for designing exact exponential time algorithms. The discussed techniques can be used either to derive faster exact exponential algorithms or to significantly reduce the space requirements while without increasing the running time. For illustration, exact algorithms arising from the use of these techniques for some optimization and counting problems are given.