Panolan, Fahad ;
Zehavi, Meirav
Parameterized Algorithms for List KCycle
Abstract
The classic KCycle problem asks if a graph G, with vertex set V(G), has a simple cycle containing all vertices of a given set K subseteq V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K subset of V(G) and an injective coloring c from K to {1,2,...,K}, decide if G has a simple cycle containing each color in {1,2,...,K} (once). Another problem widely known since the introduction of color coding is {Colorful Cycle}. Given a graph G and a coloring c from V(G) to {1,2,...,k} for some natural number k, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} (once). We study a generalization of these problems: Given a graph G, a set K subset of V(G), a listcoloring L from K to 2^{{1,2,...,k^*}} for some natural number k^* and a parameter k, List KCycle asks if one can assign a color to each vertex in K so that G would have a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors.
We design a randomized algorithm for List KCycle running in time 2^kn^{O(1)} on an vertex graph, matching the best known running times of algorithms for both KCycle and Colorful Cycle. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of List KCycle that generalizes the classic Hamiltonicity problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Bjorklund, Husfeldt and Taslaman (SODA'12), Bjorklund, Kaski and Kowalik (STACS'13), and Bjorklund (FOCS'10).
BibTeX  Entry
@InProceedings{panolan_et_al:LIPIcs:2016:6857,
author = {Fahad Panolan and Meirav Zehavi},
title = {{Parameterized Algorithms for List KCycle}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {22:122:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6857},
URN = {urn:nbn:de:0030drops68571},
doi = {10.4230/LIPIcs.FSTTCS.2016.22},
annote = {Keywords: Parameterized Complexity, KCycle, Colorful Path, kPath}
}
10.12.2016
Keywords: 

Parameterized Complexity, KCycle, Colorful Path, kPath 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

10.12.2016 