On the Hardness of Strong Metric Dimension

Abstract

Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to \emph{strongly resolve} \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the \textsc{Strong Metric Dimension} problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that \textsc{Strong Metric Dimension} is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.