GT virtuels du LaBRI à venir

GT AlgoDist
Lundi 28 septembre à 14h - Arnaud Labourel (LIS, Marseille)
Schéma d’étiquetage de distance pour des familles de graphes définies par des propriétés métriques
Connexion: et room 178 (hybride)

Les schémas d’étiquetage sont une manière de répartir l’information d’un graphe sur ses sommets. Ils consistent en une fonction d’encodage qui attribue à chaque sommet d’un graphe G une étiquette binaire, et une fonction de décodage qui calcule le résultat d’une requête entre deux sommets en utilisant seulement leurs étiquettes. Dans notre cas nous allons nous intéresser à des requêtes de distance et donc la fonction de décodage devra calculer la distance (ou une approximation de celle-ci) entre les deux sommets à partir de leurs étiquettes. Nous nous intéressons à de tels schémas pour deux familles importantes de la théorie métrique des graphes: les graphes médians et les graphes pontés. Les graphes médians sont les graphes tels que pour tout triplet de sommet l'intersection de tous les plus courts chemins possibles entre deux sommets du triplet consiste en un unique sommet. Je vous présenterai un schéma de distance pour la sous-famille des graphes médians qui ne contiennent pas de cube, utilisant des étiquettes de O(log^3 n) où n est le nombre de sommets des graphes. Les graphes pontés (bridged en anglais) sont les graphes qui n'admettent pas de cycle isométrique de plus de trois sommets et nous considérerons dans cet exposé la sous-famille de ces graphes qui ne contiennent pas de clique de taille 4. Je vous présenterai un schéma de distance 4-approchée (donnant une approximation de la distance comprise en une fois et quatre fois celle-ci) utilisant des techniques similaires à celui des graphes médians. C’est un travail effectué en collaboration avec Victor Chepoi et Sébastien Ratel.

Vendredi 2 octobre à 14h - Nicolas Bousquet
Independent Set Reconfiguration via Token Sliding

An independent set of a graph G is a subset of pairwise non incident vertices of G. Finding a maximum independent set in G is a problem that received a considerable attention in the last decades. In this talk, we will look at this problem via the lens of reconfiguration. Two independent sets X,Y are said to be adjacent (in the Token Sliding (TS) model) if there exist two vertices x,y such that X-x= Y-y. A TS-sequence of independent sets is a sequence of independent sets such that any pair of consecutive independent sets in the sequence are TS-adjacent.

In 2005, Hearn and Demaine showed that it is PSPACE-complete to determine, given two k-independent sets X,Y of G if there exists a TS-sequence between X and Y. This result had important consequences and opened a new direction of research. Since then, numerous results have been obtained. We will overview some of the most relevant results in this field and mention some possible future research directions.

(Based on joint works with Valent Bartier, Marthe Bonamy, Clément Dallard, Kyle Lomer, Amer Mouawad, Moritz Mühlenthaler)

Vendredi 9 octobre à 14h - Alexandre Blanché

Vendredi 16 octobre à 14h - Lionel Eyraud-Dubois

Vendredi 27 novembre à 14h - Noga Alon

GT virtuels passés

Vendredi 25 septembre à 14h - Jonathan Narboni
On Vizing's edge coloring question

In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.

Vendredi 18 septembre à 14h - Rose McCarty
Colouring visibility graphs

We discuss recent chi-boundedness results on visibility graphs. The visibility graph of a finite set of points S on a Jordan curve J has vertex set S, and two points in S are adjacent if the (open) segment between them is contained in the interior of J. We prove that such a graph with clique number w has chromatic number at most 3*4^{w-1}, and that w can be computed in polynomial time. Moreover, these results hold in the pseudo-visibility setting. While we focus on colouring, the talk will also serve as an introduction to visibility graphs.

This is joint work with James Davies, Tomasz Krawczyk, and Bartosz Walczak.

GT AlgoDist
Lundi 14 septembre à 14h - Jason Schoeters
Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
Connexion: and room 178 (hybrid)

We study a new version of the Euclidean TSP called VectorTSP (VTSP for short) where a mobile entity is allowed to move according to a set of physical constraints inspired from the pen-and-pencil game Racetrack (also known as Vector Racer). The spirit of this model is that no speed limitations apply and inertia depends on the current velocity. As such, this model is closer to typical models considered in path planning problems, although applied here to the visit of n cities in a non-predetermined order. In this work, we motivate and introduce VectorTSP and discuss some fundamental differences between this problem and other versions of TSP. This is joint work with Arnaud Casteigts and Mathieu Raffinot.

Vendredi 11 septembre à 14h - Irena Penev
Coloring certain even-hole-free graphs

Abstract here

Lundi 7 septembre à 10h45 - Arnaud Casteigts
Efficient generation of simple temporal graphs up to isomorphism

In this work, we consider a particular kind of isomorphism between temporal graphs, where two graphs are isomorphic if and only if they have the same reachability (set of temporal paths) up to time distortion. The underlying motivation is to capture infinite sets of temporal graphs by finitely many representatives, on which conjectures can be tested in a comprehensive manner. In this talk, I will focus on the case of "simple temporal graphs", where the edges have exactly one presence time and times are different for adjacent edges. The automorphisms of these graphs have special features which allow one to generate canonical representatives efficiently. The talk will be structured as a gentle discussion covering several topics, from symmetry, to spanners, to generation trees, and a few conjectures.

Vendredi 24 juillet à 15h - Daniel Cranston
Vertex Partitions into an Independent Set and a Forest with Each Component Small

For each integer k >= 2, we determine a sharp bound on mad(G) such that V(G) can be partitioned into sets I and Fk, where I is an independent set and G[Fk] is a forest in which each component has at most k vertices. For each k we construct an infinite family of examples showing our result is best possible. Hendrey, Norin, and Wood asked for the largest function g(a,b) such that if mad(G)<g(a,b) then V(G) has a partition into sets A and B such that mad(G[A])<a and mad(G[B])<b. They specifically asked for the value of g(1,b), which corresponds to the case that A is an independent set. Previously, the only values known were g(1,4/3) and g(1,2). We find the value of g(1,b) whenever 4/3<b<2. This is joint work with Matthew Yancey.

Vendredi 17 juillet à 14h - Martin Milanič
Treewidth versus clique number in graph classes with a forbidden structure

Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes in which this condition is also sufficient, which we call (treewidth, omega)-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and k-coloring problems.

We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs H for which the class of graphs excluding H is (treewidth, omega)-bounded. Our results imply that the class of 1-perfectly orientable graphs is (treewidth, omega)-bounded, answering a question of Brešar, Hartinger, Kos, and Milanič from 2018. We also reveal some further algorithmic implications of (treewidth,omega)-boundedness related to list k-coloring and clique problems.

This is joint work with Clément Dallard and Kenny Štorgel.

Vendredi 10 juillet à 14h - Claire Hilaire
Graph minor and graph drawing
Connexion: (en français, et aussi en salle 178 !)

Lundi 6 juillet à 10h45 - Henri Derycke
Une restriction pour un polynôme de Tutte sur la grille infinie

Dans le cas des graphes finis, le polynôme de Tutte est un invariant bivarié se spécialisant en plusieurs autres invariants de graphe comme le polynôme chromatique. Il peut se définir par une somme sur les arbres couvrants du graphe pondérée par deux statistiques : les activités interne et externe au sens de Tutte du graphe. En s'intéressant à des arbres couvrants dont la racine serait placée à l'infini dans une direction, je propose dans cet exposé un analogue (sommable) de cette définition sur le graphe infini $Z^2$: la série génératrice pour une période donnée des forêts couvrantes périodiques selon cette période, d'une généralisation des activités des arêtes du domaine fondamental. Les marginales du polynôme ont alors le bon goût d'être égales et invariantes au changement de direction des racines bien que leur loi jointe en dépende. Ce travail est notamment motivé par l'étude de configurations bipériodiques récurrentes dans le modèle du tas de sable sur la grille $Z^2$ qui sont en bijection avec ces forêts périodiques. Il s'agit d'un travail en commun avec Yvan Le Borgne.

Vendredi 3 juillet à 14h - Torsten Ueckerdt
Page Numbers: Old and New

A book embedding of a graph is a total order of its vertices and a partition of its edges into so-called pages with the property that no two edges in the same page have their endpoints alternating along the vertex ordering. The minimum number of pages needed for a graph G is the page number of G. After being open for more than 30 years, most recently the first planar graphs with page number strictly more than 3 have been found. Also recently, local page number variants have been proposed and studied.

In this talk, we will introduce page numbers, discuss a few classical results and explain the ideas behind the construction of planar graphs with page number 4. We will also introduce the local page number, summarize the state of the art, and present open problems.

This is based on joint work with M. Bekos, S. Felsner, M. Kaufmann, F. Klute, L. Merker, S. Pupyrev, C. Raftopoulou, and P. Valtr.

mardi 30 juin à 14h - Helmut Seidl
When Is a Bottom-up Deterministic Tree Transducer Top-down Deterministic?

We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable whether the translation of a transducer with look-ahead can be realized by a transducer from the same class without look-ahead. The transducers constructed in this way, may still make use of inspection, i.e., have an additional top-down deterministic tree automaton restricting the domain. We provide a second procedure which decides whether inspection can be removed and if so, constructs an equivalent transducer without inspection. The construction relies on a precise abstract interpretation of inspection requirements and a dedicated earliest-normal form for linear as well as uniform-copying transducers which can be constructed in polynomial time. As a consequence, equivalence of these transducers can be decided in polynomial time. Applying these results to deterministic bottom-up transducers, we obtain that it is decidable whether or not their translations can be realized by deterministic uniform-copying top-down transducers without look-ahead (but with inspection) - or without both look-ahead and inspection.

Vendredi 26 juin à 14h - Tom Kelly
Rainbow Hamilton paths in random 1-factorizations of Kn

A subgraph of an edge-colored graph is rainbow if every edge has a distinct color. Andersen's Conjecture states that every properly edge-colored complete graph on n vertices has a rainbow path of length n-2. We prove that as n approaches infinity, all but a vanishing proportion of 1-factorizations of Kn have a rainbow Hamilton path, which answers a recent question of Ferber, Jain, and Sudakov and implies that Andersen's Conjecture holds for almost all 1-factorizations. Joint work with Stephen Gould, Daniela Kühn, and Deryk Osthus.

GT AlgoDist/G&O
Lundi 22 juin à 14h - Mathilde Vernet
Dynamic graphs and connectivity

Connectivity in graphs is a well known issue, relevant to many applications. In the classical static context, it might seem simple even though some related problems are NP-complete. But in dynamic graphs, sometimes, even the simplest questions are far from trivial. What is the equivalent of a connected component in a dynamic graph ? How to identify those components ? In addition to connectivity itself, we can look at related problems. How to extend the definition of the Steiner problem in dynamic graphs ? This talk, based on my PhD thesis with Eric Sanlaville and Yoann Pigné, will consider those questions.

Lundi 22 juin à 10h45 - Thomas Fernique
Pavages par coupe et projection définis par des motifs

La méthode de coupe et projection permet d'obtenir de jolis pavages en discrétisant des sous-espaces affines. Par exemple, les mots strumiens peuvent s'obtenir en discrétisant une droite du plan. Les pavages de Penrose peuvent s'obtenir en discrétisant un plan dans l'espace à 5 dimensions. On se pose ensuite la question (motivée par l'étude des quasicristaux en physique) : quand est-ce qu'un pavage obtenu ainsi peut être caractérisé uniquement par ses motifs finis ? En d'autres termes : quand peut-on décrire uniquement localement la structure globale du pavage ? L'exposé sera a priori plutôt introductif, avec un survol des résultats obtenus ces dernières années en collaboration avec Nicolas Bédaride.

mardi 23 juin à 14h - Elena Gutiérrez
A Congruence-based Perspective on Automata Minimization Algorithms

Getting the deterministic finite-state automaton with the least possible number of states is an essential question in many applications such as text processing, image analysis and program verification and synthesis. Most of the minimization methods that have been proposed in the literature rely on building a partition of the set of states of the input automaton to obtain the minimal deterministic automaton. This is the case of Hopcroft's and Moore's algorithm. Another independent method is the classical textbook procedure proposed by Brzozowski. This algorithm simply combines a determinization (D) and reverse (R) operation twice applied to the input automaton N, i.e., D○R○D○R(N), to obtain the minimal automaton. Despite having an exponential worst-case complexity, its simplicity has recently motivated the study of this method and its connection with the partition-based methods, with the goal of providing more efficient versions of it. In this talk, I will address this study from a language-theoretical perspective. I will use equivalence relations on words to give a new and simple proof of correctness of the double-reversal method and shed light on the connection between this method and Moore's algorithm, a partition-based method.

GT AlgoDist/G&O
Lundi 15 juin à 14h - Louis Esperet
Distributed graph coloring

Graph coloring is a fundamental problem in distributed computing. Most of the work in the area focuses on the complexity of the algorithms, without too much concern of the number of colors used. In this talk I'll discuss the problem of obtaining distributed algorithms that are efficient and can color graphs optimally (or close to optimally). The algorithms combine ideas from structural graph theory and distributed computing.

Based on joint work with P. Alboulker, E. Bamas, M. Bonamy, and N. Bousquet.

Lundi 8 juin à 9h20 au Jeudi 11 juin à 18h - IWOCA
Connexion: (before June 3rd)

JCRAALMA on Product Structure Theorems
Monday 25th
10:30-12:00 A general introduction, by Gwenael Joret (including applications to queue number), based on and
14:00-14:45 the non-repetitive coloring consequences, by Louis Esperet, based on

Wednesday 27th
11:00-12:00 p-centered colouring, by Felix Schröder, based on
14:00-14:30 Subgraph isomorphism, by Édouard Bonnet, based on

Friday 29th
13:30-14:30 Extensions to other graph classes (k-planar, bounded degree graphs in minor-closed classes, etc), by Daniel Gonçalves, based on and
14:45-15:45 Consequences for adjacency labelling schemes, by Cyril Gavoille, based on and

Vendredi 5 juin à 14h - Paul Seymour
Pure pairs of vertex-subsets

A ``pure pair'' in a graph G is a pair (X,Y) of disjoint subsets of V(G) such that either every vertex in X is adjacent to every vertex in Y, or there are no edges from X to Y. Let f(G) be the biggest k such that G has a pure pair (X,Y) with |X|,|Y| at least k. In general, f(G) is logarithmic in |G|, and for any fixed graph H, if G does not contain H as an induced subgraph then f(G) is polynomial in |G|. (This is a result of Erdos, Hajnal and Pach.) But when is f(G) linear in |G|? This is connected with the Erdos-Hajnal conjecture and the Gyarfas-Sumner conjecture.

A couple of years ago, we proved a nice thing, a conjecture of Liebenau and Pilipczuk: for any finite set C of graphs, f(G) is linear in |G| for all graphs with no induced subgraph in C, if and only if C contains a forest and the complement of a forest. This result has since grown a number of extensions and variations. (What about bipartite graphs? What about ordered graphs? What about nearly-linear? What if the two sets have different sizes?). We give a tour.

Joint work with Maria Chudnovsky, Jacob Fox, Alex Scott and Sophie Spirkl.

vendredi 22 mai à 14h - Yelena Yuditsky
The epsilon-t-Net Problem

We study a natural generalization of the classical epsilon-net problem (Haussler--Welzl 1987), which we call the epsilon-t-net problem: Given a hypergraph on n vertices and parameters t and epsilon>= t/n, find a minimum-sized family S of t-element subsets of vertices such that each hyperedge of size at least epsilon n contains a set in S. When t=1, this corresponds to the epsilon-net problem.

We prove that any sufficiently large hypergraph with VC-dimension d admits an epsilon-t-net of size O(((1+\log t)d)/(\epsilon)*\log 1/epsilon). We also present an explicit construction of epsilon-t-nets (including \epsilon-nets) for hypergraphs with bounded VC-dimension.

This is a joint work with Noga Alon, Bruno Jartoux, Chaya Keller and Shakhar Smorodinsky.

mardi 19 mai à 14h - Antoine Amarilli
Query evaluation on probabilistic data: a story of dichotomies

Query evaluation is the problem of checking if some input data satisfies a fixed query, and probabilistic query evaluation (PQE) is its extension to probabilistic data, where we must compute the probability that the query is true. Specifically, we study this problem on tuple-independent databases of arity 2, aka probabilistic graphs: the graph has edges labeled with probabilities denoting how likely it is that the edge exists, independently from other edges. The PQE problem for a query Q, called PQE(Q) is to then take an input probabilistic graph of this kind, and compute the exact probability that a random possible world of this graph satisfies Q. We study this problem in data complexity, i.e., its complexity is measured as a function of the graph, when Q is fixed.

The talk will present several dichotomies around the PQE problem. The first one is by Dalvi and Suciu [JACM'12] and applies to unions of conjunctive queries. They showed that for any such query Q, either PQE(Q) is in PTIME or it is #P-hard. I will present our recent extension of this dichotomy with İsmail İlkan Ceylan [ICDT'20], for the larger query class of homomorphism-closed queries: for any such query Q, either PQE(Q) is in PTIME or it is #P-hard. Actually, the main result is that PQE(Q) is #P-hard for any homomorphism-closed query which is not a UCQ. I will also present our dichotomy with Pierre Bourhis and Pierre Senellart [ICALP'15, PODS'16] on restricting instance classes. We show that PQE(Q) is in PTIME, for the larger class of MSO queries, when the input probabilistic graphs are required to be trees or have bounded-treewidth. Conversely, PQE is intractable on unbounded-treewidth graphs under some technical assumptions. Last, I will present our ongoing work with Benny Kimelfeld, showing that the PQE dichotomy on self-join-free conjunctive queries also applies to unweighted PQE, i.e., when all probabilities of the graph are 1/2.

vendredi 15 mai à 14h - Guillem Perarnau
On the directed configuration model

Given a directed degree sequence D=((d_1^-,d_1^+), ..., (d_n^-,d_n^+)), the Directed Configuration Model (DCM) is a random n-vertex (multi)digraph with degree sequence D. We will give precise results on the size of the largest strongly connected component in terms of D, both in the sub- and super-critical regime. We will also show that the diameter of the DCM rescaled by log{n} converges in probability to an explicit constant. The contribution to this constant is a linear combination of the typical distance in DCM and extremal distances attained by vertices with atypically thin in- or out- neighbourhoods. In sharp contrast to the undirected case, it provides examples of random walks on random environments whose stationary distribution attains arbitrarily small polynomial values. All these results hold under convergence of the in- and out-degree of a uniform random vertex in distribution, first and second moment and apply to many other random directed graphs. This is joint work with Xing Shi Cai (Uppsala University).

lundi 11 mai à 15h - Kitty Meeks
From Decision to Approximate Counting

Decision problems – those in which the goal is to return an answer of “YES" or “NO" – are at the heart of the theory of computational complexity, and remain the most studied problems in the theoretical algorithms community. However, in many real-world applications it is not enough just to decide whether the problem under consideration admits a solution: we often want to find all solutions, or at least count (either exactly or approximately) their total number. It is clear that finding or counting all solutions is at least as computationally difficult as deciding whether there exists a single solution, and indeed in many cases it is strictly harder even to count approximately the number of solutions than it is to decide whether there exists at least one (assuming P is not equal NP).

In this talk I will discuss a restricted family of problems, in which we are interested in solutions of a given size: for example, solutions could be copies of a specific k-vertex graph H in a large host graph G, or more generally k-vertex subgraphs of G that have some specified property (e.g. k-vertex subgraphs that are connected). In this setting, although exact counting is strictly harder than decision (assuming standard assumptions in parameterised complexity), the methods typically used to separate approximate counting from decision break down. Indeed, I will describe two randomised approaches that, subject to some additional assumptions, allow efficient decision algorithms for problems of this form to be transformed into efficient algorithms to find or count all solutions.

This includes joint work with John Lapinskas (Bristol) and Holger Dell (ITU Copenhagen).

mercredi 6 mai à 11h - Stéphan Thomassé
Twin-width: a cool new parameter

In 2014, Sylvain Guillemot and Daniel Marx proved that detecting a fixed permutation pattern S in a permutation P can be done in linear time f(S).|P|. When S is 12345, this amounts to detect a 5-terms increasing subsequence in P.They invented for this a completely new (decomposition method / dynamic programming) technique. The engine of their method is the Marcus-Tardos theorem: if an nxn 01-matrix has c.n entries then there is an f(c) partition of its columns C1,...,Cf(c) and rows R1,...,Rf(c), each Ci and Rj being consecutive subsets, such that every submatrix CixRj contains a 1 entry, where f goes to infinity.

Since their approach was reminiscent of tree-width they asked for an extension to other structures. We exactly follow their tracks and propose the notion of twin-width of a graph: this corresponds to the maximum degree of errors one can make, starting from G and iteratively contracting pairs of twins or near-twins.

For instance cographs are the graphs with twin width 0. Among bounded twin width classes, let us mention bounded rank-width classes (and thus bounded tree-width), minor closed classes, posets with bounded size antichains, strict classes of dimension two posets, strict classes of permutation graphs. Squares of planar graphs (adding edges when distance is at most 2) also have bounded twin-width. Much more generally, any first-order interpretation of a bounded twin-width graph has bounded twin width.

From the computational point of view, FO model checking is linear when we have the twin-decomposition. For instance deciding if G has diameter at most k, or domination number at most k, or an induced path of length k in a graph on n vertices can be done in time f(d,k)n time where d is the twin width of G if we have a decomposition.

There are at most c^n.n! labeled graphs on the vertex set 1,...,n in any class with bounded twin width and We conjecture that this characterize that a class has bounded twin width. This implies that cubic graphs have unbounded twin-width.

In this talk I will mostly focus on the structural point of view of graphs with bounded twin width. This is joint work with Edouard Bonnet, Eunjung Kim, Rémi Watrigant.

mardi 5 mai à 14h - Thibault Godin
Order problem for automaton semigroups The class of automaton (semi)groups--that is (semi)groups generated by functions defined using transducers--has been studied since the late 70's as many very interesting (semi)groups arise from it. From a computer scientist point of view it is also very nice because the underlying automaton structure allows to apply known tools, and for instance one can decide if an element represents the identity element using automaton minimization. In this talk, we focus on a the order problem, that is given an element g in the (semi)group, does there exist two distinct integers l,m such that g^l=g^m ? This problem was proven undecidable for general automaton (semi)groups by Gilibert, but Bondarenko, Bondarenko, Sidki and Zapata showed that, if one restricts the automaton, then the problem is decidable in the group case. We extend their result to the semigroup case, introducing several extensions of their work.

This is joint work with Laurent Bartholdi, Ines Klimann and Matthieu Picantin

lundi 27 avril à 14h20 - Paweł Rzążewski
The quest for optimality in geometric intersection graphs, part 2
Connexion: (14h20-15h05, 10min break, 15h15-16h) Part 1 was here:

Most classic NP-hard problems cannot be solved in subexponential time, assuming the Exponential-Time Hypothesis. However, such algorithms exist for some restricted classes of graphs. The aim of this tutorial is to survey some basic and more advanced techniques used to design subexponential algorithms for geometric intersection graphs. In the second part we discuss some more advanced topics, where we need to make our hands dirty and look at the geometry of instances. We will see some problems where a simple combination of branching and divide & conquer using a balanced separator is not sufficient. Furthermore, we will discuss geometric separators and show how to use them to obtain parameterized algorithms.

vendredi 24 avril à 14 h - Feri Kardos
Islands in planar graphs

Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.

This is a joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.

GT Info-Quantique Mercredi 22 Avril à 15h15 - Géraud Senizergues et Stéphane Dartois
Détails de connexion sur la page du GT:

Algorithme de Deutsch et de de Deutsch-Jozsa par Géraud Senizergues
Résumé du premier exposé:
Dans cet exposé, je présenterai l'algorithme de Deutsch-Jozsa selon le plan suivant:

  • Boolean functions vs unitary operators
  • Deutsch algorithm over boolean functions
  • Advocate devil's criticism
  • Quantum parallelism
  • Deutsch-Josza algorithm over boolean functions.

Equation de Schrödinger et évolution unitaire par Stéphane Dartois
Résumé du second exposé:
Dans cet exposé nous introduirons l'équation de Schrödinger comme l'équation d'évolution des états quantiques, nous verrons alors qu'elle implique une évolution unitaire, ce qui justifie le paradigme du calcul réversible en calcul quantique.

Chaque exposé durera 30 minutes.

vendredi 17 avril à 14 h - Meike Hatzel
Perfect Matching Width, Grids and Directed Cycles

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.

The talk will comprise a few results on perfect matching width. For the restricted case of bipartite graphs, we show that perfect matching width is equivalent to directed treewidth and thus, the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies Norine’s conjecture. This result has terrible bounds though, which have been improved, but it gives rise to a new directed width parameter: cyclewidth.

We show that the perfect matching width of every bipartite matching covered graph is within a factor of 2 of the perfect matching width of its braces. Moreover, we give characterisations for braces of perfect matching width. This allows us to identify braces of perfect matching width 1 in polynomial time and provides an algorithm to construct an optimal decomposition.

The parameter cyclewidth turned out to have rather nice properties and the last result mentioned on perfect matching width directly transfers to cyclewidth as well.

The presented results are joint work with Archontia Giannopoulou, Roman Rabinovich and Sebastian Wiederrecht.

GT Quantique

Mercredi 15 Avril à 15h15 - Stéphane Dartois
Petit survol de la mécanique quantique
Salon BBB : Le lien se trouve ici (accès login/passwd LaBRI, les extérieurs peuvent contacter par courriel Yvan Le Borgne ou un autre participant pour obtenir le lien (constant)) (enregistrement probable)
Résumé: Dans cet exposé du GT informatique quantique, je présenterai un petit survol de la mécanique quantique. Je discuterai quelques morceaux d'histoire, les tous premiers problèmes physiques bizarres qui ont mis sur la piste de la mécanique quantique. Je ferai ensuite un saut dans le temps pour discuter la fameuse "dualité onde-particule". J'énoncerai par la suite les principes de base de la mécanique quantique en termes plutôt simples. Puis si le temps le permet je décrirai la version analytique du problème d'Einstein-Podolski-Rosen et des inégalités de Bell. Cet exposé est le premier d'une petite série et sera le moins technique de la série. La technicité ira croissante au long de la présentation mais devrait rester très raisonnable, avec zéro équation pour la première moitié de l'exposé, et rien qui ne dépasse les toutes premières années de licence (il sera par contre nécessaire de prendre certains faits pour acquis).

vendredi 10 avril à 14 h - Natasha Morrison
Partitioning the vertices of a torus into isomorphic subgraphs
Connexion: (25min+5min questions)

Let H be an induced subgraph of the torus Ck^n. We discuss results concerning when the vertices or edges of Ck^n can be decomposed into induced copies of H. In particular, we disprove a conjecture of Gruslys, showing that when k is odd and not a prime power, then there exists H such that |V(H)| divides some power of k, but there is no n such that the vertices of Ck^n can be decomposed into copies of H. We also disprove a conjecture of Gruslys, Leader and Tan on edge decomposing Ck^n. Joint work with Marthe Bonamy and Alex Scott.

vendredi 10 avril à 14 h30 - Natasha Morrison
Invertibility of Random Symmetric Matrices
Connexion: (25min+5min questions)

A well-known conjecture states that a random symmetric n*n matrix with entries in {-1,1} is singular with probability of order (n^2)/(2^n). In this talk I will describe some recent work where we prove that the probability of this event is at most 1/exp(Omega(n^1/2)). This improves the previous best known bound of 1/exp(Omega(n^1/4*(log n)^1/2)), which was obtained by Ferber and Jain. Our main theorem is an inverse Littlewood-Offord theorem in Zp^n, which is inspired by the method of hypergraph containers. This is joint work with Marcelo Campos, Leticia Mattos and Rob Morris.

GT Quantique
Mercredi 8 Avril à 15h15 - Yvan Le Borgne
Circuits logiques classiques, reversibles et quantiques
Connexion : Lien BBB sur ChapiChapo (login/password LaBRI), les extérieurs peuvent contacter par courriel Yvan Le Borgne ou un autre participant pour obtenir le lien (constant) (Enregistrement du GT disponible dans cette salle)
Résumé : Après le survol du premier exposé, nous reprenons plus précisément la description des différents types de circuits logiques. Pour plusieurs types, nous présentons explicitement des ensembles universels de quelques de portes. Ils sont dits universels car ces portes, combinées dans des circuits, permettent d'implémenter toutes les fonctions étudiées. C'est l'occasion d'introduire progressivement une notation matricielle pour la description du calcul. À l'occasion nous effleurerons la notion de code correcteur (surtout classique et par répétition) et d'une expérience d'interférence (Mach-Zehnder) distinguant les phénomènes quantiques des probabilités. à venir

mardi 7 avril à 14 h - Pierre Ohlmann
Controlling a random population
Connexion : (the link will be activated starting from 1:30)
Résumé : Bertrand et al. (2017) introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is decidable and EXPTIME-complete in the adversarial setting, and posed as an open problem the stochastic setting, where the agent is represented by a Markov decision process. In this paper, we show that the stochastic control problem is decidable. Our solution makes significant uses of well quasi orders, of the max-flow min- cut theorem, and of the theory of regular cost functions.

GT AlgoDist/G&O
lundi 6 avril 14h - Hendrik Molter (TU, Berlin)
Computing Maximum Matchings in Temporal Graphs
Connexion : Big Blue Button (
Résumé : Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e, t) such that no vertex is matched more than once within any time window of ∆ consecutive time slots, where ∆ ∈ N is given. The requirement that a vertex cannot be matched twice in any ∆-window models some necessary “recovery” period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.
(Joint work with George B. Mertzios, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche.)

La vidéo de l'exposé est disponible sur le serveur Mediapod de l'Université :

lundi 6 avril 10h45 - Eric Fusy (LIX)
Intervalles de Tamari généralisés et cartes planaires orientées
Connexion : zoom (
Résumé : La combinatoire des intervalles de Tamari, initiée par Chapoton, est une domaine très actif depuis une dizaine d'années, avec de riches propriétés énumératives. En particulier une construction due à Bernardi et Bonichon (s'appuyant sur les bois de Schnyder) établit une bijection entre intervalles de Tamari de taille n et triangulations à n sommets internes. Le treillis de Tamari a été récemment étendu par Préville-Ratelle et Viennot aux treillis dits de nu-Tamari, et dans ce contexte on parle d'intervalles de Tamari généralisés. Fang et Préville-Ratelle ont montré que les intervalles généralisés sont en bijection avec les cartes planaires non-séparables, par une approche bijective à base d'arbres étiquetés de parcours en profondeur. Nous montrerons ici deux autres approches bijectives. La première s'appuie sur les décompositions séparantes de quadrangulations et est une extension de la bijection de Bernardi et Bonichon. La seconde spécialise la bijection de Bernardi et Bonichon aux intervalles de Tamari dits synchronisés, qui s'identifient aux intervalles généralisés. Travail en commun avec Abel Humbert.

vendredi 3 avril 14h - Paweł Rzążewski (U. Tech. Varsovie)
The quest for optimality in geometric intersection graphs, part 1
Connexion : Zoom ( ouvert dès 13h40
Résumé : Most classic NP-hard problems cannot be solved in subexponential time, assuming the Exponential-Time Hypothesis. However, such algorithms exist for some restricted classes of graphs. The aim of this tutorial is to survey some basic and more advanced techniques used to design subexponential algorithms for geometric intersection graphs. In the first part we focus on separator-based approaches.

mardi 31 mars 14h - Jérôme Leroux
Reachability in fixed dimension vector addition systems with states
Connexion : Big Blue Button, (actif à partir de 13h30)
Résumé : The reachability problem is a central decision problem for formal verification based on vector addition systems with states (VASS), which are equivalent to Petri nets and form one of the most studied and applied models of concurrency. Reachability for VASS is also inter-reducible with a plethora of problems from a number of areas of computer science. In spite of recent progress, the complexity of the reachability problem remains unsettled, and it is closely related to the lengths of shortest VASS runs that witness reachability. We consider VASS of fixed dimension, and obtain three main results. For the first two, we assume that the integers in the input are given in unary, and that the control graph of the given VASS is flat (i.e., without nested cycles). We obtain a family of VASS in dimension 3 whose shortest reachability witnessing runs are exponential, and we show that the reachability problem is NP-hard in dimension 7. These results resolve negatively questions that had been posed by the works of Blondin et al. in LICS 2015 and Englert et al. in LICS 2016, and contribute a first construction that distinguishes 3-dimensional flat VASS from 2-dimensional VASS. Our third result, by means of a novel family of products of integer fractions, shows that 4-dimensional VASS can have doubly exponentially long shortest reachability witnessing runs. The smallest dimension for which this was previously known is 14.
Joint work with Wojciech Czerwiński, Sławomir Lasota, Ranko Lazić, Filip Mazowiecki. Paper available at

GT AlgoDist
lundi 30 mars 14h - Nancy Lynch (vidéo synchro.)
An Algorithmic Theory of Brain Networks
Connexion : Zoom (actif à partir de 13h40)
Résumé : This talk will describe my recent work with Cameron Musco and Merav Parter, on studying neural networks from the perspective of the field of Distributed Algorithms. In our project, we aim both to obtain interesting, elegant theoretical results, and also to draw relevant biological conclusions.

GT Graphes&Optimisation
Vendredi 27 mars 14h - Marthe Bonamy
Complexité algorithmique de la coloration de graphes
Connexion : Zoom ( activé à partir de 13h30, ~30min d'exposé.

Français / English



Membres / Visiteurs