Karp hardness of an equidistant set in digraph

Question

Following the success of the undirected version:

Karp hardness of an equidistant vertex set

Inspired by the success of this long ago question:

NP-hardness of problem with indices and subsets

We move on asking for the hardness of the directed version of an equidistant set.

Input: A directed graph $G(V, A)$ and a natural number $k$

Output: YES if $G$ has an equidistant vertex set of size $k$, otherwise NO

In this problem, we disallow opposite arcs like $(u,v)$ and $(v,u)$ to be both present in the arc set, i.e. either one of them or none.

$\DeclareMathOperator{\dist}{dist}$An equidistant vertex set is a set of vertices $V'\subseteq V$ such that for every two ordered pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$. Note that in digraph, it is possible that $dist(u,v)\neq dist(v,u)$.

Answer 1

This is $NP$-complete by reducing from the undirected version which was proven hard by Yuval's reduction.

For every pair of vertices $u$, $v$ in the undirected graph, if $dist(u,v)=2$ then we create two new vertices $x_{uv}$, $x_{vu}$ and add 4 arcs $(u,x_{uv})$, $(x_{uv},v)$, $(v,x_{vu})$, $(x_{vu},u)$. This guarantees that $dist(u,v)=dist(v,u)=2$ in our digraph.

Finally, add two vertices $src$ with outgoing arcs to all original vertices and $dst$ with incoming arcs from all original vertices. Add $x_{src,dst}$ with two arcs similarly. Note that we do not have the opposite direction of $x_{dst,src}$.

Now set $k=m+1$.

It is necessary to manipulate the case of having some $x_{uv}$ vertex in an equidistant set. But, this is impossible (as long as $k=m+1>4$ like in Yuval's reduction). To see this, suppose that $x_{uv}$ is included in some equidistant set. Clearly, from $x_{uv}$ going out, in one step, you must end at $v$. And, to reach $x_{uv}$ in one step, you must go from $u$. So, there cannot be any vertex within distance 2 (in both directions) of $x_{uv}$, except for $x_{vu}$. So, our equidistant set can be of size only $2<m$.That means we cannot have any $x_{uv}$ vertex in our set. If instead we have $x_{src,dst}$ in our set, we can easily see that there cannot be any other $x_{uv}$ in our set. In all cases, we still have at least $m+1-1=m$-equidistant set without any $x_{uv}$ vertices.

Conversely, if we have an $m$-equidistant set in the undirected graph, then we can add $x_{src,dst}$ to this set to form an $m+1$-equidistant set.