# On the Hardness of Strong Metric Dimension

Preprint · Prafullkumar Tale

- Archive id: arxiv:2608.06747
- Published: 2026-08-07
- arXiv: https://arxiv.org/abs/2608.06747
- Source URL: https://arxiv.org/abs/2608.06747
- PDF: https://arxiv.org/pdf/2608.06747
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.