How to find the maximum independent set of a directed acyclic graph?
Let's say we have a graph that looks like a linked list (or directed acyclic graph). An independent set consists of nodes that do not share edges with any other node in the set. If each node is weighted, how can we calculate the maximum possible value of an independent set of nodes? I understand that we have to use dynamic programming, so I have a little hint, but I hope someone can explain how they approach it. Thank!
source to share
I believe this problem is NP-hard for arbitrarily directed acyclic graphs. The corresponding problem for undirected graphs is known as NP-hard, and this problem can be transformed into a directed version of the problem by directing all edges so that the resulting graph is 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 is about solving this problem in a linked list. If you are only solving the problem for linked lists, there is a multi-term solution using dynamic programming. As a hint, if you select one node in the linked list, you need to skip the next node and then maximize what's left. If you didn't select node, you just increment the value of the rest of the list. When you consider these two options and evaluate this from the bottom up, you get a really fast DP algorithm.
Hope this helps!
source to share