GT virtuels du LaBRI à venir

GT G&O
Vendredi 9 Avril à 14h - Sang-Il Oum
A unified half-integral Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. Such a duality does not hold if we restrict to odd cycles. However, in 1999, Reed proved an analogue for odd cycles by relaxing packing to half-integral packing. We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then there is a duality between the maximum size of a half-integral packing of cycles whose values avoid a fixed finite set for each abelian group and the minimum size of a vertex set hitting all such cycles.

A multitude of natural properties of cycles can be encoded in this setting, for example cycles of length at least ℓ, cycles of length p modulo q, cycles intersecting a prescribed set of vertices at least t times, and cycles contained in given ℤ2-homology classes in a graph embedded on a fixed surface. Our main result allows us to prove a duality theorem for cycles satisfying a fixed set of finitely many such properties.

Joint work with J. Pascal Gollin, Kevin Hendrey, Ken-ichi Kawarabayashi, and O-joung Kwon.

GT G&O
Vendredi 26 Mars à 14h - Nacim Oijid
Complete coloring of signed graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Graph coloring is one of the most famous problems in Graph Theory. It has been declined into many problems by adding constraints. One of them is the notion of achromatic number, which is defined as the largest number of colors we can use to color a graph in such a way that each pair of colors appears on at least one edge. This notion of achromatic number has already led to many results on undirected graphs.

During this talk, I will present results on the achromatic number of signed graphs, obtained in collaboration with Julien Bensmail, François Dross and Eric Sopena during a three-month internship. We will see how classical operations on a signed graph can modify the achromatic number and what the complexity of computing this parameter is.

GT G&O
Vendredi 19 Mars à 14h - Gunnar Brinkmann
A survey of isomorphism rejection in structure generation programs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

If you want to exhaustively enumerate a certain class of graphs, you have to solve two problems:

a.) how to construct all elements in the class

b.) how to avoid isomorphic copies

The first problem is often the more interesting and more challenging one. Unfortunately the solutions are often very much focused on the specific problem.

For b.) there are some standard techniques that can be applied to obtain efficient algorithms and programs. The topic of this talk will be to show some of these techniques.

First some examples of applications of structure enumeration will be presented. After that some techniques -- to be exact: orderly generation, the canonical construction path method, and the homomorphism principle-- will be demonstrated at examples. The methods will be explained in an informal and -- hopefully -- easily understandable way, so that also students should be able to follow the talk.

GT G&O
Vendredi 12 Mars à 14h - Gwenaël Joret
Approximating pathwidth for graphs of small treewidth
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In this talk I will describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t\sqrt{\log t}). This is the first algorithm to achieve an f(t)-approximation for some function f.

Our approach builds on the following key insight: every graph with large pathwidth has large treewidth or contains a subdivision of a large complete binary tree. Specifically, we show that every graph with pathwidth at least th+2 has treewidth at least t or contains a subdivision of a complete binary tree of height h+1. The bound th+2 is best possible up to a multiplicative constant. This result was motivated by, and implies (with c=2), the following conjecture of Kawarabayashi and Rossman (SODA'18): there exists a universal constant c such that every graph with pathwidth \Omega(k^c) has treewidth at least k or contains a subdivision of a complete binary tree of height k.

Joint work with Carla Groenland, Wojciech Nadara, and Bartosz Walczak.

GT G&O
Vendredi 5 Mars à 14h - Piotr Micek
Dimension, height, and large standard examples in planar posets
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

This will be an introductory presentation to poset's dimension. Already Dilworth has proved that for a poset to have large dimension, the poset must be wide. It does not have to be tall though. Indeed, so-called standard examples have height 2 and unbounded dimension. A remarkable feature of planar posets is that if they have large dimension then they are also tall. In other words, we can bound dimension of planar posets from above by a function of the height. Starting from the basics, we will go through a complete proof that the dimension of posets with outerplanar cover graphs is at most 4. We will discuss how to bound the dimension of a poset in terms of the (3h)-th weak coloring number of its cover graph. This implies bounds for the planar case and far beyond. We will discuss the current state-of-art and point the key open problems in the area.

GT G&O
Vendredi 26 Février à 14h - Vida Dujmovic
Stack-Number is not bounded by Queue-Number
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Heath, Leighton and Rosenberg (1992) and Blankenship and Oporowski (1999) asked the following about the two graph parameters: 1) Is stack-number bounded by queue-number? 2) Is queue-number bounded by stack-number?

We answer the first question in the negative. More specifically, we describe an infinite family of graphs all having queue number at most 4 but having unbounded stack number. The proof of this result uses only basic combinatorics (the Pigeonhole Principle and the Erdös-Szekeres Theorem) and the well-known Hex Lemma.

This is joint work with David Eppstein, Robert Hickingbotham, Pat Morin and David R. Wood.

GT G&O
Vendredi 19 Février à 14h - Édouard Bonnet
Twin-width and ordered binary structures
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y. Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows. Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n!. Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded. Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same. In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.

GT G&O
Vendredi 22 Janvier à 14h - Marthe Bonamy
Towards polynomial Chi-boundedness of graphs with no long path
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

There are graphs of arbitrarily high chromatic number which contain no triangle and in fact no short cycle. However, in some graph classes with enough structure, we can show that the chromatic number of the graphs is bounded by some function of their largest clique -- in other words, that class is chi-bounded. One of the first such results was by Gyarfas in 1987: for any t, the class of Pt-free graphs is chi-bounded. The corresponding function is unfortunately exponential, and it remains a major open problem whether we can replace it with a polynomial. Here, we consider a relaxation of this problem, where we compare the chromatic number with the size of the largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that every Pt-free graph which does not contain Kp,p as a subgraph is p^c-colourable.

This is joint work with Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé and Bartosz Walczak

GT G&O
Vendredi 15 Janvier à 15h - Paul Seymour
The Erdos-Hajnal conjecture is true for excluding a five-cycle
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In an n-vertex graph, there must be a clique or stable set of size at least Clog n, and there are graphs where this bound is attained. But if we look at graphs not containing a fixed graph H as an induced subgraph, the largest clique or stable set is bigger.

Erdos and Hajnal conjectured in 1977 that for every graph H, there exists c>0 such that every H-free graph has a clique or stable set of size at least |G|^c (``H-free'' means not containing H as an induced subgraph, and |G| means the number of vertices of G). This is still open, even for some five-vertex graphs H; and the case that has attracted most attention is when H is a cycle of length five.

It is true in that case. I will give a sketch of the proof, which is via applying a lemma about bipartite graphs, a variant of a theorem of I. Tomon.

This lemma has several other application to the Erdos-Hajnal conjecture. For instance, it implies that for every cycle C and forest T, there exists c>0 such that every graph that is both C-free and T'-free (where T' is the complement of T) has a clique or stable set of size |G|^c. (Until now this was open when C has length five and T is a 5-vertex path.)

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

GT G&O
Vendredi 8 Janvier à 14h - Bernard Lidický
11/4-colorability of subcubic triangle-free graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

We prove that every connected subcubic triangle-free graph except for two exceptional graphs on 14 vertices has fractional chromatic number at most 11/4.
This is a joint work with Zdenek Dvorak and Luke Postle.

GT AlgoDist
Lundi 23 novembre à 14h - Cyril Gavoille
Adjacency Labelling for Planar Graphs (and Beyond)
Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an $n$-vertex planar graph $G$ is assigned a $(1+o(1))\log_2 n$-bit label and the labels of two vertices $u$ and $v$ are sufficient to determine if $uv$ is an edge of $G$. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer $n$, there exists a graph $U_n$ with $n^{1+o(1)}$ vertices such that every $n$-vertex planar graph is an induced subgraph of $U_n$. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and $k$-planar graphs. This work will appear at FOCS'20 and is joint with Vida Dujmović, Louis Esperet, Gwenaël Joret and Pat Morin.

GT G&O
Vendredi 27 novembre à 14h - Noga Alon
Unitary Signings and Induced subgraphs of Cayley graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Let G be a Cayley graph of the elementary abelian 2-group Z_2^n with respect to a set S of size d. In joint work with Kai Zheng we show that for any such G,S and d, the maximum degree of any induced subgraph of G on any set of more than half the vertices is at least \sqrt d. This is deduced from the recent beautiful result of Huang who proved the above for the n-hypercube Q^n, in which the set of generators S is the set of all vectors of Hamming weight 1, establishing the sensitivity conjecture of Nisan and Szegedy. Motivated by his method we define and study unitary signings of adjacency matrices of graphs, and compare them to the orthogonal signings of Huang. Subsequent work regarding more general Cayley graphs will be mentioned as well.

GT AlgoDist
Lundi 30 novembre à 14h - Colette Johnen (LaBRI)
Élection Autostabilisante dans les Réseaux à Haute Dynamicité
Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp et salle 178 (hybride)

Nous nous intéressons à la conception d'algorithmes autostabilisants pour des réseaux identifiés hautement dynamiques. Précisément, nous considérons le problème de l'élection dans trois classes de graphes dynamiques (TVG) : la classe TCB(∆) les TVG de diamètre temporel borné par ∆, la classe TCQ(∆) les TVG de diamètre temporel quasiment borné par ∆ et la classe TCR des TVG à connectivité temporelle récurrente. Nous montrons qu'en dépit des identités, dans les classes TCQ(∆) et TCR, tout algorithme autostabilisant d'élection nécessite la connaissance exacte du nombre de processus. Puis nous proposons trois algorithmes d'élection. Le premier, pour la classe TCB(∆), stabilise en au plus 3∆ rondes. Dans TCQ(∆) et TCR, le temps de stabilisation d'un algorithme autostabilisant d'élection ne peut pas être borné. Cependant, nous montrons que nos deux solutions sont spéculatives, c'est-à-dire qu'elles ont de bonnes performances dans des cas favorables ; en effet, elles stabilisent en O(∆) rondes lorsque l'on se restreint à la classe TCB(∆).

Travail commun avec Karine Altisen, Stéphane Devismes, Anaïs Durand, et Franck Petit.

GT G&O
Vendredi 4 décembre à 14h - Louis Esperet
Universal graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

A graph G is universal for some class F if it contains all the graphs of F as induced subgraph. The objective is to minimize the number of vertices of G. In this talk I will explain how to construct universal graphs for any given hereditary class of dense graphs, with a nearly optimal number of vertices. I will also explain several applications of our result: how to obtain nearly optimal universal posets (posets that contain all n-element posets), and how to encode reachability in digraphs in a nearly optimal way.

This is joint work with Marthe Bonamy, Carla Groenland, and Alex Scott

GT G&O
Vendredi 11 décembre à 14h - Dimitri Lajou
Cartesian product of signed graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

In this talk we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018).
We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form $P_n \ssquare P_m$, of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

GT virtuels passés

GT G&O
Vendredi 20 novembre à 14h - Bojan Mohar
On the genus of dense graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

The motivation for this talk is to find efficient methods for approximating the genus of graphs. In the setup of graph limits, any large dense graph can be approximated by a quasirandom graph based on a small weighted graph. The normalized version of the genus is a continuous function in this setup. From this top-down view of the problem, we are able to fins an EPTAS (efficient polynomial-time approximation scheme). The speaker will first provide a rough introduction and then will try to explain how various proof ingredients come together. The main results are joint work with Yifan Jing.

GT G&O
Mardi 10 novembre à 14h - Jan Volec
TBA
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

GT G&O
Vendredi 6 novembre à 14h - Boram Park
The strong cliques in graphs with forbidden cycles
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Given a graph G, the strong clique number of G, denoted SC(G), is the maximum size of a set S of edges such that every pair of edges in S has distance at most 2 in the line graph of G. As a relaxation of the renowned Erdős-Nešetřil conjecture regarding the strong chromatic index, Faudree et al. suggested investigating the strong clique number, and conjectured a quadratic upper bound in terms of the maximum degree. In this talk, we show that a {C_5, C_2k}-free graph G with Delta(G)>= 1 satisfies SC(G) <= k Delta(G)-(k-1), when either k>= 4 or k\in {2,3} and G is also C_3-free. This improves some results of Cames van Batenburg, Kang, and Pirot (2019). It is joint work with Eun-Kyung Cho, Ilkyoo Choi, Ringi Kim.

GT AlgoDist
Lundi 2 novembre à 14h - Emmanuel Godard (LIS, Marseille)
Back to the Coordinated Attack Problem
Connexion: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp et salle 178 (hybride)

We consider the well known Coordinated Attack Problem, where two generals have to decide on a common attack, when their messengers can be captured by the enemy. Informally, this problem represents the difficulties to agree in the present of communication faults. We consider here only omission faults (loss of message), but contrary to previous studies, we do not to restrict the way messages can be lost, i.e. we make no specific assumption, we use no specific failure metric. In the large subclass of message adversaries where the double simulta- neous omission can never happen, we characterize which ones are obstructions for the Coordinated Attack Problem. We give two proofs of this result. One is combinatorial and uses the classical bivalency technique for the necessary condition. The second is topological and uses simplicial complexes to prove the necessary condition. We also present two different Consensus algorithms that are combinatorial (resp. topological) in essence. Finally, we analyze the two proofs and illustrate the relationship between the combinatorial approach and the topological approach in the very general case of message adversaries. We show that the topological characterization gives a clearer explanation of why some message adversaries are obstructions or not. This result is a convincing illustration of the power of topological tools for distributed computability.

GT G&O
Vendredi 23 octobre à 14h - Lionel Eyraud-Dubois
Scheduling Independent Tasks on GPUs with co-scheduling effects, or Partitioning Pseudo-forests into Caterpillars
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

While studying a scheduling problem on GPUs, we stumbled on a graph problem: how to partition a pseudo-forest into edge-disjoint caterpillars. With some help from very kind members of the Graphs & Optimisation group, we obtained an optimal polynomial-time algorithm for this problem. We present the connection between the scheduling and partitioning problems, how and why this optimal algorithm works, and discuss several other related problems.

GT CEA
Lundi 12 octobre - Vincent Delecroix
Les courbes simples en grand genre ne séparent pas
Résumé : Fixons une surface compacte S de genre g >= 2. On s'intéresse dans cette surface aux courbes fermées simples à homotopie près ou autrement dit aux plongements du cercle dans la surface sans auto-intersection. Il y a un nombre infini dénombrable de telles courbes. A chaque courbe on associe son type topologique: lorsqu'on la découpe, soit elle sépare la surface en deux sous-surfaces de genre g1 et g2 avec g1 + g2 = g soit elle est non-séparante. En particulier, il y a un nombre fini de types topologiques. Nous expliquerons comment donner sens à la notion de courbe aléatoire dans S et associer une fréquence d'apparition à chaque type topologique. J'expliquerai alors pourquoi lorsque le genre tend vers l'infini, le type topologique d'une courbe aléatoire est non-séparant.

Connexion : https://webconf.u-bordeaux.fr/b/nic-etz-jed

GT G&O
Vendredi 9 octobre à 14h - Alexandre Blanché
Gallai's path decomposition conjecture for planar graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed et salle 178 (hybride)

In 1968, Gallai conjectured that the edges of any connected graph on n vertices can be partitioned into at most (n+1)/2 egde-disjoint paths. This conjecture is still open to this day, but was proved on some graph classes such as graphs with at most one vertex of even degree (Lovász, 1968), graphs with maximum degree at most 5 (Bonamy et al., 2016) or graphs with treewidth at most 3 (Botler et al., 2017). We proved the conjecture on the class of planar graphs, i.e. graphs that can be drawn in the plane with no edges crossing. More precisely, we proved a stronger result: any connected planar graph on n vertices can be decomposed into at most n/2 paths, except K3 and K5 minus one edge.

(Based on joint works with Marthe Bonamy and Nicolas Bonichon)

GT G&O
Vendredi 2 octobre à 14h - Nicolas Bousquet
Independent Set Reconfiguration via Token Sliding
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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)

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: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp et salle 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.

GT G&O
Vendredi 25 septembre à 14h - Jonathan Narboni
On Vizing's edge coloring question
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT G&O
Vendredi 18 septembre à 14h - Rose McCarty
Colouring visibility graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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: https://webconf.u-bordeaux.fr/b/arn-4tr-7gp et salle 178 (hybride)

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.

GT G&O
Vendredi 11 septembre à 14h - Irena Penev
Coloring certain even-hole-free graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

Abstract here

GT CEA
Lundi 7 septembre à 10h45 - Arnaud Casteigts
Efficient generation of simple temporal graphs up to isomorphism
Connexion: https://webconf.u-bordeaux.fr/b/nic-etz-jed

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.

GT G&O
Vendredi 24 juillet à 15h - Daniel Cranston
Vertex Partitions into an Independent Set and a Forest with Each Component Small
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT G&O
Vendredi 17 juillet à 14h - Martin Milanič
Treewidth versus clique number in graph classes with a forbidden structure
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT G&O
Vendredi 10 juillet à 14h - Claire Hilaire
Graph minor and graph drawing
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed (en français, et aussi en salle 178 !)

GT CEA
Lundi 6 juillet à 10h45 - Henri Derycke
Une restriction pour un polynôme de Tutte sur la grille infinie
Connexion: https://webconf.u-bordeaux.fr/b/nic-etz-jed

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.

GT G&O
Vendredi 3 juillet à 14h - Torsten Ueckerdt
Page Numbers: Old and New
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT MF
mardi 30 juin à 14h - Helmut Seidl
When Is a Bottom-up Deterministic Tree Transducer Top-down Deterministic?
Connexion: https://webconf.u-bordeaux.fr/b/gui-vqr-ax9

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.

GT G&O
Vendredi 26 juin à 14h - Tom Kelly
Rainbow Hamilton paths in random 1-factorizations of Kn
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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
Connexion: https://webconf.u-bordeaux.fr/b/jas-t4f-9dx

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.

GT CEA
Lundi 22 juin à 10h45 - Thomas Fernique
Pavages par coupe et projection définis par des motifs
Connexion: https://webconf.u-bordeaux.fr/b/nic-etz-jed

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.

GT MF
mardi 23 juin à 14h - Elena Gutiérrez
A Congruence-based Perspective on Automata Minimization Algorithms
Connexion: https://webconf.u-bordeaux.fr/b/gui-vqr-ax9

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
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

IWOCA
Lundi 8 juin à 9h20 au Jeudi 11 juin à 18h - IWOCA
https://iwoca2020.labri.fr/program/
Connexion: https://iwoca2020.labri.fr/registration/ (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 https://arxiv.org/pdf/1807.03683.pdf and https://arxiv.org/pdf/1904.04791.pdf
14:00-14:45 the non-repetitive coloring consequences, by Louis Esperet, based on https://arxiv.org/pdf/1904.05269.pdf

Wednesday 27th
11:00-12:00 p-centered colouring, by Felix Schröder, based on https://arxiv.org/pdf/1907.04586.pdf
14:00-14:30 Subgraph isomorphism, by Édouard Bonnet, based on https://arxiv.org/pdf/1807.03683.pdf

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 https://arxiv.org/pdf/1907.05168.pdf and https://arxiv.org/pdf/2002.11721.pdf
14:45-15:45 Consequences for adjacency labelling schemes, by Cyril Gavoille, based on https://arxiv.org/abs/1908.03341 and https://arxiv.org/abs/2003.04280

GT G&O
Vendredi 5 juin à 14h - Paul Seymour
Pure pairs of vertex-subsets
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT G&O
vendredi 22 mai à 14h - Yelena Yuditsky
The epsilon-t-Net Problem
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT MF
mardi 19 mai à 14h - Antoine Amarilli
Query evaluation on probabilistic data: a story of dichotomies
Connexion: https://webconf.u-bordeaux.fr/b/gui-vqr-ax9

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.

GT G&O
vendredi 15 mai à 14h - Guillem Perarnau
On the directed configuration model
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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

GT G&O
lundi 11 mai à 15h - Kitty Meeks
From Decision to Approximate Counting
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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

GT G&O
mercredi 6 mai à 11h - Stéphan Thomassé
Twin-width: a cool new parameter
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed

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.

GT MF
mardi 5 mai à 14h - Thibault Godin
Order problem for automaton semigroups
https://webconf.u-bordeaux.fr/b/gui-vqr-ax9 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

GT G&O
lundi 27 avril à 14h20 - Paweł Rzążewski
The quest for optimality in geometric intersection graphs, part 2
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed (14h20-15h05, 10min break, 15h15-16h) Part 1 was here: https://www.youtube.com/watch?v=DwueCygLqvk

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.

GT G&O
vendredi 24 avril à 14 h - Feri Kardos
Islands in planar graphs
Connexion: https://webconf.u-bordeaux.fr/b/mar-ef4-zed
Vidéo: https://youtu.be/GCX4Su4qRxc

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: https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

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.

GT G&O
vendredi 17 avril à 14 h - Meike Hatzel
Perfect Matching Width, Grids and Directed Cycles
Connexion: http://chapichapo.fr/b/mar-u77-f96

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 https://www.labri.fr/perso/borgne/ChapiChapo (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).

GT G&O
vendredi 10 avril à 14 h - Natasha Morrison
Partitioning the vertices of a torus into isomorphic subgraphs
Connexion: http://chapichapo.fr/b/mar-u77-f96 (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.

GT G&O/CEA
vendredi 10 avril à 14 h30 - Natasha Morrison
Invertibility of Random Symmetric Matrices
Connexion: http://chapichapo.fr/b/mar-u77-f96 (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 https://www.labri.fr/perso/borgne/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

GT MF
mardi 7 avril à 14 h - Pierre Ohlmann
Controlling a random population
Connexion :https://chapichapo.fr/b/gui-xzq-ydk (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 (https://chapichapo.fr/b/arn-6nw-gf3)
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é : https://mediapod.u-bordeaux.fr/video/6559-computing-maximum-matchings-in-temporal-graphs/

GT CEA
lundi 6 avril 10h45 - Eric Fusy (LIX)
Intervalles de Tamari généralisés et cartes planaires orientées
Connexion : zoom (https://zoom.us/j/551762285)
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.

GT G&O
vendredi 3 avril 14h - Paweł Rzążewski (U. Tech. Varsovie)
The quest for optimality in geometric intersection graphs, part 1
Connexion : Zoom (https://zoom.us/j/850801149) 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.
Vidéo: https://www.youtube.com/watch?v=DwueCygLqvk&t=189s

GT MF
mardi 31 mars 14h - Jérôme Leroux
Reachability in fixed dimension vector addition systems with states
Connexion : Big Blue Button, https://chapichapo.fr/b/gui-xzq-ydk (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 https://arxiv.org/abs/2001.04327

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 (https://zoom.us/j/626248736) activé à partir de 13h30, ~30min d'exposé.

Département Combinatoire et Algorithmique

du LaBRI