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

AF：小：图论及其在算法及其他领域的应用

基本信息

批准号：
2006464
负责人：
Julia Chuzhoy
金额：
$ 39.82万
依托单位：
Toyota Technological Institute at Chicago
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-07-01 至 2024-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006464&HistoricalAwards=false
关键词：
AF Small Graph Theory Its

项目摘要

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.

该项目专注于研究图的结构，以及利用对图结构的见解来为基本图问题设计更好的算法，并证明此类算法存在的负面结果。图是核心组合对象，在理论和应用中广泛应用于计算机科学、数学和其他学科。图是各种类型网络的自然模型，包括计算机和交通网络。此外，图表还用于表示数据和各种对象之间的关系。该项目的目标之一是研究可利用的复杂图的属性，以便设计更快、更准确的图算法。此外，该项目将重点关注几个基本的图形问题，这些问题与随着时间的推移而演变的网络中的路由流量有关，并计算图形的布局以创建良好的可视化效果。它还将探索使用图论技术来证明负面结果，这些结果表明为几个核心图问题设计快速而准确的算法是不可能的。更具体地说，该项目由三个主要部分组成。第一部分侧重于图论问题，旨在更好地理解复杂图的结构。这些问题包括在著名的排除网格定理上获得更强的界限，设计在很少交叉的平面上绘制图形的良好算法，以及研究图论问题研究中产生的新的图划分问题。第二部分重点介绍最短路径问题的动态算法：给定一个经历边删除和插入的图，目标是为顶点对之间的最短路径查询提供快速而准确的响应。此类问题既出现在实际场景（例如路由流量的应用程序）中，也出现在理论设置中（动态最短路径算法已被用作解决许多核心理论问题的子例程）。这部分的目标是获得非常快速的算法，为查询提供高精度响应。在第三部分中，该项目将重点关注几个被认为难以近似的密切相关的问题，并将尝试通过利用图论技术来证明情况确实如此。该项目的这一部分与近似难度和概率可检查证明领域密切相关，其目标之一是增加这些领域与算法图论之间的思想和技术的流动。该奖项反映了 NSF 的法定使命，并具有通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs

低度图中图交叉数的次多项式逼近算法

DOI：
10.1145/3519935.3519984
发表时间：
2022-06
期刊：
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Chuzhoy, Julia;Tan, Zihan
通讯作者：
Tan, Zihan

A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

2-CSP硬度的新猜想及其对最密k子图硬度及其他问题的启示