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.
Prochains séminaires
- Vendredi 10 mai, Fionn Mc Inerney (Université de Sophia Antipolis) à 10h au LIRIS
Title : Sequential Metric Dimension
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.
We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the metric dimension of a graph. Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the LOCALIZATION problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is NP-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$). We then focus on the class of trees. On the negative side, we prove that the LOCALIZATION problem is NP-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, i.e., an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the LOCALIZATION problem in trees in polynomial time if $k$ is fixed.
We also consider some of these questions in the context where, upon probing the vertices, the relative distances to the target are retrieved. This variant of the problem generalizes the notion of the centroidal dimension of a graph.
- Vendredi 5 juillet, Annegret Wagler (LIMOS, Université Clermont-Auvergne) à 10h au LIRIS
Séminaires passés
- Vendredi 15 mars, Onur Cagirici (Masaryk University), à 10h30 à l'ENS Lyon
Title: Axes-parallel unit disk graph recognition is NP-hard
Abstract: Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Recognizing a unit disk graph is an important geometric problem, and has many application areas. In general, this problem is shown to be ∃R-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensornode, and a pair of intersecting disks corresponds to a pair of sensors being able to communicatewith each other. It is usually assumed that the nodes have identical sensing ranges, and thus unit disk graph model is used to model problems concerning wireless sensor networks. In this talk, we also attack the unit disk recognition problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. We show that deciding whether there exists a realization of a given graphas unit disks on straight lines is NP-hard, even if the given lines are parallel to either x-axis or y-axis. Moreover, we remark that if the straight lines are not given, then the problem becomes ∃R-complete.
- Vendredi 25 janvier, Julien Baste (Ulm), à 10h30 au Liris en salle C5
Title: Hitting minors on bounded treewidth graphs
Abstract : 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
<https://arxiv.org/abs/1704.07284>.
- Jeudi 20 décembre 2018, Mehdi Khosravian (LAMSADE, Université Paris-Dauphine), à 13h30 à l'ENS, 4ème étage, salle A2
Title: Extension of vertex cover and independent set in some classes of graphs and generalizations
Abstract: We study extension variants of the classical problems Vertex Cover and Independent Set. Given a graph G=(V, E) and a vertex set U ⊆ V, it is asked if there exists a minimal vertex cover (resp. maximal independent set) S with U ⊆ S (resp. U ⊇ S). Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the parameterized complexity of these problems, with parameter |U|, as well as the optimality of simple exact algorithms under ETH. All these complexity considerations are also carried out in very restricted scenarios, be it degree or topological restrictions (bipartite, planar or chordal graphs). This also motivates presenting some explicit branching algorithms for degree-bounded instances. We further discuss the price of extension, measuring the distance of U to the closest set that can be extended, which results in natural optimization problems related to extension problems for which we discuss polynomial-time approximability.
- Jeudi 13 décembre 2018, Matthew Fitch (University of Warwick), à 13h30 à l'ENS, 4ème étage, salle A2
Title: Implicit Representations of Semi-algebraic Graphs
Abstract: Semi-algebraic families of graphs are special families that have some geometric meaning; they consist of graphs whose vertices represent points in space, and whose edges are defined using polynomials in this space. Given such a family, our aim will be to find an implicit representation of it. In other words, given a graph in such a family, we want to assign some string of bits to each vertex in such a way thatwe can recover the information about whether 2 vertices are adjacent or not using only the 2 strings ofbits associated with those 2 vertices. The question we will be discussing in this talk will be: how can we minimise the lengths of the strings? The trivial solution for a graph with n vertices is of O(n), but there is a conjecture (the Implicit Representation Conjecture) which states that the minimum should be of O(log(n)). Here, we will show that it is possible using O(n^(1-e)) bits for some small e>0.
- Jeudi 22 novembre 2018, Andrey Kupavskii (University of Birmingham), à 13h30 à l'ENS, 4ème étage, salle A2
The Erdos Matching Conjecture and related questions
Résumé: Consider a family of k-element subsets of an n-element set, and assume that the family does not contain s pairwise disjoint sets. The well-known Erdos Matching Conjecture suggests the maximum size of such a family. Finding the maximum is trivial for n<(s+1)k and is relatively easy for n large in comparison to s,k. There was a splash of activity around the conjecture in the recent years, and, as far as the original question is concerned, the best result until recently was due to Peter Frankl, who verified the conjecture for all n>2sk. In this talk, we discuss the improvement of the bound of Frankl for any k and large enough s. We also discuss the connection of the problem to an old question on deviations of sums of random variables going back to the work of Hoeffding and Shrikhande. Based on joint work with Peter Frankl.
- 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 8 juin 2018, Kristina Vuskovic (Leeds University), au LIP : ANNULÉ
- Vendredi 15 juin 2018, journée structure discrète LIP/Graphe@Lyon
A l'amphi Schrodinger, au rez-de-chaussée de l'ENS, site Monod (batiment du LIP).
10:15 : Coffee.
10:30 -- 11:30 Sanjay Ramassamy (ENS de Lyon, UMPA)
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).
14:00-15:00. Nicolas Bousquet. (CNRS, G-SCOP)
Recoloring, from statistical physics to combinatorics.
Résumé : Sampling (proper) k-colorings of an arbitrary graph received a considerable attention in statistical physics. A (proper) k-coloring is a function that assigns to each vertex an integer between 1 and k, such that, for every edge (u,v) the colors of u and v are different. On way to sample (proper) colorings consists in performing the following Markov chain: given the current coloring, choose a vertex v and a color c at random and recolor v with c if the resulting coloring is proper. Two questions naturally arise: 1) is the chain irreducible (ie is it possible to reach any coloring?)? 2) if yes, what is the mixing time of the Markov chain? During this talk we will discuss with these questions and many related problems of various fields such as combinatorics, algorithmics or enumeration.
15h30-16h00. Stephan Thomassé (ENS de Lyon, LIP)
Clusters in R^3.
CoAuthored by Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet and Pierre Charbit
Résumé : A cluster is a set of points which pairwise distance is at most one. Finding a maximum size cluster in the plane is a very classical polytime solvable problem. We show that this extends to 3D up to arbitrary precision, i.e. we produce a polytime algorithm which finds a c-approximate optimal solution for all c<1. We also show that in 4D, no subexponential algorithm can 0.999-approximate maximum cluster (unless Exponential Time Hypothesis fails).
The algorithm uses a tiny touch of elementary geometry, a crucial topological point, and loads of graph algorithms. Surprisingly, this algorithm also solves maximum clique in disk graphs (both problems had no better than 1/2 approximation known before).
This may not be the end of the road: NP-hardness is not known for maximum cluster in 3D. I will discuss possible approaches for this.
- Vendredi 15 juin 2018, Nicolas Schabannel (CNRS, LIP), Folding shapes with oritatami systems
A l'ENS, salle à déterminer.
Joint work with Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Shinnosuke Seki and Hadley Thomas.
Abstract:
An oritatami system (OS) is a theoretical model of self-assembly via co-transcriptional folding. It consists of a growing chain of beads which can form bonds with each other as they are transcribed. During the transcription process, the $\delta$ most recently produced beads dynamically fold so as to maximize the number of bonds formed, self-assemblying into a shape incrementally. The parameter $\delta$ is called the \emph{delay} and is related to the transcription rate in nature.
This article initiates the study of shape self-assembly using oritatami. A shape is a connected set of points in the triangular lattice. We first show that oritatami systems differ fundamentally from tile-assembly systems by exhibiting a family of infinite shapes that can be tile-assembled but cannot be folded by any OS. As it is NP-hard in general to determine whether there is an OS that folds into (self-assembles) a given finite shape, we explore the folding of upscaled versions of finite shapes. We show that any shape can be folded from a constant size seed, at any scale $n\geq 3$, by an OS with delay $1$. We also show that any shape can be folded at the smaller scale $2$ by an OS with \emph{unbounded} delay. This leads us to investigate the influence of delay and to prove that there are shapes that can be folded (at scale~$1$) with delay $\delta$ but not with delay $\delta'<\delta$, for all $\delta > 2$.
These results serve as a foundation for the study of shape-building in this new model of self-assembly, and have the potential to provide better understanding of cotranscriptional folding in biology, as well as improved abilities of experimentalists to design artificial systems that self-assemble via this complex dynamical process.
- ICGT 2018 - 9-13 juillet 2018
- Vendredi 19 octobre 2018 à 14h au LIP, Francois Pirot (LORIA), salle M7 bâtiment Monod (3eme etage), ENS
Fractional chromatic number of small degree graphs and girth
It is well known that you can colour a graph G of maximum degree Δ greedily with Δ+1 colours. Moreover, this bound is tight, since it is reached by the cliques and odd cycles. Johansson proved with a pseudo-random colouring scheme that you can colour triangle-free graphs of maximum degree Δ with no more than O(Δ/logΔ) colours. This result has been recently improved to (1+ε)(Δ/lnΔ) for any ε>0 when Δ is big enough. This is tight up to a multiplicative constant, since you can pseudo-randomly construct a family of graphs of maximum degree Δ, arbitrary large girth, and chromatic number bigger than Δ/(2lnΔ). Although these are really nice results, they are only true for big degrees, and there remains a lot to say for small degree graphs.
- 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.