Integer programs with bounded subdeterminants and two nonzeros per row
Samuel Fiorini, Gwenaël Joret, Stefan Weltge, Yelena Yuditsky
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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> vertex-disjoint odd cycles, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k$</tex> is any constant. Previously, polynomial-time algorithms were only known for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k=0$</tex> (bipartite graphs) and for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$k=1$</tex> . 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.