Enumeration using structure: algorithms and complexity

Enumeration is at the heart of exact complexity. The following question was already asked in 1956 by Kurt Gödel in a famous letter to John van Neumann: "It would be interesting to know, ... how strongly in general the number of steps in finite combinatori al problems can be reduced with respect to simple exhaustive search." Now in modern wording this means: "Is it possible that every problem in NP can be solved faster than by trivial exhaustive search, i.e., trivial enumeration of all solutions?'" We are f ar from having any answer to this challenging question. In this project we concentrate on enumeration and counting, taking into account the structure of input. Not only are enumeration and counting natural and fundamental tasks in Computer Science, with a field in Combinatorial Algorithms dealing with the enumeration of combinatorial objects, counting and enumeration are also very central tasks in Combinatorics. For many enumeration problems only exponential time algorithms exist which can be shown by s imple combinatorial lower bounds. Nothing like this is available for decision, optimisation or counting problems. For such problems complexity lower bounds are provided by complexity classes and reductions with fundamental notions like NP-completeness and #P-completeness. Enumeration also provides a fascinating interface between combinatorial issues and algorithmic issues that cannot be found in decision and optimisation.Our main aim in this project is to approach the difficult task of enumeration using t he structure of the input. A lot of attention has been given to exploiting the structure in search of tractability, when it comes to optimisation and decision problems. However this track has been left largely unexplored when it comes to enumeration and c ounting problems. The participating teams have extensive expertise in exact algorithms and graph structure, and thus the combination of our expertise is perfect for achieving the goals of this project.