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 -
Benjamin Bergougnoux - LIS, Marseille - Neighborhood operator logics: efficient model checking in terms of width parameters - 4 juin 2026 - SEMINAIRE

In this talk, I will introduce the family of neighborhood operator (NEO) logics which are extensions of existential MSO with predicates for querying neighborhoods of vertex sets. NEO logics have interesting modeling powers and nice algorithmic applications for several width parameters such as tree-width, clique-width, mim-width, and treedepth. NEO logics capture many important graphs problems such as Independent Set, generalizations of Dominating Set, and even CNF-SAT via the signed incidence graphs! We can capture more problems by considering various extensions of NEO logics with predicates for checking global constraints, for example, with connectivity constraints we can capture Hamiltonian Cycle and Longest Path.

In terms of algorithmic applications, NEO logics seem to be the perfect candidates for capturing many problems that can be solved efficiently in terms of width parameters.
This is suggested by the following three results:

For tree-width, the most powerful NEO logic can be model checked in single exponential time in terms of tree-width as implied by a result of Michal Pilipczuk [MFCS 2011] (arxiv.org/abs/1104.3057) and an equivalence between the modal logic used by Pilipczuk and this NEO logic proved in the following paper.

Jan Dreier, Lars Jaffke and I proved that, for an extension of one NEO logic, we can obtain an efficient model-checking algorithm in terms of several width parameters more general than tree-width such as clique-width, rank-width and mim-width [SODA 2023] (arxiv.org/abs/2202.13335).

Vera Checkan, Giannos Stamoulis and I proved that the most powerful NEO logic can be model checked in single exponential time and polynomial space for tree-depth [SODA 2026] (arxiv.org/abs/2510.19793).

These three results provide algorithmic meta-theorems that generalize and unify the most efficient algorithms based on these width parameters. The running times of the model checking algorithms are tight under ETH for each width parameter.

Anthony Meunier - LIMOS - Characterizing the optimum bases of a convex geometry using quasi-closed hypergraphs - 23 avril 2026 - SEMINAIRE

In this presentation, we study implication bases, specifically, their optimization (i.e. obtaining an equivalent implication base with as few elements as possible).
This is a well-known NP-complete problem, it is tractable for several classes of closure systems, in particular in convex geometry.
However and interestingly, it was shown to be NP-complete in that case as well. 
The study of the conditions which make a convex geometry tractable is a natural and intriguing follow-up question.
After some definition, we will present a characterization of optimum bases of convex geometry relying on specific hypergraph, which we call "quasi-closed hypergraph".
We prove that when these hypergraphs have disjoint edges, optimization becomes tractable and show how it fit in with previous results. 
Finally, we will look at a new tractable class, acceptant convex geometry. 

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