Tampere University of Technology

TUTCRIS Research Portal

On finding rainbow and colorful paths

Research output: Contribution to journalArticleScientificpeer-review

Standard

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

In: Theoretical Computer Science, Vol. 628, 2016, p. 110-114.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

Kowalik, Ł & Lauri, J 2016, 'On finding rainbow and colorful paths', Theoretical Computer Science, vol. 628, pp. 110-114. https://doi.org/10.1016/j.tcs.2016.03.017

APA

Kowalik, Ł., & Lauri, J. (2016). On finding rainbow and colorful paths. Theoretical Computer Science, 628, 110-114. https://doi.org/10.1016/j.tcs.2016.03.017

Vancouver

Kowalik Ł, Lauri J. On finding rainbow and colorful paths. Theoretical Computer Science. 2016;628:110-114. https://doi.org/10.1016/j.tcs.2016.03.017

Author

Kowalik, Łukasz ; Lauri, Juho. / On finding rainbow and colorful paths. In: Theoretical Computer Science. 2016 ; Vol. 628. pp. 110-114.

Bibtex - Download

@article{50a592e905004a0fb9756ddf507cb4d6,
title = "On finding rainbow and colorful paths",
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.",
author = "Łukasz Kowalik and Juho Lauri",
year = "2016",
doi = "10.1016/j.tcs.2016.03.017",
language = "English",
volume = "628",
pages = "110--114",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

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 -