Algorithmics of metric covering problems in graphs – GRALMECO

We will study the algorithmic complexity of metric-based covering problems in graphs, viewed as networks with their underlying distance-metric. 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 classes. Our focus is the innovative use of structural graph parameters that are relevant for metric properties, like distance VC dimension, tree-length and hyperbolicity, and recently introduced parameters like MIM-width and twin-width. We will explore various settings, in particular, parameterized and enumeration algorithms.