Groupe de travail ALCOLOCO

Description :
Le groupe de travail AlCoLoCo (Algorithmique, Combinatoire, Logique et Complexité), fondé en 2010, compte principalement des membres du thème Algorithmique, Graphes, Complexité de l'axe MAAD du LIMOS, mais aussi des membres d'autres thèmes (en particulier Optimisation Combinatoire) et d'autres axes du laboratoire. Il s'agit d'étudier la théorie et l'algorithmique des structures discrètes : graphes, ordres, géométrie, structures relationnelles...
Le groupe de travail se réunit pour des séminaires, des sessions de travail collaboratif, ou encore des groupes de lecture.
Site web: https://alcoloco.limos.fr

Responsable communication :
FOUCAUD Florent
Responsable du groupe : Florent FOUCAUD
Membres : Florent FOUCAUD - Laurent BEAUDOU - Gaetan BERTHE -
Foivos Fioravantes - Technical University in Prague - Exact Algorithms for Distance to Unique Vertex Cover - 26 mars 2026 - SEMINAIRE
Horiyama et al. (AAAI 2024) studied the problem of generating graph instances that possess a unique minimum vertex cover under specific conditions. Their approach involved pre-assigning certain vertices to be part of the solution or excluding them from it. Notably, for the Vertex Cover problem, pre-assigning a vertex is equivalent to removing it from the graph. Horiyama et al. focused on maintaining the size of the minimum vertex cover after these modifications. In this work, we extend their study by relaxing this constraint: 
our goal is to ensure a unique minimum vertex cover, even if the removal of a vertex may not incur a decrease on the size of said cover. We denote this as the Modulator to Unique Minimum Vertex Cover (MU-VC) problem. 
 
Surprisingly, our relaxation introduces significant theoretical challenges.
We observe that the problem is $\Sigma^2_P$-complete, and remains so even for planar graphs of maximum degree 5.
Nevertheless, we provide a linear time algorithm for trees, which is then further leveraged to show that MU-VC is in FPT when parameterized by the combination of treewidth and maximum degree. Finally, we show that MU-VC is in XP when parameterized by clique-width while it is fixed-parameter tractable (FPT) if we add the size of the solution as part of the parameter.
 
This is a joint work with Dušan Knop , Nikolaos Melissinos, Michal Opler and Manolis Vasilakis.
Maël Dumas - University of Warsaw - Variants of Merge-Width and Applications - 19 mars 2026 - SEMINAIRE

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

Clément Legrand-Duchesne, Dirac’s theorem and the geometry of perfect matchings - 8 janvier 2026 - CONFERENCE

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 ≥ 1/2 contain (\frac{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. 

Mauricio Yépez, The twin-width of powers of graphs with bounded tree-width - 4 décembre 2025 - CONFERENCE

Twin-width is a new graph parameter introduced by Bonnet, Kim, Thomassé and Watrigant. Graphs classes with bounded twin-width include those with bounded tree-width, clique-width, and also planar graphs and proper minor-closed classes. Moreover, they preserve most of the nice algorithmic properties of clique-width. In this work, we study the twin-width of power of graphs with bounded tree-width. This is known to be bounded but existing bounds are implicit and very large. We provide a bound of k for the twin-width of the k-th power of any tree and show that this
bound is tight. We also show that if G has tree-width at most t, then the twin-width of the k-th power of G is at most (1 + 2k ) · 2k·(t−1) .