# Karp hardness of an equidistant set in digraph

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)$$.

• Using Yuval's reduction, if we replace each edge by two opposite arcs then we are done. So, the interesting case is when we require the digraph to be oriented graph. – Thinh D. Nguyen Oct 9 '18 at 16:08

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.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.