Classifying customer-provider relationships in the internet

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 incident 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 orientation exists) can be done in linear time and that the maximization version of the problem is NP-hard and cannot be approximated within 1/n1−ε for n paths unless NP=co-RP . We present constantfactor 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 approximation algorithm yields very good solutions on real data sets.