We consider the problem of minimizing the number of wavelengths needed to connect a given multicast set in a multihop WDM optical network. This problem was introduced and studied by Li et al. who showed that it is NP-complete. They also presented an approximation algorithm for which they claimed an approximation ratio of c(1 + 2 log ▵), where c is the maximum number of connected components in the subgraph induced by any wavelength and ▵ is the maximum number of nodes in any connected component induced by any wavelength. In this article we present an example demonstrating that their claim cannot be correct – the approximation ratio is Ω(n), even though the subgraph induced by every wavelength is connected, where n is the number of nodes in the network. In fact, we show that the problem cannot be approximated within O(2log1/2-ϵm) unless NP⊆DTIME(npoly log n) for any constant ϵ> 0, where m is the number of edges in the network. We complement this hardness result by presenting a polynomial-time algorithm with an approximation ratio of (1 + ln 3 + 2 log ▵) when the subgraph induced by every wavelength is connected, and an approximation ratio of O(√(n log ▵)/opt)) in the general case, where opt is the number of wavelengths used in an optimal solution and 1≤opt≤n-1.
