<p>The problem you are asking is called capacitated network design. Typically each edge e also has a cost/weight w(e) and you want to minimize the weight/cost of the chosen edges such that the resulting graph supports the demands given by $T_{ij}$. The weighted version can be reduced to the unweighted version by replacing an edge of weight w(e) by a path of w(e) edges (this reduction is pseudo-polynomial). The problem is NP-Hard even when $T_{ij}$ is non-zero for a single pair and even here we don't quite understand the approximability. </p>

<p>See the following recent papers for more on this:</p>

<ul>
<li><a href="http://ect.bell-labs.com/who/ylz/2010.speedscale-focs.pdf" rel="nofollow">Minimum-Cost Network Design with (Dis)economies of Scale</a>. IEEE FOCS 2010.</li>
<li><a href="http://arxiv.org/abs/1009.5734" rel="nofollow">Approximability of Capacitated Network Design</a>. IPCO 2011.</li>
</ul>

CC BY-SA 3.0
2011-07-29T03:05:00.397Z
A some what easier variant that is well-studied is the so-called buy-at-bulk network design problem where multiple copies of an edge can be bought. This problem arises in practice and is discussed in the above papers. I should also mention that the FOCS paper above is more in line with what you want. The IPCO paper (of which I am a co-author) discusses a related but a slightly different problem.
Chandra Chekuri
CC BY-SA 3.0
2011-07-27T03:48:39.850Z
2011-07-28T16:34:55.023Z
2011-07-28T16:34:55.023Z
Chandra Chekuri
<p>Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$.  Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$.  The goal is to minimize the number of links required to support all traffic in $T_{ij}$ such that the total traffic traversing each link $e$ is less than $c(e)$.</p>

<p>Is there an equivalent problem in the literature? </p>

<p>thanks,
kwan</p>

CC BY-SA 3.0
2011-07-27T00:59:43.050Z
Just a CS undergrad here, but isn't this the max-flow problem?
bgoosman
CC BY-SA 3.0
2011-07-27T01:22:32.887Z
No.  in max-flow, you want to maximize flow by 'spreading' traffic onto as many links as possible.  But I want it to be on the fewest links as possible -- you can view it as the opposite of max-flow.
Kwan
CC BY-SA 3.0
2011-07-27T01:26:06.300Z
An equivalent question is, what is the maximum number links that I can remove from the network such that the flows in $T_{ij}$ remain supported?
Kwan
<reference-request><graph-theory><optimization><network-modeling>
Laying paths on a network using minimum number of links/edges
Kwan
# Laying paths on a network using minimum number of links/edges

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

Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$. Also given is a traffic matrix $T\_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$. The goal is to minimize the number of links required to support all traffic in $T\_{ij}$ such that the total traffic traversing each link $e$ is less than $c(e)$.

Is there an equivalent problem in the literature?

thanks,
kwan

**Tags:** reference-request, graph-theory, optimization, network-modeling

> **Comments:**
> **username_1**: Just a CS undergrad here, but isn't this the max-flow problem?  
> **username_0**: No.  in max-flow, you want to maximize flow by 'spreading' traffic onto as many links as possible.  But I want it to be on the fewest links as possible -- you can view it as the opposite of max-flow.  
> **username_0**: An equivalent question is, what is the maximum number links that I can remove from the network such that the flows in $T_{ij}$ remain supported?  

---

## 1 answers

### Answer by username_2 on 2011-07-27. Score: 6

The problem you are asking is called capacitated network design. Typically each edge e also has a cost/weight w(e) and you want to minimize the weight/cost of the chosen edges such that the resulting graph supports the demands given by $T\_{ij}$. The weighted version can be reduced to the unweighted version by replacing an edge of weight w(e) by a path of w(e) edges (this reduction is pseudo-polynomial). The problem is NP-Hard even when $T\_{ij}$ is non-zero for a single pair and even here we don't quite understand the approximability.

See the following recent papers for more on this:

* [Minimum-Cost Network Design with (Dis)economies of Scale](http://ect.bell-labs.com/who/ylz/2010.speedscale-focs.pdf). IEEE FOCS 2010.
* [Approximability of Capacitated Network Design](http://arxiv.org/abs/1009.5734). IPCO 2011.

> **Comments:**
> **username_2**: A some what easier variant that is well-studied is the so-called buy-at-bulk network design problem where multiple copies of an edge can be bought. This problem arises in practice and is discussed in the above papers. I should also mention that the FOCS paper above is more in line with what you want. The IPCO paper (of which I am a co-author) discusses a related but a slightly different problem.  

---

