start_over's blog

find the maximum subset vertices of DAG
By start_over, history, 11 months ago, In English

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

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

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})$$$.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 5   Vote: I like it +12 Vote: I do not like it

      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.

      → Reply