#### 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

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes

LICS 2024 - 39th ACM/IEEE Symposium on Logic in Computer Science

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale - July 8, 2024

Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover

Proceedings of the 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Antoine Dailly, Valentin Gledel, Richard J Nowakowski, Carlos Pereira dos Santos - June 13, 2024

Simple Chopsticks: Playing with any number of hands and fingers

Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca - June 10, 2024

On Graphs Coverable by k Shortest Paths

SIAM Journal on Discrete Mathematics

Antoine Dailly, Pascal Lafourcade, Gael Marcadet - June 4, 2024

How did they design this game? Swish: complexity and unplayable positions

12th International Conference on Fun with Algorithms (FUN 2024)

Alexander Lindermayr, Sebastian Siebertz, Alexandre Vigny - May 31, 2024

Elimination Distance to Bounded Degree on Planar Graphs Preprint

Fundamenta Informaticae

Dipayan Chakraborty, Annegret Wagler - May 22, 2024

Open-Separating Dominating Codes in Graphs

International Symposium on Combinatorial Optimization

Oscar Defrain, Jean-Florent Raymond - May 1, 2024

Sparse graphs without long induced paths

Journal of Combinatorial Theory, Series B

Florent Foucaud, Narges Ghareghani, Pouyeh Sharifani - April 15, 2024

Extremal digraphs for open neighbourhood location-domination and identifying codes

Discrete Applied Mathematics

Laurent Beaudou, Caroline Brosse, Oscar Defrain, Florent Foucaud, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor - April 2, 2024

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

Discrete Mathematics and Theoretical Computer Science

All publications are here