{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:07Z","timestamp":1781077687003,"version":"3.54.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"United States ? Israel Binational Science Foundation","award":["2018302"],"award-info":[{"award-number":["2018302"]}]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["CLASSICS and MULTIVAL"],"award-info":[{"award-number":["CLASSICS and MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2008838"],"award-info":[{"award-number":["2008838"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an\n            <jats:italic>additive form<\/jats:italic>\n            defined as follows. Given an instance (\n            <jats:italic>I,k<\/jats:italic>\n            ) of some (parameterized) problem \u03c0 with a\n            <jats:italic>guarantee<\/jats:italic>\n            <jats:italic>g(I)<\/jats:italic>\n            , decide whether\n            <jats:italic>I<\/jats:italic>\n            admits a solution of size at least (or at most)\n            <jats:italic>k<\/jats:italic>\n            +\n            <jats:italic>g(I)<\/jats:italic>\n            . Here,\n            <jats:italic>g(I)<\/jats:italic>\n            is usually a lower bound on the minimum size of a solution. Since its introduction in 1999 for M\n            <jats:sc>AX<\/jats:sc>\n            SAT and M\n            <jats:sc>AX<\/jats:sc>\n            C\n            <jats:sc>UT<\/jats:sc>\n            (with\n            <jats:italic>g(I)<\/jats:italic>\n            being half the number of clauses and half the number of edges, respectively, in the input), analysis of parameterization above a guarantee has become a very active and fruitful topic of research.\n          <\/jats:p>\n          <jats:p>\n            We highlight a\n            <jats:italic>multiplicative<\/jats:italic>\n            form of parameterization above (or, rather, times) a guarantee: Given an instance (\n            <jats:italic>I,k<\/jats:italic>\n            ) of some (parameterized) problem \u03c0 with a guarantee\n            <jats:italic>g(I)<\/jats:italic>\n            , decide whether\n            <jats:italic>I<\/jats:italic>\n            admits a solution of size at least (or at most)\n            <jats:italic>k<\/jats:italic>\n            \u00b7\n            <jats:italic>g(I)<\/jats:italic>\n            . In particular, we study the\n            <jats:sc>Long Cycle<\/jats:sc>\n            problem with a multiplicative parameterization above the girth\n            <jats:italic>g(I)<\/jats:italic>\n            of the input graph, which is the most natural guarantee for this problem, and provide a fixed-parameter algorithm. Apart from being of independent interest, this exemplifies how parameterization above a multiplicative guarantee can arise naturally. We also show that, for any fixed constant \u03b5 &gt; 0, multiplicative parameterization above\n            <jats:italic>g(I)<\/jats:italic>\n            <jats:sup>1+\u03b5<\/jats:sup>\n            of\n            <jats:sc>Long Cycle<\/jats:sc>\n            yields para-NP-hardness, thus our parameterization is tight in this sense. We complement our main result with the design (or refutation of the existence) of fixed-parameter algorithms as well as kernelization algorithms for additional problems parameterized multiplicatively above girth.\n          <\/jats:p>","DOI":"10.1145\/3460956","type":"journal-article","created":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T17:35:03Z","timestamp":1640280903000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Multiplicative Parameterization Above a Guarantee"],"prefix":"10.1145","volume":"13","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Hyderabad, Sangareddy, Kandi, Telangana, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI, India and University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beersheba, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873645"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496833"},{"key":"e_1_2_1_3_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"80","author":"Bez\u00e1kov\u00e1 Ivona","unstructured":"Ivona Bez\u00e1kov\u00e1 , Radu Curticapean , Holger Dell , and Fedor V. Fomin . 2017. Finding detours is fixed-parameter tractable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 80 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 54:1\u201354:14. Ivona Bez\u00e1kov\u00e1, Radu Curticapean, Holger Dell, and Fedor V. Fomin. 2017. Finding detours is fixed-parameter tractable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)(Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 80. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 54:1\u201354:14."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Norman Biggs. 1998. Constructions for cubic graphs with large girth. Electron. J. Combin. (1998) A1\u2013A1.  Norman Biggs. 1998. Constructions for cubic graphs with large girth. Electron. J. Combin. (1998) A1\u2013A1.","DOI":"10.37236\/1386"},{"key":"e_1_2_1_5_1","volume-title":"Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, Adrian Bondy, Jean Fonlupt, Jean-Luc Fouquet, Jean-Claude Fournier, and Jorge L. Ram\u00edrez Alfons\u00edn (Eds.). Birkh\u00e4user Basel","author":"Birmel\u00e9 E.","unstructured":"E. Birmel\u00e9 , J. A. Bondy , and B. A. Reed . 2007. Brambles, prisms and grids . In Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, Adrian Bondy, Jean Fonlupt, Jean-Luc Fouquet, Jean-Claude Fournier, and Jorge L. Ram\u00edrez Alfons\u00edn (Eds.). Birkh\u00e4user Basel , Basel, 37\u201344. E. Birmel\u00e9, J. A. Bondy, and B. A. Reed. 2007. Brambles, prisms and grids. In Graph Theory in Paris: Proceedings of a Conference in Memory of Claude Berge, Adrian Bondy, Jean Fonlupt, Jean-Luc Fouquet, Jean-Claude Fournier, and Jorge L. Ram\u00edrez Alfons\u00edn (Eds.). Birkh\u00e4user Basel, Basel, 37\u201344."},{"key":"e_1_2_1_6_1","volume-title":"Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161","author":"Bj\u00f6rklund Andreas","year":"2010","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . 2010. Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 ( 2010 ). Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2010. Narrow sieves for parameterized paths and packings. CoRR abs\/1007.1161 (2010)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947374"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716475"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283415"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.10.002"},{"key":"e_1_2_1_14_1","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913)","volume":"24","author":"Crowston Robert","year":"2013","unstructured":"Robert Crowston , Mark Jones , Gabriele Muciaccia , Geevarghese Philip , Ashutosh Rai , and Saket Saurabh . 2013 . Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound . In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) (Leibniz International Proceedings in Informatics (LIPIcs)) , Vol. 24 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 43\u201354. Robert Crowston, Mark Jones, Gabriele Muciaccia, Geevarghese Philip, Ashutosh Rai, and Saket Saurabh. 2013. Polynomial kernels for lambda-extendible properties parameterized above the Poljak-Turzik bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201913) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 24. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 43\u201354."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_16_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2005. Graph Theory ( 3 rd ed.). Graduate Texts in Mathematics, Vol. 173 . Springer-Verlag , Berlin. xvi+411 pages. Reinhard Diestel. 2005. Graph Theory (3rd ed.). Graduate Texts in Mathematics, Vol. 173. Springer-Verlag, Berlin. xvi+411 pages.","edition":"3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2650261"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061862"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024498"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/3230521.3230526"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157"},{"key":"e_1_2_1_25_1","volume-title":"27th Annual European Symposium on Algorithms (ESA\u201919)","volume":"144","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin , Petr A. Golovach , Daniel Lokshtanov , Fahad Panolan , Saket Saurabh , and Meirav Zehavi . 2019 . Going far from degeneracy . In 27th Annual European Symposium on Algorithms (ESA\u201919) (Leibniz International Proceedings in Informatics (LIPIcs)), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.) , Vol. 144 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 47:1\u201347:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.47 10.4230\/LIPIcs.ESA.2019.47 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2019. Going far from degeneracy. In 27th Annual European Symposium on Algorithms (ESA\u201919) (Leibniz International Proceedings in Informatics (LIPIcs)), Michael A. Bender, Ola Svensson, and Grzegorz Herman (Eds.), Vol. 144. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 47:1\u201347:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.47"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.04.018"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328918"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9262-y"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.01.004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/140980946"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1330-6"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119176"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3236-x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119179"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9393-4"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_6"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1150037"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0996"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.08.004"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73110-4"},{"key":"e_1_2_1_45_1","first-page":"41","article-title":"Parameterized complexity for graph layout problems","volume":"86","author":"Serna Maria J.","year":"2005","unstructured":"Maria J. Serna and Dimitrios M. Thilikos . 2005 . Parameterized complexity for graph layout problems . Bull. EATCS 86 (2005), 41 \u2013 65 . Maria J. Serna and Dimitrios M. Thilikos. 2005. Parameterized complexity for graph layout problems. Bull. EATCS 86 (2005), 41\u201365.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_46_1","volume-title":"Faster deterministic parameterized algorithm for k-Path. CoRR abs\/1808.04185","author":"Tsur Dekel","year":"2018","unstructured":"Dekel Tsur . 2018. Faster deterministic parameterized algorithm for k-Path. CoRR abs\/1808.04185 ( 2018 ). arxiv:1808.04185.http:\/\/arxiv.org\/abs\/1808.04185 Dekel Tsur. 2018. Faster deterministic parameterized algorithm for k-Path. CoRR abs\/1808.04185 (2018). arxiv:1808.04185.http:\/\/arxiv.org\/abs\/1808.04185"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_86"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.02.005"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460956","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3460956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:22Z","timestamp":1750193302000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3460956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3460956"],"URL":"https:\/\/doi.org\/10.1145\/3460956","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,30]]},"assertion":[{"value":"2020-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}