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\ge 2$ nodes, $m$ edges, and $s$ and $t$ are two distinct given nodes, then there exists an algorithm with $O(n^{2}m+n\cdot M(n,m))$ running time for the directed minimum odd (or even) $(s,t)$-cut problem and for its certain generalizations.