AF: Small: Graph Theory and Its Uses in Algorithms and Beyond

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

This project focuses on studying structure of graphs, as well as using insights about graph structure in order to design better algorithms for basic graph problems, and to prove negative results about the existence of such algorithms. Graphs are central combinatorial objects that are widely used in Computer Science, Mathematics, and other disciplines, both in theory and in applications. Graphs are a natural model of various types of networks, including computer and traffic networks. Additionally, graphs are also used to represent data and relationships between various objects. One of the goals of this project is to study properties of complex graphs that can be exploited in order to design faster and more accurate graph algorithms. In addition, the project will focus on several fundamental graph problems that have connections to routing traffic in a network that evolves over time, and to computing a layout of a graph with the goal of creating a good visualization of it. It will also explore the use of graph-theoretic techniques in proving negative results that show that designing fast and accurate algorithms for several central graph problems is impossible.More specifically, the project consists of three main parts. The first part focuses on graph-theoretic questions that aim at better understanding the structure of complex graphs. The questions include obtaining stronger bounds on the famous Excluded Grid Theorem, designing good algorithms for drawing graphs in the plane with few crossings, and studying a new problem on graph partitioning that arose from the study of graph theoretic questions. The second part focuses on dynamic algorithms for shortest-paths problems: given a graph that undergoes edge deletions and insertions, the goal is to provide quick and accurate responses to shortest-paths queries between pairs of vertices. This type of questions arises both in practical scenarios (such as applications for routing traffic), and in theoretical settings (algorithms for dynamic shortest-paths have been used as sub-routines in solving many central theoretical problems). The goal of this part is to obtain very fast algorithms that provide high-precision responses to the queries. In the third part, the project will focus on several closely related problems that are believed to be hard to approximate, and will attempt to prove that this is indeed the case, by exploiting graph-theoretic techniques. This part of the project is closely related to the areas of Hardness of Approximation and Probabilistically Checkable Proof, and one of its goals is to increase the flow of ideas and techniques between these areas and Algorithmic Graph Theory.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.