License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.22
URN: urn:nbn:de:0030-drops-68571
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6857/
Go to the corresponding LIPIcs Volume Portal


Panolan, Fahad ; Zehavi, Meirav

Parameterized Algorithms for List K-Cycle

pdf-format:
LIPIcs-FSTTCS-2016-22.pdf (1.0 MB)


Abstract

The classic K-Cycle 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 list-coloring L from K to 2^{{1,2,...,k^*}} for some natural number k^* and a parameter k, List K-Cycle 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 K-Cycle running in time 2^kn^{O(1)} on an -vertex graph, matching the best known running times of algorithms for both K-Cycle and Colorful Cycle. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of List K-Cycle 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 K-Cycle}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6857},
  URN =		{urn:nbn:de:0030-drops-68571},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.22},
  annote =	{Keywords: Parameterized Complexity, K-Cycle, Colorful Path, k-Path}
}

Keywords: Parameterized Complexity, K-Cycle, Colorful Path, k-Path
Seminar: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 08.12.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI