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

  • 13/06/2022: Michael Henning (University of Johannesburg) is visiting us for a week.
  • 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.
  • 01/04/2022: Scientific start of the project.
  • 07/03/2022: Dibyayan Chakraborty (ENS Lyon) is visiting us for a week.
  • 01/03/2022: Anni Hakanen has joined the LIMOS as a postdoc for 1 year.
  • 02/02/2022: Dipayan Chakraborty has joined the LIMOS as a PhD student for 3 years.
  • 28/07/2021: The project is accepted!