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

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

1 Answer 1


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:

  • 1
    $\begingroup$ 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. $\endgroup$ Jul 29, 2011 at 3:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.