# Laying paths on a network using minimum number of links/edges

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

• Just a CS undergrad here, but isn't this the max-flow problem? – bgoosman Jul 27 '11 at 0:59
• 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 Jul 27 '11 at 1:22
• 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 Jul 27 '11 at 1:26

## 1 Answer

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:

• 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 Jul 29 '11 at 3:05