On optimal approximability results for computing the strong metric dimension

Abstract

The strong metric dimension of a graph was first introduced by Sebö and Tannier (Mathematics of Operations Research, 29(2), 383-393, 2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, 549-559, 1975) and by Harary and Melter (Ars Combinatoria, 2, 191-195, 1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP-complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of $n$ nodes admits a polynomial-time $2$-approximation, admits a $O^{\ast }\left(2^{0.287n}\right)$-time exact computation algorithm, admits a $O(1.2738^k+nk)$-time exact computation algorithm if the strong metric dimension is at most $k$, does not admit a polynomial time $(2-\epsilon )$-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time $(10\sqrt{5}-21-\epsilon )$-approximation algorithm assuming P$\ne$NP, does not admit a $O^{\ast }\left(2^{o(n)}\right)$-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a $O^{\ast }\left(n^{o(k)}\right)$-time exact computation algorithm if the strong metric dimension is at most $k$ assuming the exponential time hypothesis is true.

revised version based on reviewer comments; to appear in Discrete Applied Mathematics

Cited by in corpus (4)

• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• On analyzing and evaluating privacy measures for social networks under active attack
• On Sharp Bounds of Local Fractional Metric Dimension for Certain Symmetrical Algebraic Structure Graphs
• Strong resolving graphs: the realization and the characterization problems