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 iin $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?
