{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T17:00:38Z","timestamp":1756573238228,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,6,22]],"date-time":"2018-06-22T00:00:00Z","timestamp":1529625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Research Council (BE)","award":["267959","306992"],"award-info":[{"award-number":["267959","306992"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0469-7","type":"journal-article","created":{"date-parts":[[2018,6,22]],"date-time":"2018-06-22T10:18:58Z","timestamp":1529662738000},"page":"1267-1287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Algorithms for List K-Cycle"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"first","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,6,22]]},"reference":[{"issue":"4","key":"469_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"1","key":"469_CR2","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/110839229","volume":"43","author":"A Bj\u00f6rklund","year":"2014","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. SIAM J. Comput. 43(1), 280\u2013299 (2014)","journal-title":"SIAM J. Comput."},{"key":"469_CR3","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","volume":"87","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87, 119\u2013139 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"469_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Taslaman, N.: Shortest cycle through specified elements. In: SODA, pp. 1747\u20131753 (2012)","DOI":"10.1137\/1.9781611973099.139"},{"key":"469_CR5","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Kamat, V., Kowalik, L., Zehavi, M.: Spotting trees with few leaves. In: ICALP, pp. 243\u2013255 (2015)","DOI":"10.1007\/978-3-662-47672-7_20"},{"issue":"2","key":"469_CR6","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1007\/s00453-015-9981-1","volume":"74","author":"A Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Constrained multilinear detection and generalized graph motifs. Algorithmica 74(2), 947\u2013967 (2016)","journal-title":"Algorithmica"},{"key":"469_CR7","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Kaski, P., Lauri, J., Kowalik, L.: Engineering motif search for large graphs. In: ALENEX, pp. 104\u2013118 (2016)","DOI":"10.1137\/1.9781611973754.10"},{"issue":"1","key":"469_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1993.1001","volume":"14","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: On linear time minor tests with depth-first search. J. Algorithms 14(1), 1\u201323 (1993)","journal-title":"J. Algorithms"},{"key":"469_CR9","doi-asserted-by":"crossref","unstructured":"Chen, J., Kneis, J., Lu, S., M\n                    \n                      \n                    \n                    $$\\ddot{\\rm o}$$\n                    \n                      \n                        \n                          o\n                          \u00a8\n                        \n                      \n                    \n                  lle, D., Richter, S., Rossmanith, P., Sze, S.H., Zhang, F.: Randomized divide-and-conquer: improved path, matching, and packing algorithms. SIAM J. Comput. 38(6), 2526\u20132547 (2009)","DOI":"10.1137\/080716475"},{"issue":"3","key":"469_CR10","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/2925416","volume":"12","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, P., Saurabh, S., Wahlstr\u00f6m, M.: On problems as hard as CNF-SAT. ACM Trans. Algorithms 12(3), 41:1\u201341:24 (2016). \n                    https:\/\/doi.org\/10.1145\/2925416","journal-title":"ACM Trans. Algorithms"},{"key":"469_CR11","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V, Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"issue":"4","key":"469_CR12","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process Lett. 7(4), 193\u2013195 (1978)","journal-title":"Inf. Process Lett."},{"key":"469_CR13","unstructured":"Deshpande, P., Barzilay, R., Karger, D.R.: Randomized decoding for selection-and-ordering problems. In: HLT-NAACL, pp. 444\u2013451 (2007)"},{"key":"469_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Springer (2013)","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"469_CR15","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0020-0190(92)90128-I","volume":"41","author":"H Fleischner","year":"1992","unstructured":"Fleischner, H., Woeginger, G.H.: Detecting cycles through three fixed vertices in a graph. Inf. Process Lett. 41, 29\u201333 (1992)","journal-title":"Inf. Process Lett."},{"issue":"3","key":"469_CR16","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/3039243","volume":"13","author":"FV Fomin","year":"2017","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Representative families of product families. ACM Trans. Algorithms 13(3), 36 (2017). \n                    https:\/\/doi.org\/10.1145\/3039243","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"469_CR17","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016). \n                    https:\/\/doi.org\/10.1145\/2886094","journal-title":"J. ACM"},{"key":"469_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"469_CR19","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/s00453-007-9008-7","volume":"52","author":"F Huffner","year":"2008","unstructured":"Huffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica 52(2), 114\u2013132 (2008)","journal-title":"Algorithmica"},{"key":"469_CR20","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K.: An improved algorithm for finding cycles through elements. In: IPCO, pp. 374\u2013384 (2008)","DOI":"10.1007\/978-3-540-68891-4_26"},{"key":"469_CR21","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Li, Z., Reed, B.A.: Recognizing a totally odd \n                    \n                      \n                    \n                    $$K_4$$\n                    \n                      \n                        \n                          K\n                          4\n                        \n                      \n                    \n                  -subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements. In: SODA, pp. 318\u2013328 (2010)","DOI":"10.1137\/1.9781611973075.27"},{"key":"469_CR22","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kawarabayashi, K.: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. In: SODA, pp. 1146\u20131155 (2009)","DOI":"10.1137\/1.9781611973068.124"},{"key":"469_CR23","doi-asserted-by":"crossref","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: ICALP, pp. 575\u2013586 (2008)","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"469_CR24","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.tcs.2016.03.017","volume":"628","author":"L Kowalik","year":"2016","unstructured":"Kowalik, L., Lauri, J.: On finding rainbow and colorful paths. Theor. Comput. Sci. 628, 110\u2013114 (2016). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2016.03.017","journal-title":"Theor. Comput. Sci."},{"key":"469_CR25","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0022-0000(80)90057-4","volume":"20","author":"AS LaPaugh","year":"1980","unstructured":"LaPaugh, A.S., Rivest, R.L.: The subgraph homomorphism problem. J. Comput. Syst. Sci. 20, 133\u2013149 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"469_CR26","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discrete Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discrete Math."},{"key":"469_CR27","doi-asserted-by":"crossref","unstructured":"Pinter, R.Y., Shachnai, H., Zehavi, M.: Improved parameterized algorithms for network query problems. In: IPEC, pp. 294\u2013306 (2014)","DOI":"10.1007\/978-3-319-13524-3_25"},{"key":"469_CR28","first-page":"29","volume":"27","author":"RY Pinter","year":"2014","unstructured":"Pinter, R.Y., Zehavi, M.: Algorithms for topology-free and alignment network queries. JDA 27, 29\u201353 (2014)","journal-title":"JDA"},{"key":"469_CR29","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors XIII: the disjoint paths problem. J. Comb. Theory Ser. B 63, 65\u2013110 (1995)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"469_CR30","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach. 27(4), 701\u2013717 (1980)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"469_CR31","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.jcss.2015.11.008","volume":"82","author":"H Shachnai","year":"2016","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488\u2013502 (2016)","journal-title":"J. Comput. Syst. Sci."},{"key":"469_CR32","unstructured":"Wahlstr\u00f6m, M.: Abusing the Tutte matrix: an algebraic instance compression for the \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -set-cycle problem. In: STACS, pp. 341\u2013352 (2013)"},{"issue":"6","key":"469_CR33","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                   in \n                    \n                      \n                    \n                    $${O}^*(2^k)$$\n                    \n                      \n                        \n                          \n                            \n                              O\n                            \n                            \u2217\n                          \n                          \n                            (\n                            \n                              2\n                              k\n                            \n                            )\n                          \n                        \n                      \n                    \n                   time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"key":"469_CR34","doi-asserted-by":"crossref","unstructured":"Zehavi, M.: Parameterized algorithms for the module motif problem. In: MFCS, pp. 825\u2013836 (2013)","DOI":"10.1007\/978-3-642-40313-2_72"},{"key":"469_CR35","doi-asserted-by":"crossref","unstructured":"Zehavi, M.: Mixing color coding-related techniques. In: ESA, pp. 1037\u20131049 (2015)","DOI":"10.1007\/978-3-662-48350-3_86"},{"key":"469_CR36","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: EUROSAM, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0469-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0469-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0469-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,23]],"date-time":"2019-09-23T21:44:40Z","timestamp":1569275080000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0469-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,22]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["469"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0469-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,6,22]]},"assertion":[{"value":"28 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}