11
$\begingroup$

I have a problem and I guess it NP-hard, but I cannot prove it.

Here is a layer graph, where layer 0 is the hignest layer and layer L the lowest.

there are some directed edge between layers, where an edge (A, B) indicates that node A can [cover] node B. And when A can cover B, every node on any path from A to B can cover B, B can cover itself.

Finally here comes a set of node S. I need to choose another set of node ANS, and ensure that for each node q in S, there exists a node p in ANS and p covers q.

For every node there is a cost, and I need to make the total cost of set ANS minimal.

Is this a NP-hard problem? I think so but I cannot prove it.

Could you help me?

Thank you very much.

Improve this question
$\endgroup$
4
  • $\begingroup$ cost of node from the upper layer is more expensive in any path in the graph. $\endgroup$
    – qin.sun
    Commented Dec 16, 2013 at 3:35
  • $\begingroup$ Yes it indeed seems NP hard. Look at the quit similar minimal set cover problem. en.wikipedia.org/wiki/Set_cover_problem $\endgroup$
    – Abhishek Bansal
    Commented Dec 16, 2013 at 5:24
  • $\begingroup$ Is there any restriction in the directed edge, such as the edges only connects a node in higher layer to a node in lower layer? Can I clarify that there can be no edge between nodes in the same layer? $\endgroup$
    – justhalf
    Commented Dec 16, 2013 at 5:31
  • $\begingroup$ @justhalf No, there is no edge between nodes in the same layer. Thank you:) $\endgroup$
    – qin.sun
    Commented Dec 23, 2013 at 4:17

1 Answer 1

Reset to default
6
$\begingroup$

Yes this problem is definitely NP hard. I am posting this answer since you require proof.

If you follow this link http://en.wikipedia.org/wiki/Set_cover_problem, it says that the optimization version of minimal set cover problem is NP-Hard.

The problem in the link:

Given a set of elements {1,2,...,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U = {1, 2, 3, 4, 5} and the set of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1, 2, 3}, {4, 5}}

You can relate this to your problem as follows:

S is the set of nodes that cover at least one node in your input set. This can be found by conducting a DFS on the nodes of input set with the direction of edges reversed.

Now the problem described in the link is a special case of your problem, where the cost of each node is equal and you just want to minimize the number of nodes (sets).

Hence your problem is even more difficult to solve in the general case and hence it is NP Hard.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think this is true with the OP's definition, but he also never specifies whether you can "cover" a node with an edge in the same layer as that node. If that's the case, then the problem seems a bit different. Otherwise, if you can only cover a node via an edge from a higher layer then it indeed seems to be equivalent to set cover optimization $\endgroup$
    – roliu
    Commented Dec 16, 2013 at 5:56
  • $\begingroup$ @roliu How would it matter whether the same layer nodes can be covered or not. The problem as I understand is that we have a directed graph with a path between node A to B means that A covers B. $\endgroup$
    – Abhishek Bansal
    Commented Dec 16, 2013 at 6:01
  • $\begingroup$ Hm, not sure I guess. It's just strange because I don't think almost any of the information in the OP is actually useful. The layers seem irrelevant and so does the transitivity. I'm mostly just waiting for the OP to clarify that he actually meant something different. In particular, you can show that it's not only at least as hard as set cover, it's actually equivalent. Because any minimal covering in the OP's problem will only contain neighboring nodes of his input set S. Maybe there are negative costs or something like that... $\endgroup$
    – roliu
    Commented Dec 16, 2013 at 6:18

Your Answer

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

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