{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:35Z","timestamp":1781305055255,"version":"3.54.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_1","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:18Z","timestamp":1781303598000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Complexity of\u00a0the\u00a0Odd-Red Bipartite Perfect Matching Polytope"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3059-6402","authenticated-orcid":false,"given":"Martin","family":"N\u00e4gele","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6864-1953","authenticated-orcid":false,"given":"Christian","family":"N\u00f6bel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7148-9304","authenticated-orcid":false,"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodular integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1206\u20131219 (2017)","DOI":"10.1145\/3055399.3055473"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Balas, E.: Disjunctive Programming. Springer, Cham (2018)","DOI":"10.1007\/978-3-030-00148-3"},{"key":"1_CR3","unstructured":"Boyd, S.: The Subtour Polytope of the Travelling Salesman Problem. PhD thesis, University of Waterloo (1986)"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Cevallos, A., Weltge, S., Zenklusen, R.: Lifting linear extension complexity bounds to the mixed-integer setting. In: Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 788\u2013807 (2018)","DOI":"10.1137\/1.9781611975031.51"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Fenner, S., Gurjar, R., Thierauf, T.: Bipartite perfect matching is in quasi-NC. In: Proceedings of the 48th ACM Symposium on Theory of Computing (STOC) (2016)","DOI":"10.1145\/2897518.2897564"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"Gurjar, R., Thierauf, T.: Linear matroid intersection is in quasi-NC. Comput. Complex. (2020)","DOI":"10.1007\/s00037-020-00200-z"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"636","DOI":"10.1137\/19M1290802","volume":"50","author":"R Gurjar","year":"2021","unstructured":"Gurjar, R., Thierauf, T., Vishnoi, N.K.: Isolating a vertex via lattices: polytopes with totally unimodular faces. SIAM J. Comput. 50(2), 636\u2013661 (2021)","journal-title":"SIAM J. Comput."},{"key":"1_CR8","unstructured":"H\u00f6rsch, F., Imolay, A., Mizutani, R., Oki, T., Schwarcz, T.: Problems on group-labeled matroid bases. In: Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 86:1\u201386:20 (2024)"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"Jia, X., Svensson, O., Yuan, W.: The exact bipartite matching polytope has exponential extension complexity. In: Proceedings of the 2023 Annual ACMSIAM Symposium on Discrete Algorithms (SODA), pp. 1635\u20131654 (2023)","DOI":"10.1137\/1.9781611977554.ch61"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Liu, S., Xu, C.: On the congruency-constrained matroid base. In: Proceedings of the 2024 Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 280\u2013293 (2024)","DOI":"10.1007\/978-3-031-59835-7_21"},{"key":"1_CR11","doi-asserted-by":"crossref","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 345\u2013354 (1987)","DOI":"10.1145\/28395.383347"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"N\u00e4gele, M., N\u00f6bel, C., Santiago, R., Zenklusen, R.: Advances on strictly $$\\Delta $$-modular IPs. In: Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 393\u2013407 (2023)","DOI":"10.1007\/978-3-031-32726-1_28"},{"key":"1_CR13","unstructured":"N\u00e4gele, M., N\u00f6bel, C., Zenklusen, R.: On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope (2026). arXiv: 2603.18232 [cs.DS]"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1287\/moor.2023.1381","volume":"49","author":"M N\u00e4gele","year":"2023","unstructured":"N\u00e4gele, M., Santiago, R., Zenklusen, R.: Congruency-constrained TU problems beyond the bimodular case. Math. Oper. Res. 49(3), 1303\u20131348 (2023)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"1_CR15","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00493-019-3900-1","volume":"39","author":"M N\u00e4gele","year":"2019","unstructured":"N\u00e4gele, M., Sudakov, B., Zenklusen, R.: Submodular minimization under congruency constraints. Combinatorica 39(6), 1351\u20131386 (2019). https:\/\/doi.org\/10.1007\/s00493-019-3900-1","journal-title":"Combinatorica"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"N\u00e4gele, M., Zenklusen, R.: A new contraction technique with applications to congruency-constrained cuts. Math. Program. 183(1), 455\u2013481 (2020)","DOI":"10.1007\/s10107-020-01498-x"},{"issue":"7","key":"1_CR17","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"1","author":"MW Padberg","year":"1982","unstructured":"Padberg, M.W., Rao, M.R.: Odd minimum cut-sets and $$b$$-matchings. Math. Oper. Res. 1(7), 67\u201380 (1982)","journal-title":"Math. Oper. Res."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.endm.2007.01.025","volume":"28","author":"A P\u00eacher","year":"2007","unstructured":"P\u00eacher, A., Pesneau, P., Wagler, A.K.: On facets of stable set polytopes of claw-free graphs with stability number three. Electron. Notes Disc. Math. 28, 185\u2013190 (2007)","journal-title":"Electron. Notes Disc. Math."},{"issue":"6","key":"1_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvo\u00df","year":"2017","unstructured":"Rothvo\u00df, T.: The matching polytope has exponential extension complexity. J. ACM 64(6), 1\u201319 (2017)","journal-title":"J. ACM"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Svensson, O., Tarnawski, J.: The matching problem in general graphs is in quasi-NC. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 696\u2013707 (2017)","DOI":"10.1109\/FOCS.2017.70"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:23Z","timestamp":1781303603000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}