Auto comment: topic has been updated by start_over (previous revision, new revision, compare).

The problem wants the largest antichain in the poset defined by the transitive closure of the DAG (so we assume that the graph is the transitive closure of itself — this can be done in $$$O(VE)$$$). You can show that it is the size of the min-cut in the graph defined as follows: the vertex set consists of a source $$$s$$$ and a sink $$$t$$$, every vertex $$$v$$$ in the DAG corresponds to two vertices $$$v_1, v_2$$$, there are edges $$$(s, v_1)$$$ and $$$(v_2, t)$$$, and for any $$$(u, v)$$$ in the DAG, there is an edge $$$(u_1, v_2)$$$. All edges have capacity $$$1$$$. Since this is a unit network, finding the max flow using Dinic will be $$$O(E \sqrt{V})$$$, and recovering the min cut can be done in linear time. So the overall complexity is $$$O(VE + V^{2.5})$$$.