A procedure to determine optimal partitions of weighted hypergraphs through a network-flow analogy

Many problems arising in computer science and applications are amenable to finding optimal partitions of weighted hypergraphs or, more simply, of ordinary weighted graphs. As recently noted by some authors, in many cases the construction of optimal or near-optimal partitions is made easier if a family of subsets of nodes of the given hypergraph, called LS sets, is previously determined. Intiutively, and LS set is a subset of nodes of the hypergraph, which are more strongly connected to each-other than to the nodes in the complementary subset. This paper presents a polynomialbounded procedure to determine all the LS sets in a given weighted hypergraph. The proposed procedure, that is considerably faster than those previously known, is based upon a network-flow analogy and replaces the given hypergraph with a «flow equivalent» tree, into which a collection of subsets of nodes, which includes all LS sets, is easily determined.