This "Projet Jeunes Chercheuses et Jeunes Chercheurs" (JCJC) is fully funded by the French Agence Nationale de la Recherche and is running from April 2022 until March 2026.

Project description

The aim of this project is 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 are, 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 is 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 will explore various paradigms such as parameterized, approximation and enumeration algorithms.

Events

  • 14/09/2023: Prafullkumar Tale (Indian Institute of Science Education and Research Pune) is visiting us for 2 weeks. (GRALMECO funding)
  • 04/09/2023: Daniel Quiroz (Universidad de Valparaiso, Chile) is visiting us for a week. (GRALMECO funding)
  • 26/06/2023: Diptapriyo Majumdar (Indraprastha Institute of Infromation Technolgy, Delhi) is visiting us for 2 weeks. (GRALMECO funding)
  • 12/06/2023: Dibyayan Chakraborty (ENS Lyon) and Ralf Klasing (Université de Bordeaux) are visiting us for a week. (GRALMECO partial funding)
  • 05/06/2023: First GRALMECO 5-days workshop, in St Jacques d'Ambur.
  • 15/05/2023: Pavol Hell (Simon Fraser University, Vancouver) is visiting us for a week. (GRALMECO funding)
  • 14/03/2023: Michael Henning (University of Johannesburg) is visiting us for two weeks. (external funding)
  • 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)
  • 26/09/2022: Dibyayan Chakraborty (ENS Lyon) is visiting us for a week. (external funding)
  • 13/06/2022: Michael Henning (University of Johannesburg) is visiting us for a week. (external funding)
  • 31/05/2022: Kick-off meeting of the project: budget/admin discussion, followed by open discussions around potential research problems.
  • 09/05/2022: Harmender Gahlawat (Ben-Gurion University of the Negev) and Dibyayan Chakraborty (ENS Lyon) are visiting us for a week. (GRALMECO funding)
  • 01/04/2022: Scientific start of the project.
  • 07/03/2022: Dibyayan Chakraborty (ENS Lyon) is visiting us for a week. (external funding)
  • 01/03/2022: Anni Hakanen has joined the LIMOS as a postdoc for 1 year. (external funding)
  • 02/02/2022: Dipayan Chakraborty has joined the LIMOS as a PhD student for 3 years. (external funding)
  • 28/07/2021: The project is accepted!