Say we have a graph that is similar to a linked list (or a directed acyclic graph). An independent set consists of nodes that don't share edges with any other node in the set. If each node is weighted, how can we calculate the max possible value of the independent set of nodes? I understand we have to use Dynamic Programming so I have a slight clue but I'm hoping someone could explain how they would approach it. Thank you!
1 Answers
3
votes
I believe that this problem is NP-hard for arbitrary directed acyclic graphs. The corresponding problem for undirected graphs is known to be NP-hard, and that problem can be converted into the directed version of the problem by directing all of the edges in a way that makes the resulting graph a DAG. Any independent set in the original graph will be an independent set in the directed graph and vice-versa, so any solution to the directed case will solve the undirected case.
Your question talks about solving this problem on a linked list. If you're solving the problem just for linked lists, there is a polynomial-time solution using dynamic programming. As a hint, if you choose one node in the linked list, you have to skip the next node, then should maximize what remains. If you don't choose the node, you just maximize the value of the rest of the list. Taking the better of these two options and evaluating this bottom-up will give you a really fast DP algorithm.
Hope this helps!
