# Graphes@Lyon

Graphes@Lyon rassemble les chercheurs de la région lyonnaise intéressés par les graphes, en particulier les chercheurs des équipes MC2 du LIP et Goal du LIRIS.

## Événement - ICGT 2018

Nous organisons la prochaine édition d'ICGT ! Rendez vous sur le site web dédié pour plus d'infos.

## Prochains séminaires

- Vendredi 8 juin 2018, Kristina Vuskovic (Leeds University), au LIP

TBA

- Vendredi 15 juin 2018, Sanjay Ramassamy (ENS de Lyon), au LIP

**Barak-Erdös graphs and the infinite-bin model**

Résumé : Barak-Erdös graphs are the directed acyclic version of Erdös-Rényi random

graphs : the vertex set is {1,...,n} and for each i<j with probability p

we add an edge directed from i to j, independently for each pair i<j. The

length of the longest path of Barak-Erdös graphs grows linearly with the

number of vertices, where the growth rate C(p) is a function of the edge

probability p.

Foss and Konstantopoulos introduced a coupling between Barak-Erdös graphs

and a special case of an interacting particle system called the

infinite-bin model. Using this coupling, we show that C(p) is analytic for

p>0 and is differentiable once but not twice at p=0. We also show that the

coefficients of the Taylor expansion at p=1 of C(p) are integers,

suggesting that C(p) is the generating function of some class of

combinatorial objects.

This is joint work with Bastien Mallein (Université Paris-13).

**Séminaires passés**

Vendredi 30 mars 2018, Marin Bougeret (LIRMM), à 10h au LIRIS, salle C5

Triangle packing in (sparse) tournaments: approximation and kernelization.

Résumé : Given a tournament T and a positive integer k, the C_3-Packing-T asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tournaments of the classical minimal feedback vertex set problem. Surprisingly C_3-Packing-T did not receive a lot of attention in the literature. We show that it does not admit a PTAS unless P=NP, even if we restrict the considered instances to sparse tournaments, that is tournaments with a feedback arc set (FAS) being a matching. Focusing on sparse tournaments we provide a (1+6/(c-1)) approximation algorithm for sparse tournaments having a linear representation where all the backward arcs have “length” at least c. Concerning kernelization, we show that C_3-Packing-T admits a kernel with O(m) vertices, where m is the size of a given feedback arc set. In particular, we derive a O(k) vertices kernel for C_3-Packing-T when restricted to sparse instances. On the negative size, we show that C_3-Packing-T does not admit a kernel of (total bit) size O(k^{2-epsilon}) unless NP is a subset of coNP / Poly. The existence of a kernel in O(k) vertices for C_3-Packing-T remains an open question.

Joint work with Stéphane Bessy and Jocelyn Thiebaut.

Vendredi 6 avril 2018, François Dross (LIRMM), à 10h au LIRIS, salle C5

(I,Ok)-partition of sparse graphs

Résumé: "The girth of a graph is the length of a shortest cycle. The maximum average degree of a graph G is the maximum over all subgraph H of G of the average degree of H. We will study two classes of sparse graphs: planar graphs of high girth on the one hand and vertices of bounded maximum average degree on the other hand.

For all k, an (I,Ok)-partition of a graph is a partition of the vertices of the graph into two sets: an independent set, and the vertex sets of an induced subgraph whose components have at most k vertices.

We will prove that every planar graph of girth at least 10 admits an (I,O_3)-partition. We will also show that for all k, every graph G with maximum average degree less than 8k/(3k+1) admits an (I,Ok)-partition, implying that every planar graphs of girth at least 9 admits an (I,O_9)-partition."

- Vendredi 11 mars 2016, à 10h au LIRIS, Nautibus, salle C3 (acces) : Eric Tannier (INRIA, LBBE)

Title : On random graphs and the evolution

The 1960 paper of Erdös and Renyi was entitled "On the evolution of random graphs". They mention possible applications in many fields, but not in evolution. I will show such an application. Evolution on genomic sequences will be an accumulation of inversions. I will show that this process is, with a reasonable approximation, similar to the accumulation of edges in a graph, where each vertex i is associated with a probability p_i, and an edge is taken with probability p_ip_j. This analogy is helpful to estimate unknown parameters (how many inversions i.e. edges?) from observable ones (how many conserved adjacencies i.e. isolated vertices?).

- Vendredi 18 mars 2016, à 10h, au LIP, salle B1 : Pierre Aboulker (Université de Nice Sophia antipollis, équipe COATI)

Titre : Configurations in digraphs

Résumé : ici

- Vendredi 13 mai 2016, à 10h au LIRIS, salle C1 : Guillem Perarnau (Université de Birmingham)

Titre: Stability of bridge-addable graph classes.

Résumé : A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. Examples of such graph classes are forests, planar graphs and graphs with bounded treewidth.

McDiarmid, Steger and Welsh showed that graphs in bridge-addable classes are likely to be connected. Moreover, they conjectured that the class of all forests is the bridge-addable class whose elements are less likely to be connected. We prove that even a stronger version of this conjecture is true: not only forests are the worst bridge-addable class with respect to connectivity, but they are the unique worst one. In other words, any bridge-addable class with not too many connected elements looks very similar to the class of all forests (stability). This is joint work with Guillaume Chapuy.

- Vendredi 27 mai 2016, à 10h au LIP, salle B1 : Eun Jung Kim.

Titre : The “art of trellis decoding” is fixed-parameter tractable

Résumé : Given n subspaces of a finite-dimensional vector space over a fixed finite field, we wish to find a linear layout V1,V2,…,Vn of the subspaces such that dim((V1+V2+⋯+Vi)∩(Vi+1+⋯+Vn))≤k for all i, such a linear layout is said to have width at most k. When restricted to 1-dimensional subspaces, this problem is equivalent to computing the trellis-width (or minimum trellis state-complexity) of a linear code in coding theory and computing the path-width of an -represented matroid in matroid theory.

We present a fixed-parameter tractable algorithm to construct a linear layout of width at most k, if it exists, for input subspaces of a finite-dimensional vector space over . As corollaries, we obtain a fixed-parameter tractable algorithm to produce a path-decomposition of width at most k for an input -represented matroid of path-width at most k, and a fixed-parameter tractable algorithm to find a linear rank-decomposition of width at most k for an input graph of linear rank-width at most k. In both corollaries, no such algorithms were known previously.

It was previously known that a fixed-parameter tractable algorithm exists for the decision version of the problem for matroid path-width, a theorem by Geelen, Gerards, and Whittle~(2002) implies that for each fixed finite field , there are finitely many forbidden -representable minors for the class of matroids of path-width at most k. An algorithm by Hlineny (2006) can detect a minor in an input -represented matroid of bounded branch-width. However, this indirect approach would not produce an actual path-decomposition. Our algorithm is the first one to construct such a path-decomposition and does not depend on the finiteness of forbidden minors.

- Vendredi 10 juin 2016, à 10h au LIRIS, bâtiment Nautibus, salle TD10: Yohann Benchetrit, TBA.

Titre: On the chromatic number of t-perfect graphs

The stable set polytope STAB(G) of a graph G is the convex hull of the incidence vectors of its stable sets. It is a well-known result of polyhedral combinatorics that non-negativity and edge inequalities are enough to completely describe STAB(G) if and only if G is bipartite. As defined by Chvátal, a graph G is t-perfect if STAB(G) is completely described by non-negativity, edge inequalities and odd circuit inequalities (equivalently, G is t-perfect if and only if the Chvátal rank of the edge relaxation of STAB(G) is at most 1). T-perfect graphs are K4-free, and results of Lovász, Fulkerson and Chvátal imply that every perfect K4-free graph is t-perfect.

Whereas every perfect K4-free graph is obviously 3-colorable, it is still unknown whether the chromatic number of t-perfect graphs is bounded by a constant.

Laurent and Seymour found a t-perfect graph of chromatic number 4, and no t-perfect graph with a greater chromatic number is known.

In this talk, I will show a new example of a (minimally) 4-chromatic t-perfect graph, and prove that this and the example of Laurent and Seymour are the only 4-chromatic graphs in a relatively wide subclass of t-perfect graphs. The talk will end with open problems and questions.

- vendredi 7 octobre 2016 à 10h au LIRIS: Marc Heinrich (LIRIS)

Titre : Coloriage avec des conflits et algorithmes distribués.

Résumé : Le modèle LOCAL est un modèle de calcul distribué dans lequel plusieurs machines coopèrent afin de calculer une solution à un problème. Dans ce modèle, les machines sont représentées par les noeuds d'un graphe et ne peuvent communiquer qu'avec leurs voisins. Les communications se font de façon synchrones, sans bornes sur les capacités de calcul des processeurs ni sur la taille des messages qu'ils peuvent envoyer.

Dans ce modèle, le problème de coloriage de graphe entre autres a attiré beaucoup d'attention, et malgré de nombreux résultats, il reste encore un écart important entre la complexité du meilleur algorithme pour ce problème, et la meilleure borne inférieure.

Dans cette présentation, je vais présenter un nouveau problème, le coloriage de graphe avec des conflits, qui généralise le problème de coloriage classique. Nous verrons ensuite un algorithme qui améliore certains résultats existants pour le coloriage de graphe, et les généralise au problème de coloriage avec des conflits.

- Les lundi 15 novembre et mardi 16 novembre 2016, les journées "Information and Complexity Day, Lyon 2016", organisé par Omar Fawzi et Graphes@Lyon, à l'ENS de Lyon.

- Le vendredi 4 novembre 2016 au LIP : Khang Le (LIP)

Title: Chromatic number of ISK4-free graphs

Abstract: A subdivision of a graph G is obtained by subdividing its edges into paths of arbitrary length (at least one). We denote by K_n the complete graph on n vertices. A graph is ISK4-free if it does not contain any subdivision of K_4 as an induced subgraph. We prove that the chromatic number of {ISK4, triangle}-free graphs is at most 3 and the chromatic number of ISK4-free graphs is at most 24, which improves the upper bound for the chromatic number of these classes provided by B. Lévêque, F. Maffray, and N. Trotignon (2012). We also discuss some related open questions.

- Le vendredi 16 décembre au LIP : Jean-Florent Raymond (LIRMM), salle de réunion équipe MC2, au LUG (LIP, Gerland)

Title: Deleting Immersions

Suppose F is a finite family of graphs. We consider the following

problem, called F-Immersion Deletion: given a graph G and integer k,

decide whether the deletion of at most k edges of G can result in a

graph that does not contain any graph from F as an immersion. This

problem is a close relative of the F-Minor Deletion problem studied by

Fomin et al. [FOCS 2012], where one deletes vertices in order to remove

all minor models of graphs from F.

We prove that whenever all graphs from F are connected and at least one

graph of F is planar and subcubic, then the F-Immersion Deletion problem

admits a constant factor approximation and a linear kernel.

These results mirror those obtained by Fomin et al. on the F-Minor

Deletion problem, with some notable differences, though.

This is joint work with Archontia Giannopoulou, Michał Pilipczuk,

Dimitrios Thilikos, and Marcin Wrochna.

A preprint can be found at http://arxiv.org/abs/1609.07780.

- Le vendredi 17 février 2017 salle de réunion équipe MC2, au LUG (LIP, Gerland) : Valentin Garnero (INRIA)

Title: (Méta)-noyaux constructifs et linéaires dans les graphes peu denses

Dans cet exposé je vous présenterai les résultats obtenus au cours de ma thèse, laquelle traite de noyaux et de complexité paramétrée.

La complexité paramétrée est une branche de l'algorithmie qui analyse la complexité d'un problème en fonction de la taille des données n et d'un paramètre k (arbitraire). L'objectif est de pouvoir attaquer des problèmes difficiles (NPc) et de montrer que l’exposition combinatoire n'est fonction que du paramètre (et pas de la taille des données), cad, trouver des algorithmes en f(k)+p(n). L'extraction de noyau est une méthode qui permet d'obtenir des algorithmes avec un telle complexité. Il s'agit d'un pré-calcul (une réduction polynomiale) qui réduit la taille des données en temps polynomial, tout en garantissant que la taille du noyau (l'instance réduite) est bornée par une fonction du paramètre g(k). Il suffit de résoudre le problème dans le noyau, de n'importe quelle façon, pour obtenir un algorithme en f(g(k)) + p(n).

La méthode de décomposition en régions [Alber, Fellows, Niedermeier] est un résultat majeur dans le domaine des noyaux. Elle a permis de construire de nombreux noyaux linaires pour des variantes de la Domination dans les graphes planaires. J'illustrerai cette méthode avec le cas de la Domination Rouge Bleu, qui consiste à trouver, dans un graphe bicoloré, un ensemble de sommets bleus tel que tous les sommets rouges sont à distance au plus 1 de la solution.

Cette méthode a ensuite été généralisée par des méta-résultats [ex: Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos], qui prouve l'existence de noyaux (dans des graphes peu denses) pour tout problème vérifiant certaines conditions génériques. Je présenterai un de ses méta-résultats, qui se base sur la programmation dynamique et sur la décomposition en protrusion, et qui a le mérite d’être constructif.

- Le vendredi 24 février 2017 au LIRIS en salle C5 : Valia Mitsou (LIRIS)

Titre : Choosability: a hard graph coloring problem

Résumé : Choosability, independently introduced by Vizing in 1976 and by Erdős, Rubin, and Taylor in 1979 is a well-studied graph-theoretic concept. We say that a graph G is k-choosable if for any assignment of lists of k colors on the verices of G we can color each vertex using a color from its list such that the coloring is proper. We will present a number of graph-theoretic observations and algorithmic results on the choosability problem and its generalization choosability deletion. This talk is based on recent work jointly done with Dániel Marx ("Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth"), which was presented at ICALP 2016.

- Le lundi 27 mars 2017 au LIRIS, salle C5: Mickaël Montassier (LIRMM)

Titre : Vertex partitions of graphs

Résumé : We present a survey on vertex partitions of graphs (especially, planar and/or sparse graphs) where each set of the partition induces a particular structure (for example, stable sets, matchings, forests,...).

- Le vendredi 7 avril 2017 au LIRIS, salle C5 du Nautibus : O-joung Kwon (Technische Universitat Berlin)

Title : Low rank-width colorings of graphs

Abstract : We introduce the concept of low rank-width colorings, generalizing the

notion of low tree-depth colorings introduced by Nesetril and Ossona de Mendez. We say that a class C of graphs admits low rank-width colorings if there exist functions N:N->N and Q:N->N such that for all integer p, every graph G in the class C can be vertex colored with at most N(p) colors such that the union of any i<= p color classes induces a subgraph of rank-width at most Q(i).

Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class C

of bounded expansion and every positive integer r, the class {G^r, G in C} of r-th powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every graph class admitting low rank-width colorings has the Erdos-Hajnal property and is chi-bounded.

- Le vendredi 28 avril 2017 au LIRIS, salle TD11 (Nautibus) : Claire Pennarun (LaBRI)

Title : Power domination in triangulations

Power domination in graphs emerged from the problem of monitoring

an electrical system by placing as few measurement devices in the system

as possible. Given a set S of vertices of a graph, a set M of vertices is built

as follows: at first, M = N [S], and then iteratively a vertex v is added to

M if v has a neighbor u in M such that v is the only neighbor of u not

in M. Such a set S is said to be power dominating for a graph G if all

vertices of G are in M at the end of the process. The power domination

number of a graph is the minimum size of a power dominating set. In this

talk, we present some results concerning power domination in triangulations,

and we in particular prove that any maximal planar graph of order n ≥ 6

admits a power dominating set of size at most (n−2)/4.

- Le lundi 15 mai 2017 au LUG, salle de réunion : Ross Khang (Radboud University Nijmegen)

Title: Distance colourings and one forbidden cycle length

Abstract: Graph powers arise naturally in the study of, for example, efficient network communication. Some basic problems have remained stubbornly open for a long time. I will first discuss previous work on the chromatic number of graph powers, for graphs of maximum degree d,

often taking d very large. This is related to conjectures of Bollobás and of Erdős and Nešetřil from the 1980s. Then I will discuss the imposition of a girth or cycle length restriction, in relation to a problem of Alon and Mohar. We have obtained several asymptotically sharp results along these lines, which extends a seminal work of Johansson to distance colourings. This is joint work with Francois Pirot.

- Le vendredi 9 juin 2017 au LIRIS, Nautibus (salle à venir) : Vincent Despré (LIP)

Titre: A Routing Algorithm for Delaunay Triangulations.

Résumé: Delaunay Triangulations are graphs defined on sets of points in the plane. They are very classical since their construction is natural and they have strong geometric properties. One of the more classical study about those triangulations is the calculation of the worst possible stretch for a pair of points . The stretch of a pair is defined by the worst length of a shortest path between those points divided by the Euclidian distance between them. Computing this shortest path is generally considered as efficient but it is not the case for very big triangulations. It becomes interesting to only consider local information at each step while routing from one vertex to the other. Our work consists in designing an algorithm with this restriction that outputs a path with a reasonable stretch.

- Vendredi 22 septembre 2017, à 10h, salle de réunion équipe MC2, au LUG :Jean-Florent Raymond (LIRMM)

Title: Separators & Expansion

The concept of bounded expansion has been introduced by Nešetřil and

Ossona de Mendez as a generalization of several known notions of

sparsity: being planar, excluding a fixed minor, having bounded degree,

and many more. Several algorithmic problems that are known to

be computationally hard in general turn out to be solvable in polynomial

time when the inputs are taken in a class of bounded expansion fixed in

advance.

On the other hand, classes of graphs with (balanced) sublinear

separators are extensively used in the design of algorithms and enjoy

nice structural properties. An example of graphs with sublinear

separators is the class of planar graphs, by a classic result of Lipton

and Tarjan.

In this talk I will discuss the connections between these two notions.

Let C be a subgraph-closed class of graphs. Dvořák and Norin proved that

graphs in C have sublinear balanced separators iff they have polynomial

expansion. They conjectured that if the balanced separators in C

have size O(n^{1−δ}) (for some 0 < δ ≤ 1), then the expansion in C is

O(k^{c/δ}), for some constant c. We prove this conjecture. This is joint

work with Louis Esperet.

- Vendredi 10 novembre 2017, à 10h au LIRIS, salle C1 du Nautibus : Lucas Pastor (G-SCOP, Grenoble)

Title: Colouring squares of claw-free graphs

Abstract: Let G be a claw-free graph. We consider the square G^2 of G, which is the

graph formed from G by the addition of edges between those pairs of vertices

connected by some two-edge path in G, and consider proper colourings of G^2. In

particular, we relate the chromatic number of G^2 to the clique number of G.

We prove that there is an absolute constant epsilon > 0 such that the chromatic

number of G^2 is at most (2- epsilon)χ(G)^2 for any claw-free graph G. Our main

theorem extends a result of Molloy and Reed who first gave a positive answer to

a conjecture of Erdős and Nešetřil.

Joint-work with Rémi de Joannis de Verclos and Ross Kang.

- Jeudi 15 février 2018, Mikaël Rabie, à 10h au LIP, salle TBA

Title : Distributed Recoloring: the addition of colors

Abstract : Given two colorings of a graph, we consider the following question: can we re-color the graph from one coloring to the other through a series of elementary changes? Here, an elementary change, or step, consists in selecting an independent set and changing the color of each vertex to another also compatible with the colors of its neighbors.

The answer is not always positive, and it is in fact a PSPACE-complete decision problem.

In this talk, we try to quantify how considering a stable set at each step instead of a single vertex impacts the number of steps necessary for a re-coloring, and how much communication is needed in the LOCAL model (at each round, a vertex can only communicate with its neighbors, with no limitation as to the size of the messages nor the computation power of the vertex) to compute the re-coloring or decide there is none.

We also consider the question of how many extra colors are needed to make the problem always feasible, and beyond that, how the number of necessary steps decreases with the addition of colors. The case of trees is of special interest.

I will provide a collection of both positive and negative results around those questions.

This a joint work with Marthe Bonamy, Paul Ouvrard, Jukka Suomela and Jara Uitto.

- Vendredi 2 mars 2018, Ahcene Bounceur, à 10h au LIRIS, salle visioconférence (au RDC)

Titre : Leader election for the surveillance of frontiers using an IoT network

Résumé :

The Leader Election is a real challenge in Wireless Sensor and IoT networks since it depends on the nature of the application domain and the energy consumption. In the case of real time applications, the choice will be based on the speed of election, and in the case where the time is not important, the choice will be based on the energy consumption. The Minimum Finding Algorithm is one of the classical algorithms allowing to elect such a node. In this algorithm, each node sends its value in a broadcast mode each time a better value is received. This process is very energy consuming and not reliable since it may be subject to an important number of collisions and lost messages. In this talk, we propose four new algorithms: 1) LOGO (Local Minima to Global Minimum), 2) BROGO (Branch Optima to Global Optimum), 3) DoTRo (Dominating Tree Routing) and 4) WBS (Wait-Before-Starting). These algorithms are based on simple routing protocols and they are more reliable since they require a small number of broadcast messages and a reduced number of nodes that send broadcast messages at the same time. The obtained results show that the proposed algorithms can reduce the energy consumption with rates that can exceed 94% compared with the classical Minimum Finding Algorithm. Finally, we will demonstrate on the CupCarbon simulator how to use the proposed algorithms to determine the starting node of a network required to run the D-LPCN algorithm, which is used to determine the boundary nodes of an IoT network.