On minimum cuts of cycles by vertices and vertex disjoint cycles

Abstract

We describe a new family of di.graphs, named connectively reducible, for which we prove that the minimum cardinality of a set of vertices intersecting all cycles equals the maximum cardinality of a set of vertex disjoint cycles. In.addltion, formulate polynomial time algorithms for the problems of recognition and finding these minimum and maxium sets for digraphs of the family. Similar results hold for the currently existing families of fully reducible and cyclically reducible digraphs. Neither the fully reducible are contained nor contain the cyclically reducible. However, we show that the connectively reducible digraphs contain both of the existing families.