Testing balancedness and perfection of linear matrices (Q689142)

A given \((0,1)\) matrix \(A\) is called perfect if the associated set packing polytope \(\{x\geq 0,\;Ax\leq 1\}\) has only integer extreme points, balanced if all submatrices of \(A\) are perfect, and linear if it does not contain a \(2\times 2\) submatrix with all entries equal to 1. Polynomial algorithms for testing whether a linear matrix is balanced or perfect are developed. They are based on decomposition results of the corresponding bipartite graphs (nodes correspond to rows and columns of \(A\), respectively, and edges correspond to 1-entries in the matrix). These results are due to previous papers of the same authors. This decomposition allows to reduce the perfectness test for the original graph to the testing of a number of subgraphs.