Degree-constrained Minimum Latency Trees are APX-Hard

Abstract

When transmitting data from a single source to many recipients, it is often desirable to use some recipients of the stream to re-broadcast the stream to other users. In such multicast systems each client may be used as a server, serving up to B other clients. Formally, we will take a set X of clients, along with a distance function d that specifies the latency (in the host network) between each pair of clients in X. Our goal will be to produce a directed spanning tree of X, rooted at some specified root 2 X, with out-degree bounded by B, and minimizing the sum of the latencies from root to every point in X. In addition to being motivated by current experimental algorithms work, the problem also interpolates naturally between the traveling repairman problem (when B = 1) and single source shortest paths (when B = n − 1). The former problem is APX-complete (in metric spaces) and the latter is in P. We explore the hardness of the problem for other values of B. In particular, we show that the problem remains APX-Hard at least up to B = Cpn for some universal constant C when the host space is a general semi-metric.