Is this problem NP?

Revision en1, by eidan, 2019-05-24 03:24:29

Hey guys, this quick problem popped into my head:

You are given a DAG, where each node has an integer value (which may be negative). You can choose an arbitrary subset of nodes, as long as this constraint holds: if you pick a node, you also have to pick all nodes reachable from that node. Obtain the maximum possible value sum.

It feels like an NP problem to me, but I couldn't prove it. Anyone heard about it? Any ideas on how to solve it?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English eidan 2019-05-24 03:24:29 466 Initial revision (published)