The Minimum Clique Routing Problem on Cycles

ABSTRACT In the minimum clique routing problem on cycles mcrpc , we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the mcrpc but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP‐hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2‐approximation algorithm and a ‐approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them.