## Modeling Hypergraphs by Graphs with the same Mincut Properties


Frank Wagner (joint work with Edmund Ihler, Dorothea Wagner)
Institut für Informatik
Freie Universität Berlin
email: wagner@inf.fu-berlin.de
Report B 92-22
August 92

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-22.ps.gz

An elegant and general way to apply graph partitioning algorithms to hypergraphs would be to model hypergraphs by graphs and apply the graph algorithms to these models. Of course such models have to simulate the given hypergraphs with respect to their cut properties. An edge-weighted graph $(V,E)$ is a {\em cut-model\/} for an edge-weighted hypergraph $(V,H)$ if the weight of the edges cut by any bipartition of $V$ in the graph is the same as the weight of the hyperedges cut by the same bipartition in the hypergraph. We show that there is no cut-model in general. Next we examine whether the addition of dummy vertices helps: An edge-weighted graph $(V\cup D,E)$ is a {\em mincut-model\/} for an edge-weighted hypergraph $(V,H)$ if the weight of the hyperedges cut by a bipartition of the hypergraphs vertices is the same as the weight of a minimum cut separating the two parts in the graph. We construct such models using positive {\em and\/} negative weights. On the other hand, we show that there is no mincut-model in general if only positive weights are allowed.