Computing a Minimum Color Path in Edge-Colored Graphs

摘要

In this paper, we study the problem of computing a min-color path in an edge-colored graph. More precisely, we are given a graph G = (V,E), source s, target t, an assignment x : E → 2~C of edges to a set of colors in C, and we want to find a path from a to t such that the number of unique colors on this path is minimum over all possible s — t paths. We show that this problem is hard (conditionally) to approximate within a factor O(n~(1/8)) of optimum, and give a polynomial time O(n~(2/3))-approximation algorithm. We translate the ideas used in this approximation algorithm into two simple greedy heuristics, and analyze their performance on an extensive set of synthe:tic and real world datasets. From our experiments, we found that our heuristics perform significantly better than the best previous heuristic algorithm for the problem on all datasets, both in terms of path quality and the running time.