I am wondering if Maximum Independent Set on DAG is NP-Complete problem. I know that if the graph is undirected then it is an NP-Complete, but what about DAGs.. Please help by a proof..