Tampere University of Technology

TUTCRIS Research Portal

On finding rainbow and colorful paths

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)110-114
Number of pages5
JournalTheoretical Computer Science
Volume628
DOIs
Publication statusPublished - 2016
Publication typeA1 Journal article-refereed

Abstract

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 2knO(1) and uses 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), then Set Cover admits a (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 Rainbow s t -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 s t -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) 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.

Publication forum classification

Field of science, Statistics Finland