In highly distributed Internet measurement systems distributed agents periodically measure the Internet using a tool called { \tt traceroute}, which discovers a path in the network graph. Each agent performs many traceroute measurement to a set of destinations in the network, and thus reveals a portion of the Internet graph as it is seen from the agent locations. In every period we need to check whether previously discovered edges still exist in this period, a process termed { \em validation}. For this end we maintain a database of all the different measurements performed by each agent. Our aim is to be able to { \em validate} the existence of all previously discovered edges in the minimum possible time. In this work we formulate the validation problem as a generalization of the well know set cover problem. We reduce the set cover problem to the validation problem, thus proving that the validation problem is ${ \cal NP}$-hard. We present a $O(\log n)$-approximation algorithm to the validation problem, where $n$ in the number of edges that need to be validated. We also show that unless ${ \cal P = NP}$ the approximation ratio of the validation problem is $\Omega(\log n)$.
Categories: cs.NI cs.CC