A cornerstone result in combinatorial optimization is the maxflow-mincut theorem in graphs for a single source-destination pair (s,t). This theorem and associated algorithms for computing the maximum (integer) flow and minimum cut in a graph have many applications. Unlike this well-understood case, the multicommodity setting with multiple source-destination pairs leads to computationally intractable problems, and this is also tied to the lack of exact min-max results. There are, however, many applications such as graph partitioning and routing in networks that are best modeled via multicommodity flow and cut problems. The project focused on developing algorithms, structural results, and mathematical programming relaxations for these problems.  The project succeeded in developing new and improved approximation algorithms, new graph theoretic results, and new linear programming relaxations. Some key results are outlined below.

One of the primary goals of the project was to better understand the role of a fundamental graph theoretic parameter called treewidth. It is a measure of a graph's complexity and is important for developing algorithms and in proving mathematical theorems about graphs. A central theorem in graph structure theory showed that that any graph with sufficiently large treewidth has a structure called a grid minor. A long-standing conjecture in graph theory postulated that the quantitative relationship between the treewidth of a graph and the size of the largest grid minor contained in the graph is polynomial. This project established the conjecture for the first time. The project also established a sparsification theorem for graph treewidth. These structural theorems had a number of algorithmic and graph theoretic applications. The project also studied the more difficult case of directed graph treewidth and made progress in the special case of planar digraphs, and as a consequence developed approximation algorithms for routing in planar directed graphs.

The project developed several new results on the multicut problem which is the generalization of the s-t mincut problem to multiple source-destination pairs. A demand graph perspective was taken to understand the complexity of the problem.  In undirected graphs a new labeling view point and an associated LP relaxation resulted in improved approximation algorithm for several special cases. Several inapproximability results were shown for directed graphs via a unified perspective. The labeling view point also led to new LP relaxations with a constant factor integrality gap for subset feedback problems in undirected graphs for the first time.

The project supported two PhD students who finished their dissertations, and the PI also supervised two MS students who finished their theses. Some publications from the project substantially simplified previous algorithms on flows, cuts and network design.  The PI gave several invited talks on developments in treewidth to graph theorists and algorithms researchers, including an invited tutorial at the machine learning conference NIPS.

Last Modified: 10/07/2018
Modified by: Chandra S Chekuri