SebiSebi's blog

Minimum path cover in DAG
By SebiSebi, 10 years ago, In English

Hello!

I'm trying to understand how the algorithm for finding the minimum path cover in DAG works. I read the description from here: http://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph . Can someone explain to me the idea behind this algorithm and why it outputs the right answer?

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

Comments Comments (11)
| Write comment?
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The phrase "to split a DAG into paths" means "to leave at most one incoming and one outcoming edge for each vertex".

If we add an edge to the answer, we merge two paths into one.

Maximum matching algorithm tries to take as many edges as possible, while not violating the rule of one incoming and one outcoming edge.

And that's all.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But why "to split a DAG into paths" means "to leave at most one incoming and one outcoming edge for each vertex"? For instance, in the second graph from this page http://stackoverflow.com/questions/10783473/minimum-path-cover-in-directed-acyclic-graph there are more incoming and outcoming edges for a vertex for the path 1-2-3-4-5.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Every node should belong to exactly one path. Initially there N one-node paths. The more edges you add, the less paths you will get eventually.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You contradict yourself. By definition, a directed path is a sequence of edges where each pair of consecutive edges share a vertex and all edges have the same direction.

      And I'll remind you that in the problem we're discussing now we cover the DAG with vertex-disjoint paths. Covering a DAG with edge-disjoint paths is much easier in fact (it's solvable by a greedy algo).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you describe the solution in case when paths are edge-disjoint more detailed?

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          This problem is too easy for you to solve it yourself :).

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Cool! You're right, that's really simple.

            → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            This is correct for the case when you want to cover all the edges of the DAG with edge-disjoint paths. I thought that you were referring to the original requirement, i.e. cover all the nodes of the DAG, but with edge-disjoint paths. Anyway, this version of the problem is also solvable — my idea uses max-flow with lower capacities in the nodes of the DAG + binary search.

            → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            could you please explain more the greedy solution to problem of the edge — disjoint paths ?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Let's take an arbitrary vertex v and look at all of its incoming edges. We know that all of them will lie on some paths (we don't care about where will these paths start and how do they really look like). So, vertex v has degin[v] incoming paths. Now we want to continue some of them. For this purpose we can use edges that come out from vertex V, and continue incoming paths in arbitrary way. Now we have two cases:

              1. degin[v] ≥ degout[v]. This means that all edges coming out of v will be used to continue incoming paths.
              2. degin[v] < degout[v]. We will have to create degout[v] - degin[v] new paths starting at vertex v.

              That's all.

              → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe this could be useful:

http://code.google.com/codejam/contest/dashboard?c=204113#s=a&a=2

(:

→ Reply