Sparsification for network design problems in planar graphs

5^th May 2015, 13:00 Ashton Lecture Theater
Dr Marcin Pilipczuk
Department of Computer Science
University of Warwick

Abstract

A well-established technique for designing polynomial-time approximation schemes (PTASes) for connectivity or network design problems on planar graphs is to first establish a spanner - a subgraph or minor of the input graph that contains a near-optimal solution, while at the same time has total cost bounded by f(epsilon) times the optimum cost (where epsilon is the accuracy parameter) - and then use a variant of the Baker's shifting technique to solve the problem on the spanner only. This approach turned out to be very fruitful, yielding PTASes on planar graph for such problems as Subset TSP, Steiner Tree, Steiner Forest. Moreover, recently, due to connections between cut problems in the primal graph and network design problems in the dual graph, we have seen a PTAS for Multiway Cut and a bicriteria PTAS for Bisection.

In our recent work with Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen (available here: http://arxiv.org/abs/1306.6593), we used the insight from the aforementioned approximation schemes to design improved exact algorithms for (unweighted) Steiner Tree in planar graphs in the framework of fixed-parameter tractability: a subexponential algorithm and an efficient preprocessing routine (called a polynomial kernel) for the parameterization by the number of edges in the solution tree. Some results generalize to bounded-genus graphs, and also to the Steiner Forest and Multiway Cut problems.

In the talk I will give an overview of both the spanner framework for designing PTASes on planar graphs and of recent results in parameterized complexity world, focusing on the Steiner Tree problem.

Additional Materials

• http://arxiv.org/abs/1306.6593