Localiser une cible dans un graphe

International audienceLe jeu de la localisation d'une cible (invisible et immobile) dans un graphe a été introduit par Seager en 2013. Dans ce jeu, une cible est placée secrètement sur un sommet et, à chaque tour, il est possible d'interroger un sommet et recevoir, comme réponse, la distance exacte entre ce sommet et la cible. L'objectif est de localiser la cible en minimisant le nombre de tours, et ce, quelle que soit sa position. Nous considérons une généralisation de ce jeu où k sommets peuvent être interrogés à chaque tour. Celle-ci est notamment liée à la notion de dimension métrique d'un graphe. Nous étudions aussi la variante où les distances relatives sont données comme réponses, qui généralise la dimension centroïdale des graphes. Pour les deux variantes, nous montrons que localiser la cible en un nombre minimum de tours est NP-complet en général, lorsque k est fixé. Dans le cas des arbres (à n noeuds) et des distances exactes, nous montrons que le problème est NP-complet lorsque k fait partie de l'entrée. Nous donnons cependant une (+1)-approximation de ce problème : nous présentons un algorithme qui, en temps O(n log n) (indépendant de k), calcule une stratégie pour localiser la cible en au plus un tour de plus que l'optimal. Cet algorithme peut aussi être utilisé pour résoudre exactement le problème en temps $n^{O(k)}$