All Colors Shortest Path problem on trees.

Given an edge weighted tree T(V, E), rooted at a designated base vertex r∈V<inline-graphic></inline-graphic>, and a color from a set of colors C={1,…,k}<inline-graphic></inline-graphic> assigned to every vertex v∈V<inline-graphic></inline-graphic>, All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically. [ABSTRACT FROM AUTHOR]