Mutual exclusion scheduling with interval graphs or related classes, Part I Original Research Article

In this paper, the mutual exclusion scheduling problem is addressed. Given a simple and undirected graph image and an integer image, the problem is to find a minimum coloring of image such that each color is used at most image times. When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be image-hard for interval graphs, even if image is a constant greater than or equal to four [H.L. Bodlaender and K. Jansen Restrictions of graph partition problems. Part I, Theoretical Computer Science 148(1995) pp. 93–109]. Several polynomial-time solvable cases significant in practice are exhibited here, for which we took care to devise simple and efficient algorithms (in particular linear-time and space algorithms). On the other hand, by reinforcing the image-hardness result of Bodlaender and Jansen, we obtain a more precise cartography of the complexity of the problem for the classes of graphs studied.