A HEURISTIC ALGORITHM FOR SMALL SEPARATORS IN ARBITRARY GRAPHS

Some heuristic random polynomial time algorithms for finding good cuts in arbitrary graphs are presented. A cut is good if there are a small number of edges across the cut and if the cut divides the set of vertices somewhat evenly. The algorithms obtain cuts from solutions to randomly chosen network flow problems based on the input graph. Probabilistic bounds for the goodness of the cut obtained in terms of the goodness of an optimal separator are derived. These bounds are valid for all input graphs. There is reason to think that the algorithm will perform better than the bounds indicate.