Tutorials

Thomas Schiex (INRA, Toulouse) : Graphical Models, Queries, Algorithms and Applications in Computational Biology

Graphical models are a family of mathematical models that aim at concisely describing functions of many variables using decomposability. The terminology of "Graphical Models" originates from probability and machine learning where the function of interest, a probability distribution, is described as a "Bayesian net" or "Markov Random Field". The same idea has been heavily exploited in sub-fields of Artificial Intelligence leading to the notions, to name a few, of constraint networks or generalized additive independance models but also, in Quantum Physics, to tensor networks. In their most general form, discrete GMs have a wide scope of applications including Image Processing, Scheduling, Verification, Computational Biology,...

As in relational databases, queries are of central importance in GMs. A query will typically ask to solve a decision, optimisation or couting problem (or a mixture of all these) on the function that it concisely describes. Given the conciseness and dimensionality, it is not surprising that most queries in discrete GMs are NP-hard.

Thanks to the decomposable nature of the function, dynamic programming has been a fundamental algorithmic tool, with its own limitations (as captured by tree-width and other graph parameters). Ultimately, when guarantees are sought, most empirically successful algorithms combine branch and bound search, heuristics and weak local variants of Dynamic Programming known as constraint propagation or message passing. While often designed empirically, these local algorithms are usually associated with polynomial classes they can solve efficiently. Heuristics and propagation are crucial components of these empirical recipes, but, as we will see,  graph parameters such as tree-width and height can still be exploited to combine improved worst-case complexity with good empirical efficiency.

In the end, we will specifically consider applications of these algorithms in Computational Biology, and more specifically Computational Protein Design, where these algorithms are increasingly used to design protein molecules with new functions. Given the essential role of proteins in all living organisms on Earth, CPD has applications in health but also bioenergies or green chemistry in general, having the potential to provide biodegradable powerful drugs and chemical agents.

Stéphan Thomassé (LIP, ÉNS de Lyon) : Domination in directed graphs

One of the classical object to look for in a directed graph is a dominating set S which satisfies that every vertex is either in S or dominated by a vertex of S. In dense digraphs, or even tournaments, one usually seek a bounded size dominating set. In sparse digraphs, the outdegree of vertices is not large enough to expect bounded size, so we try to find such S with additional constraints.

A dominating set S which is moreover an independent set is called a kernel. One can see a kernel as the set of winning positions in a game, but surprinsingly kernels proved to be particularly useful as tools in understanding the structure of directed graphs. For instance stable marriages are exactly kernels. Not all digraphs have kernels (odd oriented circuits for instance), and classes of graphs with kernels (called kernel-perfect) enjoy useful properties. Kernels are the heart of the wonderful proof of Galvin for list-coloring line graphs of bipartite graphs. Also a remarkable result of Boros and Gurvich, coupled with the Perfect Graph Theorem, asserts that a graph is perfect if and only if all its clique acyclic oriented subgraphs have a kernel.

A relaxation of the notion of kernel is to ask S to be covered by a bounded number of independent sets instead of only one. Again, the existence of a dominating set with bounded chromatic number is not always verified but one could expect that not too complex digraphs have not too complex dominating sets. For instance, Sands, Sauer and Woodrow conjectured that if a directed graph is the union of k partial orders, then  one can find a dominating set covered by no more than f(k) independent sets. They proved that f(2)=1 (which again gives the stable marriage theorem) and the existence of f(3) is still open. With Bousquet and Lochet, we confirmed their conjecture when the maximum independent set has bounded size. As a corollary we provide an alternative proof of a result of Barani and Lehel: Every finite subset F of the d-dimensional space can be covered by f(d) boxes with antipodal points in F.

To sum-up, domination is an invariant which is specific to directed graphs. It also encompasses many domains as game theory, optimization, geometry and structural graph theory. I will try in this tutorial to cover the main aspects of this great tool which is often a very good first step in understanding a digraph. I will also mention the (too many) open problems and dark areas of the domain.