Recursive contraction algorithm: a novel and efficient graph traversal method for scanning all minimal cut sets

Abstract

We propose a novel algorithm called RCA_MC, in which we use the breadth first search method (BFS) in conjunction with edge contraction and connectivity properties of a given undirected graph to enumerate and scan all its minimal edge cutsets. It is known that the problem of enumerating all minimal edge cutsets of a given graph is #P-complete. In addition, we introduce the concepts of pivot vertex and absorbable clusters, and use them to develop our enhanced recursive contraction for scanning all mimimal edge cutsets, called ERCA_MC, of a given graph. Simulation results provide empirical evidence that the complexity of the ERCA_MC algorithm is linear per cutset.