What is the fastest known algorithm for max flow on dags? Can there be a linear-time algorithm running in time $O(|V|+|E|)$?

Input: a weighted dag $G=(V,E,w)$ where $E$ is given as an edge list $E$ and $w$ is the edge weight function; and two vertices $s$ and $t$.

Output: a max flow from $s$ to $t$.

The dag is simple (no loops, no parallel edges). Edge weights are positive integers.

  • 11
    $\begingroup$ Bipartite matching can be reduced to max-flow on a DAG(in linear time). So unless bipartite matching have a linear time solution, there is no linear time algorithm for max-flow on DAGs. $\endgroup$
    – Chao Xu
    Jul 20 '15 at 14:41
  • $\begingroup$ @ChaoXu convert you comment to an answer? $\endgroup$ Jul 20 '15 at 16:05
  • $\begingroup$ I understand now. Taking the wiki graph example, I can see for a particular case why a linear time algorithm won't work. $\endgroup$
    – goelakash
    Jul 21 '15 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.