Karp hardness of a guarding set in digraph

Question

Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.

A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set $S\subseteq V(G)$ is a set of vertices such that:

For each vertex $v\in V(G)$, some of its incoming neighbor $u$ (i.e. $(u,v)\in A(G)$) is included in $S$ (i.e. $u\in S$) and some of its outgoing neighbor $w$ (i.e. $(v,w)\in A(G)$) is included in $S$ (i.e. $w\in S$)

In case of empty incoming neighborhood or empty outgoing neighborhood, the vertex $v$ itself must be included in $S$. In other word, we may think that the incoming neighborhood and outgoing neighborhood of $v$ both include $v$.

Informally, imagine a facility in which one can enter at some entry points and exit at some exit points, a guarding set for this facility needs to be placed at least at some entry point (maybe where one can enter secret area of the facility) and at some exit point (maybe where one can bring out the secrets from the secret areas inside). Hope that this suffices to explain the terminology.

Our problem is now formally defined:

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

Output: YES if $G$ has a guarding set of size $k$, otherwise NO

What is complexity of this problem?

Answer 1

It is NP-complete (it is obviously in NP) by reduction from the dominating set problem.

Given an instance $G=(V,E)$ of the dominating set problem, split each vertex $v$ into two vertices $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$, and for each edge $(u,v)\in E$, construct two edges $(u_{\mathrm{out}},v_{\mathrm{in}})$ and $(v_{\mathrm{out}},u_{\mathrm{in}})$. We claim that $G$ has a dominating set of size $k$ iff the newly-constructed graph (say $G'$) has a guarding set of size $2k$.

If $G$ has a dominating set $S$ of size $k$, easy to see $\{v_{\mathrm{in}}\mid v\in S\}\cup\{v_{\mathrm{out}}\mid v\in S\}$ is a guarding set of $G'$, which has size $2k$.

On the other hand, suppose $G'$ has a guarding set $S'$ of size $2k$. Let $S'_{\mathrm{in}}=S'\cap\{v_{\mathrm{in}}| v\in V\}$ and $S'_{\mathrm{out}}=S'\cap\{v_{\mathrm{out}}\mid v\in V\}$, then either $S'_{\mathrm{in}}$ or $S'_{\mathrm{out}}$ must has size at most $k$. Without loss of generality, say $\left|S'_{\mathrm{in}}\right|\le k$, then $S=\left\{v\mid v_{\mathrm{in}}\in S_{\mathrm{in}}'\right\}$ is a dominating set of $G$. This means $G$ has a dominating set of size $k$.