Let G be a graph. The metric dimension dim(G) of graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to X (such a set is called a resolving set). The metric dimension (and related notions such as identifying codes) received a considerable attention in the last decades from both a combinatorial and an algorithmic point of view and has several applications for instance in robotics.

Computing a minimum resolving set is a notoriously NP-hard problem even on simple graph classes such as planar graphs. However, in practice, instances are often very structured which makes the problem simpler. The first goal of this PhD is to explore the complexity of the metric dimension problem on restricted graphs in the classical and the parameterized setting. Only a few is known on the parameterized aspects of metric dimension. In particular, the Minimum Resolving Set problem admits an FPT algorithm parameterized by the size of the solution in interval graphs but it is W[1]-hard parameterized by the treewith (on general graphs). It would be interested to see to to which extend these positive and negative results can be extended to other classical width parameters (treedepth...etc...) and graph classes (intersection of disks in the plane...etc...). Looking for (parameterized) approximation algorithms also is a research direction that may be followed during the PhD.

The second aim of the thesis will consist in exploring the relations between the metric dimension and other graph parameters related to the spread of information in a network such as zero forcing number. For instance it has been shown that, for trees the metric dimension is always at most the zero forcing number. A conjecture states the the metric dimension cannot be larger than the zero forcing number plus the minimum size of a feedback edge set. We would first like to tackle this question before trying to understand more deeply the relations between metric dimension and zero forcing sets in graphs.

We hope that the techniques we will develop during this PhD can provide further ideas to solve several questions and conjectures on the complexity of identifying code in graph classes. In particular, it is open for more than 10 years to determine if the size of a minimum identifying code can be found in unit interval graphs or if it exists a constant approximation algorithm in several graph classes such as disks graphs.