Algorithmique distribuée et graphes

Date et lieu : le mardi à 14h, salle 1007, Sophie Germain

Responsable : Pierre Charbit

Mardi 20 juin 2017 · 14h00 · Salle 1007

Siddarth Gupta · A Topological Algorithm for Determining How Road Networks Evolve Over Time

We provide an efficient algorithm for determining how a road network has evolved over time, given two snapshot instances from different dates. To allow for such determinations across different databases and even against hand drawn maps, we take a strictly topological approach in this paper, so that we compare road networks based strictly on graph-theoretic properties. Given two road networks of same region from two different dates, our approach allows one to match road network portions that remain intact and also point out added or removed portions. We analyze our algorithm both theoretically, showing that it runs in polynomial time for non-degenerate road networks even though a related problem is NP-complete, and experimentally, using dated road networks from the TIGER/Line archive of the U.S. Census Bureau.

Can you tell me how long should be the talk?

Mardi 13 juin 2017 · 14h00 · Salle 1007

Afshin Behmaram · Matching and covering in cubic graphs

In this talk, i will present first some theorems and observations about matching in cubic graphs and about covering the edges of cubic graphs by perfect matchings. Then I will present some interesting open problems in this area.

Mardi 02 mai 2017 · 14h00 · Salle 1007

Pierre Aboulker (ULB) · From chromatic number to dichromatic number

A k-dicolouring of a digraph is a partition of its vertex setinto k acyclic subdigraphs. The dichromatic number of a digraph D is the minimum k such that D has a k-dicolouring.

We first give some properties related to the dichromatic number in order to show why and how it generalizes the chromatic number of non-oriented graphs. Then we investigate the following questions: What can we say about subgraphs, induced subgraphs and topological minors of a digraph with large dichromatic number?

Mardi 25 avril 2017 · 14h00 · Salle 1007

Mike Molloy (University of Toronto and Ecole Normale Superieure Paris) · Entropy Compression and the Lovasz Local Lemma

The Lovasz Local Lemma, a cornerstone of the probabilistic method, is a powerful and widely used proof technique. In 2009, Moser introduced a technique called entropy compression to provide efficient algorithms which construct objects that the Local Lemma guarantees to exist. Recently, entropy compression has been used to develop more powerful versions of the Local Lemma which provide existence proofs in settings where the original Local Lemma does not apply. I will illustrate this technique with applications to graph colouring: (a) colouring triangle-free graphs, and (b) frugal colouring, where no colour can appear too many times in any neighbourhood.

Mardi 18 avril 2017 · 14h00 · Salle 1007

Mikael Rabie (LIX) · Time and Homonyms Considerations over Community Protocols

Guerraoui and Ruppert introduced the model of Community Protocols. This Distributed System works with agents having a finite memory and unique identifiers (the set of identifiers being ordered). Each agent can store a finite number of identifiers they heard about. The interactions are asynchronous and pairwise, following a fair scheduler. The computation power of this model is fully characterized: it corresponds exactly to what non deterministic Turing Machines can compute on a space O(n\log n). In this talk, I will focus on two restrictions of the model: The first is what happens when agents may share identifiers, the population admitting homonyms. I will introduce a hierarchy, with characterizations depending on the rate of unique identifiers present in the population. The main result is that with log n identifiers, a Turing Machine with a polylogarithmic space can be simulated. The second considers the following time restriction: what can be computed in a polylogarithmic number of parallel interactions. This version is not yet characterized, but I will provide some impossibility results, some computable protocols, and I will give the tighter bound we found.

Mardi 04 avril 2017 · 14h00 · Salle 1007

Valentin Garnero (INRIA Sophia Antipolis) · (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.

Mardi 28 mars 2017 · 14h00 · Salle 1007

Juho Hirvonen (IRIF) · Recent developments in the theory of distributed graph algorithms

I will survey and try to explain the intuition behind several recent developments in the theory of distributed graph algorithms. I will focus on the LOCAL model, where the measure of interest is how far information has to be propagated in a communication network in order solve a given problem. The problems of interest will be locally checkable labelling problems (LCLs), a natural class of problems that allow distributed verification of proposed solutions.

I will discuss two recent papers in this field. First, we gave a lower bound showing that there exist LCL problems of ”intermediate” complexity, that is, complexity strictly between known complexity classes (Brandt et al., STOC 2016). The proof is by a new kind of simulation argument. Second, Chang et al. (FOCS 2016) showed that this lower bound implies an exponential separation between the randomized and deterministic LOCAL models. Chang et al. also show further connections between the randomized and deterministic models, and establish a useful speed-up simulation for the deterministic LOCAL model.

Mardi 21 mars 2017 · 14h00 · Salle 1007

Evangelos Bampas (LIF - Université Aix Marseille) · Linear search by a pair of distinct-speed robots

We will present algorithms for the evacuation problem by a pair of distinct-speed robots on an infinite line. In this problem, two mobile robots with different maximal speeds are initially placed at the same point on an infinite line. The robots need to find a stationary target (i.e., the exit), which is placed at an unknown location on the line. The search is completed when both robots arrive at the exit and the goal is to conclude evacuation in as little time as possible. The robot that discovers the exit first may communicate it to the other robot. We consider two models of communication between the robots, namely wireless communication and face-to-face communication. We present an optimal algorithm for any combination of robot speeds in the case of face-to-face communication. In the case of wireless communication, our algorithm is optimal if the slow robot is at most 6 times slower than the fast robot.

Mardi 28 février 2017 · 14h00 · Salle 1007

Laurent Viennot (INRIA - IRIF) · Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

Joint work with Adrian Kosowski

The goal of a hub-based distance labeling scheme for a network $G = (V, E)$ is to assign a small subset $S(u) \subseteq V$ to each node $u \in V$, in such a way that for any pair of nodes $u, v$, the intersection of hub sets $S(u) \cap S(v)$ contains a node on the shortest $uv$-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least $r$ intersecting a given ball of radius $2r$. In this talk, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.

Mardi 07 février 2017 · 14h00 · Salle 1007

Edouard Bonnet (Middlesex University, London) · Fine-grained complexity of coloring geometric intersection graphs.

We are interested in the following problem: Given a collection of n objects in the plane and an integer k, is there a proper k-coloring of its intersection graph (i.e., such that two overlapping objects get different colors). Here we think of k as a function of n; it can be constant, linear, or anything in between. From an application of a known separator theorem, if the input objects are fat (i.e., have bounded diameter/width ratio), then this problem can be solved in time 2^{O(\sqrt{n k} \log n)}. We will show that this running time is essentially optimal under the Exponential Time Hypothesis (ETH). We then move to intersection graphs of segments (which are quintessentially non fat) and show that the situation is quite different than with fat objects. We end on a surprising note: 3-coloring and 4+-coloring of segments have significantly different behaviors.

The guideline and motivation of the talk is to go beyond the NP-hardness of coloring those geometric graphs, and precise what is the best (hopefully subexponential) running time that we can get.

This is based on a joint work with Csaba Biró, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski, and an ongoing project with Stéphan Thomassé and a subset of the aforementioned authors.

Mardi 24 janvier 2017 · 14h00 · Salle 1007

Maximilien Danisch (Telecom Paris Tech) · Towards real-world graph algorithmics

Real-world graphs (a.k.a. complex networks) are ubiquitous: the web, Facebook, Twitter, brain networks, protein interaction networks, etc. Studying these graphs and solving computational problems on them (say maximum clique, partitioning or dense subgraph) has applications in many fields. I will first show that the structure of some real-world graphs is special. In particular, they are not adversarial and some difficult problems (say NP-complete or NP-hard problems) can be solved on some huge real-world graphs (say 2G edges or more). I will then present two works along the lines of “understanding and leveraging the structure of real-world graphs in order to build better algorithms”: (i) Enumerating all k-cliques and (ii) Computing the density-friendly graph decomposition.

Mardi 10 janvier 2017 · 14h00 · Salle 1007

Carl Feghali (IRIF) · Problems and Results in Kempe Equivalence of Colorings

Given a graph G with a coloring, a Kempe chain of G is a maximal connected subgraph of G in which each vertex has one of two colors. A Kempe change is the operation of swapping the colors of a Kempe chain. Two colorings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. In this talk, we survey some of the existing results, open problems and common proof techniques in this area.

Mardi 03 janvier 2017 · 14h00 · Salle 1007

Marthe Bonamy (Labri - CNRS) · Reed's conjecture and strong edge coloring

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex “sees few edges” in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.

This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

Mardi 13 décembre 2016 · 14h00 · Salle 1007

Hang Zhou (Max Planck Institute for Informatics) · Graph Reconstruction and Verification

How efficiently can we find an unknown graph using shortest path queries between its vertices? This is a natural theoretical question from the standpoint of recovery of hidden information. This question is related to discovering the topology of Internet networks, which is a crucial step for building accurate network models and designing efficient algorithms for Internet applications.

In this talk, I will introduce the problems of graph reconstruction and verification via oracles. I will investigate randomized algorithms based on a Voronoi cell decomposition. I will also analyze greedy algorithms, and prove that they are near-optimal.

The talk is based on joint work with Claire Mathieu and Sampath Kannan.

Mardi 29 novembre 2016 · 14h00 · Salle 1007

Michel Habib (IRIF) · Cocomparability graphs and greedy algorithms

Joint work with Derek Corneil, Jérémie Dusart and Ekkehard Kh\“oler

A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparability graphs. I will first present some recent algorithms we obtained on cocomparability graphs. They show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings.

Then I will propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph $G$ is also a maximal chordal subgraph of $G$.

This characterization also has interesting algorithmic consequences and we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an $O(n+mlogn)$ time algorithm to find a maximal interval subgraph of a cocomparability graph. Similarly I propose a linear time algorithm to compute all simplicial vertices in a cocomparability graph. In both cases we improve on the current state of knowledge.

Mardi 25 octobre 2016 · 14h00 · Salle 1007

Jonas Lefevre (IRIF) · Self-stabilizing Metric Graphs

Je présenterai un algorithme autostabilisant pour réseaux overlay construisant le graphe d'une métrique donnée par oracle. L'algorithme fonctionne sous les daemons synchrones et asynchrones. Sous daemon synchrone le temps de convergence est linéaire. Dans tout les cas, la complexité en messages et celle en mémoire sont aussi faibles que possible. Cette construction peut être utilisée pour construire pour de la construction d'un graphe arbitraire.

Mardi 27 septembre 2016 · 14h00 · Salle 1007

Ha Duong Phan (Institute of Mathematics, VAST, Vietnam.) · Algorithms for computing the rank of divisors on some classes of graphs.

The notion of rank of divisor on graph was introduced by Baker and Norine in 2007 in showing the link with the similar notion on Riemann surface. Moreover, the authors have developed a theorem for divisors on graph analogue to the classical Riemann-Roch theorem. Since then, many works have studied for computing the rank of divisors on graph. A very important is the new theorem on the NP-hardness complexity of the Problem of computing the rank of divisor on general graph. The proof of this result was based on the proof of the NP-hardness of the Problem of finding the minimum recurrent configurations of Chip Firing Game on directed graphs (by Perrot and Pham). In this talk, we will present some (linear) algorithms for computing the rank of divisors on some classes of graphs.

Jeudi 07 juillet 2016 · 10h00 · Salle 1016

Eli Gafni (UCLA) · The Role of Mantras in (Distributed-Computing) Research

A Research-Mantra is something “cosmic” one believes holds in the area of research at hand. It is then a “pillar of fire” in front that leads the way. The Mantra is to be followed as long as it is not refuted by facts.
In this talk I'll present some Mantras I followed during the years starting with one that says that Distributed-Computing Theory (DCT) is the Mathematical Study of Interleaving. Consequently, DCT researchers should have Mathematical sensibilities rather than Engineering ones. Thus, DCT should poses the beauty of Mathematics, and should not be be “hacked” as an Engineering Domain. In particular any paper that points to “anomalies” or “paradoxes” does not point to faults in the domain but to faults in the thinking of the authors. I'll show some Mantras I use and where they led, and I'll end up with the ramification of recent Mantra that holds that deterministic state-machines capture interleaving as well as message-passing interleaving.

Mardi 28 juin 2016 · 14h00 · Salle 1007

Janna Burman (LRI - Université Paris Sud) · Space-Optimal Counting in Population Protocols

We study the fundamental problem of counting, which consists in computing the size of a system. The considered model are population protocols, which is the model of finite state, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to a fairness condition). We significantly improve the previous results known for counting in this model, in terms of (exact) space complexity. Specifically, we give the first space optimal protocols solving the problem for two classical types of fairness, global and weak. Both protocols require no initialization of the counted agents. The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) per counted agent. The protocol, functioning under weak fairness, requires the necessary log P bits (P states, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits the intriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Rings and the Hanoi Towers puzzles.

Mardi 21 juin 2016 · 14h00 · Salle 1007

Qiang Sun (LRI) · Locating any two vertices on Hamiltonian cycles

We give a proof of Enomoto's conjecture for graphs of sufficiently large order. Enomoto's conjecture states that: if G is a graph of order n with minimum degree at least n/2+ 1, then for any pair x,y of vertices of G, there is a Hamiltonian cycle C of G such that the distance between x and y in C is n/2.

The main tools of our proof are Regularity Lemma of Szemeredi and Blow-up Lemma of Koml os et al..

This is a joint work with Weihua He and Hao Li.

Jeudi 09 juin 2016 · 14h00 · Salle 2015

Feodor Dragan (Kent State University) · Tree-Like Structures in Graphs: A Metric Point of View

Recent empirical and theoretical work has suggested that many real-life complex networks and graphs arising in Internet applications, in biological and social sciences, in chemistry and physics have tree-like structures from a metric point of view. A number of graph parameters trying to capture this phenomenon and to measure these tree-like structures were proposed; most notable ones being the tree-stretch, tree-distortion, tree-length, tree-breadth, Gromov’s hyperbolicity of a graph, and cluster-diameter and cluster-radius in a layering partition of a graph. If such a parameter is bounded by a constant on graphs then many optimization problems can be efficiently solved or approximated for such graphs. We discuss these parameters and recently established relationships between them for unweighted and undirected graphs; it turns out that all these parameters are at most constant or logarithmic factors apart from each other. We give inequalities describing their relationships and discuss consequences for some optimization problems.

Mardi 24 mai 2016 · 14h00 · Salle 1007

Eujung Kim · TBA

Mardi 17 mai 2016 · 14h00 · Salle 1007

Edita Rollova (University of West Bohemia, Pilsen, Czech republic) · New proof of Seymour's 6-flow theorem

We will provide (two) new proof(s) of Seymour's 6-flow theorem (both) using induction.

Mardi 12 avril 2016 · 14h00 · Salle 1007

Nicolas Schabanel · Folding Turing is hard but feasible

Nicolas Schabanel, joint work with Cody Geary (Caltech), Pierre-Étienne Meunier (U. Aalto), et Shinnosuke Seki (U. Electro-Communications, Tokyo).

We introduce and study the computational power of Oritatami, a theoretical model to explore greedy molecular folding, by which the molecule begins to fold before waiting the end of its production. This model is inspired by our recent experimental work demonstrating the construction of shapes at the nanoscale by folding an RNA molecule during its transcription from an engineered sequence of synthetic DNA. While predicting the most likely conformation is known to be NP-complete in other models, Oritatami sequences fold optimally in linear time. Although our model uses only a small subset of the mechanisms known to be involved in molecular folding, we show that it is capable of efficient universal computation, implying that any extension of this model will have this property as well.

We introduce general design techniques for programming these molecules. Our main result in this direction is an algorithm in time linear in the sequence length, that finds a rule for folding the sequence deterministically into a prescribed set of shapes depending of its environment. This shows the corresponding problem is fixed-parameter tractable although we proved it is NP-complete in the number of possible environments. This algorithm was used effectively to design several key steps of our constructions.

Mardi 05 avril 2016 · 14h00 · Salle 1007

Matteo Seminaroti · Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition

We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and, for an n×n nonnegative matrix with m nonzero entries, it terminates in n−1 SFS sweeps, with overall running time O(n^2+nmlogn).

Mardi 29 mars 2016 · 14h00 · Salle 1007

Benjmain Momege · Autour de la connexité dans les graphes avec conflits

Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d'arêtes ne pouvant pas simultanément faire partie d'un sous-graphe), dans lesquels nous étudierons différents types de problèmes, de nature aussi bien algorithmique que combinatoire, notre ligne directrice étant la notion de connectivité. Nous verrons que plusieurs résultats, simples sans conflit, ne le sont plus lors de l'ajout de conflits. Nous présenterons : des algorithmes exacts (non polynomiaux), des résultats de NP-complétude, et des conditions suffisantes assurant l'existence de certains objets (arbre couvrant, chemin et cycle Hamiltonien) sans conflits.

Mardi 09 février 2016 · 14h00 · Salle 1007

Thomas Perrett (Technical University of Denmark) · Roots of the chromatic polynomial, spanning trees and minors

The real and complex roots of chromatic polynomials, which we call chromatic roots, have been studied since the 1940s yet it is not well understood how structural properties of graphs affect their chromatic roots. In this talk we survey some results and open problems, and present recent work on the following question: For a minor- closed class of graphs, what is the infimum of the non-trivial real chromatic roots of the graphs in that class?

Mardi 19 janvier 2016 · 14h00 · Salle 1007

Sang-il Oum (KAIST) · Variants of Hadwiger's conjecture

Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable; in other words, every graph with no K_t minor admits a partition of its vertex set into t-1 independent sets. This conjecture is still widely open and if true, it implies the four color theorem. Gerards and Seymour made a stronger conjecture claiming that every graph with no K_t odd minor is (t-1)- colorable, commonly called the odd Hadwiger's conjecture. We prove variants of Hadwiger's conjecture. First, we prove that every graph with no K_t minor admits a partition of its vertex set into t-1 sets, each inducing a subgraph of bounded maximum degree. Secondly, we prove that every graph with no K_t minor admits a partition of its vertex set into 3(t-1) sets, each inducing a subgraph having no large components.

We also prove variants of the odd Hadwiger's conjecture as follows: Every graph with no odd K_t minor admits a partition of its vertex set into 7t-10 sets, each inducing a subgraph of bounded maximum degree. As a corollary, we prove that every graph with no odd K_t minor admits a partition of its vertex set into 16t-19 sets, each inducing a subgraph with no large components. The last result improves the result of Kawarabayashi, who showed it with 496t sets.

This talk is a combination of three works; first with K. Edwards, D. Kang, J. Kim, and P. Seymour, second with C. Liu, and third with D. Kang.

  • 01-12-2015 : M. Sozio (INFRES - TelecomParisTech), Finding dense subgraphs and interesting events in social networks
  • 17-11-2015 : Victor Chepoi (LIF (Marseille)), Colouring hyperplanes of CAT(0) cube complexes
  • 22-09-2015 : R. R. del Vecchio (Department of Mathematics, federal Fluminense University, Rio de Janeiro, Brasil), Laplacian Integrality in P4-Sparse Graphs