Vendredi 15 décembre à 15h - Gautier Stauffer
Horizontal collaboration in logistics: game theory models and algorithms for trading demands

In this talk, we will introduce a novel cooperative game theory model designed to tackle a significant unresolved issue in operations research within the forestry sector as initially highlighted by Rönnqvist and colleagues in 2015. This issue centers on developing and suggesting effective principles for shared transportation in forestry. Additionally the model is applicable to urban distribution and plays a crucial role in exploring potential expansions to more complex large-scale collaborative efforts in logistics, particularly in the context of emerging frameworks like the physical internet. We will discuss the reasons for examining such models, the difficulties they present, some initial findings, and future outlooks. The project inherently spans multiple disciplines, integrating elements from supply chain optimization, cooperative game theory, polyhedral combinatorics, and combinatorial optimization.

Vendredi 15 décembre à 13h30 - Chien-Chung Huang
Matroid-Constrained Maximum Vertex Cover
We introduce the problem of Matroid-Constrained Vertex Cover: given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied max k-vertex cover problem, in which the matroid is the simple uniform matroid.

This problem is APX-hard and also W[1]-hard (with k being the paramter). Nonethess, in this work, by two different techniques, we are able to design Fixed-Parameter Tractable Approximation Schemes (FPT-AS).

This is joint-work with François Sellier at École des Mines.

Vendredi 1 décembre à 14h - František Kardoš
Three-cuts are a charm: acyclicity in 3-connected cubic graphs
Let G be a bridgeless cubic graph. Recently, in collaboration with Edita Máčajová and Jean Paul Zerafa, we have solved a conjecture (also known as the S4-Conjecture) made by Mazzuoccolo in 2013: there exist two perfect matchings of G such that the complement of their union is a bipartite subgraph of G. (There was a talk on this topic in June 2022.) This is a step closer to comprehend better the Fan--Raspaud Conjecture and eventually the Berge--Fulkerson Conjecture. The S4-Conjecture, now a theorem, is also the weakest assertion in a series of three conjectures made by Mazzuoccolo in 2013, with the next stronger statement being: there exist two perfect matchings of G such that the complement of their union is an acyclic subgraph of G. Unfortunately, this conjecture is not true: Jin, Steffen, and Mazzuoccolo showed that there exists a counterexample admitting 2-cuts. Here we show that, despite of this, every cyclically 3-edge-connected cubic graph satisfies this second conjecture.

Vendredi 17 novembre à 14h - Julien Bensmail
On the hardness of determining the irregularity strength of graphs
The irregularity strength s(G) of a graph G is the smallest k such that the edges of G can be labelled with 1,...,k so that no two vertices are incident to the same sum of labels. This parameter was introduced in the late 1980s as an alternative way to deal with an optimisation problem where one aims at making a graph irregular by multiplying its edges in an optimal way. Since then, the irregularity strength has received a lot of attention, focusing mainly on proving bounds and investigating side aspects and variants.

In a recent work, we considered the algorithmic complexity of determining the irregularity strength of a given graph. We proved that two close variants of this problem are NP-hard, which we suspect might indicate that the original problem is hard too. Namely, we proved that determining the distant irregularity strength, where only vertices within a certain distance are required to be incident to different sums of labels, and the multiset irregularity strength, where any two distinct vertices are required to be incident to different multisets of labels, are NP-hard problems.

The talk will essentially be focused on introducing the general problem (which remains open to date), on going through most of the ideas behind the proofs of our two results, and on explaining what we can get and learn from our arguments and tools.

Vendredi 10 novembre à 14h - František Kardoš
New reducible configurations for Barnette's conjecture
Barnette's conjecture states that all 3-connected bipartite cubic planar graphs are Hamiltonian. So far, only a sporadic (finite) set of reducible configurations (i.e., induced subgraphs forbidden in a smallest counterexample) have been known. We present a new infinite family of reducible configurations, obtained by generalizing some configurations found by an exhaustive computer-assisted search. This is a joint work with Richard Bíró (Comenius University, Bratislava).

Vendredi 06 octobre à 14h - Florian Galliot
The Maker-Breaker positional game
The Maker-Breaker game is played on a hypergraph H. Maker and Breaker take turns coloring vertices of H, in red and blue respectively. Maker wins if she gets a monochromatic red edge at any point, otherwise Breaker wins. We present some state of the art around this game and then proceed with our own results. Our study is centered on the notion of danger at x, which is a subhypergraph representing an urgent threat that Breaker must hit with his next pick if Maker picks x. Applying this concept in hypergraphs of rank 3 i.e. in which all edges are of size at most 3, we provide a structural characterization of the winner with perfect play, as well as optimal strategies for both players based on danger intersections. A crucial corollary is that Maker has a winning strategy on H if and only if she can guarantee the appearance, within the first three rounds of play, of a very specific elementary subhypergraph on which she easily wins. As a consequence, we are able to determine the algorithmic complexity of deciding which player has a winning strategy on a given hypergraph: this problem, which is known to be PSPACE-complete on 6-uniform hypergraphs, is in polynomial time on hypergraphs of rank 3. Another consequence is that, if Maker has a winning strategy on a hypergraph H of rank 3, then she can get a monochromatic red edge in just O(log(|V(H)|)) rounds of play.

Vendredi 29 septembre à 14h - Borut Lužar
Combining proper and square colorings
Proper colorings of graphs with additional distance constraints are an attractive topic in both settings: the vertex and the edge coloring. In particular, when we require that two vertices are colored differently if they are at distance at most 2, we are essentially coloring the square of a graph. Similarly, in a proper coloring of edges where two edges are colored differently as soon as they are adjacent or two of their endvertices are at distance 1, we are coloring the square of the line graph of a graph. We usually refer to the former as the square coloring and to the latter as the strong edge coloring.

Motivated by the notion of S-packing coloring, we will consider colorings with two types of colors: proper colors, which will be allowed to appear on two non-adjacent objects (regarding the setting---vertex or edge coloring), and strong colors, with which we will be able to color objects at distance at least 3 (in the edge coloring setting, the distance between two edges is taken as the distance between the corresponding vertices in the line graph). This combination of color types positions us in between the proper and the square colorings, which in most of the cases makes determination of the corresponding chromatic indices harder, but it also reveals several nice properties.

In the talk, we will focus mainly to coloring subcubic graphs and review recent results and the most interesting open problems on the topic in the vertex and the edge coloring settings.

Vendredi 22 septembre à 14h - Théo Pierron
Spanning tree reconfiguration
Given n points in the plane, a spanning tree is a set of n-1 straight line edges connecting them while inducing a tree. We consider only those trees that are non-crossing, i.e. where no two edges are allowed to cross. Our goal is to transform a tree into another using as few operations as possible. Here, the operations consist in adding an edge and removing another so that the resulting graph remains a non-crossing spanning tree. While it is easy to show that there is a transformation between any two non-crossing spanning trees, beating the 2n naive upper bound stood up as an open problem for 25 years. In this talk, we will present the recent improvements on this topic.

This is based on joint works with Nicolas Bousquet, Valentin Gledel, Lucas De Meyer, Jonathan Narboni and Alexandra Wesolek.

Vendredi 15 septembre à 14h - Saeed Odak
An Optimal Algorithm for Product Structure in Planar Graphs
The Product Structure Theorem for planar graphs (Dujmovic et al. JACM, 67(4):22) states that any planar graph is contained in the strong product of a planar 3-tree, a path, and a 3-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous O(n log n) time algorithm (Morin. Algorithmica, 85(5):1544–1558).