Return to Answer

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 $x$'s vertices and $dst$ with incoming arcs from all $x$'s 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.

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.

This is $NP$-complete by tweaking Yuval's reduction.

We reduce from E3SAT like his reduction with a small modification that we are allowed to leave at most one clause unsatisfied.

So, for each edge $(C_i,l)(C_j,l')$ where $i<j \land l\neq\lnot l$, we have an arc $((C_i,l),(C_j,l'))$ (i.e. originates from $(C_i,l)$, ends in $(C_j,l')$). In other word, we orient each edge according to its endpoints clauses $C_i$ and $C_j$ such that $i<j$.

Now, for every pair of vertices $u=(C_i,l)$, $v=(C_j,l')$ in the undirected graph, if $dist(u,v)=2$ then we have $dist(u,v)=2$ also in our digraph, but not necessarily $dist(v,u)=2$.

To guarantee that each equidistant set in the undirected graph is also an equidistant set in our being constructed digraph, for each pair of vertices $u,v$ that $dist(u,v)=2$, we create a new verex $x_{uv}$ and add 2 arcs $(v,x_{uv})$, $(x_{uv},u)$. This guarantees that $dist(v,u)=2$.

Finally, add two vertices $src$ with outgoing arcs to all $(C_i,.)$ vertices and $dst$ with incoming arcs from all $(C_i,.)$ vertices. Add $x_{src,dst}$ with two arcs similarly.

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>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 $u$. And, to reach $x_{uv}$ in one step, you must go from $v$. So, all the vertices that can be reached from $x_{uv}$ in two steps must have the form $(C_k,l'')$ where $i<k<j$ and $l''\neq\lnot l$ and $l''\neq \lnot l'$. That means we cannot have any other $x_{uv}$ vertex in our set. This is also true for $x_{src,dst}$. So, we can still satisfy at least $m-1$ clauses.

Conversely, if we have an assignment satisfying $m-1$ clauses, then first take the corresponding vertex set, i.e. all the vertices $u=(C_i,l)$ where literal $l$ satisfies clause $C_i$. Then add $x_{src,dst}$ to this set to form an $m$-equidistant set.

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 $x$'s vertices and $dst$ with incoming arcs from all $x$'s 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.

This is $NP$-complete by tweaking Yuval's reduction.

We reduce from E3SAT like his reduction with a small modification that we are allowed to leave at most one clause unsatisfied.

So, for each edge $(C_i,l)(C_j,l')$ where $i<j \land l\neq\lnot l$, we have an arc $((C_i,l),(C_j,l'))$ (i.e. originates from $(C_i,l)$, ends in $(C_j,l')$). In other word, we orient each edge according to its endpoints clauses $C_i$ and $C_j$ such that $i<j$.

Now, for every pair of vertices $u=(C_i,l)$, $v=(C_j,l')$ in the undirected graph, if $dist(u,v)=2$ then we have $dist(u,v)=2$ also in our digraph, but not necessarily $dist(v,u)=2$.

To guarantee that each equidistant set in the undirected graph is also an equidistant set in our being constructed digraph, for each pair of vertices $u,v$ that $dist(u,v)=2$, we create a new verex $x_{uv}$ and add 2 arcs $(v,x_{uv})$, $(x_{uv},u)$. This guarantees that $dist(v,u)=2$.

It is also necessary to manipulate the case of having some $x_{uv}$ vertex in an equidistant set. But, this is impossible (as long as $k=m>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 $u$. And, to reach $x_{uv}$ in one step, you must go from $v$. So, all the vertices that can be reached from $x_{uv}$ in two steps must have the form $(C_k,l'')$ where $i<k<j$ and $l''\neq\lnot l$ and $l''\neq \lnot l'$. That means we cannot have any other $x_{uv}$ vertex in our set. So, we can still satisfy at least $m-1$ clauses.

Conversely, if we have an assignment satisfying $m-1$ clauses, then in the corresponding vertex set, we have $u=(C_i,.)$ and $v=(C_j,.)$ where $C_i$ is the smallest-indexed satisfied clause and $C_j$ is the largest-indexed satisfied clause. Then add $x_{uv}$ to this set to form an $m$-equidistant set.

This is $NP$-complete by tweaking Yuval's reduction.

We reduce from E3SAT like his reduction with a small modification that we are allowed to leave at most one clause unsatisfied.

So, for each edge $(C_i,l)(C_j,l')$ where $i<j \land l\neq\lnot l$, we have an arc $((C_i,l),(C_j,l'))$ (i.e. originates from $(C_i,l)$, ends in $(C_j,l')$). In other word, we orient each edge according to its endpoints clauses $C_i$ and $C_j$ such that $i<j$.

Now, for every pair of vertices $u=(C_i,l)$, $v=(C_j,l')$ in the undirected graph, if $dist(u,v)=2$ then we have $dist(u,v)=2$ also in our digraph, but not necessarily $dist(v,u)=2$.

To guarantee that each equidistant set in the undirected graph is also an equidistant set in our being constructed digraph, for each pair of vertices $u,v$ that $dist(u,v)=2$, we create a new verex $x_{uv}$ and add 2 arcs $(v,x_{uv})$, $(x_{uv},u)$. This guarantees that $dist(v,u)=2$.

Finally, add two vertices $src$ with outgoing arcs to all $(C_i,.)$ vertices and $dst$ with incoming arcs from all $(C_i,.)$ vertices. Add $x_{src,dst}$ with two arcs similarly.

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>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 $u$. And, to reach $x_{uv}$ in one step, you must go from $v$. So, all the vertices that can be reached from $x_{uv}$ in two steps must have the form $(C_k,l'')$ where $i<k<j$ and $l''\neq\lnot l$ and $l''\neq \lnot l'$. That means we cannot have any other $x_{uv}$ vertex in our set. This is also true for $x_{src,dst}$. So, we can still satisfy at least $m-1$ clauses.

Conversely, if we have an assignment satisfying $m-1$ clauses, then first take the corresponding vertex set, i.e. all the vertices $u=(C_i,l)$ where literal $l$ satisfies clause $C_i$. Then add $x_{src,dst}$ to this set to form an $m$-equidistant set.