On the Hardness of Approximating the Multicast Delay Variation Problem

Given a network with one source and multiple destinations, the multicast delay variation problem attempts to construct a multicast tree such that the interdestination delay variation among all the paths from the source to each destination is minimized. In this paper, we show that the problem is NP-hard and that it is not approximable within a constant factor in polynomial time unless NP = P. These findings indicate that it is impossible to develop efficient optimal or approximation algorithms for any multicast routing problem under the interdestination delay variation constraint unless NP = P.