Improving graph partitions using submodular functions

AbstractWe investigate into the role of submodular functions in designing new heuristics and approximate algorithms to some NP-hard problems arising in the field of VLSI Design Automation. In particular, we design and implement efficient heuristic for improving a bipartition of a graph in the sense of ratioCut (Discrete Appl. Math. 90 (1999) 3; 29th Annual Symposium on Foundations of Computer Science, 1988, p. 422). We also design an approximate algorithm for another NP-hard problem which is a dual of the well-known NP-hard problem of finding a densest k-subgraph of a graph (see J. Algorithms 34 (2000) 203; Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993, p. 692). Our algorithms are based on submodular function and are implementable in polynomial time using efficient network flow based subroutines. To the best of our knowledge our algorithms are the first ones to use submodular functions based approach for the problems considered here. We also describe the experimental results which provide the evidence of our heuristic for improving the ratioCut