Complexity of selective network improvement problem

Question

We have a network flow problem with a given directed graph $G=(V,E)$, for each arc $(i,j) \in E$, there is a cost $c_{ij}$ and upper and lower capacity $u_{ij}$ and $l_{ij}$ for the flow $f_{ij}$ through it. The min-cost flow to minimize $\sum_{(i,j) \in E}{c_{ij}f_{ij}}$ is well known to be solved in polynomial time. But now we are given opportunities to improve the cost on the arcs. Suppose we know in advance that after improvement on an arc, its cost will be reduced by $\Delta_{ij}$. My problem is given an integer $K$ ($K<|E|$), how to select the $K$ arcs to improve so that the resulting min-cost objective function is minimized?

Currently, I can formulate the problem as:

$\min{\sum_{(i,j) \in E}{(c_{ij}-x_{ij}\Delta_{ij})f_{ij}}}$

subject to

1. $\sum{f_{ij}} - \sum{f_{ji}}=b_i, \quad i \in V$
2. $l_{ij} \leq f_{ij} \leq u_{ij}, \quad (i,j) \in E$
3. $\sum{x_{ij}}=K, \quad (i,j) \in E$
4. $x_{ij} \in \{0,1\}, \quad (i,j) \in E$

Constraints 1. and 2. are just normal flow constraints while 3. and 4. are like packing constraints. With the introduce of 0/1 variable $x_{ij}$, this problem seems to be hard to solve. So I'm wondering what is the complexity of this problem? Thanks.

Answer 1

Reduction from Set Cover. Suppose the Set Cover instance has sets $S_1,\ldots,S_m$ which are subsets of a universe $U$ of $n$ elements, and an integer $k$. The problem is to decide if the elements of $U$ can be covered by using at most $k$ sets from $\{S_1,\ldots,S_m\}$. Create a directed graph with a node for each set $S_i$ and a node for each element in $U$ and a set is connected by an arc to an element iff that element is in that set (these arcs have a capacity of $1$ each). Add a source node $s$ and connect it to each set $S_i$ with an arc of capacity $|S_i|$. Add a sink node $t$ and arcs connecting each element to $t$ (the capacity if $1$ and cost is $0$). The arc $(s,S_i)$ has cost $1$ and if we improve it the cost becomes $0$. The other arcs have cost $0$ so there is no point improving them. The claim is that there is a feasible cover of size $k$ in the Set Cover instance iff one can select $k$ arcs to improve so that the resulting graph has an $s$-$t$ flow of $n$ with cost $0$. This is not hard to see. One can use lower bounds on a $(t,s)$ arc to enforce a flow of $n$ between $s$ and $t$.