Theme Algorithmics, Graphs, Complexity
Presentation
The main research areas of the team can be classified into two parts : (1) structural graph/lattice theory and the consequences in algorithmics, and (2) algorithmic geometry with a main focus on discrete convexity.
It is usual when studying discrete objects to follow the advice of Descartes, namely divide and conquer, i.e., define operators on discrete objects and decompose with respect to these operators in order to explain their inherent complexity. The team has a strong expertise in studying structural graph/lattice theory through the lens of graph/lattice decompositions and their applications in several algorithmic questions and in combinatorics. Some examples of graph decompositions studied in this group are tree-decomposition, rank-decomposition and understanding when the associated width measures are bounded in some graph classes, and also decompositions based on cut set such as clique and stable-cut set and skew partitions with applications in colouring graphs. Some examples of decompositions in lattices are recursive constructions based on copying convex sets or based on colored posets. Some other applications of the studied decompositions can be:
- Listing problems in (hyper)graphs and lattices. We have a strong expertise in the listing of vertex subsets of a hypergraph satisfying a property. We have, for instance, and proved that the listing of minimal dominating sets is equivalent to the well-known Hypergraph Dualisation problem.
- Representation of lattices and efficient algorithms on lattices. This question is mainly studied with respect to the Lattice Dualisation problem, a particular case of which is the Hypergraph Dualisation Problem.
- Optimisation problems in (hyper)graphs. Studied problems include, but are not limited to, colouring problems, graph identification problems, homomorphism questions, etc. We are mostly interested in obtaining either tight bounds on some parameters such as chromatic number or identifying codes, or tight time complexities parametrised by complexity measures.
- Packing and covering problems such as Erdös-Posa functions.
The main interests in algorithmic geometry deal with computational aspects in digital/discrete geometry such as the computation of convex hulls in digitall euclidean spaces. The members are experts in designing heuristics for obtaining competetive algorithms for computing (approximate) convex hulls for various configurations of points in the 2D euclidean space (many of such problems are NP-hard ones). Members often participate to the CG:SHOP challenge, organised during SoCG conference, and win the 2021 edition which were about the coordinated robot motion planning.
Keywords: graph theory; graph complexity parameters; graph decompositions; algorithmic lattice theory; algorithmic geometry; discrete convexity; listing/enumerating algorithms;
last publications
Distance-based (and path-based) covering problems for graphs of given cyclomatic number
Discrete Mathematics
Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, Prafullkumar Tale - June 10, 2025
Structural Parameterization of Locating-Dominating Set and Test Cover
Proceedings of the 14th International Conference on Algorithms and Complexity (CIAC 2025)
Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor - April 24, 2025
The Canadian Traveller Problem on unit-weighted and arbitrarily weighted outerplanar graphs
Dipayan Chakraborty, Florent Foucaud, Michael Antony Henning, Tero Laihonen - April 7, 2025
A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
Tapas Das, Florent Foucaud, Clara Marcille, P.D. Pavan, Sagnik Sen - March 21, 2025
Monitoring arc-geodetic sets of oriented graphs
Theoretical Computer Science
Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-Il Oum, Michal Pilipczuk, Erik Leeuwen - March 18, 2025
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
ACM Transactions on Computation Theory
Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale - March 4, 2025
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Louis Esperet, Harmender Gahlawat, Ugo Giocanti - Feb. 24, 2025
Coarse cops and robber in graphs and groups
Aude Marêché, Isabelle Debled-Rennesson, Fabien Feschet, Phuc Ngo - Feb. 19, 2025
Local Fan of Digital Planes for Parameter-Free Normal Vector Estimation on Digital Surfaces
Florent Foucaud, Atrayee Majumder, Tobias Mömke, Aida Roshany-Tabrizi - Feb. 13, 2025
Polynomial-time algorithms for Path Cover on trees and graphs of bounded treewidth
10th International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2025)
All publications are here
Team
Persons in charge
Lecturing Researchers
- BEAUDOU Laurent
- BERGE Pierre
- FESCHET Fabien
- FOUCAUD Florent
- GERARD Yan
- KANTE Mamadou
- LIMOUZY Vincent
- NOURINE Lhouari
- PASTOR Lucas
- RAYNAUD Olivier
- VIGNY Alexandre