## On finding rainbow and colorful paths

Research output: Contribution to journal › Article › Scientific › peer-review

### Standard

**On finding rainbow and colorful paths.** / Kowalik, Łukasz; Lauri, Juho.

Research output: Contribution to journal › Article › Scientific › peer-review

### Harvard

*Theoretical Computer Science*, vol. 628, pp. 110-114. https://doi.org/10.1016/j.tcs.2016.03.017

### APA

*Theoretical Computer Science*,

*628*, 110-114. https://doi.org/10.1016/j.tcs.2016.03.017

### Vancouver

### Author

### Bibtex - Download

}

### RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - On finding rainbow and colorful paths

AU - Kowalik, Łukasz

AU - Lauri, Juho

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

U2 - 10.1016/j.tcs.2016.03.017

DO - 10.1016/j.tcs.2016.03.017

M3 - Article

VL - 628

SP - 110

EP - 114

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -