×

Approximation complexity of metric dimension problem. (English) Zbl 1247.68100

Summary: We study the approximation complexity of the metric dimension problem in bounded degree, dense as well as in general graphs. For the general case, we prove that the metric dimension problem is not approximable within \((1-\epsilon) \ln n\) for any \(\epsilon >0\), unless \(\mathrm{NP} \subseteq \mathrm{DTIME}(n^{\log\log n})\), and we give an approximation algorithm which matches the lower bound.
Even for bounded degree instances it is APX-hard to determine (compute) the value of the metric dimension which we prove by constructing an approximation preserving reduction from the bounded degree vertex cover problem.
The special case, in which the underlying graph is superdense turns out to be APX-complete. In particular, we present a greedy constant factor approximation algorithm for this kind of instances and construct an approximation preserving reduction from the bounded degree dominating set problem. We also provide the first explicit approximation lower bounds for the metric dimension problem restricted to dense and bounded degree graphs.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beerliova, Z.; Eberhard, F.; Erlebach, T.; Hall, A.; Hoffmann, M.; Mihalák, M.; Ram, L., Network discovery and verification, IEEE J. Sel. Area Comm., 24, 2168-2181 (2006)
[2] Berman, P.; DasGupta, B.; Kao, M., Tight approximability results for test set problems in bioinformatics, J. Comput. System Sci., 71, 145-162 (2005) · Zbl 1076.68113
[3] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I.; Puertas, M.; Seara, C.; Wood, D., On the Metric Dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21, 423-441 (2007) · Zbl 1139.05314
[4] Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I.; Puertas, M., On the Metric Dimension of Infinite Graphs, Electron. Notes Discrete Math., vol. 35 (2009), pp. 15-20 · Zbl 1268.05140
[5] Chappell, G.; Gimbel, J.; Hartman, C., Bounds on the metric and partition dimensions of a graph, Ars Combin., 88, 349-366 (2008) · Zbl 1224.05133
[6] Chartrand, G.; Eroh, L.; Johnson, M.; Oellermann, O., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 99-133 (2000) · Zbl 0958.05042
[7] Chlebík, M.; Chlebíková, J., Complexity of approximating bounded variants of optimization problems, Theoret. Comput. Sci., 354, 320-338 (2006) · Zbl 1105.90110
[8] Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems in bounded degree graphs, Inform. and Comput., 206, 1264-1275 (2008) · Zbl 1169.68037
[9] Chvátal, V., Mastermind, Combinatorica, 3, 325-329 (1983) · Zbl 0717.05002
[10] Fehr, M.; Gosselin, S.; Oellermann, O., The metric dimension of Cayley digraphs, Discrete Math., 306, 31-41 (2006) · Zbl 1085.05034
[11] Garey, M.; Johnson, D., Computers and Intractability: A Guide to the Theory on NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[12] Halldórsson, B.; Halldórsson, M.; Ravi, R., On the approximability of the minimum test collection problem, (Proc. 9th ESA 2001. Proc. 9th ESA 2001, LNCS, vol. 2161 (2001)), 158-169 · Zbl 1006.68958
[13] Harary, F.; Melter, R., On the Metric Dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118
[14] Hernando, C.; Mora, M.; Pelayo, I.; Seara, C.; Wood, D., Extremal graph theory for metric dimension and diameter, Electron. Notes Discrete Math., 29, 339-343 (2007) · Zbl 1341.05132
[15] M. Karpinski, W. Schudy, Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems, in: Proc. 41st ACM STOC 2009, pp. 313-322.; M. Karpinski, W. Schudy, Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems, in: Proc. 41st ACM STOC 2009, pp. 313-322. · Zbl 1304.68218
[16] M. Karpinski, A. Zelikovsky, Approximating dense cases of covering problems, in: Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, 1997, pp. 169-178; also published in ECCC TR97-004, 1997.; M. Karpinski, A. Zelikovsky, Approximating dense cases of covering problems, in: Proc. DIMACS Workshop on Network Design: Connectivity and Facilities Location, 1997, pp. 169-178; also published in ECCC TR97-004, 1997. · Zbl 0896.68078
[17] Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 217-229 (1996) · Zbl 0865.68090
[18] B. Manthey, Approximability of cycle covers and smoothed analysis of binary search trees, Doctoral thesis, University of Lübeck, 2005.; B. Manthey, Approximability of cycle covers and smoothed analysis of binary search trees, Doctoral thesis, University of Lübeck, 2005. · Zbl 1173.68457
[19] Sebö, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 383-393 (2004) · Zbl 1082.05032
[20] Shapiro, H.; Söderberg, S., A combinatory detection problem, Amer. Math. Monthly, 70, 1066-1070 (1963) · Zbl 0123.00205
[21] Slater, P., Leaves of trees, Southeastern Conf. on Combin., Graph Theory, and Comp.. Southeastern Conf. on Combin., Graph Theory, and Comp., Congr. Numer., 14, 549-559 (1975)
[22] Slater, P., Dominating and reference sets in graphs, J. Math. Phys. Sci., 22, 445-455 (1988) · Zbl 0656.05057
[23] Tomescu, I., Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math., 308, 5026-5031 (2008) · Zbl 1184.05033
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.