CAREER: A New Theory of Length-Constrained Graph Algorithms

The field of graph algorithms aims to understand how to efficiently construct and use networks, as well as what properties make for a good network. This project aims to advance graph algorithms by way of a new theory of “length-constrained” graph algorithms. Length constraints are a way of encouraging communication to happen quickly in networks. However, most classic graph algorithms do not work in the presence of length constraints. This project aims to build new graph algorithms that work in the presence of length constraints and, in doing so, provide new algorithms for solving classic problems as fast as possible. Results from this project will be made broadly accessible through peer-reviewed publications, research tutorials, new survey papers and new graduate-level courses, with all material made available to the general public. The project aims to develop the proposed solutions by leveraging the theory of graph cuts and metric embeddings. Firstly, the project will develop a new approach to length-constrained cuts as the foundation of new techniques in iterative linear programming methods under length constraints. Second, it will develop a theory of metric embeddings for length-constrained distances using a new paradigm for embedding graphs into spanning trees. Additionally, the project will build close-to-linear-time algorithms for classic flow problems, such as min cost multi-commodity flow, by leveraging new techniques in length-constrained expander decompositions and flow emulators. Particular focus will be for established problem domains from non-length-constrained settings, such as directed Steiner tree, hop sets, and embeddings of graph distances into trees. 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. NSF Award ID: 2540331 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: David Hershkowitz | Institution: Brown University, PROVIDENCE, RI | Award Amount: $591,687 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2540331 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2540331.html