Is there a linear-time reduction from the sorting problem to the max-flow problem?
If so, what would such a reduction look like?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIt 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.