Abstract
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 treedepth and the entry complexity of A, and when parameterized by the dual treedepth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its nonzero 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 treedepth 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 treedepth and entry complexity of a matrix equivalent to the constraint matrix, and when parameterized by the smallest dual treedepth and entry complexity of a matrix equivalent to the constraint matrix.
BibTeX  Entry
@InProceedings{brianski_et_al:LIPIcs.ICALP.2022.29,
author = {Bria\'{n}ski, Marcin and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na and Schr\"{o}der, Felix},
title = {{Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {29:129:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16370},
URN = {urn:nbn:de:0030drops163702},
doi = {10.4230/LIPIcs.ICALP.2022.29},
annote = {Keywords: Integer programming, width parameters, matroids, Graver basis, treedepth, fixed parameter tractability}
}
Keywords: 

Integer programming, width parameters, matroids, Graver basis, treedepth, fixed parameter tractability 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 