Minimum s - t hypercut in (s, t)-planar hypergraphs

Abstract

Planar hypergraphs are widely used in several applications, including VLSI design, metro maps, information visualisation, and databases. The minimum s − t hypercut problem in a weighted hypergraph is to find a partition of the vertices into two nonempty sets, S and S, with s ∈ S and t ∈ S that minimizes the total weight of hyperedges that have at least two endpoints in two different sets. In the present study, we propose an approach that effectively solves the minimum s−t hypercut problem in (s, t)-planar hypergraphs. The method proposed demonstrates polynomial time complexity, providing a significant advancement in solving this problem. The modelling example shows that the proposed strategy is effective at obtaining balanced bipartitions in VLSI circuits.