1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ @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. $\endgroup$ Mar 5 at 20:38

1 Answer 1

1
$\begingroup$

The problem appears to be NP-hard, by a reduction from subset sum.

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.

There could still be a pseudo-polynomial time algorithm, FPTAS, or constant-factor approximation.

$\endgroup$
1
  • $\begingroup$ Thank you for your proof! $\endgroup$ Mar 6 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.