<p>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.</p>

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

<p>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 <a href="http://en.wikipedia.org/wiki/Unimodular_matrix#Total_unimodularity">totally unimodular</a>. The optimal solutions to these programs are always integer.</p>

CC BY-SA 3.0
2014-12-05T21:55:13.943Z
2014-12-05T21:55:13.943Z
Tom van der Zanden
<p>What are some ways to prove that a certain problem cannot be solved using Network Flow (NF)?</p>

<p>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?</p>

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

CC BY-SA 3.0
2014-12-05T07:03:12.260Z
It's problematic to define "solvability by NF".
R B
CC BY-SA 3.0
2014-12-05T16:40:22.173Z
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.
Tom van der Zanden
CC BY-SA 3.0
2014-12-05T17:48:57.533Z
@TomvanderZanden I think that could be an answer.
Sasho Nikolov
<max-flow-min-cut>
Characterizing the set of problems solvable via network flow
tba
# Characterizing the set of problems solvable via network flow

(Asked by: username_0 on 2014-12-05)

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.

**Tags:** max-flow-min-cut

> **Comments:**
> **username_1**: It's problematic to define "solvability by NF".  
> **username_2**: 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.  
> **username_3**: @TomvanderZanden I think that could be an answer.  

---

## 1 answers

### Answer by username_2 on 2014-12-05. Score: 7 | Accepted answer

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](http://en.wikipedia.org/wiki/Unimodular_matrix#Total_unimodularity). The optimal solutions to these programs are always integer.


---

