Preconditioners for matrix sparsity

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 parameterizations 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 an equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ₁-norm of the Graver basis is bounded by a function of the maximum ℓ₁-norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a  matrix equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such an equivalent matrix exists.

Our results yield parameterized algorithms for integer programming when parameterized by the ℓ₁-norm of the Graver basis of the constraint matrix, when parameterized by the ℓ₁-norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a  matrix equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix equivalent to the constraint matrix.

The talk is based on the results of joint work with M. Briański, M. Koutecký, D. Kráľ, and F. Schröder.