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 Nicolas Bousquet (firstname.lastname@grenoble-inp.fr) ou Rémi Pellerin (firstname.lastname@ens-lyon.fr).
Pour voir les anciennes présentations, vous pouvez consulter la page d'archives.
Vu la situation sanitaire actuelle, les séminaires Graphes@Lyon sont temporairement suspendus. Ils ont été remplacés 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
- 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 problem :
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.
Séminaires passés
- 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 $\Delta\ge 9$ to
$\Delta\ge 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
<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.
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<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
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
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 $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.