5
$\begingroup$

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

If so, what would such a reduction look like?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Brilliant answer! $\endgroup$
    – Peter
    Jun 17, 2015 at 5:22
  • $\begingroup$ @DavidEppstein Is this lower bound on some comparisonless model? $\endgroup$
    – Turbo
    Aug 8, 2019 at 0:41
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Aug 8, 2019 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.