This "Projet Jeunes Chercheuses et Jeunes Chercheurs" (JCJC) was fully funded by the French Agence Nationale de la Recherche and was running from April 2022 until June 2026. It can be seen on the ANR website here.
The project was succesfully completed, led to many new collaborations and scientific results. We thank all the members, collaborators, and friends ofGRALMECO for this great human and scientific experience!

Project description

The aim of this project was to study the algorithmic complexity of metric-based covering problems in graphs, viewed as networks with their underlying distance-metric. Examples of such problems are Metric Dimension, Geodetic Set, variants of Path Cover, distance-constrained Domination or Packing, etc. Such problems have important applications, such as routing or monitoring in communication and transportation networks, information retrieval in graph databases, or computational learning in large datasets. They pose important technical challenges, as most classic techniques used for more localized graph problems fail in this context. Our objectives were, on one hand, to exhibit common properties of the inputs that render these problems intractable; on the other hand, to develop efficient algorithms for relevant graph classes and parameters. Our focus was the use of structural graph parameters that are relevant for metric properties, like distance VC dimension, tree-length, hyperbolicity, highway dimension, but also more local parameters like MIM-width and twin-width. We explored various paradigms such as parameterized, approximation and enumeration algorithms.

Highlights (selection of five key results)

  1. Tight double-exponential treewidth lower bounds for parameterized algorithms solving metric-based problems e.g. Metric Dimension and Geodetic Set
    Representative paper: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale. 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), Leibniz International Proceedings in Informatics 297, 66:1-66:19, 2024. [hal | arXiv (full version) | www]
  2. Improved bounds for the profile complexity in structured graph classes
    Representative paper: Laurent Beaudou, Jan Bok, Florent Foucaud, Daniel A. Quiroz, Jean-Florent Raymond. Profile and neighbourhood complexity of graphs with excluded minors and tree-structured graphs. Submitted manuscript, 2025. [hal | arXiv]
  3. Graphs covered with few shortest paths have small pathwidth
    Representative paper: Maël Dumas, Florent Foucaud, Anthony Perez, Ioan Todinca. On graphs coverable by k shortest paths. SIAM Journal on Discrete Mathematics 38(2):1840-1862, 2024. [arXiv | hal | www]
  4. Long induced paths in structured graph classes
    Representative paper: Julien Duron, Louis Esperet, Jean-Florent Raymond. Long induced paths and forbidden patterns: Polylogarithmic bounds. SIAM Journal on Discrete Mathematics 40(1):52-81, 2026. [hal | www]
  5. Approximation algorithms for Isometric Path Cover and isometric path complexity parameter
    Representative paper: Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, Yann Vaxès. Isometric path complexity of graphs. Discrete Mathematics 349(2):114743, 2026. [hal | arXiv | www]

Timeline and main events

  • 30/06/2026: end of the project.
  • 22/06/2026: Final GRALMECO 5-days workshop, in Aydat (joint with the IRN GRAPHMETRIX pre-project workshop).
  • 01/09/2025: Gaétan Berthe has joined the LIMOS as a postdoc for 1 year (external funding: CNRS).
  • 01/01/2025: Harmender Gahlawat has joined the LIMOS as a postdoc for 8 months (external funding: cap 20-25).
  • 01/10/2024: Lucas Lorieau has joined the LIMOS as a PhD student for 3 years (external funding: CNRS).
  • 24/06/2024: Second GRALMECO 5-days workshop, in St Jacques d'Ambur (joint with the AGC team workshop).
  • 20/02/2024: Jan Bok stays at LIMOS as a postdoc for 3 more months (external funding: cap 20-25).
  • 01/10/2023: Antoine Dailly stays at LIMOS as a postdoc for 11 more months (external funding: cap 20-25).
  • 05/06/2023: First GRALMECO 5-days workshop, in St Jacques d'Ambur.
  • 20/02/2023: Jan Bok has joined the LIMOS as a postdoc for 1 year (GRALMECO funding).
  • 01/10/2022: Antoine Dailly has joined the LIMOS as a postdoc for 1 year (GRALMECO funding).
  • 31/05/2022: Kick-off meeting of the project: budget/admin discussion, followed by open discussions around potential research problems.
  • 01/04/2022: Scientific start of the project.
  • 01/03/2022: Anni Hakanen has joined the LIMOS as a postdoc for 1 year (external funding from Finland).
  • 02/02/2022: Dipayan Chakraborty has joined the LIMOS as a PhD student for 3 years (external funding: cap 20-25).
  • 28/07/2021: The project is accepted!