11
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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". :) $\endgroup$
    – Raphael ♦
    Mar 27, 2012 at 8:22
  • $\begingroup$ Yes, thanks, this is indeed a more compact version. $\endgroup$
    – user8879
    Mar 27, 2012 at 8:36

1 Answer 1

Reset to default
9
$\begingroup$

Reduce from NP-complete SET-COVER instead.

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:

example
[source]

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – user8879
    Mar 27, 2012 at 10:52
  • $\begingroup$ @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$. $\endgroup$
    – Raphael ♦
    Mar 27, 2012 at 12:54
  • $\begingroup$ 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. $\endgroup$
    – user8879
    Mar 27, 2012 at 13:03
  • $\begingroup$ @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.) $\endgroup$
    – Raphael ♦
    Mar 27, 2012 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.