Algorithms for robust graph coloring on paths

摘要

We study algorithms for the robust graph coloring problem on paths: Given a blue path and a red path (with costs on its edges) on the same set of vertices, find a 3-coloring of the blue path that minimizes the sum of the costs of the red edges whose ends have the same color. First we give an exact but exponential-time algorithm. Then we give a randomized algorithm and we prove that the expected cost of its output is bounded above by half the cost of the red edges and we prove that this bound is sharp. Later, we give a greedy algorithm and we prove that the cost of its output is also bounded above by half the cost of the red edges. Finally, we present some results regarding the maximization problem and we propose some conjectures.