@inproceedings{1ad60a64ad394e74b6aea0f148eb9b9b,
title = "Integer programs with bounded subdeterminants and two nonzeros per row",
abstract = "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 k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1. 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 b-matching.",
keywords = "integer programming, odd cycle packing number, stable set, subdeterminants",
author = "Samuel Fiorini and Gwenael Joret and Stefan Weltge and Yelena Yuditsky",
note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021 ; Conference date: 07-02-2022 Through 10-02-2022",
year = "2022",
doi = "10.1109/FOCS52979.2021.00011",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "13--24",
booktitle = "Proceedings - 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science, FOCS 2021",
}