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.

Vendredi 19 octobre 2018 - On the density of critical graphs without large cliques - Tom Kelly (University of Waterloo, Canada).
A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture.

Joint work with Luke Postle.

Vendredi 26 octobre 2018 - Claw-free matroids - Peter Nelson (University of Waterloo, Canada).
Let M be a set of nonzero vectors in a vector space over the two-element field. We say that M is claw-free if there are no vectors x, y, z in M for which x+y, y+z, x+y, x+y+z are not in M. These objects are a matroidal/geometric analogue of claw-free graphs. I will discuss a theorem, obtained recently with Kazuhiro Nomoto, that exactly classifies all claw-free M.

Lundi 5 novembre 2018 à 15h30 - Acyclic Colouring of Graphs on Surfaces - Shayla Redlin (University of Waterloo, Canada).

An acyclic k-colouring of a graph G is a proper k-colouring of G with no bichromatic cycles. In 1979, Borodin proved that planar graphs are acyclically 5-colourable, an analog of the Four Colour Theorem. Kawarabayashi and Mohar proved in 2010 that "locally" planar graphs are acyclically 7-colourable, an analog of Thomassen's result that "locally" planar graphs are 5-colourable. We say that a graph G is critical for (acyclic) k-colouring if G is not (acyclically) k-colourable, but all proper subgraphs of G are. In 1997, Thomassen proved that for every k >= 5 and every surface S, there are only finitely many graphs that embed in S that are critical for k-colouring. Here we prove the analogous result that for all k >= 12 and each surface S, there are finitely many graphs embeddable on S that are critical for acyclic k-colouring. This result implies that there exists a linear time algorithm that, given a surface S and large enough k, decides whether a graph embedded in S is acyclically k-colourable.

Mardi 6 novembre 2018 à 15h - Density and Structure of Homomorphism-Critical Graphs - Evelyne Smith-Roberge (University of Waterloo, Canada).

Let $H$ be a graph. A graph $G$ is $H$-critical if every proper subgraph of $G$ admits a homomorphism to $H$, but $G$ itself does not. In 1981, Jaeger made the following conjecture concerning odd-cycle critical graphs: every planar graph of girth at least $4t$ admits a homomorphism to $C_{2t+1}$ (or equivalently, has a $\tfrac{2t+1}{t}$-circular colouring). The best known result for the $t=3$ case states that every planar graph of girth at least 18 has a homomorphism to $C_7$. We improve upon this result, showing that every planar graph of girth at least 16 admits a homomorphism to $C_7$. This is obtained from a more general result regarding the density of $C_7$-critical graphs. Our main theorem is that if $G$ is a $C_7$-critical graph with $G \not \in \{C_3, C_5\}$, then $e(G) \geq \tfrac{17v(G)-2}{15}$. In this talk, I will go over the history of the progress towards Jaeger's conjecture, and give a general overview of the proof structure of our main theorem. Along the way, I will prove several structural lemmas concerning graphs that are $H$-critical, when $H$ is a vertex-transitive non-bipartite graph.

Vendredi 9 novembre 2018 - Labeling schemes for trees and planar graphs - Paweł Gawrychowski (University of Wrocław, Poland).

Labeling schemes seek to assign a label to each node in a network, so that a function on two nodes can be computed by examining their labels alone. The goal is to minimize the maximum length of a label and (as a secondary goal) the time to evaluate the function. As a prime example, we might want to compute the distance between two nodes of a network using only their labels. We consider this question for two natural classes of networks: trees and planar graphs. For trees on n nodes, we design labels consisting of 1/4log^2(n) bits (up to lower order terms). Interestingly, our solution circumvents a lower bound of 1/2log^2(n) obtained for a natural class of schemes based on the so-called universal graphs. I will discuss how a related notion of minor-universal graphs allows us to significantly improve on the best known bounds for NCA labeling.

For planar graphs, the situation is much more complex. A major open problem is to close the gap between an upper bound of O(n^{1/2}log(n))-bits and a lower bound of O(n^{1/3})-bits for unweighted planar graphs. We show that, for undirected unweighted planar graphs, there is no hope to achieve a higher lower bound using the known techniques. This is done by designing a centralized structure of size ~O(min(k^2,(kn)^{1/2})) that can calculate the distance between any pair of designated k terminal nodes. We show that this size it tight, up to polylogarithmic terms, for such centralized structures. This is complemented by an improved upper bound of O(n^{1/2}) for labeling nodes of an undirected unweighted planar graph for calculating the distances.

Vendredi 7 décembre 2018 - à partir de 11h30 - Pique-nique et exposé de Michał Pilipczuk.

Vendredi 7 décembre à 14h - Progressive algorithms for distance domination in sparse graphs. - Michał Pilipczuk (University of Warsaw, Poland).

In the distance-r dominating set problem we are given a graph G and integers r and k, and the question is whether G can be covered with k balls of radius r. We present a new, generic approach to the problems that gives a simple, linear-time fixed-parameter tractable algorithm (i.e. with running time f(r,k) * n) on a whole spectrum of sparse graph classes; more precisely, on any graph class that is nowhere dense. This topic will serve as an excuse to give an introduction to the theory of structural sparsity, an active research area originating in the work of Nesetril and Ossona de Mendez which provides a variety of combinatorial and algorithmic tools for working with sparse graphs.

Vendredi 21 décembre 2018 - Sequential Metric Dimension (in trees) - Julien Bensmail (Université de Nice).

In the Localization Game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph G. At every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location. In a joint work with D. Mazauric, F. Mc Inerney, N. Nisse and S. P ́erennes, we addressed the generalization of the Localization Game where k ≥ 1 vertices can be probed at every step, which also stands as a generalization of the notion of metric dimension of graphs. Precisely, given a graph G and two integers k, l ≥ 1, the Localization problem asks whether there exists a strategy to locate a target hidden in a given graph G in at most l steps and probing at most k vertices per step. The Localization problem is, in general, hard to comprehend. However, we settled it in the context of trees; namely:

• On the negative side, the Localization problem is, in general, NP-complete when restricted to trees.

• On the positive side, there is a (+1)-approximation for the problem in trees, i.e., a polynomial strategy to locate the target in at most one more step than the optimal number of steps.

In other words, in trees, the hardness of the Localization problem only arises from the first probing step, which is NP-hard to decide. A consequence is that we can optimally determine the location of the target, assuming the first probing step is provided e.g. by an oracle. The talk will be dedicated to discussing these aspects.

Vendredi 11 janvier 2019 - Hitting minors on bounded treewidth graphs - Julien Baste (Universität Ulm, Allemagne).

For a fixed collection of graphs F, the F-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S, subset of V(G), with |S| <= k such that G-S does not contain any of the graphs in F as a minor. This NP-hard problem is a generalization of some well-known graph problems as VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), or VERTEX PLANARIZATION (F={K_5,K_{3,3}}). We are interested in its parameterized complexity when the parameter is the treewidth of G, denoted by tw. Namely, the objective is to determine, for a fixed F, the (asymptotically) smallest function f_F: N -> N such that F-DELETION can be solved in time f_F(tw)*n^{O(1)} on n-vertex graphs. In this talk we will provide the basic definitions of parameterized complexity, motivate the problem, and then, review some of the lower and upper bounds on the function f_F for several instantiations of F. The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found in

Vendredi 25 janvier 2019 - Eternal domination in graphs - Ben Seamone (Dawson College, Canada).

Given a graph, how can one distribute resources to the vertices (nodes) so that one can use these resources to respond to any infinite sequences of demands? This is the fundamental question which the study of eternal domination in graphs attempts to answer. I will give a brief survey of what is known about eternal domination, followed by recent progress on some eternal domination problems. Notably, we refute a conjecture of Klostermeyer and Mynhardt on eternal domination in prisms over graphs, and introduce a fractional version of eternal domination which to our knowledge has not yet been studied. These results were jointly obtained with D. Khatri, A. Krim-Yee, N. Kumar, G. MacGillivray, V. Virgile, and A. Xu.

Vendredi 1 février 2019 - Octal games on graphs - Antoine Dailly (G-SCOP, Grenoble).

Octal games are two-player take-away games played on heaps of counters: the players remove counters from a heap, and may split the heap in two nonempty heaps, under conditions that can be expressed as an octal code. The main question in the study of those games is whether the sequences of their Grundy values (equivalence classes for games, that fully express the winner of the game) on heaps of increasing size are regular. We propose a generalization of those games on graphs: players now remove connected components from a graph, and may disconnect the graph under conditions similar to those of octal games. This definition includes several vertex-deletion games on graphs, such as Arc-Kayles. We focus our study on subtraction games, a subclass of octal games where the players are not allowed to disconnect the graph.

In this talk, I will first give an introduction to the theory of take-away games, before showing how we generalized octal games to play them on graphs, and how we redefined the notion of regularity to study them. I will then give several regularity results for subtraction games on graphs, with a focus on the class of subdivided stars. In particular, we show that all subtraction games on graphs have ultimately periodic sequences of Grundy values. However, we notice that the study of specific families of subtraction games is difficult, even on subdivided stars. Finally, I will show how we used a pseudo-sum of games to study the case of subdivided bistars for the subtraction game CSG(1,2).

The results presented in this talk were jointly obtained with L. Beaudou, P. Coupechoux, S. Gravier, J. Moncel, A. Parreau and É. Sopena.

Emplois - Stages


GT Graphes et Optimisation


edit SideBar