# 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. Oct 9, 2018 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.