Abstract. The modeling flexibility provided by hypergraphs has drawn a lot of interest from the combinatorial scientific community, leading to novel models and algorithms, their applications, and development of associated tools. Hypergraphs are now a standard tool in combinatorial scientific computing. The modeling flexibility of hypergraphs however, comes at a cost: algorithms on hypergraphs are inherently more complicated than those on graphs, which sometimes translates to nontrivial increases in processing times. Neither the modeling flexibility of hypergraphs, nor the runtime efficiency of graph algorithms can be overlooked. Therefore, the new research thrust should be how to cleverly trade-off between the two. This work addresses one method for this trade-off by solving the hypergraph partitioning problem by finding vertex separators on graphs. Specifically, we investigate how to solve the hypergraph partitioning problem by seeking a vertex separator on its net intersection graph (NIG), where each net of the hypergraph is represented by a vertex, and two vertices share an edge if their nets have a common vertex. We propose a vertex-weighting scheme to attain good node-balanced hypergraphs, since the NIG model cannot preserve node balancing information. Vertex-removal and vertex-splitting techniques are described to optimize cutnet and connectivity metrics, respectively, under the recursive bipartitioning paradigm. We also developed implementations of our proposed hypergraph partitioning formulations by adopting and modifying a state-of-the-art graph partitioning by vertex separator tool onmetis. Experiments conducted on a large collection of sparse matrices demonstrate the effectiveness of our proposed techniques. Key words. hypergraph partitioning; combinatorial scientific computing; graph partitioning by vertex separator; sparse matrices. AMS subject classifications. A hypergraph is a generalization of a graph, since it replaces edges that connect only two vertices, with hyperedges (nets) that can connect multiple vertices. This generalization provides a critical modeling flexibility that allows accurate formulation of many important problems in combinatorial scientific computing. After their introduction in [7, 38] , the modeling power of hypergraphs appealed to many researchers and they were applied to a wide variety of many applications in scientific computing [1, 4, 6, 8, 10, 11, 12, 14, 19, 29, 30, 33, 44, 45, 48, 49, 50, 51, 52, 53, 54] . Hypergraphs and hypergraph partitioning are now standard tools of combinatorial scientific computing. Increasing popularity of hypergraphs has been accompanied with the development of effective hypergraph partitioning (HP) tools: wide applicability of hypergraphs motivated development of fast HP tools, and availability of effective HP tools motivated further applications. This virtuous cycle produced sequential HP tools such as hMeTiS [28] , PaToH [9] and Mondriaan [52] , and parallel HP tools such
Kayaaslan et al. REF present a heuristic method for hypergraph partitioning based on graph partitioning by vertex separator (GPVS), a procedure which for p = 2 partitions the vertices of a graph into two unconnected sets and a separator set.
PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS
SIAM J. Scientific Computing
SIAM J. Scientific Computing
Mathematics Computer Science