EAPSI: Characterizing and Finding Faster Algorithms for Hypergraph Cuts

超图是图的一种推广。图由连接两个顶点的边组成，而超图由连接任意数量顶点的边组成。超图出现在广泛的应用中，其中边模型顶点之间的关系。一个例子是一个社交网络，其中边代表俱乐部，顶点代表人。割是捕捉超图连接紧密程度的对象。这个项目将考虑更快的算法，涉及超图切割的各种问题。这项研究将在日本国立信息学研究所与图论和图形算法专家Ken-ichi Kawarabayashi教授合作进行。超图可能是密集的，因此，处理超图在空间和时间上都产生了巨大的成本。找到一个近似所有切割的稀疏超图允许使用稀疏超图代替原始超图，这可能会快得多。找到稀疏近似图的削减已解决。对于超图，类似的发展也在数学方面。然而，这些算法效率不高。目前，找到一个稀疏近似可能需要更多的时间比它是值得的。这个项目将把图技术推广到超图，并导致更快的算法。该项目还将探索超图割的特征，包括回答关于唯一性和识别性的问题。该奖项是东亚和太平洋夏季研究所计划的一部分，由NSF和日本科学促进会共同资助，旨在支持美国研究生的夏季研究。

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.