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?

$\endgroup$
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.

$\endgroup$
  • 1
    $\begingroup$ Brilliant answer! $\endgroup$ – Peter Jun 17 '15 at 5:22
  • $\begingroup$ @DavidEppstein Is this lower bound on some comparisonless model? $\endgroup$ – Turbo Aug 8 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 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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