Collaborative research: AF: medium: fast combinatorial algorithms for (dynamic) matchings and shortest paths

This $443,217 Project Grant award from the National Science Foundation's (NSF) Computer and Information Science and Engineering (CISE) program (CFDA 47.070) supports research on fast combinatorial algorithms for graph problems such as maximum matching, maximum flow, and shortest paths. The award aims to develop new algorithms for dynamic graphs, where the graph structure changes over time, as well as improve expander-related tools that can serve as building blocks for many graph algorithms. The research, led by the Toyota Technological Institute at Chicago (TTIC), a private non-profit university, focuses on advancing the theoretical foundations of graph algorithms with the goal of improving computational efficiency and performance. As a sub-awardee, TTIC has also contributed to projects on machine learning efficiency and robustness, working with partners like the University of Wisconsin-Madison. The award will fund this research over the period from July 1, 2024 to June 30, 2028.

Abstract

A graph is a collection of vertices (points or objects), and a collection of edges (links or lines), that connect pairs of vertices. Graphs are a central and an extensively studied type of mathematical object, and they are commonly used to model various problems in many different real world scenarios and applications. For example, IT is natural to model a road network in a city, or a computer network, or friendship relationships in a social network as a graph. There are countless other scenarios where a problem one needs to solve, or an object one desires to study, can be naturally abstracted by a graph. As a consequence, the design of efficient algorithms for central graph problems is fundamental to computer science and beyond, and has a significant impact on many aspects of computation. As the amount of data that applications need to deal with grows, IT is increasingly important to ensure that such algorithms are very fast. In this project, the investigators will study several central graph problems, such as maximum matching, maximum flow, and shortest paths, in two basic settings. The first is the standard model where the input graph is known in advance, and the goal is to design a fast algorithm for the problem, with running time not significantly higher than the time required to read the input, which is close to the fastest possible running time. The second is the model of dynamic algorithms, where the graph changes over time (for example, consider a road network, where the computation has to account for roads becoming more or less congested with traffic), and the goal is to quickly support queries about the graph, such as, for example, computing a short path between two given vertices. This project is organized along four main interconnected thrusts. The first thrust focuses on the design of algorithms for dynamic all-pairs shortest paths (apsp), that can withstand an adaptive adversary, and that significantly improve upon the currently known tradeoffs between the approximation quality and the running time, in both directed and undirected graphs. Algorithms for apsp and its variants are often used in combination with the multiplicative weights update framework to efficiently solve various flow and cut problems in graphs, and thus provide a valuable and powerful algorithmic toolkit. The second thrust is directed towards improving and extending known expander-related tools that are often used in the design of fast algorithms for various graph problems. Expanders are playing an increasingly central role in graph algorithms, and these tools can serve as building blocks for many other graph problems. The third thrust focuses on the maximum matching problem. Using techniques inspired by algorithms for dynamic shortest path in directed graphs, the goal of this part of the project is to develop fast combinatorial algorithms for both the bipartite and the general version of the problem. The final thrust focuses on designing improved algorithms for maintaining near-optimal matchings in dynamic graphs, building on insights and algorithms developed for the second and the third thrusts. 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.- subawards are not planned for this award.