Algorithms and Complexity Seminar

PTAS for planar Steiner forest

Mohammad Hossein Bateni (Princeton University)

We describe a thorough complexity study of Steiner forest in bounded treewidth graphs, planar graphs, and bounded genus graphs.
We give the first polynomial-time approximation scheme for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle. We also give a polynomial-time approximation scheme for Steiner forest on graphs of bounded treewidth, a problem that is NP-hard even on graphs of treewidth 3, and show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a combination of dynamic programming and minimum cut computations.

This is joint work with MohammadTaghi Hajiaghayi and Daniel Marx.