The complexity of path coloring and call scheduling (Q5941061)

Modern high-performance communication networks pose a number of challenging problems concerning the efficient allocation of resources to connection requests. In all-optical networks with wavelength-division multiplexing, connection requests must be assigned paths and colors (wavelengths) such that intersecting paths receive different colors, and the goal is to minimize the number of colors used. This path coloring problem is proved NP-hard for undirected and bidirected ring networks. Path coloring in undirected tree networks is shown to be equivalent to edge coloring of multigraphs, which implies a polynomial-time optimal algorithm for trees of constant degree as well as NP-hardness and an approximation algorithm with absolute approximation ratio \(\frac 43\) and asymptotic approximation ratio 1.1 for trees of arbitrary degree. For bidirected trees, path coloring is shown to be NP-hard even in the binary case. A polynomial-time optimal algorithm is given for path coloring in undirected or bidirected trees with \(n\) nodes under the assumption that the number of paths touching every single node of the tree is \(O((\log n)^{1-\varepsilon})\). Call scheduling is the problem of assigning paths and starting times to calls in a network with bandwidth reservation such that the maximum completion time is minimized. In the case of unit bandwidth requirements, unit edge capacities, and unit call durations, call scheduling is equivalent to path coloring. If either the bandwidth requirements or the call durations can be arbitrary, call scheduling is shown NP-hard for virtually every network topology.