Using Equivalence Relations For Hypergraph Partitioning

Abstract

We have found that hypergraph partitioning is a problem particularly suited to parallel computation. We found that PMondriaan solves some issues effectively but lacks on many others, generally having mixed results. We also found that PMondriaan is not yet ready for the purpose it was created for, but we also see clear paths towards these goals. We also have introduced the notion of instance equivalence in a specific manner and its application to hypergraph partitioning with fixed vertices. We found that instance equivalence can be useful, but it is not yet clear how to best take advantage of the concepts. We also saw how to practically implement all of the theoretical algorithms used and have seen some results that follow from the implemented software. Last we also saw that there may be implications of the theory that apply to other similar projects, like what coarsening rating function is used.