Document Open Access Logo

Parameterized Algorithms for List K-Cycle

Authors Fahad Panolan, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.22.pdf
  • Filesize: 0.54 MB
  • 15 pages

Document Identifiers

Author Details

Fahad Panolan
Meirav Zehavi

Cite As Get BibTex

Fahad Panolan and Meirav Zehavi. Parameterized Algorithms for List K-Cycle. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.22

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

Subject Classification

Keywords
  • Parameterized Complexity
  • K-Cycle
  • Colorful Path
  • k-Path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Alon, R. Yuster, and U. Zwick. Color coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  2. A. Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. Google Scholar
  3. A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto. Narrow sieves for parameterized paths and packings. CoRR abs/1007.1161, 2010. Google Scholar
  4. A. Björklund, T. Husfeldt, and N. Taslaman. Shortest cycle through specified elements. In SODA, pages 1747-1753, 2012. Google Scholar
  5. A. Björklund, V. Kamat, L. Kowalik, and M. Zehavi. Spotting trees with few leaves. In ICALP, pages 243-255, 2015. Google Scholar
  6. A. Björklund, P. Kaski, and L. Kowalik. Constrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947-967, 2016. Google Scholar
  7. A. Björklund, P. Kaski, J. Lauri, and L. Kowalik. Engineering motif search for large graphs. In ALENEX, pages 104-118, 2016. Google Scholar
  8. H. L. Bodlaender. On linear time minor tests with depth-first search. J. Algorithms, 14(1):1-23, 1993. Google Scholar
  9. J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S. H. Sze, and F. Zhang. Randomized divide-and-conquer: Improved path, matching, and packing algorithms. SIAM J. on Computing, 38(6):2526-2547, 2009. Google Scholar
  10. M. Cygan, H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, P. Paturi, S. Saurabh, and M. Wahlström. On problems as hard as CNF-SAT. In CCC, pages 74-84, 2012. Google Scholar
  11. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  12. R. A. DeMillo and R. J. Lipton. A probabilistic remark on algebraic program testing. Inform. Process Lett., 7(4):193-195, 1978. Google Scholar
  13. P. Deshpande, R. Barzilay, and D. R. Karger. Randomized decoding for selection-and-ordering problems. In HLT-NAACL, pages 444-451, 2007. Google Scholar
  14. R. Downey and M. Fellows. Fundamentals of parameterized complexity. Springer, 2013. Google Scholar
  15. H. Fleischner and G. H. Woeginger. Detecting cycles through three fixed vertices in a graph. Inform. Process Lett., 41:29-33, 1992. Google Scholar
  16. F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh. Representative sets of product families. In ESA, pages 443-454, 2014. Google Scholar
  17. F. V. Fomin, D. Lokshtanov, and S. Saurabh. Efficient computation of representative sets with applications in parameterized and exact agorithms. In SODA, pages 142-151, 2014. Google Scholar
  18. S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111-121, 1980. Google Scholar
  19. F. Hüffner, S. Wernicke, and T. Zichner. Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica, 52(2):114-132, 2008. Google Scholar
  20. K. Kawarabayashi. An improved algorithm for finding cycles through elements. In IPCO, pages 374-384, 2008. Google Scholar
  21. K. Kawarabayashi, Z. Li, and B. A. Reed. Recognizing a totally odd k₄-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. In SODA, pages 318-328, 2010. Google Scholar
  22. I. Koutis. Faster algebraic algorithms for path and packing problems. In ICALP, pages 575-586, 2008. Google Scholar
  23. L. Kowalik and J. Lauri. On finding rainbow and colorful paths. Theor. Comput. Sci., 2016. Google Scholar
  24. A. S. LaPaugh and R. L. Rivest. The subgraph homomorphism problem. J. Comput. Sys. Sci., 20:133-149, 1980. Google Scholar
  25. B. Monien. How to find long paths efficiently. Annals Disc. Math., 25:239-254, 1985. Google Scholar
  26. R. Y. Pinter, H. Shachnai, and M. Zehavi. Improved parameterized algorithms for network query problems. In IPEC, pages 294-306, 2014. Google Scholar
  27. R. Y. Pinter and M. Zehavi. Algorithms for topology-free and alignment network queries. JDA, 27:29-53, 2014. Google Scholar
  28. N. Robertson and P. D. Seymour. Graph minors XIII: The disjoint paths problem. J. Combin. Theory Ser. B, 63:65-110, 1995. Google Scholar
  29. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach., 27(4):701-717, 1980. Google Scholar
  30. H. Shachnai and M. Zehavi. Representative families: A unified tradeoff-based approach. In ESA, pages 786-797, 2014. Google Scholar
  31. M. Wahlström. Abusing the Tutte matrix: an algebraic instance compression for the k-set-cycle problem. In STACS, pages 341-352, 2013. Google Scholar
  32. R. Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. Google Scholar
  33. Kobayashi Y. and K. Kawarabayashi. Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In SODA, pages 1146-1155, 2009. Google Scholar
  34. M. Zehavi. Parameterized algorithms for the module motif problem. In MFCS, pages 825-836, 2013. Google Scholar
  35. M. Zehavi. Mixing color coding-related techniques. In ESA, pages 1037-1049, 2015. Google Scholar
  36. R. Zippel. Probabilistic algorithms for sparse polynomials. In EUROSAM, pages 216-226, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact