## Graphs

#### Day, hour and place

Tuesday at 2pm, room 1007

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.

#### Contact(s)

### Next talks

Graphs

Tuesday February 2, 2021, 2PM, Salle 1007

**Zhouningxin Wang** *Density of $C_{-4}$-critical signed graphs*

Graphs

Tuesday February 23, 2021, 2PM, Online

**Carl Feghali** (Charles University) *Some conjectures and open questions in coloring reconfiguration*

### Previous talks

#### Year 2021

Graphs

Tuesday January 12, 2021, 3PM, Online

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

#### Year 2020

Graphs

Tuesday November 24, 2020, 2PM, 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

Graphs

Tuesday October 20, 2020, 2PM, Salle 3052

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

Graphs

Tuesday October 6, 2020, 2PM, Salle 3052

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

Graphs

Tuesday September 22, 2020, 3PM, Salle 3052

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

Graphs

Tuesday June 2, 2020, 3:30PM, Online

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

Graphs

Friday May 29, 2020, 2PM, 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.

Graphs

Tuesday April 14, 2020, 3:30PM, Online

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

Graphs

Tuesday April 7, 2020, 3:30PM, Online

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

Graphs

Tuesday January 28, 2020, 2PM, 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

#### Year 2019

Graphs

Tuesday December 3, 2019, 2PM, Salle 1007

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

Graphs

Tuesday November 26, 2019, 2PM, Salle 1007

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

Graphs

Tuesday November 12, 2019, 3:30PM, Salle 3052

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

Graphs

Wednesday November 6, 2019, 11AM, Salle 3052

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

Joint work with Adrian Kosowski and Przemyslaw Uznanski.

Graphs

Tuesday October 22, 2019, 2PM, Salle 3052

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

Graphs

Tuesday October 8, 2019, 2PM, Salle 3052

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

Graphs

Monday June 24, 2019, 11AM, 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.

Graphs

Tuesday May 28, 2019, 3PM, 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

Graphs

Tuesday May 21, 2019, 2PM, Salle 3052

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

Graphs

Thursday May 9, 2019, 3PM, Salle 1007

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

Graphs

Tuesday April 9, 2019, 2PM, 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.

Graphs

Friday March 22, 2019, 2PM, 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>.

Graphs

Tuesday March 12, 2019, 2PM, 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.

Graphs

Wednesday March 6, 2019, 11AM, 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.

Graphs

Tuesday February 19, 2019, 2PM, Salle 1007

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

Graphs

Tuesday February 19, 2019, 11AM, Salle 3052

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

Graphs

Tuesday January 22, 2019, 2PM, Salle 3052

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

#### Year 2018

Graphs

Tuesday December 18, 2018, 3:30PM, 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

Graphs

Tuesday December 11, 2018, 2PM, 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)

Graphs

Thursday November 29, 2018, 2PM, Salle 3014

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

Graphs

Tuesday November 27, 2018, 2PM, Salle 3052

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

Graphs

Tuesday October 23, 2018, 2PM, 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.

Graphs

Tuesday May 22, 2018, 2PM, Salle 1007

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

Graphs

Friday April 6, 2018, 10AM, Salle 3052

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

Graphs

Tuesday April 3, 2018, 2PM, 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.

Graphs

Tuesday March 27, 2018, 2PM, Salle 1007

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

Graphs

Tuesday March 20, 2018, 2PM, Salle 1007

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

Graphs

Tuesday March 13, 2018, 2PM, Salle 1007

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

Graphs

Tuesday February 27, 2018, 2PM, Salle 1007

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

Graphs

Tuesday February 20, 2018, 2PM, 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.

Graphs

Monday February 12, 2018, 2PM, Salle 3052

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

#### Year 2017

Graphs

Tuesday December 12, 2017, 2PM, 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

Graphs

Tuesday October 17, 2017, 2PM, Salle 3052

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

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