Équipe-projet INRIA GANG

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

## Graphes

#### Jour, heure et lieu

Le mardi à 14h, salle 1007

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)

### Prochaines séances

Graphes

Mardi 26 novembre 2019, 14 heures, Salle 3052

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

Graphes

Mardi 10 décembre 2019, 14 heures, Salle 3052

**Nicolas Schabanel** (IRIF) *Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model*

The Oritatami model was proven that it is capable of efficient Turing universal computation by Geary et al (2018) thanks to a quite complicated construction that simulates Turing machines via tag systems. We propose here a simple Oritatami system which intrinsically simulates arbitrary $1$D cellular automata. Being intrinsic, our simulation emulates the behavior of the cellular automata in a readable way and in time linear in space and time of the simulated automaton. Furthermore, the number of bead types needed is quite modest (182 as opposed to 542), and the delay δ is 2 (instead of 3). The length of the transcript is also only quadratic in the size of the cellular automata: $O(rQ^{2(2r+1)}\log Q)$ for a cellular automata with $Q$ states and radius $r$ (whose size is thus $O(Q^{2r+1}\log Q)$).

Our construction relies on the development of new tools which are simple enough that we believe that some simplification of them may be implemented in the wet lab. Our construction has been implemented and will be soon freely downloaded for testing.

Joint work with Daria Pchelina (ENS Paris), Shinnosuke Seki (UEC Tokyo) and Yuki Ubukata (NTT Data Corp, Japan)

### Séances passées

#### Année 2019

Graphes

Mardi 12 novembre 2019, 15 heures 30, Salle 3052

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

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.

Graphes

Mardi 22 octobre 2019, 14 heures, Salle 3052

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

Graphes

Mardi 8 octobre 2019, 14 heures, Salle 3052

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

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.

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

Graphes

Mardi 21 mai 2019, 14 heures, Salle 3052

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

Graphes

Jeudi 9 mai 2019, 15 heures, Salle 1007

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

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.

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

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.

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.

Graphes

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

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

Graphes

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

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

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

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

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)

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*

Graphes

Mardi 27 novembre 2018, 14 heures, Salle 3052

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

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.

Graphes

Mardi 22 mai 2018, 14 heures, Salle 1007

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

Graphes

Vendredi 6 avril 2018, 10 heures, Salle 3052

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

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.

Graphes

Mardi 27 mars 2018, 14 heures, Salle 1007

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

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*

Graphes

Mardi 13 mars 2018, 14 heures, Salle 1007

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

Graphes

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

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

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.

Graphes

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

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

#### Année 2017

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 Algorithmes et Structures Discrètes

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.