Lundi 27 août 2018 - Soutenance de thèse de Thomas Bellitto.

Amphithéâtre du LaBRI, à 10h. Titre de la thèse : Walks, Transitions and Geometric Distances in Graphs. Jury : Christine Bachoc (directeur de thèse) - Jørgen Bang-Jensen (rapporteur) - Sylvain Gravier (rapporteur) - Mickael Montassier (examinateur) - Arnaud Pêcher (directeur de thèse) - Éric Sopena (examinateur).

Vendredi 7 septembre 2018 - Proportionally dense subgraph of maximum size: complexity and approximation - Clément Dallard (University of Portsmouth, Royaume-Uni).

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is NP-hard, more precisely APX-hard, even on split graphs. On the other hand, we present a simple polynomial-time (2 - (2/(Δ+1)))-approximation algorithm for the problem, where Δ is the maximum degree in the graph. We also prove that all Hamiltonian cubic graphs (except two) have a PDS of the maximum possible size which can be found in linear time (if a Hamiltonian cycle is given) and sketch the proof. Finally, we show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs.

Vendredi 14 septembre 2018 - Soutenance de thèse de Mohammed Senhaji.

Amphithéâtre du LaBRI, à 14h. Titre de la thèse : Neighbour-distinguishing decompositions of graphs. Jury : Maria Axenovich et Alexandre Pinlou (rapporteurs) - Aline Parreau, Arnaud Pêcher, Olivier Baudon et Eric Sopena (examinateurs).

Vendredi 21 septembre 2018 - Maximum Independent Set in H-free graphs - Édouard Bonnet (LIP, Lyon).

Maximum Independent Set (MIS) in graphs without a connected H as an induced subgraph (that is, H-free) is NP-complete when H is not a tree with at most one vertex of degree at least 3. For the other graphs H, which are paths and subdivisions of the claw (K_1,3), the computational complexity of MIS is generally open except for a small number of cases. We will explore the parameterized complexity of MIS in H-free graphs. Our distant goal is to establish a dichotomy of the H for which the problem can be solved in time f(k)n^{O(1)} and the ones for which such an algorithm is unlikely to exist (where n is the total number of vertices, k is the size of the solution, and f is any computable function). Recast in the parameterized complexity language, we want to know when the problem is FPT and when it is W[1]-complete. We will present a selection of results and draw a parallel with the situation for the 'classical dichotomy' (P/NP-complete). This is joint work with Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant.

Vendredi 28 septembre 2018 - Coloring the squares of planar graphs with no 4-cycle - Théo Pierron (LaBRI).

Coloring the square of a graph consists in assigning colors to its vertices in such a way that any two vertices at distance at most 2 receive different colors. While D+1 colors are needed to properly color the square of any graph of maximum degree D, Wegner proved that there is no hope for a matching upper bound of D+O(1) in general, even for planar graphs. We study the cycle obstructions needed to obtain such a bound for planar graphs. We present here the case where only finitely many cycles lengths are forbidden. In this setting, we prove that removing only cycles of length 4 is necessary and sufficient to obtain the desired bound. For very large D, we also improve a result of Bonamy, Cranston and Postle by showing that D+2 colors are always sufficient for coloring the square of C_4-free planar graphs, which is tight. This is joint work with Ilkyoo Choi and Daniel W. Cranston.

Mercredi 10 octobre 2018 15h - salle 76 - Rapid mixing of Glauber dynamics for colorings below Vigoda’s 11/6 threshold - Michelle Delcourt (University of Waterloo, Canada).

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $\Delta$ is rapidly mixing for $k \geq \Delta+2$. In 1999 Vigoda showed rapid mixing time of a modified version of flip dynamics for $k >11/6 \Delta$, implying polynomial time mixing for Glauber dynamics under the same constraints. This conjecture has attracted a lot of attention in the literature and better results are known for certain classes of graphs. In this talk, we improve Vigoda's bound for general graphs by showing that there exists a constant $\eta>0$ such that the Glauber dynamics mixes in polynomial time for $k \geq (11/6- \eta)\Delta$. Our proof combines path coupling with a new kind of metric we introduce to incorporate a count of the extremal configurations of the chain. This "extremal" metric proves to be much easier to analyze than stopping-time-based metrics, and hence we believe will have fruitful applications for bounding the mixing times of other Markov chains. This is joint work with Guillem Perarnau and Luke Postle.


Emplois - Stages

Groupe

GT Graphes et Optimisation

Historique

edit SideBar