AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate

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

What do the following have in common: sending an email, planning a road trip using GPS software, robot motion planning, uncovering structure in biological regulatory networks and measuring the spread of information in social networks? The answer is: they all necessitate the computation of shortest paths. Efficiently computing shortest paths is among the oldest and most well-studied problems in computer science, with myriads of applications. Many ways to find shortest paths in networks have been designed over the last several decades, with various guarantees on their speed. How fast a shortest paths algorithm runs depends on the size of the network it is run on. In today's world of big data, what was considered fast in the past may no longer be, and new faster algorithms are needed. In many applications it is better to be fast than accurate, so that fast algorithms that obtain paths that are almost (but not quite) shortest are often desired. Real world networks are also dynamic rather than static: roads can become unavailable due to construction or traffic, network links on the internet can go down, and friendship links in social networks can appear and disappear. Shortest paths algorithms need to be able to handle the dynamic nature of the networks they run on. To this end, this project considers the computation of shortest paths and a variety of shortest paths parameters, considering trade-offs between speed and accuracy, preparing for network changes, and proving tight guarantees on the performance of the algorithms.This project focuses on developing algorithms for classical computer science problems such as All-Pairs Shortest Paths (APSP), Replacement Paths, graph Diameter and Radius and Betweenness centrality, in various settings. APSP in graphs on n vertices and arbitrary edge weights, can be solved exactly in time which is cubic in n. Slightly faster algorithms are known, but none run substantially faster than cubic time. Cubic time is completely impractical for any modern application, unfortunately, and it is widely believed that APSP does not admit a substantially faster algorithm that works for all graphs. One of the goals of this project is to determine when faster algorithms for APSP are possible. For instance, what restrictions on the input graphs allow for faster APSP? What kinds of approximation guarantees are achievable with fast algorithms? The project asks similar questions for the other problems of study. In addition, it considers ways to deal with the dynamic nature of graphs. One way is to construct distance sensitivity oracles: data structures that store a graph, and support shortest paths queries while also allowing for a small number of edges of the graph to be updated for each query. The project considers the tradeoffs between speed, accuracy and the number of edge faults that will be supported. Finally, the project also focuses on proving limitations on how fast computers can solve the problems of interest, using fine-grained complexity. Nearly all scientists using computational methods appreciate the implications of NP-hardness on their work. When faced with an NP-hard problem, one can resort to heuristics or approximation, but it is likely impossible to find a polynomial-time algorithm that works for all instances. Using techniques from fine-grained complexity, this project can have a similarly broad impact on how researchers across many scientific disciplines view the polynomial-time primitives they need. Fine-grained complexity can offer a powerful explanation for why their computational problems seem to be "stuck" at a quadratic- or cubic-time barrier, and point to specific hardness conjectures that must be refuted to break those barriers.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.