  Given a connected graph $G=(V,E)$, a set $S\subseteq V$ is a $k$-metric
generator for $G$ if for any two different vertices $u,v\in V$, there exist at
least $k$ vertices $w_1,...,w_k\in S$ such that $d_G(u,w_i)\ne d_G(v,w_i)$ for
every $i\in \{1,...,k\}$. A metric generator of minimum cardinality is called a
$k$-metric basis and its cardinality the $k$-metric dimension of $G$. We study
some problems regarding the complexity of some $k$-metric dimension problems.
For instance, we show that the problem of computing the $k$-metric dimension of
graphs is $NP$-Complete. However, the problem is solved in linear time for the
particular case of trees.
