Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

CHAN Timothy Fong Nam COOPER Jacob KOUTECKÝ Martin KRÁĽ Daniel PEKÁRKOVÁ Kristýna

Year of publication 2022
Type Article in Periodical
Magazine / Source SIAM JOURNAL ON COMPUTING
MU Faculty or unit

Faculty of Informatics

Citation
Web https://epubs.siam.org/doi/10.1137/20M1353502
Doi http://dx.doi.org/10.1137/20M1353502
Keywords branch-depth; fixed-parameter tractability; integer programming; matroids; tree-depth
Description A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry ? are solvable in time g(d, ?)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual treedepth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*, ?)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.