On finding rainbow and colorful paths

In the Colorful Path problem we are given a graph G=(V,E)G=(V,E) and an arbitrary vertex coloring function c:V→[k]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 2knO(1)2knO(1) and uses O(2k)O(2k) 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−ε)knO(1)(2−ε)knO(1), then Set Cover admits a (2−ε′)n(nm)O(1)(2−ε′)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 Rainbowst-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 Vertexst-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 2knO(1)2knO(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.