<p>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$.</p>

CC BY-SA 3.0
2011-09-08T21:59:09.273Z
I checked it. I think it's correct. Thank you.
Kid
CC BY-SA 3.0
2011-09-08T23:51:43.917Z
added this to the list of original proofs generated on the site (http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site/1324#1324)
Suresh Venkat
CC BY-SA 3.0
2011-09-08T19:54:38.373Z
2011-09-08T19:54:38.373Z
Chandra Chekuri
<p>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&lt;|E|$), how to select the $K$ arcs to improve so that the resulting min-cost objective function is minimized? </p>

<p>Currently, I can formulate the problem as:</p>

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

<p>subject to </p>

<ol>
<li>$\sum{f_{ij}} - \sum{f_{ji}}=b_i, \quad i \in V$ </li>
<li>$l_{ij} \leq f_{ij} \leq u_{ij}, \quad (i,j) \in E$</li>
<li>$\sum{x_{ij}}=K, \quad (i,j) \in E$</li>
<li>$x_{ij} \in \{0,1\}, \quad (i,j) \in E$</li>
</ol>

<p>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. </p>

CC BY-SA 3.0
2011-09-08T03:27:34.717Z
It appears that one can reduce the Set Cover problem to this problem, thus showing that it is NP-Complete.
Chandra Chekuri
CC BY-SA 3.0
2011-09-08T19:38:52.787Z
@ChandraChekuri From set cover? Could you explain more?
Kid
<ds.algorithms><np-hardness><network-modeling>
Complexity of selective network improvement problem
Kid
# Complexity of selective network improvement problem

(Asked by: username_0 on 2011-09-07)

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.

**Tags:** ds.algorithms, np-hardness, network-modeling

> **Comments:**
> **username_1**: It appears that one can reduce the Set Cover problem to this problem, thus showing that it is NP-Complete.  
> **username_0**: @ChandraChekuri From set cover? Could you explain more?  

---

## 1 answers

### Answer by username_1 on 2011-09-08. Score: 6 | Accepted answer

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$.

> **Comments:**
> **username_0**: I checked it. I think it's correct. Thank you.  
> **username_2**: added this to the list of original proofs generated on the site (http://meta.cstheory.stackexchange.com/questions/784/original-proofs-generated-on-the-parent-site/1324#1324)  

---

