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
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. IEEE FOCS 2010.
Approximability of Capacitated Network Design. IPCO 2011.