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.

• Welcome to CS.SE! How do you know that if there is no size-$w$ edge cover, then there is no size-$w$ watch set? That doesn't look right to me. I don't see any way to construct a size-$w$ edge cover from a size-$w$ watch set (naively it seems you need to include all edges $(u,v)$ such that $u \in W$, and a single vertex might have many edges out of it, so the size of the edge cover might be much larger than $w$). Am I missing something obvious? – D.W. Apr 28 '17 at 6:07

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:

1. Set $G_0 \leftarrow G$ and $w_0\leftarrow w$.
2. 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.
3. 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.

Your problem is equivalent to dominating set for directed graphs. The dominating set problem is known to be NP-hard. The standard proof shows that dominating set is NP-hard for undirected graphs; it follows that it is hard for directed graphs, too, if we simply focus on directed graphs where $(u,v)$ is an edge iff $(v,u)$ is an edge. Consequently, you shouldn't expect an algorithm that will have worst-case polynomial running time and will work on all possible graphs.

• Somehow, I'm expected to prove the claim that this decision problem can be decided in polynomial time, but your reasoning seems pretty convincing. Does the constraint that $w \geq n/2$ and the fact that every vertex appears in at least one edge make the decision problem any easier, as opposed to the more general decision problem of deciding whether for some $w \geq 0$ (i.e., $w$ is not constrained), an arbitrary directed graph G has a watch set of size $w$? – R. Potts Apr 28 '17 at 7:13
• @R.Potts Every vertex having at least one edge doesn't make any difference. If you had isolated vertices, you'd have to put them in your cover, so you can easily preprocess to the situation where there are no isolated vertices. – David Richerby Apr 28 '17 at 10:29
• @R.Potts, can you give us more context? Who told you to decide it in polynomial time? Where did you encounter this problem? Is it an exercise? Is it from a book? If so, can you edit the question to give a full reference to the book and where the exercise appears? Can you give an excerpt (a quote) from the source of the problem? – D.W. Apr 28 '17 at 13:53
• @D.W. This comes from a set of practice problems in a course I'm taking. Verbatim, the problem asks, "show we are able to decide, in polynomial time, whether G has a size-$w$ watch set whenever $w \geq n/2$ and every vertex is in at least one edge. Explain how this doesn't contradict what you concluded about the NP-completeness of the general form of the problem." By general form, it means when $w$ isn't restricted to be at least $n/2$. – R. Potts Apr 28 '17 at 14:28