Sequential Metric Dimension
- PDF / 6,057,245 Bytes
- 35 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 159 Views
Sequential Metric Dimension Julien Bensmail1 · Dorian Mazauric2 · Fionn Mc Inerney1 · Nicolas Nisse1 · Stéphane Pérennes1 Received: 4 September 2018 / Accepted: 28 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph G. At every step, one vertex v of G can be probed which results in the knowledge of the distance between v and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location. We address the generalization of this game where k ≥ 1 vertices can be probed at every step. Our game also generalizes the notion of the metric dimension of a graph. Precisely, given a graph G and two integers k, 𝓁 ≥ 1 , the Localization problem asks whether there exists a strategy to locate a target hidden in G in at most 𝓁 steps and probing at most k vertices per step. We first show that, in general, this problem is NP-complete for every fixed k ≥ 1 (resp., 𝓁 ≥ 1 ). We then focus on the class of trees. On the negative side, we prove that the Localization problem is NP-complete in trees when k and 𝓁 are part of the input. On the positive side, we design a (+ 1)-approximation algorithm for the problem in n-node trees, i.e., an algorithm that computes in time O(n log n) (independent of k) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the Localization problem in trees in polynomial time if k is fixed. We also consider some of these questions in the context where, upon probing the vertices, the relative distances to the target are retrieved. This variant of the problem generalizes the notion of the centroidal dimension of a graph. Keywords Games in graphs · Metric dimension · Complexity
* Fionn Mc Inerney [email protected] 1
Université Côte d’Azur, Inria, CNRS, I3S, Sophia Antipolis, France
2
Université Côte d’Azur, Inria, Sophia Antipolis, France
13
Vol.:(0123456789)
Algorithmica
1 Introduction Unless stated otherwise, every graph considered in this paper is assumed to be connected, undirected, and simple. Localization (or Identification) problems consist of distinguishing the vertices of a graph G = (V, E) using a smallest subset R ⊆ V of its vertices. Many variants have been studied depending on how R is required to make the vertices distinguishable. For instance, identifying codes [16], adaptive identifying codes [2], and locating dominating sets [21] ask for the vertices to be distinguished by their neighbourhood in R. Another well studied example is the one of resolving sets [13, 20], where one aims at distinguishing the vertices of a graph by their distances to such a set. Given a graph G, the main problem is to compute a resolving set with minimum size, this minimum being called the metric dimension of G [13, 20]. The corresponding decision problem (first shown to be NP-complete in [12]) is NP-com
Data Loading...
