2026-08-15T23:02:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6857 2024-03-06T10:39:02Z ddc:004 open_access

Parameterized Algorithms for List K-Cycle Panolan, Fahad Zehavi, Meirav Parameterized Complexity K-Cycle Colorful Path k-Path 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fahad Panolan and Meirav Zehavi 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.22 urn:nbn:de:0030-drops-68571 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode