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.