AF: Small: Algorithms meet Structural Graph Decomposition

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

A graph consists of dots, called vertices, representing objects, and lines between these dots, called edges, representing relationships between the objects the edge connects. Graphs and graph algorithms have a crucial role in computing, and by extension in all of science. They are used to model such diverse objects as people and friendships (social networks such as Facebook or LinkedIn), maps (Google Maps), connections between neurons in the brain, or the possible configurations of pieces on a chess-board connected by valid moves of chess pieces. For this reason graphs are extensively studied, both from structural and computational viewpoints. The structural approach to graphs often seeks to explain what a graph has to "look like" when it has certain desirable properties. The computational viewpoint seeks to design algorithms (efficient computer programs) that can process a graph to answer questions about it. For example, what is the shortest path from one place (vertex) to another? Which person on this social network is the "most influential?", etc. The aim of this project is a closer connection between the computational and the structural approaches to graphs. Such a connection already exists - for example many graph algorithms are based on powerful structural graph decompositions. However, the usage of structure decompositions in algorithms is most commonly in a black-box fashion - the algorithms simply exploit the structure provided by the theorems. Because the structure theorems were not designed with these concrete algorithmic applications in mind, the obtained algorithms have sub-optimal performance. For other important algorithmic problems the existing structure theorems seem to “not quite fit”, leaving efficient algorithms for these problems just out of reach. In this project the team of researchers will prove new algorithmically-focused graph-structure theorems, and use the new structure theorems to design efficient algorithms.The investigator has identified several directions where algorithmically-minded structure theorems have a big potential for success: graph isomorphism on minor-free graphs, optimization problems on weighted graphs, and (generalized) cut and separation problems. In each of these directions the team of researchers will design radically new algorithms with superior performance guarantees, and take the field far beyond the state of the art. The project cuts to the heart of several well-known open problems in theoretical computer science, specifically within the fields of parameterized algorithms and approximation algorithms. Is there a polynomial time for graph isomprohism if the input graphs exclude a clique with log log(n) vertices as a minor? What is the best approximation algorithm for deleting the fewest possible vertices to get a planar graph? Can approximation schemes for unweighted problems on planar graphs be lifted to their weighted counterparts? What is the parameterized complexity of removing k vertices of minimum weight from a digraph to make it acyclic? This project is to resolve these problems by designing new and algorithmically efficient graph-decomposition theorems. The new decomposition theorems will be built on completely new insights, as well novel combinations of insights from structural graph theory and algorithms. The combination of graph-theoretic and algorithmic thinking holds a wealth of untapped potential. Therefore the results of this project will yield substantial new results both in algorithms and in structural graph theory, and will bring the two fields closer together.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.