Invariant sets of arcs in network flow problems (Q1071638): Difference between revisions

Assume a standard network flow problem. The set \(A=A^+\cup A^-\) of arcs is said to be invariant if there exists a constant c so that for every max flow x \[ \sum \{x(a);\quad a\in A^+\}-\sum \{x(a);\quad a\in A^-\}=c. \] The main result of the paper reads as follows: Let \(A=A^+\cup A^-\) be a set of arcs. If there exists a cut \((S,\bar S)\) such that \(A^+\subseteq (S,\bar S)\), \(A^-\subseteq (\bar S,S)\) or \(A^+\subseteq (\bar S,S)\), \(A^-\subseteq (S,\bar S)\) with \(((S,\bar S)\cup (\bar S,S))\setminus A\) consisting of invariant arcs, then A is an invariant set of arcs. Conversely, if \(A=A^+\cup A^-\) is a minimal invariant set of arcs, then such a cut \((S,\bar S)\) exists. This assertion is applied to \((0,1)\)-matrices with given row and column sums and some new results are obtained.