EAPSI: Characterizing and Finding Faster Algorithms for Hypergraph Cuts

EAPSI：表征和寻找更快的超图切割算法

• 批准号: 1714027
• 负责人: Chao Xu
• 金额: $ 0.54万
• 依托单位: Xu Chao
• 依托单位国家: 美国
• 项目类别: Fellowship Award
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-06-01 至 2018-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714027&HistoricalAwards=false
• 关键词: EAPSI; Characterizing; Finding; Faster; Algorithms

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.

超图是图形的概括。图形由连接两个顶点的边缘组成，而HyperGraphs由连接任意数量的顶点的边缘组成。 HyperGraphs出现在广泛的应用中，其中边缘模型的顶点之间的关系。一个例子是一个社交网络，边缘代表俱乐部，顶点代表人。切割是捕获超图紧密连接的对象。该项目将考虑涉及削减超图的各种问题的更快算法。这项研究将在日本国家信息学研究所与肯·伊奇·卡瓦拉巴亚西（Ken-Ichi Kawarabayashi）教授合作。找到近似所有切口的稀疏超图，使人们可以使用稀疏的超图代替原始超图，这可能会更快。发现图上切割的稀疏近似已得到解决。对于超图，类似的发展在数学方面。但是，该算法效率不高。目前，找到稀疏的近似可能需要的时间超过价值。该项目将将图形技术推广到超图，并导致更快的算法。该项目还将探讨削减超图的特征，包括回答有关独特性和认可的问题。根据东亚和太平洋夏季研究所计划，该奖项支持美国研究生的夏季研究，并由NSF和日本科学促进协会共同资助。