<p>It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are unused, and which form a spanning tree of used but unsaturated edges). Similar arguments apply to minimum-cost flow, etc. So to make a flow problem that has enough information in the solution to recover the sorted order, you need $\Omega(n\log n)$ edges.</p>

CC BY-SA 3.0
2015-06-17T05:22:49.920Z
Brilliant answer!
Peter
CC BY-SA 4.0
2019-08-08T00:41:15.730Z
@DavidEppstein Is this lower bound on some comparisonless model?
Turbo
CC BY-SA 4.0
2019-08-08T04:51:29.547Z
It's a handwavy argument. You could make it rigorous in some sort of comparison tree model (because in such models bits of information in the output translate directly to number of comparisons needed in an algorithm) but the hard part would be devising a model in which the flow part made sense.
David Eppstein
CC BY-SA 3.0
2015-06-16T22:54:00.967Z
2015-06-16T22:54:00.967Z
David Eppstein
<p>Is there a linear-time reduction from the sorting problem to the max-flow problem?</p>

<p>If so, what would such a reduction look like?</p>

<reductions><sorting><max-flow>
Reducing sorting to max-flow
Peter
# Reducing sorting to max-flow

(Asked by: username_0 on 2015-06-16)

Is there a linear-time reduction from the sorting problem to the max-flow problem?

If so, what would such a reduction look like?

**Tags:** reductions, sorting, max-flow

---

## 1 answers

### Answer by username_1 on 2015-06-16. Score: 9 | Accepted answer

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are unused, and which form a spanning tree of used but unsaturated edges). Similar arguments apply to minimum-cost flow, etc. So to make a flow problem that has enough information in the solution to recover the sorted order, you need $\Omega(n\log n)$ edges.

> **Comments:**
> **username_0**: Brilliant answer!  
> **username_2**: @DavidEppstein Is this lower bound on some comparisonless model?  
> **username_1**: It's a handwavy argument. You could make it rigorous in some sort of comparison tree model (because in such models bits of information in the output translate directly to number of comparisons needed in an algorithm) but the hard part would be devising a model in which the flow part made sense.  

---

