La dimension métrique d'un graphe est le plus petit nombre de sommets d'un ensemble X tel que chaque sommet du graphe est uniquement déterminé par son vecteur de distances à X. Un tel ensemble est appelé ensemble résolvant.

Calculer la dimension métrique est un problème NP-difficile, même sur des classes de graphes assez simples. Cependant en pratique, les instances sont souvent très structurées ce qui rend le problème plus simple.

Le premier objectif de cette thèse est d'explorer la compléxité classique et paramétrée de ce problème sur des classes restreintes de graphes. Seulement quelques résultats sont connus sur les aspects paramétrés. En particulier, ce problème admet un algorithme FPT paramétré par la taille de la solution dans les graphes d'intervalles mais est W[1] difficile paramétré par la largeur d'arborescence. Il serait intéressant d'étendre ces résultats pour d'autes paramètres et d'autres classes de graphes. Trouver des algorithmes d'approximations sera une autre direction de recherche à suivre.

Le deuxième objectif de cette thèse est d'explorer les liens entre la dimension métrique et d'autres paramètres de graphes reliés à la transmission d'information comme le zero forcing number.