Complexity of selective network improvement problem
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$.