Rearrangeability in multicast clos networks is np-complete

Three-stage Clos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if Clos network is represented as a bipartite graph then connecting paths are easy transformed into edge coloring. It is also natural to use on-line edge coloring algorithms. However, the things get more complicated in case of multicast connections. There are four models of multicast 3-stage Clos networks: model-1 where only the first stage switches do not have fan-out capability, model-2 where only the second stage switches do not have fan-out capability, model-3 where only the third stage switches do not have fan-out capability and model-0 where no switches lack fan-out capability. In the paper we show some new results on model-0 and model-1 multicast Clos networks. In particular, we focus on rearrangeable multicast networks and prove that the problem of their rearranging is NP-complete.