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

Édouard Bonnet, Florent Foucaud, Tuomo Lehtilä, Aline Parreau - Jan. 1, 2024
Neighbourhood complexity of graphs of bounded twin-width
European Journal of Combinatorics

Silvia M. Bianchi, Dipayan Chakraborty, Yanina Lucarini, Annegret K. Wagler - Nov. 27, 2023
Location-Domination Type Problems Under the Mycielski Construction


Anni Hakanen, Ismael G. Yero - Nov. 21, 2023
Complexity and equivalency of multiset dimension and ID-colorings


Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond - Oct. 11, 2023
Subexponential parameterized algorithms for cycle-hitting problems in contact and intersection graphs of segments


Dipayan Chakraborty, R. Sandeep - Sept. 21, 2023
Contracting Edges to Destroy a Pattern: A Complexity Study


Dibyayan Chakraborty, Florent Foucaud, Anni Hakanen - Sept. 18, 2023
Distance-Based Covering Problems for Graphs of Given Cyclomatic Number
24th International Symposium on Fundamentals of Computation Theory (FCT 2023)

Dipayan Chakraborty, Florent Foucaud, Tuomo Lehtilä - Sept. 18, 2023
Identifying codes in bipartite graphs of given maximum degree
12th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2023)

Virginia Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi, Jean-Florent Raymond - Sept. 6, 2023
A lower bound for constant-size local certification
Theoretical Computer Science

Caroline Brosse, Oscar Defrain, Kazuhiro Kurita, Vincent Limouzy, Takeaki Uno, Kunihiro Wasa - Aug. 29, 2023
On the hardness of inclusion-wise minimal separators enumeration


Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, Yann Vaxès - Aug. 28, 2023
Isometric Path Complexity of Graphs
48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

All publications are here