Recognizing hidden bicircular networks (Q1208462)

A generalized network flow problem is a linear program \(\min\{cx\mid Ax=b,\;x\geq 0\}\), where the matrix \(A\) has at most 2 nonzero entries in each column. The authors present a polynomial-time algorithm for transforming an \(m\times n\) matrix \(A\) of full rank into the constraint matrix of a generalized network flow problem provided there exists an underlying bicircular generalized network \(N\) whose generalized incidence matrix can be obtained from \(A\) by elementary row operations and nonzero column scaling. A bicircular generalized network is a weighted digraph having no cycle in which the product of the weights of forward arcs equals the product of the weights of backward arcs. Such a transformation is useful because generalized network flow problems can be solved much faster than regular linear programs. In this paper, the underlying graph \(G\) of \(N\) is constructed using an algorithm with worst-case complexity \(m^ 2 n^ 2\).