CAREER: Paths in Graphs: Structural Primitives and Algorithmic Advances

Graphs, or networks, are a ubiquitous way of representing data. Paths in graphs can represent, for instance, transportation routes, chemical reaction pathways, or information movement through a digital or social network. To efficiently compute meaningful information about paths in graphs it is important to have efficient algorithms with strong theoretical foundations, i.e., proofs of correctness and efficiency. This project addresses the theoretical foundations of algorithmic problems regarding paths in graphs. This research should enhance future artificial intelligence research through providing a better understanding of paths in graphs and the simplification and processing of large graphs that are common in modern applications. Although algorithms for computing paths in graphs have been studied since the dawn of computer science, many foundational algorithmic problems remain poorly understood. Lack of understanding often comes down to structural aspects of paths in graphs. The research objective of this project is to advance structural understanding of paths in graphs, and leverage this to advance algorithms for foundational problems, ultimately in settings with massive and evolving graphs. The research plan has three central aims: (1) Advance graph simplification, i.e., representing a graph by a simpler graph that preserves important properties of paths in the original graph, (2) Address algorithmic complications inherent to directed graphs by overcoming a common structural bottleneck, and (3) Develop algorithms for the practically and theoretically relevant dynamic and query models, where data is revealed over time and the algorithm must efficiently adapt. 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: 2541910 | Program: 01002627DB NSF RESEARCH & RELATED ACTIVIT,01002930DB NSF RESEARCH & RELATED ACTIVIT,01003031DB NSF RESEARCH & RELATED ACTIVIT | Principal Investigator: Nicole Wein | Institution: Regents of the University of Michigan - Ann Arbor, ANN ARBOR, MI | Award Amount: $530,283 View on NSF Award Search: https://www.nsf.gov/awardsearch/show-award/?AWD_ID=2541910 View on Research.gov: https://www.research.gov/awardapi-service/v1/awards/2541910.html