Graphes@Lyon

Graphes@Lyon is the graph theory seminar jointly organized by the MC2 team at LIP and the GOAL team at LIRIS.

Local organizers: Nicolas Bousquet (LIRIS) and Rémi Watrigant (MC2). Contact us if you want to give a talk!

Upcoming talks

Linda Kleist (Univ. Hambourg) and Joseph Dorfer (TU Graz)
  • When: 01/10/26 at 14:00
  • Where: LIRIS
  • Who: Linda Kleist (Univ. Hambourg) and Joseph Dorfer (TU Graz)
  • What:

Joseph Dorfer 

Title: Flip distance between triangulations of a convex polygon.

Abstract:

Triangulations of a convex (n+2)-gon are famously counted by the n-th Catalan number, and so are binary trees on n internal nodes. Consequently, there exists a bijection between the triangulations of convex polygons and binary trees of the right sizes.
One way to transform one triangulation into another is via an edge flip, that is, an operation that replaces one diagonal in a convex quadrilateral with the other diagonal. To transform a binary tree into another, one can perform a rotation that exchanges an internal node with its parent node and reattaches the subtrees rooted at those two nodes. The standard bijection between triangulations of convex polygons and binary trees preserves incidence under these reconfiguration operations. If two triangulations only differ by a single edge flip, then their corresponding binary trees only differ in a single rotation.

The complexity of determining the minimum number of rotations that transform one binary tree into another (or the equivalent problem for triangulations) has been raised as an open problem by Culik and Wood in 1982. It was popularized through the study of extremal pairs of triangulations by Sleator, Tarjan, and Thurston in 1986.

We settle this open problem by proving that the flip distance problem for triangulations of convex polygons is NP-complete.

Linda Kleist 

Title: Online Packing and Online Sorting Problems

Abstract: Packing problems arise on a daily basis—organizing a kitchen drawer, baking cookies, cutting fabric, packing a suitcase, or loading a car. Similar problems appear in industrial settings such as shipping, the clothing industry, and logistics. In this talk, we study translational online packing problems, where items arrive one by one and must be placed irrevocably into a strip (or into bins, a square, or the plane).  The goal is to minimize resource usage, such as the strip width. 

While online algorithms with a constant competitive ratio have been known for rectangles for decades, the theoretical foundations for more complex objects are much less understood.  In joint work with Aamand, Abrahamsen, and Beretta [SODA 2023], we prove a lower bound of  \Omega(\sqrt{\log n/\log\log n}) on the competitive ratio of any online strip packing algorithm for convex polygons. Very recently, together with Aamand, Abrahamsen, Bartlmae, Khan, and Tóth, we present an O(\log^2 n)-competitive algorithm for online translational strip packing of convex polygons, improving upon the previous algorithm with competitive ratio O(n^.59). 

With Gerlach and Hennies [SoCG 2026], we study online packing of orthogonal polygons and show that the competitive ratio one any online algorithm that aims to orthogonal 6-gons into a minimal number of unit bins is in \Omega(n/\log n). Already for 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible. 

Interestingly, the insights are gained through three different online sorting problems. In this talk, we discuss these packing problems and their connections to natural online sorting problems.

TBA

  • When: 15/10/26 at 14:30
  • Where: LIRIS
  • What: TBA
  • Abstract: TBA

TBA

  • When: 12/11/26 at 14:30
  • Where: LIP
  • What: TBA
  • Abstract: TBA

TBA

  • When: 26/11/26 at 14:30
  • Where: LIRIS
  • What: TBA
  • Abstract: TBA

TBA

  • When: 10/12/26 at 14:30
  • Where: LIP
  • What: TBA
  • Abstract: TBA

Past talks

Eva Rotenberg (ITU Copenhagen, Denmark)

  • When: 29/06/26 at 10am
  • Where: TD5 (ground floor of the Nautibus building)
  • What: Whether a Graph Admits a Vertex that Lies in All Longest Paths is Θ2-Complete
  • Abstract:
    When a graph admits a vertex v that is contained in all its longest paths, we call v a Gallai vertex. These are named after Gallai, who in 1969 asked the question if it is true that every connected graph contains such a vertex. This was soon answered in the negative by Walther and Zamfirescu, who presented a graph in which every vertex is omitted by some longest path of the graph.

    Inspite of its long history, the Gallai Vertex Problem, i.e. determining whether a graph has a Gallai vertex, was until now not known to be neither NP- nor coNP-hard. In this work, we show something much stronger, as we completely settle the computational complexity of determining whether a graph has a Gallai vertex: We show that it is complete for the complexity class Θ_2^p = P^(NP[log n]).
    This class, also known as “parallel access to NP”, is a complexity class larger than NP situated just below the class Σ_2^p in Stockmeyer’s polynomial hierarchy.

    In more generality, the longest path transversal number of a connected graph is the minimum size of a set of vertices that intersects all its longest paths. I.e. if the graph has a Gallai vertex, its longest path transversal number is 1. Thus, as a consequence of our theorem, the longest path transversal number of a graph cannot be approximated in polynomial time by a factor better than 2, unless P=NP. In fact, using related techniques, we show a strengthening of this result: For any constant C, if there is a graph with longest path transversal number C, then there is no polynomial time algorithm for approximating the longest path transversal number by a factor better than C, unless P = NP. In particular, this excludes approximation by a factor below 3. Similar results hold for the longest cycle transversal.

Claire Hilaire (Université Clermont Auvergne)

  • When: 29/06/26 at 10:45am
  • Where: TD5 (ground floor of the Nautibus building)
  • What: Maximal order of planar graphs of small diameter
  • Abstract:
    The degree diameter problem asks for the maximum possible number of vertices in a graph of maximum degree $\Delta$ and diameter $D$. In this paper, we focus on planar graphs of diameter $3$. Fellows, Hell and Seyffarth (1995) proved that for all $\Delta\geq 8$, the maximum number $\np_{\Delta, D}$ of vertices of a planar graph with maximum degree at most $\Delta$ and diameter at most 3 satisfies $\frac{9}{2}\Delta – 3 \leq \np_{\Delta,3} \leq 8 \Delta + 12$. We show that the lower bound they gave is optimal, up to an additive constant, by proving that there exists $c>0$ such that $\np_{\Delta,3} \leq \frac{9}{2}\Delta + c$ for every $\Delta\geq 0$. Our proof consists in a reduction to the fractional maximum matching problem on a specific class of planar graphs.
    Joint work with Antoine Dailly, Sasha Darmon, Ugo Giocanti and Petru Valic

Ioan Todinca (Université Orléans)

  • When: 30/06/26 at 10:30am
  • Where: Amphi B, ENS de Lyon
  • What: What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
  • Abstract:
    Algorithmic meta-theorems are results of the form “every computational problem that can be formalised in a given logic L can be solved efficiently on every class C of [graphs] satisfying certain conditions” [Kreutzer 2011]. They have become central to classical (sequential) graph theory since Courcelle’s theorem in the 1990s, with numerous recent developments, particularly on first-order logic. We are currently witnessing the gradual introduction of algorithmic meta-theorems into distributed computing, initiated by [Feuilloley, Bousquet, Pierron, PODC 2022].
    My presentation will begin with an easily accessible introduction to distributed computing, in particular to the CONGEST model, in which the nodes of a network communicate in synchronous rounds by exchanging “small” messages (of logarithmic size) with their neighbours. The aim is to collectively solve a task in a small number of rounds. We shall see that, in distributed computing, even the decision of simple properties such as “the graph has no 4-vertex cycle” or “the graph has at most one vertex of degree 3” encounters barriers of congestion or (non-)locality. Both problems are expressible in on first-order logic (FO).
    In the second part, I will discuss the decision of FO problems in graph classes of bounded expansion. We shall see that sequential FO model-checking extends to the CONGEST model, in O(Diameter + log n) rounds, notably thanks to the low tree-depth colouring tools for these classes. For local FO formulas f(x) (whose truth depends only on a ball of constant radius around x, such as “x has a twin”), we have shown that all vertices satisfying the formula can be marked in O(log n) rounds, answering a question posed by [Nešetřil, Ossona de Mendez, Distributed Computing 2016]. 

Maxime Flin (Aalto University, Finland)

  • When: 25/06/2026
  • Where: Nautibus, La Doua
  • Who: Maxime Flin (Aalto University, Finland)
  • What: Distributed and semi-streaming coloring

Graph meetings

in memory of Carl Feghali

  • When: 18/06/2026
  • Where: LIP, amphi B
  • Who: everyone

Fanny Hauser (LaBRI, Bordeaux)

  • When: 21/05/2026
  • Where: LIP, amphi B
  • Who: Fanny Hauser (LaBRI, Bordeaux)
  • What: Tree-independence through distance to chordal graphs

Abstract:

The tree-independence number of a graph is the analogue of treewidth where, instead of minimising the size of bags, we minimise the size of a stable set contained in a bag. Chordal graphs have tree-independence 1, and it remains an active line of research to determine the tree-independence of various graph classes — or even to establish whether it is bounded in general. We show that graphs with no induced 

C4 nor P1 +P4  have tree-independence at most 2 by proving a conjecture of Hilaire, Milanič, and Vasić (2025) stating that they can be made chordal by deleting a clique. This is joint work with Marthe Bonamy and Sarah Houdaigoui.

Graph Meetings : Clara Marcille and Nicolas Bousquet

  • When: 05/05/2026
  • Where: LIRIS, room TBA
  • Who: Clara Marcille (MC2, LIP) and Nicolas Bousquet (GOAL, LIRIS)
  • What: Monitoring edge-geodetics of graphs

Graph Meetings : Felicia Lucke (LIP) and Yannick Mogge (LIRIS)

First talk

  • Who: Felicia Lucke (MC2, LIP)
  • What: Optimising Matching Cuts – Why Maximising is Harder than Minimising
  • Abstract: The problem Matching Cut asks for an edge set of a graph which is both an edge cut and a matching. We consider the two recent optimisation variants Maximum and Minimum Matching Cut, where we aim to maximise respectively minimise the number of edges in the matching cut. Both variants are NP-hard but differ in complexity for certain graph classes. In this talk we investigate why maximising is harder than minimising. We further compare the optimisation variants of Matching Cut to the classical Matching Cut and its oldest variant Perfect Matching Cut.

Second Talk

  • Who: Yannick Mogge (GOAL, LIRIS)
  • What: Cops and Cleaners with limited visibility
  • Abstract: We consider the model of limited visibility Cops and Robbers, where the cops can only see within their $l$-neighbourhood. We prove that the gap between the number of cops needed to see the robber and the number of cops needed to capture the robber can be arbitrarily large, answering an open question from the literature. We also consider how close we can get to seeing the robber when we do not have enough cops available.

Alp Müyesser : Cycle-factors of regular graphs via entropy

  • When: 09/04/2024 at 14:00 Cancelled
  • Where: LIP, amphi A (to be confirmed)
  • Who: Alp Müyesser (New College, University of Oxford)
  • What: Cycle-factors of regular graphs via entropy

Abstract:

It is a classical result that a random permutation of n elements has, on average, about \log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has O((n\log d)/d) cycles. This is tight up to the constant factor and improves the best previous bound of the form O(n/\sqrt{\log d}) due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length (1+O((\log d)/d)) \cdot n if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close. Joint work with Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley and Lukas Michel.

Maël Dumas: Variants of Merge-Width and Applications

  • When: 12/03/2026 at 14:00
  • Where: LIP, Amphi A
  • Who: Maël Dumas (University of Warsaw)
  • What: Variants of Merge-Width and Applications

Abstract:
Merge-width is a recently introduced family of graph parameters that unifies treewidth, clique-width, twin-width, and generalised colouring numbers. We prove the equivalence of several alternative definitions of merge-width, thus demonstrating the robustness of the notion. Our characterisation via definable merge-width uses vertex orderings inspired by generalised colouring numbers from sparsity theory, and enables us to obtain the first non-trivial approximation algorithm for merge-width, running in time n^O(1)·2^n. Using these alternative definitions we also establish that graphs of bounded merge-width admit sparse quotients with bounded strong colouring numbers, are quasi-isometric to graphs of bounded expansion, and admit neighbourhood covers with constant overlap.

  • When: 19/03/2026 at 14:00
  • Where: LIP, amphi A

Graph Meetings : Ana Beatriz Da Silveira Martins : (Even hole, triangle)-free graphs revisited + Milica Maksimović : Rainbow connectivity Maker-Breaker games

  • When: 05/03/2026 at 14:00
  • Where: LIRIS, room TBA
  • Who: Ana Beatriz Da Silveira Martins (MC2, LIP)
  • What: (even hole, triangle)-free graphs revisited

    Abstract:
    We revisit a classical paper about (even hole, triangle)-free graphs  [Conforti, Cornuejols, Kapoor and Vuskovic, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204–220, 2000].
    In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs.
    A theta is a graph made of three chordless ab-paths of length at least 2, vertex-disjoint apart from a and b, and such that the only edges are the edges of the paths. An wac is a graph W= (H, c, c’) induced by a hole H together with two adjacent vertices c and c’ that both have at least three neighbours in H (the terminology wac this stands for Wheel with Adjacent Centres).
  • Who: Milica Maksimović (Univ Novi Sad)
  • What: Rainbow connectivity Maker-Breaker games

Blair Sullivan : Graph Modification in Algorithmic Differentiation

  • When: 26/02/2026 at 14:00
  • Where: LIP, Amphi A
  • Who: Blair Sullivan (Invited professor at MC2, LIP)
  • What: Graph Modification in Algorithmic Differentiation

    Abstract:
    In this talk, we present graph-theoretic formulations of two problems with wide application in algorithmic differentiation (AD): accumulating a Jacobian matrix while minimizing multiplications (Minimum Cost), and obtaining a minimum-size matrix-free Jacobian representation (Minimum Representation). Both problems can be naturally modeled as finding sequences of graph modifications (vertex eliminations) in a directed acyclic graph. We recently showed that both problems are NP-complete, resolving a long-standing open problem in AD. For Minimum Cost, we also show that a relatively straight-forward O*(2n) algorithm is essentially best possible under the Exponential Time Hypothesis. Our results are facilitated by several illustrative structural insights about sequences of vertex eliminations. We conclude with a discussion of open problems related to parameterized algorithms, approximations, and problem variants allowing edge eliminations. In addition to sharing our results, we hope to instigate more collaboration between graph algorithms researchers and the AD community. This talk is based on joint work with Matthias Bentert, Alex Crane, Pal Drange, and Yosuke Mizutani.

Martin Milanič: Inverting Ramsey: awesome graph parameters

  • When: 12/02/2026 at 14:00
  • Where: LIP, Amphi A
  • Who: Martin Milanič (University of Primorska in Koper, Slovenia)
  • What: Inverting Ramsey: awesome graph parameters

Abstract:
We investigate connections between two lines of research related to independent sets and cliques in graphs. One of them studies independence variants of graph parameters such as treewidth or degeneracy. The second line deals with graph classes where some parameters are bounded by a function of the clique number. A famous example is given by the family of χ-bounded graph classes, where the chromatic number is bounded by a function of the clique number.
A Ramsey-type argument implies that a graph parameter is bounded by a function of the clique number in any graph class in which the independence variant of the parameter is bounded by a constant. If the reverse implication also holds, we say that the parameter is awesome; otherwise, it is awful. We identify a number of awesome and awful graph parameters, derive some algorithmic applications of awesomeness, and propose a number of open problems related to these notions.
This is joint work with Kenny Bešter Štorgel (FIŠ Novo mesto and Primorska), Clément Dallard (Fribourg), Vadim Lozin (Warwick), and Viktor Zamaraev (Liverpool).

Clément Legrand-Duchêne: Dirac’s theorem and the geometry of perfect matchings

  • When: 13/11/2025 at 14:30
  • Where: M7, ENS de Lyon
  • Who: Clément Legrand-Duchêne (University in Kraków, Poland)
  • What: Dirac’s theorem and the geometry of perfect matchings

Dirac’s theorem states that all n-vertex graphs with minimum degree n/2 contain a perfect matching. This is tight and graphs with minimum degree cn are more generally called c-Dirac graphs. In fact, a phase transition occurs at c=1/2: c-Dirac graphs with c \ge 1/2 contain (cn/-e+o(1)))^{n/2} perfect matchings [Cuckler, Kahn 2009]. Moreover, for any fixed c-Dirac graph G with c >= 1/2, there exist nice probability distributions on the perfect matchings of G called spread distributions [Pham, Sah, Sawhney, Simkin 2024]; as a result, if the edges of $G$ are sampled with probability O(\log(n)/n), the resulting graph still contains a perfect matching with good probability, thereby witnessing that these matchings are “everywhere” in G.

With Ross Kang, we give a new understanding of this phase transition by describing how the perfect matchings of a Dirac graph cluster. More precisely, we analyse the geometrical properties of the space of perfect matchings of $G$, endowed with the graph metric such that perfect matchings differing on at most k edges are at distance one. For any fixed k, we pinpoint sharp thresholds at which this space is shattered into exponentially many components, has isolated perfect matchings, becomes connected, or becomes an expander.

Laure Morelle : H-Planarity and Parametric Extensions: when Modulators Act Globally

  • When: 11/12/2025 at 14:30
  • Where: Room M7 (3rd floor), LIP, ENS de Lyon
  • Who: Laure Morelle (University of Bergen)
  • What: H-Planarity and Parametric Extensions: when Modulators Act Globally

Abtract:
We introduce a series of graph decompositions based on the modulator/target scheme of modification problems. As such, we define H-Planarity as the problem of deciding whether a graph G contains a vertex set X such that the torso of X is planar and the connected components of G-X are in H. We prove that, if H is hereditary, CMSO-definable, and decidable in polynomial time, then H-Planarity is solvable in polynomial time.
Additionally, we define two planar extensions of elimination distance to H and H-treewidth, namely H-planar treedepth and H-planar treewidth, for which we find FPT results under some mild conditions on H.
All previous (meta) algorithmic studies on modulators deal with modulators of “low bidimensionality” in the sense that they cannot be spread along a grid-minor of the input graph. Our results are the first to handle the situation where the modulators act globally. For this, we introduce a new version of the “irrelevant vertex technique” that can deal with modulators that may act “everywhere” in the input graph.

Alexander Crane: Probabilistic Network Design

  • When: 26/09/2025 at 14:00
  • Where: Amphi A1, ENS de Lyon
  • Who: Alexander Crane (University of Utah)
  • What: Probabilistic Network Design

Probabilistic graphs allow us to model randomized propagation
in graphs, for example communication in lossy networks or the spread of
information in a social network. In a realization of a probabilistic
graph G = (V, E, p), each edge in E is said to be “active”
independently with probability p. The proximity of a vertex pair u, v
is the probability with which there exists a uv-path consisting
entirely of active edges. The reach of G is the minimum proximity
across all vertex pairs.

In this talk, we will cover some recent approximation results on a
natural network design question in this setting: given a probabilistic
graph G and a budget k, how can we choose k edges to add to G such that
the reach of the resulting graph is maximized? The results rely on
connections to the k-center clustering problem, with an assist from
tools developed in percolation theory.

Alexey Gorelov: Lifting maps between graphs to embeddings

  • When: 19/06/2025 at 10:30
  • Where: Room B1, ENS de Lyon
  • Who: Alexey Gorelov (Institut Fourier)
  • What: Lifting maps between graphs to embeddings

Let $f \colon G \to H$ be a graph homomorphism. In general, $f$ is not injective. The goal is to transform $f$ into an embedding by introducing a new dimension, that is, replacing $H$ by the space $|H| \times \mathbb{R}$, and perturbing $f$ along the new dimension. This task was originally motivated by similar problems in topology, which were in turn motivated by the classical embeddability question. Our problem can be reformulated in a purely combinatorial way. A \emph{combinatorial lifting} of $f \colon G \to H$ is a collection of linear orders $<_{v}$ on $f^{-1}(v)$ for all $v \in V(H)$ such that no crossings occur. A crossing is a pair of edges $x_1 y_1, x_2 y_2 \in E(G)$ with $f(x_1) = f(x_2) = v$, $f(y_1) = f(y_2) = w$, and $x_1 >_v x_2$ while $y_1 <_w y_2$. We study the computational complexity of deciding whether such a lifting exists. In a former work, we showed that this problem is NP-complete in general. However, for the special case of maps from trees to path graphs, we proved a complete criterion that can be checked in polynomial time. Our approach relies on combining and transforming liftings, a technique that may be of independent interest.

Graph meetings: Malory Marin & Yannick Mogge

  • When: 22/05/2025 at 14:00
  • Where: LIRIS
  • Who (1st speaker): Malory Marin (LIP)
  • What: Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets

Given a graph G, the hard-core model defines a probability distribution over its independent sets, assigning to each set of size k a probability of λ^k/Z, where λ>0 is a parameter known as the fugacity and Z is a normalization constant. The Glauber dynamics is a simple Markov chain that converges to this distribution and enables efficient sampling. Its mixing time–the number of steps needed to approach the stationary distribution–has been widely studied across various graph classes, with most previous work emphasizing the dichotomy between polynomial and exponential mixing times, with a particular focus on sparse classes of graphs.
We investigate subexponential mixing times of the Glauber dynamics on geometric intersection graphs, such as disk graphs. We also study parameterized mixing times by focusing on two structural parameters that can remain small even in dense graphs: the tree independence number and the path independence number. We show that Glauber dynamics mixes in polynomial time on graphs with bounded path independence number and in quasi-polynomial time when the tree independence number is bounded. Moreover, we prove both bounds are tight, revealing a clear separation between the two parameters.

  • Who (2nd speaker): Yannick Mogge (LIRIS)
  • What: Variants of Maker-Breaker games on complete and random graphs

In this talk we discuss two variants of Maker-Breaker games: fast strategies in Waiter-Client games, as well as a result for Connector-Breaker and Walker-Breaker games.

Waiter-Client games are played on some hypergraph $(X, \mathcal{F})$, where $\mathcal{F}$ denotes the family of winning sets. During each round of the game, Waiter offers two elements of $X$ to Client, from which she claims one for himself and the other element goes to Waiter. Waiter wins the game, if he can force Client to claim all the elements of a winning set from $\mathcal{F}$.
We will discuss fast strategies for the Waiter-Client Hamiltonicity game on the edges of the complete graph $K_n$, and we will show that Waiter can force Client to claim a Hamilton cycle within $n+1$ rounds.

Connector-Breaker and Walker-Breaker games are defined similarly to Waiter-Client games on graphs, but in each round both players claim some predefined number of edges for themselves, with the additional restriction that Connector (or Walker) has to play in such a way that her graph stays connected throughout the game (or according to a walk). We will discuss the $(2:2)$-biased version of those games (where both players claim two edges of the graph in each turn) on a random graph $G \sim G_{n,p}$ and we will show that the threshold probabilities for Connector/Walker to claim a Hamilton cycle are of order $n^{-2/3 + o(1)}$.

See the archives.