{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T06:22:58Z","timestamp":1781072578402,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Belgian National Fund for Scientific Research"},{"name":"PDR","award":["BD-OCP"],"award-info":[{"award-number":["BD-OCP"]}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["451026932"],"award-info":[{"award-number":["451026932"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"<jats:p>\n            We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than\n            <jats:italic>k<\/jats:italic>\n            vertex-disjoint odd cycles, where\n            <jats:italic>k<\/jats:italic>\n            is any constant. Previously, polynomial-time algorithms were only known for\n            <jats:italic>k<\/jats:italic>\n            =0 (bipartite graphs) and for\n            <jats:italic>k<\/jats:italic>\n            =1.\n          <\/jats:p>\n          <jats:p>\n            We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to\n            <jats:italic>b<\/jats:italic>\n            -matching.\n          <\/jats:p>","DOI":"10.1145\/3695985","type":"journal-article","created":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T08:03:21Z","timestamp":1726214601000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Integer programs with bounded subdeterminants and two nonzeros per row"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6845-9008","authenticated-orcid":false,"given":"Samuel","family":"Fiorini","sequence":"first","affiliation":[{"name":"Department of Mathematics, Universit\u00e9 libre de Bruxelles, Bruxelles, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7157-6694","authenticated-orcid":false,"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[{"name":"Computer Science Department, Universit\u00e9 libre de Bruxelles, Bruxelles, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0102-8326","authenticated-orcid":false,"given":"Stefan","family":"Weltge","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Munchen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6467-3437","authenticated-orcid":false,"given":"Yelena","family":"Yuditsky","sequence":"additional","affiliation":[{"name":"Computer Science Department, Universit\u00e9 libre de Bruxelles, Bruxelles, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1793-8"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055473"},{"key":"e_1_3_3_4_2","series-title":"(LIPIcs","first-page":"187","volume-title":"Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science","volume":"29","author":"Bock Adrian","year":"2014","unstructured":"Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres Jacinto Ruiz-Vargas. 2014. Solving the stable set problem in terms of the odd cycle packing number. In Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science(LIPIcs, Vol. 29). Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 187\u2013198."},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","unstructured":"Nicolas Bonifas Marco Di Summa Friedrich Eisenbrand Nicolai H\u00e4hnle and Martin Niemeier. 2014. On sub-determinants and the diameter of polyhedra. Discr. Comput. Geom. 52 1 (2014) 102\u2013115.","DOI":"10.1007\/s00454-014-9601-x"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.176"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45771-6_9"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","unstructured":"W. Cook A. M. H. Gerards A. Schrijver and \u00c9. Tardos. 1986. Sensitivity theorems in integer linear programming. Math. Program. 34 3 (1986) 251\u2013264.","DOI":"10.1007\/BF01582230"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.101"},{"key":"e_1_3_3_10_2","volume-title":"Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation","author":"Dadush Daniel","year":"2012","unstructured":"Daniel Dadush. 2012. Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation. Ph.D. Dissertation. Georgia Institute of Technology."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.28"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Reinhard Diestel Ken-ichi Kawarabayashi Theodor M\u00fcller and Paul Wollan. 2012. On the excluded minor structure theorem for graphs of large tree-width. J. Combin. Theor. Ser. B 102 6 (2012) 1189\u20131210.","DOI":"10.1016\/j.jctb.2012.07.001"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","unstructured":"Martin Dyer and Alan Frieze. 1994. Random walks totally unimodular matrices and a randomised dual simplex algorithm. Math. Program. 64 1-3 (1994) 1\u201316.","DOI":"10.1007\/BF01582563"},{"key":"e_1_3_3_14_2","volume-title":"Combinatorial Structures and Their Applications: Proceedings of the Calgary Symposium, June 1969","author":"Edmonds Jack","year":"1907","unstructured":"Jack Edmonds and Ellis L. Johnson. 1907. Matching: A well-solved class of linear programs. In Combinatorial Structures and Their Applications: Proceedings of the Calgary Symposium, June 1969. Gordon and Breach, New York."},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"Friedrich Eisenbrand and Santosh Vempala. 2017. Geometric random edge. Math. Program. 164 1-2 (2017) 325\u2013339.","DOI":"10.1007\/s10107-016-1089-0"},{"key":"e_1_3_3_16_2","doi-asserted-by":"crossref","unstructured":"Friedrich Eisenbrand and Robert Weismantel. 2019. Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algor. 16 1 (2019) 1\u201314.","DOI":"10.1145\/3340322"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","unstructured":"Jim Geelen Bert Gerards Bruce Reed Paul Seymour and Adrian Vetta. 2009. On the odd-minor variant of Hadwiger\u2019s conjecture. J. Combin. Theor Ser. B 99 1 (2009) 20\u201329. JCBTB8DOI:10.1016\/j.jctb.2008.03.006","DOI":"10.1016\/j.jctb.2008.03.006"},{"key":"e_1_3_3_18_2","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans and Thomas Rothvoss. 2020. Polynomiality for bin packing with a constant number of item types. J. ACM 67 6 (2020) 1\u201321.","DOI":"10.1145\/3421750"},{"key":"e_1_3_3_19_2","doi-asserted-by":"crossref","unstructured":"Jerrold W. Grossman Devadatta M. Kulkarni and Irwin E. Schochetman. 1995. On the minors of an incidence matrix and its Smith normal form. Lin. Algeb. Appl. 218 (1995) 213\u2013224.","DOI":"10.1016\/0024-3795(93)00173-W"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","unstructured":"Raymond Hemmecke Shmuel Onn and Lyubov Romanchuk. 2013. N-fold integer programming in cubic time. Math. Program. 137 1 (2013) 325\u2013341.","DOI":"10.1007\/s10107-011-0490-y"},{"key":"e_1_3_3_21_2","doi-asserted-by":"crossref","unstructured":"Dorit S. Hochbaum Nimrod Megiddo Joseph (Seffi) Naor and Arie Tamir. 1993. Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62 (1993) 69\u201383.","DOI":"10.1007\/BF01585160"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2019.44"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","unstructured":"Klaus Jansen Alexandra Lassota and Lars Rohwedder. 2020. Near-linear time algorithm for n-fold ILPs via color coding. SIAM J. Discr. Math. 34 4 (2020) 2282\u20132299.","DOI":"10.1137\/19M1303873"},{"key":"e_1_3_3_24_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"Johnson David S.","year":"1979","unstructured":"David S. Johnson and Michael R. Garey. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman."},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","unstructured":"Ravi Kannan. 1987. Minkowski\u2019s convex body theorem and integer programming. Math. Oper. Res. 12 3 (1987) 415\u2013440.","DOI":"10.1287\/moor.12.3.415"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.31"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806785"},{"key":"e_1_3_3_28_2","unstructured":"Ken-ichi Kawarabayashi Robin Thomas and Paul Wollan. 2020. Quickly Excluding a Non-planar Graph. (2020). arXiv:2010.12397"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","unstructured":"Hendrik W. Lenstra Jr. 1983. Integer programming with a fixed number of variables. Math. Oper. Res. 8 4 (1983) 538\u2013548.","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_3_30_2","unstructured":"Bojan Mohar. 1997. Face-width of embedded graphs. Math. Slov. 47 1 (1997) 35\u201363."},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.162"},{"key":"e_1_3_3_33_2","doi-asserted-by":"crossref","unstructured":"G. L. Nemhauser and L. E. Trotter Jr. 1974. Properties of vertex packing and independence system polyhedra. Math. Program. 6 (1974) 48\u201461.","DOI":"10.1007\/BF01580222"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","unstructured":"George L. Nemhauser and Leslie Earl Trotter. 1975. Vertex packings: Structural properties and algorithms. Math. Program. 8 1 (1975) 232\u2013248.","DOI":"10.1007\/BF01580444"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45771-6_26"},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou. 1981. On the complexity of integer programming. J. ACM 28 4 (1981) 765\u2013768.","DOI":"10.1145\/322276.322287"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","unstructured":"Bruce Reed. 1999. Mangoes and blueberries. Combinatorica 19 2 (1999) 267\u2013296. DOI:10.1007\/s004930050056","DOI":"10.1007\/s004930050056"},{"key":"e_1_3_3_38_2","doi-asserted-by":"crossref","unstructured":"Neil Robertson and Paul D. Seymour. 2003. Graph minors. XVI. Excluding a non-planar graph. J. Combin. Theor Ser. B 89 1 (2003) 43\u201376. JCBTB8","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_3_39_2","first-page":"293","volume-title":"Paths, Flows, and VLSI-Layout","author":"Robertson Neil","year":"1990","unstructured":"Neil Robertson and Richard P. Vitray. 1990. Representativity of surface embeddings. In Paths, Flows, and VLSI-Layout. Springer-Verlag Berlin, 293\u2013298."},{"key":"e_1_3_3_40_2","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","year":"1998","unstructured":"Alexander Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons."},{"key":"e_1_3_3_41_2","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Vol. 24. Springer Science & Business Media."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044488002-4\/50012-9"},{"key":"e_1_3_3_43_2","doi-asserted-by":"crossref","unstructured":"Eva Tardos. 1986. A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34 2 (1986) 250\u2013256.","DOI":"10.1287\/opre.34.2.250"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","unstructured":"Siamak Tazari. 2012. Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs. Theoret. Comput. Sci. 417 (2012) 95\u2013107. DOI:10.1016\/j.tcs.2011.09.014","DOI":"10.1016\/j.tcs.2011.09.014"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","unstructured":"Sergey I. Veselov and Aleksandr J. Chirkov. 2009. Integer program with bimodular matrix. Discr. Optim. 6 2 (2009) 220\u2013222.","DOI":"10.1016\/j.disopt.2008.12.002"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","unstructured":"Jonas T. Witt Marco E. L\u00fcbbecke and Bruce Reed. 2018. Polyhedral results on the stable set problem in graphs containing even or odd pairs. Math. Program. 171 1 (2018) 519\u2013522.","DOI":"10.1007\/s10107-017-1168-x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695985","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695985","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:30Z","timestamp":1750291470000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695985"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3695985"],"URL":"https:\/\/doi.org\/10.1145\/3695985","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"2022-12-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-22","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}