Time complexity of art gallery-like problem

Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ such that every vertex in $G$ is being "watched" by some watchman. More formally, we'd like to decide whether there exists a $w$-sized watch set $W \subseteq V$ (with $|W| = w$) such that for any vertex $v \in V$, either $v \in W$ or there exists a (directed) edge in $E$ of the form $(u, v)$, with $u \in W$.

I'd like devise a deterministic polynomial time algorithm for deciding whether, for a given $w \geq n/2$, where $n$ is the number of vertices in $G$, $G$ has a $w$-sized watch set $W \subseteq V$. So the decision problem would be $\{\langle G, w \rangle : w \geq n/2 \mbox{ and } G \mbox{ has a size } w \mbox{ watch set} \}$.

One approach I'm considering is finding, in polynomial time, a minimum edge covering for $G$. If the size of this edge covering is strictly larger than $w$, then we know a size-$w$ watch set does not exist; otherwise we can easily construct a watch set from this edge covering. However, the polynomial time edge-covering algorithms I've seen are a bit complicated, so I'm looking for a simpler approach.

Your problem is a special case of finding a dominating set of size at most $w$ for directed graphs $G$, where we require that there are no isolated vertices in $G=(V,E)$ and that $w\geq |V|/2$.

Unfortunately, this problem is still NP-hard, since there is a polynomial time reduction from the general directed dominating set problem:

Given an arbitrary directed graph $G=(V,E)$ and an integer $w$, construct the instance $(G',w)$ as follows:

• Set $G_0 \leftarrow G$ and $w_0\leftarrow w$.

• Remove all $i$ isolated vertices from $G_0$ and 'place guards on them': $w_0\leftarrow w_0 - i$. If $w_0\leq 0$, simply construct some instance that yields NO and we're done.

• If $w_0\geq |V|/2$, we are done. Otherwise, 'add two guards' for every cycle we will introduce: $w'\leftarrow w_0+2\cdot(|V_0|-2w_0)$ and add $|V_0|-2w_0$ directed 3-cycles to $G_0$. Set $G'\leftarrow G_0$.

Observe that now $w'\geq |V|/2$, since if we have added the three-cycles, we get $2w'= 2w_0+4(|V_0|-2w_0) \geq |V_0| + 3(|V_0|-2w_0) = |V'|$. The reduced instance is a YES-instance if and only if the original instance is, since 'disconnected' components do not influence the rest of the graph and at least 2 guards are required to watch a 3-cycle.

So a polynomial time algorithm most likely doesn't exist, even for this special case.

StackExchange Computer Science Q#74641, answer score: 3