Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming

• 成果类型: Article
• 署名作者: Brianski, Marcin; Koutecky, Martin; Kral, Daniel; Pekarkova, Kristyna; Schroder, Felix
• 署名单位: Jagiellonian University; Charles University Prague; Masaryk University; Charles University Prague
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02048-x
• 发表日期: 2024
• 页码: 497-531
• 关键词: monadic 2nd-order logic; branch-width; parse trees; DECOMPOSITION; algorithm

摘要

An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the l(1)-norm of the Graver basis is bounded by a function of the maximum l(1)-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the l(1)-norm of the Graver basis of the constraint matrix, when parameterized by the l(1)-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.