  Numerous problems consisting in identifying vertices in graphs using
distances are useful in domains such as network verification and graph
isomorphism. Unifying them into a meta-problem may be of main interest. We
introduce here a promising solution named Distance Identifying Set. The model
contains Identifying Code (IC), Locating Dominating Set (LD) and their
generalizations $r$-IC and $r$-LD where the closed neighborhood is considered
up to distance $r$. It also contains Metric Dimension (MD) and its refinement
$r$-MD in which the distance between two vertices is considered as infinite if
the real distance exceeds $r$. Note that while IC = 1-IC and LD = 1-LD, we have
MD = $\infty$-MD; we say that MD is not local
  In this article, we prove computational lower bounds for several problems
included in Distance Identifying Set by providing generic reductions from
(Planar) Hitting Set to the meta-problem. We mainly focus on two families of
problem from the meta-problem: the first one, called bipartite gifted local,
contains $r$-IC, $r$-LD and $r$-MD for each positive integer $r$ while the
second one, called 1-layered, contains LD, MD and $r$-MD for each positive
integer $r$. We have:
  - the 1-layered problems are NP-hard even in bipartite apex graphs,
  - the bipartite gifted local problems are NP-hard even in bipartite planar
graphs,
  - assuming ETH, all these problems cannot be solved in $2^{o(\sqrt{n})}$ when
restricted to bipartite planar or apex graph, respectively, and they cannot be
solved in $2^{o(n)}$ on bipartite graphs,
  - even restricted to bipartite graphs, they do not admit parameterized
algorithms in $2^{O(k)}.n^{O(1)}$ except if W[0] = W[2]. Here $k$ is the
solution size of a relevant identifying set.
  In particular, Metric Dimension cannot be solved in $2^{o(n)}$ under ETH,
answering a question of Hartung in 2013.
