Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.[-]

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.[-]

Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. In this talk, we focus on two graph searches: Lexicographic Breadth First Search (LBFS), and Lexicographic Depth First Search (LDFS).
Many classes of graphs have a vertex ordering characterisation, and we review how graph searching is used to produce efficiently such vertex orderings.
These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance) on some special classes of graphs such as cocomparability graphs.
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. Then I will present the relationships between graph searches, graph geometric convexities and antimatroids. These relationships are for to be completely understood and I will pose some hard conjectures and some interesting problems to consider.
To finish I will present some recent results about Robinsonian matrices by M. Laurent and M. Seminaroti and their relationships with graph searches. This yields a new area of research to investigate.[-]

This talk will cover two recent advancements in the theory of online algorithms for dynamic matching markets. The first set of results concern a stochastic model of matching with Poisson arrivals and memoryless departures over edge-weighted graphs. The second set of results focus on the incorporation of serial correlation properties in classical online stochastic matching models. We develop new mathematical programming relaxations and correlated rounding schemes, yielding the first constant-factor performance guarantees in such settings.[-]

The chromatic number $\chi(G)$ of a graph $G$ is always at least the size of its largest clique (denoted by $\omega(G)$), and there are graphs $G$ with $\omega(G)=2$ and $\chi(G)$ arbitrarily large.
On the other hand, the perfect graph theorem asserts that if neither $G$ nor its complement has an odd hole, then $\chi(G)=\omega(G)$ . (A "hole" is an induced cycle of length at least four, and "odd holes" are holes of odd length.) What happens in between?
With Alex Scott, we recently proved the following, a 1985 conjecture of Gyárfás:

For graphs $G$ with no odd hole, $\chi(G)$ is bounded by a function of $\omega(G)$.

Gyárfás also made the stronger conjecture that for every integer $k$ and for all graphs $G$ with no odd hole of length more than $k$, $\chi(G)$ is bounded by a function of $k$ and $\omega(G)=2$. This is far from settled, and indeed the following much weaker statement is not settled: for every integer $k$, every triangle-free graph with no hole of length at least $k$ has chromatic number bounded by a function of $k$. We give a partial result towards the latter:

For all $k$, every triangle-free graph with no hole of length at least $k$ admits a tree-decomposition into bags with chromatic number bounded by a function of $k$.

Both results have quite pretty proofs, which will more-or-less be given in full.[-]

A central concept in graph theory is the notion of tree decompositions - these are decompositions that allow us to split a graph up into "nice" pieces by "small" cuts. It is possible to solve many algorithmic problems on graphs by decomposing the graph into "nice" pieces, finding a solution in each of the pieces, and then gluing these solutions together to form a solution to the entire graph. Examples of this approach include algorithms for deciding whether a given input graph is planar, the $k$-Disjoint paths algorithm of Robertson and Seymour, as well as many algorithms on graphs of bounded tree-width. In this talk we will look at a way to compare two tree decompositions of the same graph and decide which of the two is "better". It turns out that for every cut size $k$, every graph $G$ has a tree decomposition with (approximately) this cut size, such that this tree-decomposition is "better than" every other tree-decomposition of the same graph with cut size at most $k$. We will discuss some consequences of this result, as well as possible improvements and research directions.[-]

The problem of testing if a graph can be colored with a given number $k$ of colors is $NP$-complete for every $k>2$. But what if we have more information about the input graph, namely that some fixed graph $H$ is not present in it as an induced subgraph? It is known that the problem remains $NP$-complete even for $k=3$, unless $H$ is the disjoint union of paths. We consider the following two questions: 1) For which graphs $H$ is there a polynomial time algorithm to 3-color (or in general $k$-color) an $H$-free graph? 2) For which graphs $H$ are there finitely many 4-critical $H$-free graphs? This talk will survey recent progress on these questions, and in particular give a complete answer to the second one.[-]