# Characterizing the set of problems solvable via network flow

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.

• It's problematic to define "solvability by NF".
– R B
Dec 5 '14 at 7:03
• 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. Dec 5 '14 at 16:40
• @TomvanderZanden I think that could be an answer. Dec 5 '14 at 17:48

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