Robust linear algorithms for cutsets

Abstract

Shamir's algorithm for finding a minimum cutset in a (quasi)reducible graph runs in linear time and aborts if it discovers nonreducibility. A slight modification of the algorithm is more useful in contexts where valid input graphs may fail to be (quasi)reducible. The modified algorithm never aborts, always finds a cutset in linear time, and comes close to finding a minimum cutset when the input graph is close to being an acceptable input for the original algorithm. We study the size of the cutset as a function of the choices made in the search order. Examples suggest that the modified algorithm will do well in practice, especially if it is followed by another linear algorithm that scans a given cutset and removes any obviously unnecessary nodes. Detecting and breaking deadlocks in multiprogramming is one of the applications. In particular, the periodic centralized detect-and-break strategy can be implemented with linear time and space bounds and without any risk of starvation. Previous proposals for this strategy have exponential bounds. © 1982.