Is this NP-hard? I cannot prove it.

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.

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.

StackExchange Computer Science Q#19051, answer score: 6