AF: Small: Graph Routing, Vertex Sparsifiers, and Connections to Graph Theory

图是基本的组合对象，广泛用于计算机科学、工程等领域。许多问题，无论是理论上的还是实际的，都可以通过图来抽象，而图也被用来表示数据。图上的几个基本优化问题自然会出现在许多不同的上下文中，重要的是要建立和扩展一个解决这些问题的算法思想和技术的工具包。这个项目将集中在两大类图优化问题：图路由和图稀疏化。图路由问题在许多应用中被用作抽象，例如，在设计超大规模集成电路芯片、多机器人运动规划以及跨光网络路由流量时。图稀疏化可以成为分析大型复杂网络（包括社交网络）以及为各种图问题设计更快算法的有用工具。图路由和稀疏化问题在几个不同的领域进行了研究，如近似算法，固定参数的易处理性，和图论。除了为这些问题设计更好的算法外，该项目的另一个目标是通过研究这些领域交叉点的问题，增加这些不同社区之间的思想交流和合作。该项目将涉及TTIC和芝加哥大学的研究生和可能的本科生，以及参加TTIC暑期实习计划的其他机构的学生。PI还将参加旨在提高妇女参与理论计算机科学的活动，通常在图路由问题中，给定一个图G和一组需要相互连接的顶点对，称为需求对。目标是通过路径连接尽可能多的对，通常会受到图顶点或边的最大负载的限制。这些都是理论计算机科学和图论社区广泛研究的基本问题。不幸的是，我们对这一领域一些最基本问题的理解仍然存在很大差距，本项目旨在在这些问题上取得进展。在图的稀疏化问题中，给定一个图G和一个称为终端的顶点的小集合T。我们的目标是用一个小得多的图H（称为稀疏化器）来表示图G，该图H近似地保持了G关于T的性质。人们想要保留的特定类型的属性会产生几种类型的稀疏器（例如，我们可能想要保留终端之间的切割，流动或整体路由）。这一领域的问题自然与近似算法（稀疏化器可以用来获得各种问题的改进近似因子），固定参数的易处理性（它们提供了一种黑盒方法来设计更快的算法）和图论（许多稀疏化问题可以用图论术语来描述，并已被图论社区研究）有关。在这方面仍然有许多悬而未决的问题，本项目将试图改善其中几个方面的技术水平。

Graphs are basic combinatorial objects that are widely used in computer science, engineering, and beyond. Many problems, both theoretical and practical, can be abstracted through graphs, and graphs are also used to represent data. Several basic optimization problems on graphs naturally arise in many different contexts, and it is important to build and expand a toolkit of algorithmic ideas and techniques for addressing such problems. This project will focus on two broad classes of graph optimization problems: graph routing and graph sparsification. Graph routing problems are used as abstractions in many applications, for example, when designing VLSI chips, in multi-robot motion planning, and routing traffic across optical networks. Graph sparsification can be a useful tool in analyzing large and complex networks, including social ones, and in designing faster algorithms for a variety of graph problems. Graph routing and sparsification problems were studied in several different areas, such as approximation algorithms, fixed parameter tractability, and graph theory. In addition to designing better algorithms for such problems, another goal of the project is to increase the flow of ideas and collaboration between these different communities, by studying problems lying in the intersection of these areas. The project will involve graduate and possibly undergraduate students from TTIC and University of Chicago, as well as students from other institutions who participate in TTIC's summer internship program. The PI will also participate in activities aimed at increasing the participation of women in theoretical computer science.Typically in a graph routing problem one is given a graph G and a collection of pairs of vertices, called demand pairs, that need to be connected to each other. The goal is to connect as many of the pairs as possible via paths, usually subject to some restrictions on the maximum load on graph vertices or edges. These are fundamental problems that have been studied extensively by both theoretical computer science and graph theory communities. Unfortunately, there are still wide gaps in our understanding of some of the most basic problems in this area, and this project aims to make progress on them. In graph sparsification problems, one is given a graph G and a small set T of its vertices called terminals. The goal is to represent the graph G by a much smaller graph H (called a sparsifier), that approximately preserves the properties of G with respect to T. The specific types of properties one would like to preserve give rise to several types of sparsifiers (for example, we may want to preserve cuts, flows or integral routings between the terminals). Problems in this area naturally connect to approximation algorithms (where sparsifiers can be used to obtain improved approximation factors to various problems), fixed-parameter tractability (where they give a black-box way to design faster algortihms), and to graph theory (many sparsification problems can be cast in graph theoretic terms and have been studied by the graph theory community). There are still many open problems in this area, and this project will attempt to improve the state of the art on several of them.