0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Thinh D. Nguyen Oct 9 '18 at 16:08
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.