Блог пользователя start_over

Автор start_over, история, 17 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
17 месяцев назад, # |
Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      17 месяцев назад, # ^ |
      Rev. 5   Проголосовать: нравится +12 Проголосовать: не нравится

      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.