# Is there a linear-time algorithm for max flow on dags

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.

• 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. – Chao Xu Jul 20 '15 at 14:41
• @ChaoXu convert you comment to an answer? – Sasho Nikolov Jul 20 '15 at 16:05
• I understand now. Taking the wiki graph example, I can see for a particular case why a linear time algorithm won't work. – goelakash Jul 21 '15 at 12:52