T. Erlebach and A. Hall (Switzerland), and T. Schank (Germany)
autonomous system, internet topology, approximation
The problem of inferring customer-provider relationships in the autonomous system topology of the Internet leads to the following optimization problem: given an undirected graph G and a set P of paths in G, orient the edges of G such that as many paths as possible are valid, meaning that they do not contain an internal node with both inci dent edges on the path directed away from that node. The complexity of this problem was left open by Subramanian et al. (“Characterizing the Internet hierarchy from multiple vantage points,” INFOCOM 2002). We show that finding an orientation that makes all paths valid (if such an orien tation exists) can be done in linear time and that the maxi mization version of the problem is NP-hard and cannot be approximated within 1/n1−ε for n paths unless NP=co RP. We present constant-factor approximation algorithms for the case where the paths have bounded length and prove that the problem remains APX-hard in this case. Finally, we report experimental results demonstrating that the ap proximation algorithm yields very good solutions on real data sets.
Important Links:
Go Back
