[Solved]: Proving that directed graph diagnosis is NP-hard

ignougroup
Problem Detail: 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=Otimes I$. Now, the problem is whether we can cover all nodes with at most $k$ elements of $D$, i.e. $qquad displaystyle exists,Ssubseteq D, |S|leq k. forall, vin V. exists,(v_1,v_2) in S. v_1 to^* v to^* v_2 $ where $ato^* 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$?

Asked By : user8879

Answered By : Raphael

Reduce from NP-complete SET-COVER instead. Let $S_1,dots,S_m subseteq{1,dots,n}$ with $kinmathbb{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: example
[source]

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/811