{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:53Z","timestamp":1750309313374,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"Institute for Basic Science","award":["IBS-R029-C1"],"award-info":[{"award-number":["IBS-R029-C1"]}]},{"name":"JSPS KAKENHI","award":["JP20A402 and 22H05001"],"award-info":[{"award-number":["JP20A402 and 22H05001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649682","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"692-703","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Packing Even Directed Circuits Quarter-Integrally"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-7816-7084","authenticated-orcid":false,"given":"Maximilian","family":"Gorsky","sequence":"first","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6056-4287","authenticated-orcid":false,"given":"Ken-ichi","family":"Kawarabayashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan \/ The University of Tokyo, Tokyo, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9409-5356","authenticated-orcid":false,"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[{"name":"TU Berlin, Berlin, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0462-7815","authenticated-orcid":false,"given":"Sebastian","family":"Wiederrecht","sequence":"additional","affiliation":[{"name":"Institute for Basic Science, Daejeon, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190050102"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520030"},{"volume-title":"Graph theory","author":"Bondy John Adrian","key":"e_1_3_2_1_3_1","unstructured":"John Adrian Bondy and Uppaluri Siva Ramachandra Murty. 2008. Graph theory. Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2157-8"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0030-1"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.176"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45771-6_9"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.29"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-035-8"},{"key":"e_1_3_2_1_10_1","volume-title":"16th Annual Symposium on Foundations of Computer Science","author":"Even S.","year":"1975","unstructured":"S. Even, A. Itai, and A. Shamir. 1975. On the complexity of timetable and multi-commodity flow problems. In 16th Annual Symposium on Foundations of Computer Science (Univ. California, Berkeley, Calif., 1975). IEEE, Long Beach, CA, 184\u2013193."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.03.006"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.15"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.19"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch81"},{"key":"e_1_3_2_1_16_1","unstructured":"Archontia C Giannopoulou and Sebastian Wiederrecht. 2021. Two Disjoint Alternating Paths in Bipartite Graphs. arXiv preprint arXiv:2110.02013."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms.12858"},{"key":"e_1_3_2_1_18_1","unstructured":"J Pascal Gollin Kevin Hendrey O-joung Kwon Sang-il Oum and Youngho Yoo. 2022. A unified Erd\u0151s-P\u00f3sa theorem for cycles in graphs labelled by multiple abelian groups. arXiv preprint arXiv:2209.09488."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Maximilian Gorsky Ken-ichi Kawarabayashi Stephan Kreutzer and Sebastian Wiederrecht. 2023. Packing even directed circuits quarter-integrally. arXiv preprint arXiv:2311.16816.","DOI":"10.1145\/3618260.3649682"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-1687-5"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-017-3683-z"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-017-3683-z"},{"key":"e_1_3_2_1_23_1","unstructured":"Lars Jaffke Laure Morelle Ignasi Sau and Dimitrios M Thilikos. 2023. Dynamic programming on bipartite tree decompositions. arXiv preprint arXiv:2309.07754."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451068"},{"volume-title":"Eulerian Digraph Immersion","author":"Thor Johnson Carl Darwin","key":"e_1_3_2_1_25_1","unstructured":"Carl Darwin Thor Johnson. 2002. Eulerian Digraph Immersion. Princeton University."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2031"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53174-7_24"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/100786423"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Kakimura Naonori","year":"2012","unstructured":"Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi. 2012. Erd\u0151s-P\u00f3sa property and its algorithmic applications\u2014parity constraints, subset feedback set, and subset packing. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 1726\u20131736. isbn:978-1-611972-11-5"},{"key":"e_1_3_2_1_30_1","first-page":"52","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Kawarabayashi K.","year":"1972","unstructured":"K. Kawarabayashi, D. Kr\u00e1l\u2019, M. Kr\u010d\u00e1l, and S. Kreutzer. 2012. Packing directed cycles through a specified vertex set. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 365\u2013377. isbn:978-1-611972-52-8"},{"key":"e_1_3_2_1_31_1","volume-title":"2015 ACM Symposium on Theory of Computing. ACM","author":"Stephan Kreutzer Kawarabayashi","year":"2015","unstructured":"Ken-ichi Kawarabayashi and Stephan Kreutzer. 2015. The directed grid theorem. In STOC\u201915\u2014Proceedings of the 2015 ACM Symposium on Theory of Computing. ACM, New York, 655\u2013664. isbn:978-1-4503-3536-2"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch118"},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Bruce Reed Kawarabayashi","year":"2010","unstructured":"Ken-ichi Kawarabayashi and Bruce Reed. 2010. An (almost) linear time algorithm for odd cycles transversal. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 365\u2013378."},{"key":"e_1_3_2_1_34_1","volume-title":"2010 ACM International Symposium on Theory of Computing. ACM","author":"Bruce Reed Kawarabayashi","year":"2010","unstructured":"Ken-ichi Kawarabayashi and Bruce Reed. 2010. Odd cycle packing [extended abstract]. In STOC\u201910\u2014Proceedings of the 2010 ACM International Symposium on Theory of Computing. ACM, New York, 695\u2013704. isbn:978-1-60558-817-9"},{"key":"e_1_3_2_1_35_1","unstructured":"Ken-ichi Kawarabayashi Robin Thomas and Paul Wollan. 2020. Quickly Excluding a Non-Planar Graph. arXiv preprint arXiv:2010.12397."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140403"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(75)90048-9"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.134"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","unstructured":"W. Mader. 1978\/79. \u00dcber die Maximalzahl kreuzungsfreier H-Wege. Arch. Math. (Basel) 31 4 (1978\/79) 387\u2013402. issn:0003-889X 1420-8938 https:\/\/doi.org\/10.1007\/BF01226465 10.1007\/BF01226465","DOI":"10.1007\/BF01226465"},{"key":"e_1_3_2_1_41_1","first-page":"124","volume-title":"27th Annual European Symposium on Algorithms (LIPIcs. Leibniz Int. Proc. Inform.","volume":"72","author":"Masa\u0159\u00edk Tom\u00e1\u0161","year":"2019","unstructured":"Tom\u00e1\u0161 Masa\u0159\u00edk, Irene Muzi, Marcin Pilipczuk, Pawe\u0142 Rza\u017cewski, and Manuel Sorge. 2019. Packing directed circuits quarter-integrally. In 27th Annual European Symposium on Algorithms (LIPIcs. Leibniz Int. Proc. Inform., Vol. 144). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 72, 13. isbn:978-3-95977-124-5"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379861.1379865"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1380483.1380485"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.37236\/1832"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258625"},{"key":"e_1_3_2_1_46_1","first-page":"271","article-title":"Aufgabe 424","volume":"20","author":"P\u00f3lya Gyorgy","year":"1913","unstructured":"Gyorgy P\u00f3lya. 1913. Aufgabe 424. Archiv der Mathematik und Physik, 20 (1913), 271.","journal-title":"Archiv der Mathematik und Physik"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050056"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01271272"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_3_2_1_50_1","article-title":"Graph Minors I to Graph Minors XX","author":"Robertson Neil","year":"1983","unstructured":"Neil Robertson and Paul D Seymour. 1983. Graph Minors I to Graph Minors XX. Journal of Combinatorial Theory, Series B.","journal-title":"Journal of Combinatorial Theory, Series B."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.2307\/121059"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224061"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01844848"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(87)90061-X"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958204.1958207"},{"key":"e_1_3_2_1_60_1","volume-title":"Parameterized Algorithms for Directed Modular Width. In Conference on Algorithms and Discrete Applied Mathematics. 415\u2013426","author":"Steiner Raphael","year":"2020","unstructured":"Raphael Steiner and Sebastian Wiederrecht. 2020. Parameterized Algorithms for Directed Modular Width. In Conference on Algorithms and Discrete Applied Mathematics. 415\u2013426."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00104"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.02.011"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2307\/2152767"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90053-X"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.05.003"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2551-5"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1137\/130949877"},{"key":"e_1_3_2_1_69_1","volume-title":"Proceedings of the Midwest symposium on circuit theory. 2, XVI\u20132.","author":"Younger Daniel H","year":"1973","unstructured":"Daniel H Younger. 1973. Graphs with interlinked directed circuits. In Proceedings of the Midwest symposium on circuit theory. 2, XVI\u20132."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649682","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649682","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649682"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":69,"alternative-id":["10.1145\/3618260.3649682","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649682","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}