DS0704 - Fondements du numérique

Enumeration on Graphs and Hypergraphs: Algorithms and Complexity – GraphEn

Enumeration in graphs and hyper graphs : algorithms and complexity

Listing, generating and enumerating objects of specified types and properties is a fundamental algorithmic task with many applications in various domains of Computer Science and in real life. We shall concentrate on problems for graphs and hypergraphs and study three different approaches to construct enumeration algorithms.

The scientific goals of the project are of theoretical nature and oriented towards a better understanding of the complexity of enumeration and the study of algorithmic techniques .

Study of principal algorithmic approaches to establish enumeration algorithms: classical output-sensitive approach and recently proposed input-sensitive approach and parameterized enumeration

Output-sensitive and input-sensitive approach will be studied from theoretical point of view. The study of parameterized enumeration is oriented towards practical computer programs.

Algorithms and computer programs to solve fundamental enumeration problems, new algorithmique techniques.Organization of a summer school and international workshops on algorithmic enumeration

Establishing the emerging field of algorithmic enumeration as important domaine within «Algorithms and Complexity«

Publication of the results in scientific journals and conferences well-known in Theoretical Computer Science and Algorithms

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 of optimisation versions of the problem, and it is clearly at least as hard as these other versions. 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 of enumeration and optimization 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. Thereby we shall concentrate on problems for graphs and hypergraphs and study three different approaches to the algorithmics of enumeration.

For many enumeration problems the number of generated objects is exponential in the input size, e.g. the number of vertices of the input graph or hypergraph. This is one of the motivations of the so-called output-sensitive approach in which the running time of an enumeration algorithm depends on the size of input and the size of the output. This approach has a long tradition and is the classical one in enumeration algorithms. Recently research on exact exponential-time algorithms triggered the study of enumeration algorithms in which the running time depends on the input length only. It is of great use in establishing (exponential) bounds on the number of objects as well as in the study of exact complexity of hard problems. Another approach to solve enumeration problems on graphs is the use of algorithms parameterized by some width parameter like treewidth or cliquewidth. Our goal is to establish meta-theorems producing algorithms for enumeration problems based on logic, automata and the structure of graphs. This includes the implementation in the experimental system AUTOGRAPH, which will allow to verify the usability of algorithmic meta-theorems.

Besides the common goals of such a project bringing together various groups of French researchers interested in algorithmic enumeration in graphs, like cumulating knowledge on particular enumeration problems and scientific production, our principal motivation is to establish an enumeration community in France and is also to help making enumeration an important research subject world-wide in algorithmics. A workshop at the Lorentz Center in Leiden co-organised by the leader of this project has the aim to bring researchers of different research direction in enumeration together. Writing a book on algorithmic enumeration will be another cornerstone in giving algorithmic enumeration the place it merits.

Project coordination

Mathieu Liedloff (Laboratoire d'informatique théorique et appliquée)

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

LITA Laboratoire d'informatique théorique et appliquée
LIMOS Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes
LaBRI Laboratoire Bordelais de Recherche en Informatique

Help of the ANR 398,320 euros
Beginning and duration of the scientific project: September 2015 - 48 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter