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

<p><strong>Input</strong>: 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$.  </p>

<p><strong>Output</strong>: a max flow from $s$ to $t$.</p>

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

CC BY-SA 3.0
2015-07-20T14:41:21.833Z
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
CC BY-SA 3.0
2015-07-20T16:05:03.207Z
@ChaoXu convert you comment to an answer?
Sasho Nikolov
CC BY-SA 3.0
2015-07-21T12:52:57.600Z
I understand now. Taking the wiki graph example, I can see for a particular case why a linear time algorithm won't work.
goelakash
<ds.algorithms><directed-acyclic-graph><max-flow>
Is there a linear-time algorithm for max flow on dags
goelakash
# Is there a linear-time algorithm for max flow on dags

(Asked by: username_0 on 2015-07-20)

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.

**Tags:** ds.algorithms, directed-acyclic-graph, max-flow
> **Comments:**
> **username_1**: 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.  
> **username_2**: @ChaoXu convert you comment to an answer?  
> **username_0**: I understand now. Taking the wiki graph example, I can see for a particular case why a linear time algorithm won't work.  

---

## 0 answers

