EAPSI: Characterizing and Finding Faster Algorithms for Hypergraph Cuts

Xu Chao, Urbana IL

Investigators

Abstract

Hypergraphs are a generalization of graphs. Graphs comprise of edges connecting two vertices, while hypergraphs consist of edges connecting any number of vertices. Hypergraphs appear in a wide range of applications, where the edges model relationships between vertices. An example is a social network, where the edges represent clubs, and vertices represent people. Cuts are objects that capture how tightly connected a hypergraph is. This project will consider faster algorithms for various problems involving hypergraphs cuts. This research will be conducted at the National Institute of Informatics, Japan, in collaboration with Professor Ken-ichi Kawarabayashi, an expert in graph theory and graph algorithms. Hypergraphs can be dense, therefore, processing the hypergraph incurs substantial cost in both space and time. Finding a sparse hypergraph that approximates all the cuts allows one to use the sparse hypergraph in place of the original hypergraph, which might be much faster. Finding sparse approximation of cuts on graphs has been resolved. For hypergraphs, similar developments are on the mathematical side. However, the algorithms are not efficient. Currently, finding a sparse approximation might take more time than it is worth. This project will generalize the graph techniques to hypergraphs, and lead to faster algorithms. The project will also explore characterizations of hypergraph cuts, including answering questions on uniqueness and recognition. This award, under the East Asia and Pacific Summer Institutes program, supports summer research by a U.S. graduate student and is jointly funded by NSF and the Japan Society for the Promotion of Science.