Équipe thématique Calcul distribué

Équipe thématique Théorie et algorithmique des graphes

## Graphes et calcul distribué

#### Jour, heure et lieu

Le mardi à 14h, salle 3052 ou en ligne

Le calendrier des séances (format iCal).

Pour ajouter le calendrier des séances à votre agenda favori, souscrire au calendrier en indiquant ce lien.

#### Contact(s)

### Prochaine séance

Algorithmique distribuée et graphes

Mardi 30 novembre 2021, 14 heures, Salle 1007

**Marco Caoduro** (G-Scop) *Hitting and packing squares*

Clearly, $\tau(\mathcal{S})$ is at least $\nu(\mathcal{S})$. We prove that $\tau(\mathcal{S}) \leq 10 \nu(\mathcal{S})$ and present a family where $\tau(\mathcal{S}) = 3\nu(\mathcal{S})$.

During the talk, we will sketch the proof of the main result and remark how to extend our approach to families of rectangles with \emph{bounded aspect ratios}.

This is joint work with András Sebő.

### Séances passées

#### Année 2021

Algorithmique distribuée et graphes

Mardi 9 novembre 2021, 14 heures, Salle 1007

**Subir Kumar Ghosh** (RKMVERI) *Chromatic art gallery problems for point and vertex guards*

Chromatic art gallery problems arise from applications in areas like landmark-based robot navigation and wireless networks. One such problem is the weak-conflict free guarding of polygons, where the objective is to colour a chosen guard set S for P using the minimum number of colours such that each point within P sees at least one guard from S with a unique colour. Note that the objective here is to minimize the number of colors rather than the number of guards in S. We present an algorithm for weak conflict-free guarding of P (without holes) where the point guard set is coloured using only O(log n) colours. If the guards are allowed to place only on vertices of P, the corresponding algorithm for weak conflict-free vertex guarding problem uses O(log^2 n) colours. This algorithm uses funnel structures of weak visibility polygons for placing coloured guards.

Finally, we discuss a few open problems on weak conflict-free guarding of P for both point and vertex guards.

Algorithmique distribuée et graphes

Mardi 26 octobre 2021, 14 heures, Salle 1007

**Sagnik Sen** (IIT Dharwad, India) *On homomorphisms of simple signed graphs of some families*

Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the chromatic number. In this work, we provide new results and bounds on the chromatic number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).

Joint work with: Bensmail, Das, Nandi, Pierron, Sopena

Algorithmique distribuée et graphes

Mardi 19 octobre 2021, 14 heures, Salle 1007 and via ZOOM

**Mirna Džamonja** (IRIF) *On limits-from the finite to the countable and very much uncountable graphs*

Algorithmique distribuée et graphes

Mardi 5 octobre 2021, 14 heures, ZOOM

**Daniel Gonçalves** (CNRS, Université de Montpellier) *Segment representation of planar graphs*

In his PhD Thesis E.R. Scheinerman conjectured that every planar graph has a segment intersection representation, and he also conjectured that in the case of 3-colorable planar graphs, such a representation exists where only 3 slopes appear, one for each color class. We proved both of these conjectures, and we also proved that such a representation with 4 slopes, one per color class, does not always exist. This last proof relies on the fact that planar signed graphs are not always four colorable, for some signed version of colorings. During the talk we will provide the general idea of these proofs.

These works were joint works with J. Chalopin, L. Isenmann, and C. Pennarun

Algorithmique distribuée et graphes

Jeudi 24 juin 2021, 10 heures, 3052 and ZOOM

**David Roberson** (Department of Applied Mathematics and Computer Science, Technical University ofDenmark) *Quantum isomorphism and counting homomorphisms from planar graphs*

This is joint work with Laura Mančinska.

Algorithmique distribuée et graphes

Mardi 25 mai 2021, 14 heures, ZOOM

**Adrian Pastine** (Universidad Nacional de San Luis) *Null Decomposition of Graphs*

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

Algorithmique distribuée et graphes

Mardi 11 mai 2021, 14 heures, ZOOM

**Bérénice Delcroix-Oger** *Parking trees*

This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo.

This would be a joint (Combi-Graph) seminar.

Algorithmique distribuée et graphes

Mardi 27 avril 2021, 15 heures, ZOOM

**Daniel Adolfo Quiroz** *Colouring with conditions on distances*

Algorithmique distribuée et graphes

Mardi 13 avril 2021, 15 heures, ZOOM

**Adrian Pastine** (Universidad Nacional de San Luis) *Null Decomposition of Graphs*

In this talk, we study the null decomposition of bipartite graphs without cycles of length $0$ modulo $4$. We show that $C_S(G)$ contains a unique maximum independent set and that $C_N(G)$ contains a unique maximum matching. We use the decomposition to show that $\Supp{G}$ is the intersection of all maximum independent sets of $G$, and the union of the unmatched vertices over all maximum matchings. As an application, we present an algorithm that finds a sparse basis for the null space of adjacency matrix of forests in optimal time.

This talk is based on joint work with Daniel Jaume and Gonzalo Molina, from Universidad Nacional de San Luis, and Martin Safe, from Universidad Nacional del Sur.

Algorithmique distribuée et graphes

Mardi 16 mars 2021, 14 heures, ZOOM

**Filippo Brunelli** (IRIF) *On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks*

Meeting ID: 894 0889 8417 Passcode: 005585

Algorithmique distribuée et graphes

Mardi 2 mars 2021, 14 heures, Online Via ZOOM

**Stephane Devismes** (VERIMAG U. Grenoble Alpes) *Self-stabilizing Systems in Spite of High Dynamics*

In this talk, we will consider self-stabilization in highly dynamic networks, i.e., networks suffering from unexpected and frequent topological changes. Precisely, assuming that nodes are uniquely identified, we study the self-stabilizing leader election problem in three important classes of dynamic networks to obtain solutions tolerating both transient faults (such as memory corruption) and frequent topological changes.

We first study conditions under which our problem can be solved and then propose several algorithms. Our results reveal that the assumption on the knowledge of the number N of processes is central. Indeed, we show that, as soon as there is no strong guarantees on the temporal connectivity in the network, the knowledge of the exact value of N is required. Finally, the convergence time of self-stabilizing leader election cannot be bounded in some important cases. In those cases, we show that our solutions are speculative since their convergence time can be still bounded in a subset of more probable executions.

Algorithmique distribuée et graphes

Jeudi 25 février 2021, 14 heures, Online, via Zoom

**Matej Stehlik** (G-SCOP) *Critical subgraphs of Kneser graphs*

Joint work with Tomas Kaiser.

Algorithmique distribuée et graphes

Mardi 23 février 2021, 14 heures, Online, via Zoom

**Arnau Padrol** (Institut de Mathématiques de Jussieu) *Sweeps, polytopes, oriented matroids, and allowable graphs of permutations*

This is based on joint work with Eva Philippe.

https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09

Algorithmique distribuée et graphes

Mardi 2 février 2021, 14 heures, Salle 3052 and ZOOM

**Zhouningxin Wang** (IRIF) *Density of C_{-4}-critical signed graphs*

Zoom link: https://u-paris.zoom.us/j/89408898417?pwd=bTNpVXJXc085MzJabWZ6YVJFRFUwZz09

Meeting ID: 894 0889 8417 Passcode: 005585

Algorithmique distribuée et graphes

Mardi 12 janvier 2021, 15 heures, Online

**Benjamin R. Moore** (University of Waterloo) *The Pseudoforest Nine Dragon Tree conjecture is true*

#### Année 2020

Algorithmique distribuée et graphes

Mardi 24 novembre 2020, 14 heures, Online

**Laurent Feuilloley** (IRIF) *Graph classes and forbidden patterns on three and four vertices*

A popular way to characterize a graph class is to list a minimal set of forbidden induced subgraphs. Unfortunately, this strategy hardly ever leads to a very efficient recognition algorithm. On the other hand, many graph classes can be efficiently recognized by techniques that use some ordering of the nodes, such as the one given by a traversal.

We study specifically graphs that have an ordering avoiding some ordered structures that we call *patterns*. Several well-known classes such as chordal, bipartite, interval, and comparability graphs have a characterization in terms of forbidden patterns. It is also known that any class defined by a set of forbidden patterns on three nodes can be recognized in polynomial time. In a recent paper, we've characterized systematically all the classes defined by sets of forbidden patterns (on three nodes). Surprisingly there is a relatively small number of them, and they are all well-known. Also, almost all of them can actually be recognized in linear time. I will talk about these results and about the rich structure of the classes defined by patterns. I will also talk about on-going work in building bridges between intersection graphs and patterns on four vertices.

https://bbb-front.math.univ-paris-diderot.fr/recherche/zho-14p-vqa-bic

Algorithmique distribuée et graphes

Mardi 20 octobre 2020, 14 heures, Salle 3052

**Pierre Fraigniaud** (IRIF) *Distributed Certification of Graph Classes*

Algorithmique distribuée et graphes

Mardi 6 octobre 2020, 14 heures, Salle 3052

**Marthe Bonamy** (CNRS, LaBRI) *On Vizing's edge colouring question*

Algorithmique distribuée et graphes

Mardi 22 septembre 2020, 15 heures, Salle 3052

**Rongxing Xu** *Multiple list colouring of $3$-choice critical graphs*

Algorithmique distribuée et graphes

Mardi 2 juin 2020, 15 heures 30, Online

**Julien Baste** (Universität Ulm) *Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory*

Algorithmique distribuée et graphes

Vendredi 29 mai 2020, 14 heures, Online

**Guillaume Ducoffe** *Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension*

• Our first main result is a Monte Carlo algorithm that on graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time O(k · mn^{1−εd}), where εd ∈ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such graphs. • Then as a byproduct of our approach, we get a truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense graph classes. The latter classes include all proper minor-closed graph classes, bounded-degree graphs and graphs of bounded expansion. • Finally, we show how to remove the dependency on k for any graph class that excludes a fixed graph H as a minor. More generally, our techniques apply to any graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such graphs one obtains a truly subquadratictime randomized algorithm for computing their diameter.

We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hypergraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of ε-nets, region decomposition and other partition techniques.

If time allows, I will also mention recent improvements of the above results, to eccentricity and distance oracle computations.

This is joint work with Michel Habib and Laurent Viennot.

Algorithmique distribuée et graphes

Mardi 14 avril 2020, 15 heures 30, Online

**Pierluigi Crescenzi** (IRIF) *Temporal Closeness in Temporal Networks*

Algorithmique distribuée et graphes

Mardi 7 avril 2020, 15 heures 30, Online

**Pierre Berge** *Fixed-parameter algorithms for finding small separators in graphs*

Algorithmique distribuée et graphes

Mardi 28 janvier 2020, 14 heures, Salle 3052

**Ana Silva** (Departamento de Matemática - Universidade Federal do Ceará) *Time for coloring*

In this talk, I will present the results, obtained in collaboration with Andrea Marino, in which we focus on temporal graphs whose edges remain active for at least $t$ timestamps (these are called $t$-persistent temporal graphs). Among other things, we: 1) give some upper bounds for the minimum number of colors needed in terms of $t$ and of the chromatic number of the underlying static graph $G$; 2) prove that $k$ colors are always sufficient when $t$ is at least $\log_k n$, and that if $t$ is smaller, then it is NP-complete to decide whether $k$ colors are enough; 3) prove that the problem is NP-complete even when $G$ has bounded treewidth, and each snapshot is planar and has constant size; and 4) give an FPT algorithm with parameters the treewidth of $G$ and $T$.

Our results also imply many interesting facts: for instance, we know that if $G$ is planar and 2-persistent, then 2 colors are always sufficient

#### Année 2019

Algorithmique distribuée et graphes

Mardi 3 décembre 2019, 14 heures, Salle 1007

**Marc Heinrich** *Counting independent sets in strongly orderable graphs*

Algorithmique distribuée et graphes

Mardi 26 novembre 2019, 14 heures, Salle 1007

**Denis Cornaz** (Université Paris Dauphine) *Flows in signed graphs*

Algorithmique distribuée et graphes

Mardi 12 novembre 2019, 15 heures 30, Salle 3052

**Suchismita Mishra** (IITM) *Strong chromatic index of unitary Cayley graphs*

Algorithmique distribuée et graphes

Mercredi 6 novembre 2019, 11 heures, Salle 3052

**Laurent Viennot** *Distance labeling, Ruzsa-Szemeredi graphs and SumIndex communication complexity problem*

Joint work with Adrian Kosowski and Przemyslaw Uznanski.

Algorithmique distribuée et graphes

Mardi 22 octobre 2019, 14 heures, Salle 3052

**Michael Lampis** (Universite Paris Dauphine) *Finer Tight Bounds for Coloring on Clique-Width*

Algorithmique distribuée et graphes

Mardi 8 octobre 2019, 14 heures, Salle 3052

**Fabien De Montgolfier** (IRIF) *Algorithms for generalized modular decomposition*

Algorithmique distribuée et graphes

Lundi 24 juin 2019, 11 heures, Salle 3052

**Carola Doerr** (CNRS, LIP6 Sorbonne University) *Evolutionary Algorithms – From Theory to Practice and Back*

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Algorithmique distribuée et graphes

Mardi 28 mai 2019, 15 heures, Salle 1007

**Jean-Florent Raymond** (TU Berlin) *Enumerating minimal dominating sets in $K_t$-free graphs*

Link to the article: https://arxiv.org/abs/1810.00789

Algorithmique distribuée et graphes

Mardi 21 mai 2019, 14 heures, Salle 3052

**Ben Seamone** (Université de Montréal and Dawson College) *Eternal domination in graphs*

Algorithmique distribuée et graphes

Jeudi 9 mai 2019, 15 heures, Salle 1007

**Amélie Gheerbrant** (IRIF) *Graph query languages*

Algorithmique distribuée et graphes

Mardi 9 avril 2019, 14 heures, Salle 3052

**Binh-Minh Bui-Xuan** (LIP6) *Temporal matching*

In contrast to classical graph theory, we show that the problem of computing a temporal matching of maximum size in a link stream is in general NP-hard. We then depict a kernelization algorithm parameterized by the solution size for the problem, producing quadratic kernels. As a byproduct we also give a 2-approximation algorithm. Both algorithms are implemented and confronted to link streams collected from real world graph data:

https://github.com/antoinedimitriroux/Temporal-Matching-in-Link-Streams

We observe from the experiments that the kernelization algorithm can perform very well in practice, reducing the instance size downto 10-20% on realistic mining parameters. In contrast, the 2-approximation gives rather mixed results. We conjecture that the approximation factor can be improved.

Algorithmique distribuée et graphes

Vendredi 22 mars 2019, 14 heures, Salle 1007

**Julien Baste** (Universität Ulm, Ulm, Germany) *Hitting minors on bounded treewidth graphs*

The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found in <https://arxiv.org/abs/1704.07284>.

Algorithmique distribuée et graphes

Mardi 12 mars 2019, 14 heures, Salle 3052

**Rémy Belmonte** *Token Sliding on Split Graphs*

Joint work with Eun-Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi and Florian Sikora.

Algorithmique distribuée et graphes

Mercredi 6 mars 2019, 11 heures, Salle 3052

**Marc Lelarge** (Inria & ENS Paris) *Spectral embedding for graph classification*

Although our SGE is handcrafted, we also show how our generic embedding technique can be learned and built in a data-driven manner opening the way to new learning algorithms and deep learning architectures with some invariant constraints built-in.

Algorithmique distribuée et graphes

Mardi 19 février 2019, 14 heures, Salle 1007

**Marthe Bonamy** (CNRS - LABRI) *Around Brooks' theorem*

Algorithmique distribuée et graphes

Mardi 19 février 2019, 11 heures, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Algorithmique distribuée et graphes

Mardi 22 janvier 2019, 14 heures, Salle 3052

**Guillaume Ducoffe** (ICI Roumanie) *Computing Giant Diameters with Breadth-First Search and Range Queries*

#### Année 2018

Algorithmique distribuée et graphes

Mardi 18 décembre 2018, 15 heures 30, Salle 3052

**Bergougnoux Benjamin** (IRIF) *Rank Based Approach on Graphs with Structured Neighborhood*

The $d$-neighbor equivalence is a tools introduced by Bui-Xuan et al. in 2013 to obtained efficient parameterized algorithms for many width measures (clique-width, rank-width, mim-width,…) and for many problems with a locally checkable constraint (Dominating Set, Independent Set,…).

By combining these two notions, we obtain efficient algorithms for several connectivity problems such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, $\mathbb{Q}$-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the best time complexity for Vertex Cover and Dominating Set.

Paper available on HAL : https://hal.archives-ouvertes.fr/hal-01799573v2/document

Algorithmique distribuée et graphes

Mardi 11 décembre 2018, 14 heures, Salle 3052

**Riste Škrekovski** (University of Ljubljana) *Some results and problems on unique-maximum colorings of plane graphs*

We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.

Additionally, we will consider a facial edge-coloring analogue of the aforementioned coloring, and we will conclude the talk with various open problems.

(Joint work with Vesna Andova, Bernard Lidick\'y, Borut Lu\v{z}ar, and Kacy Messerschmidt)

Algorithmique distribuée et graphes

Jeudi 29 novembre 2018, 14 heures, Salle 3014

**Carenne Ludeña** (Universidad Jose Tadeo Lozano) *A random graph model based on the Modular decomposition of graphs*

Algorithmique distribuée et graphes

Mardi 27 novembre 2018, 14 heures, Salle 3052

**Miguel Mendez** *Set operads and decomposition theory*

Algorithmique distribuée et graphes

Mardi 23 octobre 2018, 14 heures, Salle 3052

**Yllka Velaj** (CWI Amsterdam) *Stable Outcomes in Modified Fractional Hedonic Games*

We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions, leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0-1 weights.

Algorithmique distribuée et graphes

Mardi 22 mai 2018, 14 heures, Salle 1007

**François Pirot** (Université de Strasbourg) *Fractional chromatic number of small degree graphs and girth.*

Algorithmique distribuée et graphes

Vendredi 6 avril 2018, 10 heures, Salle 3052

**Cédric Bentz** *Steiner trees with edge capacities.*

Algorithmique distribuée et graphes

Mardi 3 avril 2018, 14 heures, Salle 1007

**Marcin Kaminski** *Induced minors and well-quasi-ordering*

We show that the class of H-free graphs is well-quasi-ordered by induced minors if and only if H is an induced minor of the gem (=the path on 4 vertices plus a dominating vertex) or the graph obtained by adding a vertex of degree 2 to the K4 (= the complete graph on 4 vertices).

This generalizes a a result of Robin Thomas who proved that K4-free graphs are well-quasi-ordered by induced minors and complements similar dichotomy theorems proved by Guoli Ding for subgraphs and Peter Damaschke for induced subgraphs.

This is joint work with Jarosław Błasiok, Jean-Florent Raymond, and Théophile Trunck.

Algorithmique distribuée et graphes

Mardi 27 mars 2018, 14 heures, Salle 1007

**Matej Stehlik** (Université Grenoble Alpes - GSCOP) *Nombre chromatique et la méthode topologique*

Algorithmique distribuée et graphes

Mardi 20 mars 2018, 14 heures, Salle 1007

**Pierluigi Crescenzi** (Universite de Pise) *Computing node centrality in large graphs: from theory to practice and back*

Algorithmique distribuée et graphes

Mardi 13 mars 2018, 14 heures, Salle 1007

**Mamadou Kante** (ISIMA) *Obstructions pour certaines classes de matroides linéaires*

Algorithmique distribuée et graphes

Mardi 27 février 2018, 14 heures, Salle 1007

**Dieter Mitsche** (Université Nice) *Aspects des Graphes Aléatoires*

Algorithmique distribuée et graphes

Mardi 20 février 2018, 14 heures, Salle 1007

**Jan Arne Telle** (University of Bergen) *Width parameters of graphs and structured graph classes*

Parts of the talk are based on joint work with O.Kwon and L.Jaffke, to appear at STACS 2018.

Algorithmique distribuée et graphes

Lundi 12 février 2018, 14 heures, Salle 3052

**Nabil Mustafa** (ESIEE) *Local Search for Geometric Optimization Problems.*

#### Année 2017

Algorithmique distribuée et graphes

Mardi 12 décembre 2017, 14 heures, Salle 3052

**Jean Krivine** (IRIF) *Incremental Update for Graph Rewriting*

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Séminaire commun du pole Algorihtmes et Structures Discrètes.

Algorithmique distribuée et graphes

Mardi 17 octobre 2017, 14 heures, Salle 3052

**Claire Mathieu** (DI - ENS) *Online k-compaction*

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.

Algorithmique distribuée et graphes

Mardi 26 septembre 2017, 14 heures, Salle 1007

**Jara Uitto** (ETH Zurich) *Tight Lower Bounds for the Cops and Robbers Game*

Algorithmique distribuée et graphes

Mardi 12 septembre 2017, 14 heures, Salle 1007

**Mor Perry** *Aspects of Distributed Verification*

1. Space-time tradeoffs for distributed verification, joint work with Rafail Ostrovsky and Will Rosenbaum. In this work, we introduce the notion of a t-PLS, which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of t-PLS between time, label size, message length, and computation space. We construct a universal t-PLS and prove that it uses the same amount of total communication as a known one-round universal PLS, and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space-time tradeoffs of t-PLS. We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal t-PLS for acyclicity uses proof size, message size and computation space O( ( log n)/t).

2. Approximate proof-labeling schemes, joint work with Keren Censor-Hillel and Ami Paz. In this work we extend the PLS model by defining the approximate PLS (APLS) model. In this new model, the predicates for verification are of the form f(G)\le f'(G), where f, f': F → N for a family of configurations F and the set of natural numbers N. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration alpha, so that only if f(G) > alpha*f'(G) some node must reject. We show that in the APLS model, the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size.

Algorithmique distribuée et graphes

Mardi 20 juin 2017, 14 heures, Salle 1007

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

Can you tell me how long should be the talk?

Algorithmique distribuée et graphes

Mardi 13 juin 2017, 14 heures, Salle 1007

**Afshin Behmaram** *Matching and covering in cubic graphs*

Algorithmique distribuée et graphes

Mardi 2 mai 2017, 14 heures, Salle 1007

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

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?

Algorithmique distribuée et graphes

Mardi 25 avril 2017, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 18 avril 2017, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 4 avril 2017, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 28 mars 2017, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 21 mars 2017, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 28 février 2017, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 7 février 2017, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 24 janvier 2017, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 10 janvier 2017, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 3 janvier 2017, 14 heures, 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).

#### Année 2016

Algorithmique distribuée et graphes

Mardi 13 décembre 2016, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 29 novembre 2016, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 25 octobre 2016, 14 heures, Salle 1007

**Jonas Lefevre** (IRIF) *Self-stabilizing Metric Graphs*

Algorithmique distribuée et graphes

Mardi 27 septembre 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Jeudi 7 juillet 2016, 10 heures, 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.

(Attention jour horaire et salle inhabituels)

Algorithmique distribuée et graphes

Mardi 28 juin 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 21 juin 2016, 14 heures, 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.

Algorithmique distribuée et graphes

Jeudi 9 juin 2016, 14 heures, Salle 2015

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

Algorithmique distribuée et graphes

Mardi 24 mai 2016, 14 heures, Salle 1007

**Eujung Kim** *Non encore annoncé.*

Algorithmique distribuée et graphes

Mardi 17 mai 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 12 avril 2016, 14 heures, 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.

Algorithmique distribuée et graphes

Mardi 5 avril 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 29 mars 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 9 février 2016, 14 heures, Salle 1007

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

Algorithmique distribuée et graphes

Mardi 19 janvier 2016, 14 heures, 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.