Decomposition Of Relational Structures and Combinatorial Optimisation – DORSO

This project deals with fundamental aspects of computer science, namely theoretical aspects of decomposition methods for graphs, hypergraphs and other combinatorial structures. In the last decades, many decomposition methods have been developed and helped in proving graph conjectures and designing new algorithms. We believe that more applications can be found but we also believe that only a deep understanding of those decompositions will permit groundbreaking results. This is why, in this project, we want to focus on and develop few chosen theoretical aspects of decomposition theory.

Graphs are simple and natural structures which capture a large part of the computational complexity. In many application areas, such as networks, biology, chemistry and more recently social sciences, problems can be naturaly translated in terms of graphs. To solve these problems, the well known ``divide and conquer'' paradigm directly leads to graph decompositions, and indeed, many practical algorithms use - explicitly or not - decompositions techniques. Decompositions also play an important role from a theoretical point of view.

It is thus not surprising that, in the last decades, graphs decompositions have been intensively studied. Many have been defined in the literature (e.g. clique, modular, tree-decomposition...), and some of them, such as the tree-decompositions, have even been rediscovered independently several times.

Maybe the most successful decomposition for graphs so far is the tree-decomposition and its related parameter, the tree-width which measures how far a graph is to being a tree. Graphs of low tree-width share many properties with trees, indeed, many NP-complete problems are decidable in linear time on graphs of low tree-width. More precisely, any problem which is expressible in a certain logic on graph can be solved in linear time in any class of graph of bounded tree-width Although these linear-time algorithms hide huge constants (at least exponential in the tree-width), they have found applications, for examples in heuristic methods, e.g. in the Travel Salesman Problem. 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. Tree-width is even the subject of a chapter in the textbook of Fellows and Downey on parametrised algorithms. From a theoretical point of view, tree-width is closely related to the minor relation which is a well-quasi-order for the finite graphs. This result is known as the ``Wagner's conjecture', and tree-decompositions are a key tool of its proof.

Given the success of tree-decompositions for graphs, it is no wonder that these techniques have been extended in many directions. Efforts have been made to define decompositions more powerful than the tree-decomposition. For example, complete graphs have very simple structure, and yet, they have arbitrarily large tree-width. This lead to the definition of clique-width by Courcelle et al. In another direction, some authors have generalised the tree-width to more general combinatorial structures such as matroids. When considering databases, hypergraphs and relational structures are more relevant than graphs. The definition of tree-width also apply to hypergraphs but some variants such as the hyper-tree-width are better suited.

Although these decompositions have been studied for some time now, there is still a lot to do. Indeed, as an example, it took 21 years to publish the 20 papers containing the proof of Wagner's conjecture and very few people really understand the proof. In the meantime, many decompositions have been defined with some very general results but also many scattered ones which could be unified or clarified. This whole cleaning process would lead to better generalisations, and this is what we plan to do in this project, by looking at few chosen theoretical parts of this decomposition theory.