New publication on Metric Dimension and Geodetic Set accepted at STACS 2025

Fionn Mc Inerney, researcher at Telefónica and ELASTIC project partner, co-authored a new publication titled “Metric Dimension and Geodetic Set Parameterized by Vertex Cover,” accepted for presentation at the Symposium on Theoretical Aspects of Computer Science (STACS) 2025.

The paper investigates the parameterized complexity of two classical graph problems—Metric Dimension and Geodetic Set—when parameterized by the vertex cover number of the input graph. These problems have applications in areas such as network monitoring and design, localization via sensors, and low-dimensional embeddings, but are known to be computationally hard under most standard parameterizations.

Main results

The authors show that both problems admit:

  • Fixed-parameter tractable (FPT) algorithms with runtime 2^(O(vc^2)) · n^(O(1)), and

  • Kernelization algorithms that reduce the problem to an equivalent instance with 2^(O(vc)) vertices,

where vc denotes the vertex cover number of the graph and n is its number of vertices.

Importantly, the work also proves that these results are tight under the Exponential Time Hypothesis (ETH). The authors establish that neither problem admits:

  • an algorithm running in 2^(o(vc^2)) · n^(O(1)) time, nor

  • a kernel with 2^(o(vc)) vertices,

unless the ETH fails. Very few other problems are known to admit such tight lower bounds.

Context and relevance

The Metric Dimension problem asks whether a graph contains a small set of landmark nodes such that all other nodes are uniquely identified by their distances to these landmarks. The Geodetic Set problem, on the other hand, seeks a small subset of vertices such that every other node lies on a shortest path between two members of this subset. Both problems are NP-hard and highly non-local, making standard algorithmic approaches ineffective.

By providing such rare results with respect to parameterizations by the vertex cover number, the authors not only give the precise algorithmic complexity for these problems in this context, but also provide new algorithmic insights in the field of parameterized complexity.

Contribution to ELASTIC

This research is partially supported by the ELASTIC project (Smart Networks and Services Joint Undertaking, Horizon Europe, Grant Agreement No. 101139067). The project explores scalable and secure data processing across edge and cloud systems. This theoretical contribution strengthens the project’s research in graph-based models relevant to distributed and networked environments, as well as in computing low-dimensional embeddings of symbolic data (e.g., biological sequence data) that facilitate efficient machine learning on this data.

Authors

  • Florent Foucaud (Université Clermont Auvergne, CNRS, Mines Saint-Étienne)

  • Esther Galby (Chalmers University of Technology and University of Gothenburg)

  • Liana Khazaliya (Technische Universität Wien)

  • Shaohua Li (Central South University)

  • Fionn Mc Inerney (Telefónica Research)

  • Roohani Sharma (University of Bergen)

  • Prafullkumar Tale (IISER Pune)

Reference

Foucaud, F., Galby, E., Khazaliya, L., Li, S., Mc Inerney, F., Sharma, R., Tale, P.
Metric Dimension and Geodetic Set Parameterized by Vertex Cover.

The full publication is availabe on project Zenodo repository.