AF: Small: Cuts, Connectivity and Partitioning in Graphs, Hypergraphs and Beyond

图形和网络在计算机科学、人工智能和社会科学中无处不在。现实生活中的许多应用，如通信网络中的可靠性和社会网络中的聚类，都可以建模为图和相关结构中的划分问题。例如，在无线网络中找到其中断将中断两个给定代理之间的通信的最小基站数量，以及在社交网络中找到与外部人相比彼此之间具有很强联系的人群，这两个问题都可以建模为划分问题。该项目旨在为泛化图的结构中的基本划分问题设计新的高效算法。该项目将推动在目前由计算机科学和工业工程专业的PI教授的几门课程中整合广义图形模型。这些课程的课堂讲稿和作为本项目一部分开发的算法代码将公开提供。该项目将支持两名或更多博士生。私人投资机构正在与代表性不足群体的学生合作，并将继续努力招收更多的研究生和本科生，以使理论计算机科学的研究人员群体多样化。PI计划在不久的将来在他们的机构组织中西部理论日，将广泛的研究人员和学生聚集在一起。图中的割、连通性和划分问题是组合优化和理论计算机科学的中心话题。虽然无向图已经被广泛研究过，但这个项目的主要目标是在更复杂的结构中解决这些问题，包括有向图、超图和子模集函数。这些更丰富的模型中的几个问题的复杂性状况是开放的。PIS将调查多项式时间的可解性，结构结果，如稀疏化，近似算法，改进的运行时间，以及目前只知道随机算法的确定性算法的开发。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graphs and networks are ubiquitous in computer science, artificial intelligence, and social sciences. Many real-life applications, such as reliability in communication networks and clustering in social networks, can be modeled as partitioning problems in graphs and related structures. For example, finding the minimum number of base stations in a wireless network whose disruption will disconnect communication between two given agents, and finding groups of people in a social network that have strong ties amongst themselves when compared to outsiders, can both be modeled as partitioning problems. This project aims to design new efficient algorithms for fundamental partitioning problems in structures that generalize graphs. The project will drive the integration of generalized graph models in several courses currently taught by the PIs in Computer Science and Industrial Engineering. Lecture notes from these courses and codes of algorithms developed as part of this project will be made publicly available. The project will support two or more PhD students. The PIs are working with students from under-represented groups and will continue to make efforts to recruit additional graduate and undergraduate students to diversify the population of researchers in theoretical computer science. The PIs plan to organize the Midwest Theory Day at their institution in the near future to bring together a broad cross-section of researchers and students.Cuts, connectivity and partitioning problems in graphs are a central topic in combinatorial optimization and theoretical computer science. While undirected graphs have been extensively studied previously, the primary goal of this project is to address these problems in more complex structures including directed graphs, hypergraphs, and submodular set functions. The complexity status of several problems in these richer models is open. The PIs will investigate polynomial-time solvability, structural results such as sparsification, approximation algorithms, improved running times, and the development of deterministic algorithms where only randomized algorithms are currently known.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.