×

Sequential metric dimension. (English) Zbl 1459.05209

Summary: In the localization game, introduced by S. M. Seager [Ars Comb. 110, 45–54 (2013; Zbl 1313.05099)], 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\ge 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,\ell \ge 1\), the Localization problem asks whether there exists a strategy to locate a target hidden in \(G\) in at most \(\ell\) steps and probing at most \(k\) vertices per step. We first show that, in general, this problem is NP-complete for every fixed \(k \ge 1\) (resp., \( \ell \ge 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 \(\ell\) 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.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
05C12 Distance in graphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1313.05099
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Belmonte, R.; Fomin, FV; Golovach, PA; Ramanujan, MS, Metric dimension of bounded tree-length graphs, SIAM J. Discrete Math., 31, 2, 1217-1243 (2017) · Zbl 1371.68103 · doi:10.1137/16M1057383
[2] Ben-Haim, Y.; Gravier, S.; Lobstein, A.; Moncel, J., Adaptive identification in graphs, J. Comb. Theory Ser. A, 115, 7, 1114-1126 (2008) · Zbl 1183.94063 · doi:10.1016/j.jcta.2007.12.009
[3] Bensmail, J., Mazauric, D., Mc Inerney, F., Nisse, N., Pérennes, S.: Sequential metric dimension. In: Proceedings of the 16th Workshop on Approximation and Online Algorithms, WAOA 2018, Lecture Notes in Computer Science, vol. 11312, Springer, pp. 36-50 (2018) · Zbl 1459.05208
[4] Bosek, B.; Gordinowicz, P.; Grytczuk, J.; Nisse, N.; Sokól, J.; Sleszynska-Nowak, M., Centroidal localization game, Electron. J. Comb., 25, 4, P4.62 (2018) · Zbl 1406.05068 · doi:10.37236/7488
[5] Bosek, B.; Gordinowicz, P.; Grytczuk, J.; Nisse, N.; Sokól, J.; Sleszynska-Nowak, M., Localization game on geometric and planar graphs, Discrete Appl. Math., 251, 30-39 (2018) · Zbl 1401.05195 · doi:10.1016/j.dam.2018.04.017
[6] Brandt, A.; Diemunsch, J.; Erbes, C.; LeGrand, J.; Moffatt, C., A robber locating strategy for trees, Discrete Appl. Math., 232, 99-106 (2017) · Zbl 1372.05138 · doi:10.1016/j.dam.2017.07.019
[7] Carraher, JM; Choi, I.; Delcourt, M.; Erickson, LH; West, DB, Locating a robber on a graph via distance queries, Theor. Comput. Sci., 463, 54-61 (2012) · Zbl 1258.91041 · doi:10.1016/j.tcs.2012.06.035
[8] Díaz, J.; Pottonen, O.; Serna, MJ; van Leeuwen, EJ, Complexity of metric dimension on planar graphs, J. Comput. Syst. Sci., 83, 1, 132-158 (2017) · Zbl 1350.68119 · doi:10.1016/j.jcss.2016.06.006
[9] Foucaud, F.; Klasing, R.; Slater, PJ, Centroidal bases in graphs, Networks, 64, 2, 96-108 (2014) · Zbl 1386.05046 · doi:10.1002/net.21560
[10] Foucaud, F.; Mertzios, GB; Naserasr, R.; Parreau, A.; Valicov, P., Identification, location-domination and metric dimension on interval and permutation graphs. i. Bounds, Theor. Comput. Sci., 668, 43-58 (2017) · Zbl 1358.05216 · doi:10.1016/j.tcs.2017.01.006
[11] Foucaud, F.; Mertzios, GB; Naserasr, R.; Parreau, A.; Valicov, P., Identification, location-domination and metric dimension on interval and permutation graphs. II. Algorithms and complexity, Algorithmica, 78, 3, 914-944 (2017) · Zbl 1371.05212 · doi:10.1007/s00453-016-0184-1
[12] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to NP-Completeness (1979), New York: W.H Freeman and Company, New York · Zbl 0411.68039
[13] Harary, F.; Melter, RA, On the metric dimension of a graph, Ars Comb., 2, 191-195 (1976) · Zbl 0349.05118
[14] Sepp, H., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Proceedings of the 28th Conference on Computational Complexity, CCC, IEEE Computer Society, pp. 266-276 (2013)
[15] Haslegrave, J.; Johnson, RAB; Koch, S., Locating a robber with multiple probes, Discrete Math., 341, 1, 184-193 (2018) · Zbl 1372.05140 · doi:10.1016/j.disc.2017.08.028
[16] Karpovsky, MG; Chakrabarty, K.; Levitin, LB, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory, 44, 2, 599-611 (1998) · Zbl 1105.94342 · doi:10.1109/18.661507
[17] Seager, SM, Locating a robber on a graph, Discrete Math., 312, 22, 3265-3269 (2012) · Zbl 1250.91020 · doi:10.1016/j.disc.2012.07.029
[18] Seager, SM, A sequential locating game on graphs, Ars Comb., 110, 45-54 (2013) · Zbl 1313.05099
[19] Seager, SM, Locating a backtracking robber on a tree, Theor. Comput. Sci., 539, 28-37 (2014) · Zbl 1358.05189 · doi:10.1016/j.tcs.2014.04.019
[20] Slater, P.J.: Leaves of trees. In: Congressus Numerantium, No. XIV, pp. 549-559 (1975) · Zbl 0316.05102
[21] Slater, PJ, Domination and location in acyclic graphs, Networks, 17, 1, 55-64 (1987) · Zbl 0643.90089 · doi:10.1002/net.3230170105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.