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 D are solvable in time g(d,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 tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,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.
翻译:对整数编程的固定参数可追溯性进行一长行的研究,其最终结果是显示,具有n变量的整数程序以及具有双树深度和最大条目D的制约矩阵在时间上可以溶解 g(d,D)poly(n) 对于某些函数 g。然而,限制矩阵的双树深度并非由行操作所保存,即给定整数程序可以等同于具有较小双树深度的另一个程序,因此不反映其几何结构。我们证明,行等矩阵的最小双树深度与矩阵列所定义的类体深度相等。我们设计了一个固定参数算法,用于计算代表有限字段的类体深度的成像体,并设计一个计算具有最小双树深度的行等值矩阵的固定参数算法。最后,我们利用这些结果获得一个算法,用于在时间(d*,D)poly(n)运行的整数线性编程的算法,从而不反映其几何结构。我们证明,行等等值矩阵的最小双树深度等于矩阵的分支深度等于矩阵的深度;不能被更宽容的分支边缘概念取代。