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. Si vous désirez parler au séminaire, merci de contacter Théo Pierron ou Rémi Watrigant (firstname.lastname@univ-lyon1.fr).
Pour voir les anciennes présentations, vous pouvez consulter la page d'archives.
Pendant les confinements de 2020 et 2021, Graphes@Lyon a été remplacé par des séminaires GRAA (Graphes en Rhone Alpes Auvergne) communs au laboratoire LIP / LIRIS / LIMOS et G-SCOP.
En espérant vous revoir bientôt pour des séminaires en présentiels..
Prochains séminaires
- Jeudi 11 avril 2024 à 14h, amphi A, ENS de Lyon : Zdeněk Dvořák (Charles University, Czech Republic)
Title : On flow-critical graphs
Abstract : A connected graph is k-flow-critical if it does not have a nowhere-zero flow, but every proper contraction does. By the coloring-flow duality of Tutte, k-flow-criticality is a dual notion to the notion of (k+1)-criticality from the graph coloring theory. I will present some results and open questions concerning k-flow-critical graphs.
- Jeudi 2 mai 2024 à 14h, amphi B, ENS de Lyon : Damien Pous and Samuel Humeau (ENS de Lyon)
Title : A finite presentation of treewidth at most 3 graphs
Abstract :
We provide a finite equational presentation of graphs of treewidth
at most three, solving an instance of an open problem by Courcelle
and Engelfriet.
We use a syntax generalising series-parallel expressions, denoting
graphs with a small interface. We introduce appropriate notions of
connectivity for such graphs (components, cutvertices, separation
pairs). We use those concepts to analyse the structure of graphs of
treewidth at most three, showing how they can be decomposed
recursively, first canonically into connected parallel components,
and then non-deterministically. The main difficulty consists in
showing that all non-deterministic choices can be related using only
finitely many equational axioms.
Séminaires passés
- Jeudi 4 avril 2024 à 10h, salle B2, ENS de Lyon : Viktor Zamaraev (Liverpool University, UK)
-
Title : Sharp thresholds in random simple temporal graphs
Abstract :A graph whose edges only appear at certain points in time is called a temporal graph (among other names). Such a graph is temporally connected if each ordered pair of vertices is connected by a path which traverses edges in chronological order (i.e., a temporal path). In this work, we consider a simple model of random temporal graph, obtained from an Erdős-Rényi random graph G_{n,p} by considering a random permutation π of the edges and interpreting the ranks in π as presence times.
We study the behaviour of various natural temporal graph properties in this model and obtain sharp thresholds for most of them.
Based on joint work with Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric, Michael Raskin, Malte Renken.
- Jeudi 30 novembre 2023à 14h à l'ENS Lyon : Martin Milanič (University of Primorska, Koper, Slovenia)
Title : Introduction to tree-independence number
Abstract :
I will talk about a relatively new graph width parameter called tree-independence number, which was introduced by Yolov in 2018 and independently by Dallard, Milanič, and Štorgel in 2021. This parameter is a generalization of treewidth that considers the independence number of the subgraphs induced by the bags rather than just the size of the bags. The aim of the talk is to give a light introduction to tree-independence number, by presenting its key structural properties, algorithmic applications, and conditions for boundedness. We will also review some of the tools and techniques leading to the current state of the art and discuss the main open questions.
- Mardi 19 septembre à 10h30 à l'ENS Lyon : Linda Cook (Institute of Basic Sciences, Daejeon, Corée du Sud)
Title : Reuniting chi-boundedness with polynomial chi-boundedness
Abstract :
Joint with: Sang-il, Maria Chudnovsky, James Davies.
A class F of graphs is chi-bounded if there is a function f such that chi(H) <= f(omega(H)) for all induced subgraphs H of a graph in F. If f can be chosen to be a polynomial, we say that F is polynomially chi-bounded. Esperet proposed a conjecture that every chi-bounded class of graphs is polynomially chi-bounded. This conjecture has been disproved; it has been shown that there are classes of graphs that are chi-bounded but not polynomially chi-bounded.
As an attempt to understand the structural distinctions between $chi$-bounded graph classes and polynomially chi-bounded graph classes, we introduce Pollyanna classes of graphs. A class C of graphs is Pollyanna if C cap F$ is polynomially chi-bounded for every chi-bounded class F of graphs. We prove that several classes of graphs are Pollyanna and also present a non-trivial class of graphs that is not Pollyanna.
- Mardi 20 juin 2023 14h à l'ENS Lyon : Felix Klingelhoefer (G-SCOP, Grenoble)
Title: Coloring tournaments with few colors: Algorithms and complexity
Abstract:A k-coloring of a tournament is a partition of its vertices into k acyclic sets. Deciding if a tournament is 2-colorable is NP-hard. A natural problem, akin to that of coloring a 3-colorable graph with few colors, is to color a 2-colorable tournament with few colors. This problem does not seem to have been addressed before, although it is a special case of coloring a 2-colorable 3-uniform hypergraph with few colors, which is a well-studied problem with super-constant lower bounds. We present an efficient decomposition lemma for tournaments and show that it can be used to design polynomial-time algorithms to color various classes of tournaments with few colors, including an algorithm to color a 2-colorable tournament with ten colors. For the classes of tournaments considered, we complement our upper bounds with strengthened lower bounds, painting a comprehensive picture of the algorithmic and complexity aspects of coloring tournaments.
(Joint work with Alantha Newman)
- Mardi 25 Avril 2023, 10h à l'ENS Lyon : François Schwarzentruber (ENS Rennes)
Title: Overview on Connected Multi-agent path finding
Abstract:
Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. In the first part of the talk, we study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents. We also introduce a new class called sight-moveable graphs which admit efficient algorithms. In the second part, we discuss several algorithms to solve connected multi-agent path finding.
- Mardi 14 Mars, Milos Stojakovic (Novi Sad)
Title: Maker-Breaker games on random boards
Abstract:
In Maker-Breaker games played on edge sets of graphs, two players, Maker and Breaker, alternately claim unclaimed edges of a given graph until all of its edges are claimed. Maker wins the game if he claims all edges of one representative of a prescribed graph-theoretic structure (e.g. a Hamiltonian cycle, or a fixed graph H). Breaker wins otherwise.
We take a closer look at various Maker-Breaker games played on the edge sets of random graphs.
- Mardi 28 Fevrier, Ambroise Baril (LORIS)
Title: Linear equivalence between component twin-width and clique-width with algorithmic applications
Abstract: It is a common strategy to solve efficiently NP-complete problems on graphs by exploiting its structural parameters. Recent examples include (put 2 examples). This approach motivated the theory of parameterized complexity, in which parameters such as treewidth or cliquewidth emerged as especially efficient to design fast parameterized algorithms.
Following the same principle, Bonnet et al. recently introduced the notion of contraction sequence of a graph: the high-level idea is to gain time by treating in the same way vertices with a similar neighborhood. The quality of a contraction sequence can be mesured by two (among other) non-functionally equivalent parameters called twin-width and component twin-width, the former being the main focus by Bonnet et al., whereas the latter remained rather unexplored.
It is known that cliquewidth and component twinwidth are functionnaly equivalent: Bonnet et al. proved this result through functional equivalence with booleanwidth (which is known to be functionnaly equivalent with cliquewidth). In particular, this entails an exponential bound on component twin-width by cliquewidth,and a double-exponential bound on cliquewidth by component twin-width.
In this presentation, we show that the latter bounds can be drastically improved to simple linear bounds. As a concrete application, we will provide an algorithmic approach to counting versions of several graph coloring problems relying on component twin-width (using dynamic programming), and that always beats the best known complexity upper bounds. We will also discuss how these linear bounds can be used to extend known approximations of cliquewidth to approximations of component twinwidth.
- Vendredi 7 Novembre 2022, Alexandre Vigny (Bremen)
Title: Approximation of dominating sets for planar graphs with distributed computing.
Abstract:
While only knowing its neighborhood, how can a node make an educated guess on whether it should be part of a dominating set?
We will discuss how on some graph classes, like planar graphs, it is possible to design an algorithm that:
- Only make local decisions, and
- Overall builds a dominating set that is of a size proportional to a globally optimal dominating set.
This is a joint work with Ozan Heyd, Simeon Kublenz, Patrice Ossona de Mendez, and Sebastian Siebertz.
- Vendredi 23 Septembre 2022, Alexandra Wesolek (Simon Fraser)
Title: Tight local algorithms for the minimum dominating set problem in outerplanar graphs
Abstract:
We present a deterministic local algorithm which computes a 5-approximation of a minimum dominating set on outerplanar graphs, and show that this is optimal. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed. This talk will also discuss recent progress for the same problem on K_{2,t}-minor free graphs. The best approximation factor for planar graphs is still unknown (the current best upper bound is 11+ epsilon, the best lower bound is 7- epsilon).
- Vendredi 06 Mai 2022 à 10h30, Lena Yuditsky (Université Libre de Bruxelles)
Title: On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs
Abstract:
For n >= s > r >= 1 and k >= 2, write n erarrow (s)_{k}^r$ if every hyperedge colouring with $k$ colours of the complete $r$-uniform hypergraph on $n$ vertices has a monochromatic subset of size $s$. Improving upon previous results by Axenovich et al. and ErdH{o}s et al. we show that
If r >= 3 and n nerarrow (s)_k^r then 2^n nerarrow (s+1)_{k+3}^{r+1}.
This improves some of the known lower bounds on multicolour hypergraph Ramsey numbers.
(Joint work with Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.)
- Vendredi 08 avril 2022 à 13h30, Dibyayan Chakraborty (ENS Lyon)
Title: Finding Geometric Representations of Apex Graphs is NP-Hard
Abstract:
Planar graphs can be represented as intersection graphs of different types of geometric objects in the plane, e.g., circles, line segments, L-shapes (Gonçalves et al., SODA 2018). For general graphs, however, even deciding whether such representations exist is often NP-hard.
We consider apex graphs, i.e., graphs that can be made planar by removing one vertex from them. We show, somewhat surprisingly, that deciding whether geometric representations exist for apex graphs is NP-hard.
Most known NP-hardness reductions for these problems are from variants of 3-SAT. We reduce from the PLANAR HAMILTONIAN PATH COMPLETION problem, which uses the more intuitive notion of planarity. As a result, our proof is much simpler and encapsulates several classes of geometric graphs.
(Talk based on a joint work with K. Gajjar )
Vendredi 18 mars 2022 à 14h, Hugo Jacob (Utrecht University)
Title: Looking for an improved upper bound to the twin-width of planar graphs
Abstract: Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of
``nicely structured'' graph classes. In particular, it has been known to be bounded for planar
graphs since its introduction by Bonnet et al. but the given bound was not considered satisfactory
(tower of exponentials). It is still open whether we can obtain an upper bound of 100.
We present an upper bound of 183 to the twin-width of planar graphs, and upper bounds for
graphs of bounded treewidth obtained along the way. This is joint work with Marcin Pilipczuk (University of Warsaw).
Preprint: https://arxiv.org/abs/2201.09749
- Vendredi 17 Décembre 2021 à 10h, Maria Chudnovsky (Princeton University)
Title: Induced subgraphs and logarithmic tree width
Abstract: Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. Several constructions of Sintiari and Trotignon show that it is probably very difficult to characterize induced subgraph obstructions to bounded tree width. However, if instead we ask for the tree width to be logarithmic in the number of vertices of the graph (which has similar algorithmic consequences), the situation improves significantly: there is a conjectured characterization, and several related open questions. In this talk we will show that (pyramid, prism, theta)-free graphs with bounded clique number have logarithmic tree width, answering a question of Pilipczuk, Sintiari, Thomassé and Trotignon.
This is joint work with Tara Abrishami, Sepehr Hajebi and Sophie Spirkl.
- Vendredi 3 Décembre 2021 à 10h, Nolleen Kohler (LAMSADE, Paris Dauphine)
Title: Introduction to graph property testing
Abstract: Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph.
In this tutorial I will introduce the basics as well as some useful tools for property testing on bounded degree graphs. I will further give a quick overview of known results in graph property testing and explain the role of bounded degree graphs.
- Vendredi 8 Octobre 2021 à 10h, Carla Groenland (Utrecht)
Title: Intersection sizes of linear subspaces with the hypercube
Abstract: What are the possible intersection sizes that a k-dimensional linear subspace can have with the vertices of the n-dimensional hypercube (in Euclidean space)? Melo and Winter [arXiv:1712.01763, 2017] conjectured that all intersection sizes larger than 2^{k-1} (the “large” sizes) are of the form 2^{k-1} + 2^i. We show that this is almost true: the large intersection sizes are either of this form or of the form 35·2^{k-6} . We also disprove a second conjecture of Melo and Winter by proving that a positive fraction of the “small” values is missing. I will finish with some open problems about hypercube intersection patterns.
This is based on joint work with Tom Johnston
- Vendredi 22 Janvier 2021 à 10h, Thibault Espinasse (Institut Camille Jordan, Lyon 1), en distanciel
Title: Can we recover a graph from observations of noisy eigen-spaces of its adjacency matrix, and why would you like to do so.
Abstract: We adresss the following proble:
Assume that we are able to estimate a matrix K defined as a power serie K = f(W) of some weighted adjacency matrix W of a non oriented (unkown) graph. The aim is to recover the support of W only from this estimation. This problem arises from graph signal processing, where covariance of (second order) stationary signals on graphs may be defined through power series of adjacency (or Laplacian) matrices.
At first glance, this problem seems highly non identifiable, and we will see what assumptions we can make about W to get identifiability. We then build a first estimator of W, and a cross validation procedure to get an adaptative estimator.
- Vendredi 15 Janvier 2021 à 10h, Alexandre Vigny (Université Paris Diderot).
Title:
Query enumeration and nowhere dense classes of graphs
Abstract :
Given a query q and a graph G the enumeration of q over G consists in computing, one element at a time, the set q(G) of all solutions to q on G. The delay is the maximal time between two consecutive output and the preprocessing time is the time needed to produce the first solution. Ideally, we would like to have constant delay enumeration after linear preprocessing. Since this it is not always possible to achieve, we need to add restriction to the classes of graphs and/or queries we consider.
In this talk I will talk about some restrictions for which such algorithms exist: graphs with bounded degree, tree-like structures, conjunctive queries...
We will more specifically consider nowhere dense classes of graphs: What are they? Why is this notion relevant? How to make algorithms from these graph properties?
- Vendredi 4 décembre 2020, Louis Dublois (Paris-Dauphine) à 10h en ligne (informations de connexions transmises par mail)
Title: (In)approximability of Maximum Minimal FVS
Abstract: We study the approximability of the NP-complete textsc{Maximum Minimal
Feedback Vertex Set} problem. Informally, this natural problem seems to lie in
an intermediate space between two more well-studied problems of this type:
textsc{Maximum Minimal Vertex Cover}, for which the best achievable
approximation ratio is $sqrt{n}$, and textsc{Upper Dominating Set}, which
does not admit any $n^{1-epsilon}$ approximation. We confirm and quantify this
intuition by showing the first non-trivial polynomial time approximation for
textsc{Max Min FVS} with a ratio of $O(n^{2/3})$, as well as a matching hardness
of approximation bound of $n^{2/3-epsilon}$, improving the previous known
hardness of $n^{1/2-epsilon}$. Along the way, we also obtain an
$O(Delta)$-approximation and show that this is asymptotically best possible,
and we improve the bound for which the problem is NP-hard from $Deltage 9$ to
$Deltage 6$.
Having settled the problem's approximability in polynomial time, we move to the
context of super-polynomial time. We devise a generalization of our
approximation algorithm which, for any desired approximation ratio $r$,
produces an $r$-approximate solution in time $n^{O(n/r^{3/2})}$. This
time-approximation trade-off is essentially tight: we show that under the ETH,
for any ratio $r$ and $epsilon>0$, no algorithm can $r$-approximate this
problem in time $n^{O((n/r^{3/2})^{1-epsilon})}$, hence we precisely
characterize the approximability of the problem for the whole spectrum between
polynomial and sub-exponential time, up to an arbitrarily small constant in the
second exponent.
- Vendredi 6 mars 2020, Louis Esperet (G-SCOP, Grenoble) à 10h au LIP
Title : Coloration non-répétitive
Abstract: On montre que l'on peut colorier les graphes planaires avec un nombre constant de couleurs, de manière à ce que sur tout chemin de taille paire, la suite de couleurs sur la première motié du chemin diffère de la suite de couleurs sur la seconde moitié. Cela avait été conjecturé par Alon, Grytczuk, Haluszczak et Riordan en 2002. Travail en commun avec Vida Dujmovic, Gwenaël Joret, Bartosz Walczak, et David Wood.
- Vendredi 15 mars 2019, 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 2019, 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
- 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.
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.
- Vendredi 30 mars 2018, Marin Bougeret (LIRMM), à 10h au LIRIS, salle C5
Title : 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
Title : (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 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
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
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 $ngeq 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'
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
Title: Fractional chromatic number of small degree graphs and girth
Abstract: 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 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 $kgeq 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.