Approximation Algorithms for Graph Connectivity Problems
(L. C. Lau)

Graph connectivity is an important notion. In graph theory and combinatorial optimization, many fundamental problems (e.g. maximum flow, maximum matching, minimum spanning tree, spanning tree packing, etc) can be formulated as graph connectivity problems. In practice, efficient algorithms for graph connectivity problems have found numerous applications in computer science especially in computer networks and VLSI circuit design.

Graph connectivity has a rich literature and a deep theory based on submodular set functions. Most of the successes of this theory are on edge-connectivity problems and polynomial time solvable problems. The objective of this project is to extend this theory to vertex-connectivity problems, and to design approximation algorithms for NP-complete problems. We will have an in-depth study on packing and covering problems, and consider some outstanding conjectures such as Woodall’s conjecture on packing directed cut cover and Kriesell’s conjecture on packing Steiner trees. We are also interested in graph orientation problems and Frank’s conjecture on finding a k-connected graph orientation.

The study of graph connectivity problems has also lead to beautiful and surprising connections to geometric problems such as covering a rectilinear polygon by rectangles. Using this connection, we will investigate some open problems in computational geometry, such as finding constant factor approximation algorithms for the rectangle covering problem and the rectangle packing problem.