Approximation algorithms for Min-k-overlap problems using the principal lattice of partitions approach

In this paper we discuss strategies for constructing approximation algorithms for solving the Min-k-cut problem, the Min-k-certex sharing problem, and their generalization the Min-k-overlap problem. In each case, we first formulate an appropriate submodular function and construct its principal lattice of partitions (PLP) (H. Narayanan, Linear Algebra Appl. 144 (1991), 179-216), Applying an elementary strategy on an appropriate subinterval of the PLP yields the approximation algorithms. We give two such strategies. For convenience and greater generality we present our results in terms of bipartite graphs (which may be regarded as representing hypergraphs). We observe that the Min-k-cut problem is NP-Hard (O. Goldschmidt and D. S. Hochbaum, in ''Proceeding 29th Annual Symposium on the Foundations of Computer Science.'' pp. 444-451, 1988). Approximation algorithms for the Min-k-cut problem were first given in (M. Saran and V. V. Vazirani, in ''Proceedings 32nd Annual Symposium on the Foundations of Computer Science, 1991''). Their algorithms yield a Min-k-cut which is at most 2(1 - (1/k)) times worse than the optimal. Our algorithm using the first strategy has a 2(1 - (1/n)) factor (times worse than optimal) for both Min-k-cut and Min-k-vertex sharing (1) problems (n is \V(G)\, \E(G)\ respectively). For Min-k-vertex sharing (2) this strategy yields a q(1 - (1/\E(G)\)) factor, where q is the maximum degree of a vertex in the graph G. Using a second strategy we are able to obtain a (2 - (k'/n')) factor for the Min-k-cut problem, where k' = k - k(0), n' = n - k(0), k(0) being an appropriate integer defined in the paper. In our approach the chief labor consists in finding a sequence of increasingly coarser partitions (starting with the partition into singleton blocks and ending with the single block partition of S) called the principal sequence. Once this is done the remaining effort is essentially O(\S\log S). (C) 1996