Algorithmique distribuée et graphes

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

Responsable : Nicolas Schabanel

Mardi 14 mars 2017 · 14h00 · Salle 1007

Juho Hirvonen (IRIF) · TBA

Mardi 21 mars 2017 · 14h00 · Salle 1007

Evangelos Bampas (LIF - Université Aix Marseille) · TBA

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