Coordinators: (General) Dieter Kratsch, LITA, University of Lorraine, France, (in Clermont-Ferrand) Mamadou Moustapha Kanté, LIMOS, University of Clermont-Ferrand, France, (in Bordeaux) Paul Dorbec, LABRI, University of Bordeaux, France; Participant in BAOBAB-ERABLE Teams LBBE-UCBL-INRIA: Arnaud Mary.
Duration: 2016-2019
Brief description
The P vs. NP question is arguably the most important open question in Theoretical Computer Science these days. Under the widely believed assumption that the complexity classes P and NP are not equal, there are problems that cannot be solved efficiently with the help of computers. Thus it is important to identify such problems and to find other ways of dealing with them, different from the traditional means of polynomial-time algorithms. Unfortunately, many problems of great theoretical importance and also many problems that arise from real applications turn out to be intractable in the general case.
While optimisation is ubiquitous in Computer Science and a lot of research has been done on algorithms and complexity on optimisation problems, surprisingly little attention has been given to enumeration. A solution of the enumeration version of a problem typically provides an immediate solution for the optimisation version of the problem. This seems to suggest that enumeration is “much harder” than optimisation, which, among others, directed the search for tractability and efficient algorithms to optimisation problems. New insights from the recent research on the exact complexity of hard problems indicate that the relation between enumeration and optimisation is more subtle and worth a fundamental study from theoretical point of view.
Listing, generating or enumerating objects of specified type and properties has important applications in various domains of Computer Science as e.g. data mining, machine learning and artificial intelligence, as well as in other sciences, in particular in biology, and also many applications in real life. This is one of the motivations of our interest in enumeration. The scientific goals of the project are of theoretical nature and oriented towards better understanding of the complexity of enumeration and the study of algorithmic techniques to solve enumeration problems. This project will concentrate focus on problems for graphs and hypergraphs and study three different approaches to the algorithmics of enumeration.
