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

点击翻译按钮获取中文摘要

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.