### Algorithmique distribuée et graphes

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

** Responsable :** Pierre Charbit

Mardi 02 mai 2017 · 14h00 · Salle 1007

Pierre Aboulker (ULB) · TBA

Mardi 25 avril 2017 · 14h00 · Salle 1007

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

Mardi 18 avril 2017 · 14h00 · Salle 1007

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

Mardi 04 avril 2017 · 14h00 · Salle 1007

Valentin Garnero (INRIA Sophia Antipolis) · (Méta)-noyaux constructifs et linéaires dans les graphes peu denses

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 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

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

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

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.

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

Mardi 10 janvier 2017 · 14h00 · Salle 1007

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

Mardi 03 janvier 2017 · 14h00 · Salle 1007

Marthe Bonamy (Labri - CNRS) · Reed's conjecture 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

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

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

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.

Jeudi 07 juillet 2016 · 10h00 · Salle 1016

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

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

Mardi 21 juin 2016 · 14h00 · Salle 1007

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

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

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

Mardi 12 avril 2016 · 14h00 · Salle 1007

Nicolas Schabanel · Folding Turing is hard but feasible

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

Mardi 29 mars 2016 · 14h00 · Salle 1007

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

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

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

Mardi 19 janvier 2016 · 14h00 · Salle 1007

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

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*