Id: arxiv/2611.13065 Url: https://arxiv.org/abs/2611.13065 Tags: cs.DS, cs.DM, math.CO, math.OC Score: 0 Title: Combinatorial optimization with bounded subdeterminants Domain: cs.DS Source: arxiv Authors: Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon, Sang-il Oum, Roohani Sharma, Stefan Weltge Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-09 Page: https://delphi.science/r/arxiv/2611.13065 We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular.…