2026-07-20T11:14:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12433 2024-03-06T10:50:07Z ddc:004 open_access

Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming Chan, Timothy F. N. Cooper, Jacob W. Koutecký, Martin Král', Daniel Pekárková, Kristýna Matroid algorithms width parameters integer programming fixed parameter tractability branch-width branch-depth 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 tree-depth d and largest entry Δ are solvable in time g(d,Δ) poly(n) for some function g, i.e., fixed parameter tractable when parameterized by tree-depth d and Δ. However, the tree-depth of a constraint matrix depends on the positions of its non-zero entries and thus does not reflect its geometric structure. In particular, 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. We prove that the branch-depth of the matroid defined by the columns of the constraint matrix is equal to the minimum tree-depth of a row-equivalent matrix. We also design a fixed parameter algorithm parameterized by an integer d and the entry complexity of an input matrix that either outputs a matrix with the smallest dual tree-depth that is row-equivalent to the input matrix or outputs that there is no matrix with dual tree-depth at most d that is row-equivalent to the input matrix. Finally, we use these results to obtain a fixed parameter algorithm for integer programming parameterized by the branch-depth of the input constraint matrix and the entry complexity. The parameterization by branch-depth cannot be replaced by the more permissive notion of branch-width. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy F. N. Chan and Jacob W. Cooper and Martin Koutecký and Daniel Král' and Kristýna Pekárková 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.26 urn:nbn:de:0030-drops-124339 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode