Daniel Král will start with an overview of width parameters for matroids, relating them to their counterparts for graphs and demonstrating some of their algorithmic applications. He will particularly focus on the parameter called branch-depth, which is the counterpart of tree-depth of a graph. The interest in this parameter comes from the integer programming. There is a strongly fixed parameter algorithm for integer programs with the constraint matrix with bounded dual tree-depth and bounded entries. However, the dual tree-depth of the matrix is not preserved by row operations. He will show that the branch-depth of the column space of the constraint matrix is bounded if and only if the matrix is row-equivalent to a matrix with small dual tree-depth, and discuss how to obtain such a row-equivalent matrix in an algorithmic way. In particular, he establishes the existence of a strongly fixed parameter algorithm for integer programs with the constraint matrix with bounded branch-depth and bounded entries.
The talk is based on results joint with Frantisek Kardos, Anita Liebenau and Lukas Mach, and with Martin Koutecky.