On optimal approximability results for computing the strong metric dimension
| Autor: | DasGupta, Bhaskar, Mobasheri, Nasim |
|---|---|
| Rok vydání: | 2014 |
| Předmět: | |
| Zdroj: | Discrete Applied Mathematics, 221, 18-24, 2017 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.dam.2016.12.021 |
| Popis: | The strong metric dimension of a graph was first introduced by Seb\"{o} 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\big(2^{\,0.287\,n}\big)$-time exact computation algorithm, admits a $O\big(1.2738^k+n\,k\big)$-time exact computation algorithm if the strong metric dimension is at most $k$, does not admit a polynomial time $(2-\varepsilon)$-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time $(10\sqrt{5}-21-\varepsilon)$-approximation algorithm assuming P$\neq$NP, does not admit a $O^\ast\big(2^{o(n)}\big)$-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a $O^\ast\big(n^{o(k)}\big)$-time exact computation algorithm if the strong metric dimension is at most $k$ assuming the exponential time hypothesis is true. Comment: revised version based on reviewer comments; to appear in Discrete Applied Mathematics |
| Databáze: | arXiv |
| Externí odkaz: |
|