# Constrained Maximum Flow Minimum Cost

Let $$G=(V, E)$$ be a directed network with a set $$V$$ of vertices and a set $$E$$ of edges. Two vertices are distinguished, $$s,t$$ which are the source and sink respectively. Each edge $$(i, j)$$ has an associated cost $$c_{ij} \in \mathbb{Z}$$ and a capacity $$u_{ij} \in \mathbb{N}$$. The objective is to achieve a flow of value $$K$$ from $$s$$ to $$t$$ and minimize the cost. The flow through each edge must be integral, is conserved at each vertex (except at $$s$$ and $$t$$) and doesn't exceed edge capacities. In addition, the total cost of the flow must also satisfy $$\Sigma_{(i, j) \in E} c_{ij}x_{ij} \ge D$$ where $$x_{ij}$$ is the flow through edge $$(i, j)$$ and $$D \in \mathbb{Z}$$.

Is this problem solvable in polynomial time or even in pseudo-polynomial time? If not, is there a constant factor approximation for the cost for general networks with a flow of value $$K$$?

I was able to find a paper describing a similar problem but with an upper-bound for the cost: A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem, Ravindra K. Ahuja, James B. Orlin, Networks, 25(2), 1995.

• @D.W. Thank you for your warning, I have edited the question. It's not possible to negate the costs and $D$ because the minimization property would return the solution $max_{cost}(G)$, it would become the smallest solution smaller than $-D$, the problem would instead become a maximization problem which would solve it, but it isn't the paper's focus. Mar 5 at 20:38

In particular, suppose we are given integers $$a_1,\dots,a_n$$ and target $$D$$. Create a graph with two vertices, $$s,t$$. Add edges $$s \to t$$, where the $$i$$th edge has capacity 1, cost $$a_i$$, then add another edge $$s \to t$$ with capacity $$n$$ and cost $$0$$. Set $$K=n$$. Finally, find the minimum possible cost of all flows whose cost is $$\ge D$$ and value is $$K$$. If the minimum possible cost is $$D$$, then you know there is a subset of $$a_1,\dots,a_n$$ that sums to $$D$$; otherwise no such subset exists.