Projet ANR graal

"Décompositions de Graphes et Algorithmes"

Description of the project

This project deals with fundamental aspects of computer science, namely theoretical and algorithmic aspects of decomposition methods for graphs and various combinatorial structures and extensions such as matroids, countable graphs... We propose to combine approaches issued from graphs, discrete algorithms, formal languages and logic theory. We believe that major contributions to decomposition methods are no longer possible if each of these theories is considered separately. 

Despite the simplicity of their definition, graphs are fundamental objects for computer science. On one side, they are the basis of a number of models in many different application areas, such as networks, biology, molecular chemistry and more recently social sciences. On the other side, they capture a large part of the computational complexity. A deep understanding of graph structure is therefore crucial. To this aim, a powerful approach, already suggested by Descartes, is to divide the problem into small pieces and then to reconstruct a global solution. This principle is known as the divide and conquer paradigm. In the last decades, many decomposition methods have been developed and helped in proving graph conjectures and designing new algorithms. For example, the graph minor theorem and the associated tree decomposition theory [Roberston, Seymour] provided an important breakthrough in the proof of the Wagner conjecture. More recently, new graph decompositions appear in the proof [Chudnovsky et al.] of the strong perfect graph conjecture of Berge. On the algorithmic side, decomposition methods and associated width parameters (such as treewidth, cliquewidth…) are important for various reasons. First, decomposing a graph is often required as a preliminary step in the resolution of the considered problem. Then the associated width parameter, which aims to measure the quality of the decomposition, enables to prove the low complexity cost of heuristic methods [Downey, Fellows], e.g. in the Concorde Computer Code for the Travel Salesman Problem [Chvatal, Cook et al.]. It has also been shown that small treewidth is characteristic of the control flow graphs of programs written in good programming languages and yielding to good register allocation algorithm [Thorup]. Finally, links can be established between graph decomposition theory and formal languages notably by providing extension of the famous Fagin theorems on computational complexity in terms of structural complexity. 

The originality of the project relies on the opportunity to gather researchers of different areas of theoretical computer science (algorithmicians, combinatoricians, logicians). The objective is to provide new insights on complementary aspects of decomposition methods: discrete algorithms (fixed parametrized complexity theory, algorithm design…), theory and related applications. More precisely: 

• By using relational logic structures to represent graphs, it is possible to describe various graph properties with logical formulas. The Monadic Second Order Logic (MSOL) turns out to be a powerful specification language [Courcelle]. Expressing a maximum number of graph properties with MSOL constitutes an ambitious project. Moreover for well-structured graphs (e.g. graphs of bounded treewidth) an MSOL formulation of a problem directly implies the existence of polynomial time algorithms [Courcelle, Makowsky, Rotics]. More generally, many optimization problems on graphs with bounded width parameter are fixed parameter tractable [Downey, Fellows]. The challenge is to lower as much as possible the hidden constants, which may still constitutes an obstruction for a practical use. 

• Designing practical decomposition algorithms is crucial for real applications. As mentioned above, polynomial time algorithms, or even linear time algorithms, may not be useful in practice. For decomposition methods such as modular decomposition [Gallai] large effort has been devoted to simplify (optimal) algorithms (Habib, de Montgolfier, Paul). The goal is to improve the robustness of the algorithm and to lead a better understanding of the combinatorial structure. Such work still has to be done for various methods (e.g. for the split decomposition [Cunningham, Edmonds]). An original approach consists in considering the “algebraic” aspects of the algorithms. 

• Some purely theoretical structural questions naturally arise in the study of decompositions. For instance, the fact that the branchwidth of graphs [Roberston, Seymour] coincides with the branchwidth of matroids [Hlineny][Oum, Seymour] is a strong recent structural result [Mazoit, Thomassé]. For another example, partitive families (in graphs, set systems, boolean functions…) can always be treated through a general decomposition theorem (including modular decomposition for graphs) [Möhring, Radermacher]. In this connection, a new and interesting question would be to develop a modular-like decomposition for matroids. Generally, such fundamental questions will arise while considering new decompositions or extension to new structures. 

Indeed, generalisation of decomposition methods to other combinatorial structures is also an important objective of this project. Recent advances and current research concern: countable graphs for process model (Courcelle, Delhommé), study of homogeneous relation generalizing both graphs and hypergraphs (Habib, de Montgolfier), functional decomposition of directed graphs (Burckel), decompositions in the set of graph orientations (Bessy, Gioan), matroid and oriented matroid theory (Gioan), plane or spatial graph representation systems (Courcelle, Gioan), dynamic graph representations (Crespelle, Paul), informative labelling schemes (Gavoille, Paul). The ambition of the project is to establish links between all those problems and to propose unified approaches in the perspective of a decomposition theory. 

Moreover, practical applications of these (revisited/new) decomposition methods can be expected. Preliminary results have already been obtained in phylogeny and comparative genomic in bioinformatics by considering the modular decomposition on signed permutations, which are used as model for the genome [Paul et al.]. In the interaction network area, tree-decomposition is used to provide compact routing labelling schemes [Gavoille et al.]. New approaches consist in designing non tree-like decompositions that reveals to be more robust (fault tolerant). These two examples require research on both algorithm design and purely combinatorial aspects.