# Complexity \ Reference request for variant of max flow problem

In the standard max cost flow problem with arc capacities, the cost of using an arc is proportional to the flow through the arc. For example, if $$f_{uv}$$ is the flow through the arc $$(u,v)$$, then the cost of using this arc is given by $$\mathbf{c}_{uv} f_{uv}$$, where $$\mathbf{c}_{uv}$$ is some predefined real number. So the objective we are interested in maximizing is $$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$$, where $$E$$ is the edges in the graph. You may assume that graph contains a source and a sink node, and all flows emanate from the source and drain into the sink node.

Consider the variant in which the cost associated with using the arc $$(u,v)$$ is instead given by: $$\begin{cases} \mathbf{c}_{uv} f_{uv} + \mathbf{b}_{uv}, \text{ if } f_{uv} > 0,\\ 0, \text{ otherwise} \end{cases}$$ where $$\mathbf{b}_{uv}$$ is some predefined positive number.

1. Does the variant of the max flow problem admit a polynomial-time solution?
2. If not, are there any references that you can point me to?

P.S. I know that the variant I stated can be posed easily as a MILP, however, I am interested in learning about the structural results and complexity of this problem.

• Is your objective to maximize the sum of the weighted flows, or are you looking for the weighted minimum-cost solution given that the unweighted flow is equal to the maximum (a min-cost max-flow problem)? – Kevin Dalmeijer Aug 18 '20 at 0:54
• @KevinDalmeijer - The OP should have read max cost flow. So yes, I am interested in maximizing the sum of weighted flows, where the weights for the edges are provided in the $\mathbf{c}$ vector. – batwing Aug 18 '20 at 1:51
• You want to maximize cost? Are there any demand constraints on the nodes? Do you have a source node and a sink node? – RobPratt Aug 18 '20 at 2:00
• @RobPratt - Just the simplest case where we have a source and a sink node, and we want to find the flow from source to sink that costs the most. I will clarify this in the OP as well. – batwing Aug 18 '20 at 2:10
• In this case, the standard form would be to multiply all weights by -1 and state it as an equivalent min-cost flow problem. – Kevin Dalmeijer Aug 18 '20 at 12:17

You want to have $$\epsilon$$-flow across every edge to collect all the cost $$b_{uv}$$. On the other hand you want to maximize the flow across the edges with the highest cost $$c_{uv}$$. This leads to pressure to have $$\epsilon$$ as small as possible, while still $$\epsilon > 0$$. Such an $$\epsilon$$ cannot exist.