On finding rainbow and colorful paths

In the COLORFUL PATH problem we are given a graph G = (V, E) and an arbitrary vertex coloring function c : V -> [k]. The goal is to find a colorful path, i.e., a path on k vertices, that visits each color. This problem has been introduced in the classical work of Alon et al. (1995) [1], and the authors proposed a dynamic programming algorithm that runs in time 2(k)n(O) (1) and uses O(2(k)) space. Since then the only progress obtained is reducing the space size to a polynomial at the cost of using randomization. In this work we show that a progress in time complexity is unlikely: if COLORFUL PATH can be solved in time (2 - epsilon)(k)n(O)(1), then SET COVER admits a (2 - epsilon')(n)(nm)(O(1))-time algorithm. The same applies to other versions of the problem: when edges are colored instead of vertices, or we ask for a walk instead of a path, or when the requested path/walk has specified endpoints. We study also a second, very related problem. In RAINBOW St-CONNECTIVITY, we are given a k-edge-colored graph and two vertices s and t. The goal is to decide whether there is a rainbow path between s and t, that is, a path on which no color repeats. In its vertex variant (RAINBOW VERTEX st-CONNECTIVITY) the input graph is k-vertex-colored, and a rainbow path is defined analogously. Uchizawa et al. (2011) [14] show that both variants can be solved in 2(k)n(O(1)) time and exponential space. We show that the space size can be reduced to a polynomial, while keeping the same running time. In contrast to the polynomial space algorithm for COLORFUL PATH, our algorithm for finding rainbow paths is deterministic. (C) 2016 Elsevier B.V. All rights reserved.