Given a DAG (V, E), find the maximum subset V' of V so that every vertex in V' can't reach other vertices in V'. |V| <= 3000, |E| <= 20000
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
Given a DAG (V, E), find the maximum subset V' of V so that every vertex in V' can't reach other vertices in V'. |V| <= 3000, |E| <= 20000
Name |
---|
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})$$$.
I'm not sure if this is the correct solution or not. For the DAG with no edge, the answer is |V|, but the min-cut for graph created by your solution is 0.
My bad, I had intended to write the complement of the min cut in some sense instead of the min cut. The vertices that form an antichain are the vertices $$$v$$$ such that $$$v_1$$$ and $$$v_2$$$ are in different partitions of the cut. Hopefully this clears the confusion.