3
$\begingroup$

What are some ways to prove that a certain problem cannot be solved using Network Flow (NF)?

One way is to prove the problem is NP-hard. But NF has substantial structure -- is there some symmetry or invariant that all solutions must satisfy in order to be solvable with NF?

I'm interested in any necessary or sufficient conditions that a problem should satisfy in order to be solvable using NF.

$\endgroup$
3
  • $\begingroup$ It's problematic to define "solvability by NF". $\endgroup$
    – R B
    Dec 5 '14 at 7:03
  • 6
    $\begingroup$ It depends strongly on what kind of preprocessing (reductions) you allow. If you allowed preprocessing to take arbitrarily long, then any problem could be solved using a flow, simply by solving the problem and then outputting a trivial flow that has the desired answer. Under logspace reductions, maximum flow is a $P$-complete, so any problem in $P$ can be solved "efficiently" using network flow. $\endgroup$ Dec 5 '14 at 16:40
  • 2
    $\begingroup$ @TomvanderZanden I think that could be an answer. $\endgroup$ Dec 5 '14 at 17:48
7
$\begingroup$

It depends on how you define "solvable via network flows". If you allow the preprocessing step to take arbitrarily long, then anything is solvable using network flows by simply solving it an then outputting a trivial network flow that has the desired answer.

Under log-space reductions, network flow is $P$-complete so any problem in $P$ can be solved "efficiently" using a network flow.

Another interesting aspect of flows is that if you start with integer capacities, then the solution will be integer as well. Network Flows (when viewed as Linear Programs) are actually part of a larger class of problems called totally unimodular. The optimal solutions to these programs are always integer.

$\endgroup$

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.