Algorithm Problem: Converting non-integer maximum flow to integer maximum flow

Consider, we have a non-integer maximum flow in a directed network with integer arc capacity.

Is there an algorithm that can convert this开发者_JS百科 flow into an integer maximum flow?

And what is its running time?

It is not a homework problem.

---

If you are looking for a max s-t flow(integer) with integral arc capacities it is not NP-complete. And maybe there is an algorithms for that purpose. What you would try is to find some arcs that are not saturated with there capacity. On all path that takes this edge has to be an edge that is saturated. Here you will have multiple s-t paths with non-integral capacity. Try to make the integral by increasing one and decrease the other without violating the capacities.

Additionally, take a look at the algorithms at this page: http://en.wikipedia.org/wiki/Maximum_flow_problem All mentioned algorithms should produce integral flows.

It also states the Integral Flow Theorem: If each edge in a flow network has integral capacity, then there exists an integral maximal flow.

---

Im not sure what you mean by convert this flow into an integer maximum flow. If you have a non integral max flow then of course its not possible to get the same flow from an integral problem, as the solution of an integer graph is also integral.

(E.g. if you max flow is 3.5, there is no way to get this max flow from an integral graph).

If you want just the solution the rounded integer graph. Just solve it again, and then you got the corrosponding integer solution.

PS: Neither integer nor non-integer max flow is NP-complete. They are both in P.

---

This is similar to the exercise 9.42 from AMO's book. I think it is better to look at "integer equal flow problem".