Recognizing max-flow min-cut path matrices (Q1103514): Difference between revisions

Let A be a 0,1-matrix, \(c\geq 0\) integral vector, and \(\mathbf{1}\) the vector of all 1's. Consider the following dual pair of linear programs: (P) minimize cx, subject to Ax\(\geq \mathbf{1}\), \(x\geq 0.\) (D) maximize \(y\mathbf{1}\), subject to yA\(\leq c\), \(y\geq 0.\) Seymour has shown that if A is a path matrix of a matroid M relative to an element e, then (P) and (D) have integral optimum solutions for every \(c\geq 0\) integral, iff M is binary and has no \(F\) \(*_ 7\) minor containing e. In this paper, a polynomial-time algorithm for determining whether a given 0,1-matrix is the path matrix of some binary matroid, is given. Combining this with an algorithm of Truemper to determine whether a matroid has an \(F\) \(*_ 7\) minor, leads to a polynomial-time algorithm for determining whether a given matrix A is in Seymour's class.