AF: Small: Algorithms for Graph Cuts

Duke University, Durham NC

Investigators

Abstract

Graphs are ubiquitous in nature and in the sciences, and model a broad array of objects and activities ranging from telecommunication and transportation networks to social interactions to biological and artificial neural networks. Unsurprisingly, the algorithmic study of graphs has a long history tracing back to the earliest days of computer science; today, graph algorithms are routinely used in applications ranging from online maps to medical imaging to VLSI design. Fundamentally, graphs connect entities, and many of the core questions in graph algorithms seek to understand how robust or fragile these connections are in the presence of link failures. This project aims to design new algorithms that are faster, simpler, and help better understand the connectivity properties of a graph. The newly designed algorithms have the potential of significant real-world impact in areas such as image segmentation and design of reliable networks. On the educational front, the project will train graduate and undergraduate students, with an emphasis on participation of underrepresented groups. The project has two main thrusts: the design of deterministic algorithms for graph cuts and the study of graph connectivity under random edge failures. Over the last few decades, progress in problems such as minimum cut has largely been driven by the design of new (Monte Carlo) randomized algorithms. These algorithms, while often very elegant and highly efficient, suffer from the shortcoming that they provide answers that are inconsistent across multiple runs, and that are occasionally incorrect. This prevents their use in many downstream applications, both in theory and practice. The first thrust of the project is to design derandomization tools that help bridge the gap between the best randomized and deterministic algorithms for fundamental graph connectivity problems. The second thrust is motivated by the observation that in many practical scenarios, edge failures are random, rather than adversarial, events. Traditional graph connectivity measures such as minimum cuts do not provide a faithful estimate of the resilience of a network to such random failures. The project aims to design new paradigms and algorithms to study connectivity properties in networks that are subject to random edge failures. 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.