# Proving that directed graph diagnosis is NP-hard

I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and constructing a reduction from that problem to the following problem I'll call DGD (directed graph diagnosis).

### Problem

An instance of DGD $$(V,E,k)$$ consist of vertices $$V = I \overset{.}{\cup} O \overset{.}{\cup} B$$, directed edges $$E$$ and a positive integer $$k$$. There are three types of vertices: vertices with only incoming edges $$I$$, vertices with only outgoing edges $$O$$ and vertices with both incoming and outgoing edges $$B$$. Let furthermore $$D=O\times I$$.

Now, the problem is whether we can cover all nodes with at most $$k$$ elements of $$D$$, i.e.

$$\qquad \displaystyle \exists\,S\subseteq D, |S|\leq k.\ \forall\, v\in V.\ \exists\,(v_1,v_2) \in S.\ v_1 \to^* v \to^* v_2$$

where $$a\to^* b$$ means that there is a directed path from $$a$$ to $$b$$.

I think that the Dominating Set problem is the one I should be reducing from, because this too is concerned about covering a subset of nodes with another subset. I tried creating a DGD instance by first creating two nodes for each element of the dominating set, copying all edges, and then setting the $$k$$ of the DGD instance equal to that of the DS instance.

Suppose a simple DS-instance with nodes $$1$$, $$2$$ and $$3$$ and edges $$(1,2)$$ and $$(1,3)$$. This is a yes-instance with $$k = 1$$; the dominating set in this case consists of only node $$1$$. Reducing with the method just described, this would lead to a DGD instance with two paths $$(1 \to 2 \to 1')$$ and $$(1 \to 3 \to 1')$$; to cover all nodes, just one pair $$(1, 1')$$ would be sufficient. This would have worked perfectly, were it not for the fact that the dominating set of the DS-instance cannot, of course, be determined in polynomial time, which is a requirement here.

I have found that there are many good-looking ways to transform the edges and vertices when reducing, but my problem is somehow expressing DGD's $$k$$ in terms of DS's $$k$$. Dominating Set seemed a fitting problem to reduce from, but because of this I think that maybe I should try to reduce from a problem that has no such $$k$$?

• Welcome! I tried to clarify the problem statement; is this how you meant it? Btw, you might want to choose a more recognisable username than "user8879". :) – Raphael Mar 27 '12 at 8:22
• Yes, thanks, this is indeed a more compact version. – user8879 Mar 27 '12 at 8:36

Let $S_1,\dots,S_m \subseteq\{1,\dots,n\}$ with $k\in\mathbb{N}$ an instance of set cover. Define an instance $(V,E,k')$ of DGD like this:

• $V= \{s_1,\dots,s_m,o_1,\dots,o_m,e_1,\dots,e_n,o\}$
• $E= \{(s_i,o_i) \mid i = 1,\dots,n \} \cup \{(s_i,e_j)\mid j \in S_i\} \cup\{(e_j,o)\mid j=1,\dots,n\}$
• $k' = m + k$

It is easy to see that the constructed DGD instance has a positive answer if and only if the given set cover instance has a positive answer. In particular, all $m$ pairs $(s_i,o_i)$ have to be chosen no matter what in order to cover all $o_i$; then $k$ of the $m$ pairs $(s_i,o)$ have to cover all the $e_j$, and the first components of those chosen are the solution of the SET-COVER instance. If no such choice is possible the SET-COVER instance has no solution as well.

As the construction is possible in polynomial time, this proves SET-COVER $\leq_p$ DGD.

As an example,consider the example set cover instance given on Wikipedia, namely $\{1,2,3,4,5\}$ and sets $S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$. This translates to the following graph:

[source]

• This is almost correct, in that I and B are indeed covered completely, but O is not. The set-cover instance is a yes-instance for k = 2, but in the DGD instance k = 2 leaves s2 and s3 uncovered. I think that this can probably be solved by automatically adding an edge from each node in O to o. – user8879 Mar 27 '12 at 10:52
• @user8879: Oh damn, right. The way the problem is posed now, edges $(s_i,o)$ won't fix it because in order to cover $s_i$ you need at least one pair containing it in $S$. – Raphael Mar 27 '12 at 12:54
• Got it now: create an additional node in B for each node in O, then link it to it's corresponding node in O and to o. In this example you get four extra paths (s1 -> s1' -> o, etc.). Finally, after increasing k with four it should be complete. – user8879 Mar 27 '12 at 13:03
• @user8879: Fixed it now. We need some additional nodes that enfore that all $s_i$ are covered, but we remain polynomial in size. (Oh, you commented while I was fixing, well done.) – Raphael Mar 27 '12 at 13:09