Note: On Directed Odd or Even Minimum \((s, t)\)-Cut Problem and Generalizations

Abstract

We show that if \(M(n, m)\) denotes the time of a \((u, v)\)-minimum cut computation in a directed graph with \(n \geq 2\) nodes, \(m\) edges, and \(s\) and \(t\) are two distinct given nodes, then there exists an algorithm with \(O(n^2m+n\cdot M(n, m))\) running time for the directed minimum odd (or even) \((s, t)\)-cut problem and for its certain generalizations.