{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:00:26Z","timestamp":1750309226928,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Council of Norway via the project BWCA","award":["314528"],"award-info":[{"award-number":["314528"]}]},{"name":"ANR project ESIGMA","award":["ANR-17-CE23-0010"],"award-info":[{"award-number":["ANR-17-CE23-0010"]}]},{"name":"French-German Collaboration ANR\/DFG Project UTMA","award":["ANR-20-CE92-0027"],"award-info":[{"award-number":["ANR-20-CE92-0027"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,1,31]]},"abstract":"<jats:p>\n            We introduce the following submodular generalization of the\n            <jats:sc>Shortest Cycle<\/jats:sc>\n            problem. For a nonnegative monotone submodular cost function\n            <jats:italic>f<\/jats:italic>\n            defined on the edges (or the vertices) of an undirected graph\n            <jats:italic>G<\/jats:italic>\n            , we seek for a cycle\n            <jats:italic>C<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            of minimum cost \ud835\uddae\ud835\uddaf\ud835\uddb3 =\n            <jats:italic>f(C)<\/jats:italic>\n            . We give an algorithm that given an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            , parameter \u025b &gt; 0, and the function\n            <jats:italic>f<\/jats:italic>\n            represented by an oracle, in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\ud835\udcaa<\/jats:sup>\n            (log 1\/\u025b) finds a cycle\n            <jats:italic>C<\/jats:italic>\n            in\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>f(C)<\/jats:italic>\n            \u2264 (1+\u025b). \ud835\uddae\ud835\uddaf\ud835\uddb3. This is in sharp contrast with the non-approximability of the closely related\n            <jats:sc>\n              Monotone Submodular Shortest (\n              <jats:italic>s,t<\/jats:italic>\n              -Path\n            <\/jats:sc>\n            problem, which requires exponentially many queries to the oracle for finding an\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2\/3-\u025b<\/jats:sup>\n            -approximation Goel et\u00a0al. [\n            <jats:xref ref-type=\"bibr\">7<\/jats:xref>\n            ], FOCS 2009. We complement our algorithm with a matching lower bound. We show that for every \u025b &gt; 0, obtaining a (1+\u025b)-approximation requires at least\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9 (log 1\/ \u025b)<\/jats:sup>\n            queries to the oracle.\n          <\/jats:p>\n          <jats:p>\n            When the function\n            <jats:italic>f<\/jats:italic>\n            is integer-valued, our algorithm yields that a cycle of cost \ud835\uddae\ud835\uddaf\ud835\uddb3 can be found in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\ud835\udcaa(log \ud835\uddae\ud835\uddaf\ud835\uddb3)<\/jats:sup>\n            . In particular, for \ud835\uddae\ud835\uddaf\ud835\uddb3 =\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\ud835\udcaa(1)<\/jats:sup>\n            this gives a quasipolynomial-time algorithm computing a cycle of minimum submodular cost. Interestingly, while a quasipolynomial-time algorithm often serves as a good indication that a polynomial time complexity could be achieved, we show a lower bound that\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \ud835\udcaa(log\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            queries are required even when \ud835\uddae\ud835\uddaf\ud835\uddb3= \ud835\udcaa(\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            We also consider special cases of monotone submodular functions, corresponding to the number of different color classes needed to cover a cycle in an edge-colored multigraph\n            <jats:italic>G<\/jats:italic>\n            . For special cases of the corresponding minimization problem, we obtain fixed-parameter tractable algorithms and polynomial-time algorithms, when restricted to certain classes of inputs.\n          <\/jats:p>","DOI":"10.1145\/3626824","type":"journal-article","created":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T15:43:48Z","timestamp":1696520628000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Shortest Cycles with Monotone Submodular Costs"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-6515","authenticated-orcid":false,"given":"Tuukka","family":"Korhonen","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3166-9212","authenticated-orcid":false,"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4175-7793","authenticated-orcid":false,"given":"Giannos","family":"Stamoulis","sequence":"additional","affiliation":[{"name":"LIRMM, University of Montpellier, CNRS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,11,13]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"299","article-title":"Paths and cycles in colored graphs","volume":"31","author":"Broersma Hajo","year":"2005","unstructured":"Hajo Broersma, Xueliang Li, Gerhard J. Woeginger, and Shenggui Zhang. 2005. Paths and cycles in colored graphs. Australas. J. Comb. 31 (2005), 299\u2013312. http:\/\/ajc.maths.uq.edu.au\/pdf\/31\/ajc_v31_p299.pdf","journal-title":"Australas. J. Comb."},{"doi-asserted-by":"publisher","key":"e_1_3_1_3_2","DOI":"10.1007\/BF02579361"},{"doi-asserted-by":"publisher","key":"e_1_3_1_4_2","DOI":"10.1007\/978-3-662-53622-3"},{"doi-asserted-by":"publisher","key":"e_1_3_1_5_2","DOI":"10.1007\/BF01386390"},{"doi-asserted-by":"publisher","key":"e_1_3_1_6_2","DOI":"10.1109\/SFCS.1984.715934"},{"doi-asserted-by":"publisher","key":"e_1_3_1_7_2","DOI":"10.5555\/3039686.3039757"},{"doi-asserted-by":"publisher","key":"e_1_3_1_8_2","DOI":"10.1109\/FOCS.2009.81"},{"doi-asserted-by":"publisher","key":"e_1_3_1_9_2","DOI":"10.1137\/1.9781611973068"},{"doi-asserted-by":"publisher","key":"e_1_3_1_10_2","DOI":"10.1007\/BF02579273"},{"doi-asserted-by":"publisher","key":"e_1_3_1_11_2","DOI":"10.1145\/502090.502096"},{"doi-asserted-by":"publisher","key":"e_1_3_1_12_2","DOI":"10.1109\/FOCS.2009.31"},{"doi-asserted-by":"publisher","key":"e_1_3_1_13_2","DOI":"10.5555\/1496770.1496903"},{"key":"e_1_3_1_14_2","article-title":"A tight quasi-polynomial bound for Global Label Min-Cut","volume":"2207","author":"Jaffke Lars","year":"2022","unstructured":"Lars Jaffke, Paloma T. Lima, Tom\u00e1s Masar\u00edk, Marcin Pilipczuk, and U\u00e9verton S. Souza. 2022. A tight quasi-polynomial bound for Global Label Min-Cut. CoRR abs\/2207.07426 (2022). arXiv:2207.07426","journal-title":"CoRR"},{"doi-asserted-by":"publisher","key":"e_1_3_1_15_2","DOI":"10.1137\/1.9781611977554.ch12"},{"doi-asserted-by":"publisher","key":"e_1_3_1_16_2","DOI":"10.1007\/s10107-016-1038-y"},{"doi-asserted-by":"publisher","key":"e_1_3_1_17_2","DOI":"10.1006\/jctb.2000.1989"},{"doi-asserted-by":"publisher","key":"e_1_3_1_18_2","DOI":"10.1137\/10078335"},{"doi-asserted-by":"publisher","key":"e_1_3_1_19_2","DOI":"10.1007\/BF02579435"},{"doi-asserted-by":"publisher","key":"e_1_3_1_20_2","DOI":"10.1007\/s10878-009-9222-0"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626824","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:15Z","timestamp":1750290255000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1,31]]}},"alternative-id":["10.1145\/3626824"],"URL":"https:\/\/doi.org\/10.1145\/3626824","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"2022-11-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}