{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:09Z","timestamp":1750220829787,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            We consider the fundamental Matroid Theory problem of finding a circuit in a matroid containing a set\n            <jats:italic>T<\/jats:italic>\n            of given terminal elements. For graphic matroids, this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gaven\u010diak, Kr\u00e1l\u2019, and Oum [ICALP\u201912], who proved that the case of the problem with \u2223T\u2223 = 2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gaven\u010diak, Kr\u00e1l\u2019, and Oum by showing that for regular matroids\n          <\/jats:p>\n          <jats:p>\n            \u2022 the M\n            <jats:sc>inimum<\/jats:sc>\n            S\n            <jats:sc>panning<\/jats:sc>\n            C\n            <jats:sc>ircuit<\/jats:sc>\n            problem, deciding whether there is a circuit with at most \u2113 elements containing\n            <jats:italic>T<\/jats:italic>\n            , is FPT parameterized by\n            <jats:italic>k<\/jats:italic>\n            = \u2113 \u2212 \u2223T\u2223\n          <\/jats:p>\n          <jats:p>\n            \u2022 the S\n            <jats:sc>panning<\/jats:sc>\n            C\n            <jats:sc>ircuit<\/jats:sc>\n            problem, deciding whether there is a circuit containing \u2223T\u2223, is FPT parameterized by \u2223T\u2223.\n          <\/jats:p>\n          <jats:p>\n            We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: M\n            <jats:sc>inimum<\/jats:sc>\n            S\n            <jats:sc>panning<\/jats:sc>\n            C\n            <jats:sc>ircuit<\/jats:sc>\n            parameterized by \u2113 is W[1]-hard on binary matroids even when \u2223T\u2223 = 1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that M\n            <jats:sc>inimum<\/jats:sc>\n            S\n            <jats:sc>panning<\/jats:sc>\n            C\n            <jats:sc>ircuit<\/jats:sc>\n            parameterized by \u2223T\u2223 is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.\n          <\/jats:p>","DOI":"10.1145\/3355629","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T12:20:59Z","timestamp":1570450859000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Spanning Circuits in Regular Matroids"],"prefix":"10.1145","volume":"15","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, University of California Santa Barbara, Santa Barbara, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway and The Institute of Mathematical Sciences, HBNI, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Bhattacharyya Arnab","year":"2018","unstructured":"Arnab Bhattacharyya , Suprovat Ghoshal , Karthik C. S., and Pasin Manurangsi . 2018 . Parameterized intractability of even set and shortest vector problem from gap-ETH . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) , Vol. 107 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17:1--17:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2018.17 10.4230\/LIPIcs.ICALP.2018.17 Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. 2018. Parameterized intractability of even set and shortest vector problem from gap-ETH. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918), Vol. 107. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17:1--17:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.17"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.139"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm086"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_22"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820609"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1032077"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_8_1","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3 10.1007\/978-3-319-21275-3 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. DOI:https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2041"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/13094030X"},{"key":"e_1_2_1_12_1","volume-title":"Electr. Colloq. Comput. Complex. 23","author":"Dinur Irit","year":"2016","unstructured":"Irit Dinur . 2016 . Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover . Electr. Colloq. Comput. Complex. 23 (2016), 128. Irit Dinur. 2016. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electr. Colloq. Comput. Complex. 23 (2016), 128."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19600220107"},{"key":"e_1_2_1_14_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . DOI:https:\/\/doi.org\/10.1007\/978-1-4471-5559-1 10.1007\/978-1-4471-5559-1 Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer. DOI:https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797323571"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90128-I"},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 39th International Colloquium of Automata, Languages and Programming (ICALP\u201912)","author":"Gavenciak Tom\u00e1s","unstructured":"Tom\u00e1s Gavenciak , Daniel Kr\u00e1l , and Sang-il Oum. 2012. Deciding first order properties of matroids . In Proceedings of the 39th International Colloquium of Automata, Languages and Programming (ICALP\u201912) , Lecture Notes in Computer Science , Vol. 7392 . Springer , 239--250. Tom\u00e1s Gavenciak, Daniel Kr\u00e1l, and Sang-il Oum. 2012. Deciding first order properties of matroids. In Proceedings of the 39th International Colloquium of Automata, Languages and Programming (ICALP\u201912), Lecture Notes in Computer Science, Vol. 7392. Springer, 239--250."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/noti1139"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2001.2059"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908)","volume":"5035","year":"2008","unstructured":"Ken-ichi Kawarabayashi. 2008 . An improved algorithm for finding cycles through elements . In Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908) , Lecture Notes in Computer Science , Vol. 5035 . Springer, 374--384. Ken-ichi Kawarabayashi. 2008. An improved algorithm for finding cycles through elements. In Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization (IPCO\u201908), Lecture Notes in Computer Science, Vol. 5035. Springer, 374--384."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS\u201911)","author":"Mikkel Thorup Kawarabayashi","year":"2011","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup . 2011 . The minimum k-way cut of bounded size is fixed-parameter tractable . In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS\u201911) . IEEE Computer Society, 160--169. Ken-ichi Kawarabayashi and Mikkel Thorup. 2011. The minimum k-way cut of bounded size is fixed-parameter tractable. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS\u201911). IEEE Computer Society, 160--169."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90057-4"},{"key":"e_1_2_1_23_1","article-title":"Faster parameterized algorithms using linear programming","volume":"11","author":"Lokshtanov Daniel","year":"2014","unstructured":"Daniel Lokshtanov , N. S. Narayanaswamy , Venkatesh Raman , M. S. Ramanujan , and Saket Saurabh . 2014 . Faster parameterized algorithms using linear programming . ACM Trans. Algor. 11 , 2 (2014), 15:1--15:31. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. 2014. Faster parameterized algorithms using linear programming. ACM Trans. Algor. 11, 2 (2014), 15:1--15:31.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017","volume":"80","author":"Manurangsi Pasin","year":"2017","unstructured":"Pasin Manurangsi and Prasad Raghavendra . 2017 . A birthday repetition theorem and complexity of approximating dense CSPs . In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017 ), Vol. 80 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 78:1--78:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2017.78 10.4230\/LIPIcs.ICALP.2017.78 Pasin Manurangsi and Prasad Raghavendra. 2017. A birthday repetition theorem and complexity of approximating dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Vol. 80. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 78:1--78:15. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.78"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.02.001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796315"},{"volume-title":"Matroid Theory","author":"Oxley James G.","key":"e_1_2_1_27_1","unstructured":"James G. Oxley . 1992. Matroid Theory . Oxford University Press . James G. Oxley. 1992. Matroid Theory. Oxford University Press."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200909"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90075-1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579179"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80044-0"},{"key":"e_1_2_1_33_1","unstructured":"Klaus Truemper. 1992. Matroid Decomposition. Academic Press.  Klaus Truemper. 1992. Matroid Decomposition. Academic Press."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258559"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371182"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:29Z","timestamp":1750202009000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3355629"],"URL":"https:\/\/doi.org\/10.1145\/3355629","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,10,4]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}