Monday, September 28th, 2015 4pm-5pm Burnside 1205
Ohio State University
Approximation algorithms for topological graph properties

Topological graph theory has given rise to fundamental algorithms for computing several graph invariants. Some of the central problems in this area concern the computation of crossing number, graph genus, vertex/edge deletion number, and various other minor-closed properties. Many of these algorithms build upon and expand the seminal work of Robertson and Seymour on graph minors. Consequently many of these algorithms are applicable only on the exact setting. Since computing most topological graph invariants of interest is in general NP-hard, the running time of these exact algorithms has exponential dependence on the topological parameter in question. This talk will present some recent efforts to extend the above results to the setting of approximation algorithms, thus removing the exponential dependence of the running time on the topological parameter. More precisely, we obtain algorithms for approximating the orientable and non-orientable genus and crossing number of bounded degree graphs. We also extend our approximation algorithm for non-orientable genus to the case of general graphs. Finally, we obtain a poly-logarithmic approximation for minimum vertex deletion. This is the first approximation algorithm with a poly-logarithmic guarantee for any topological property of this kind. Based on joint works with Chandra Chekuri, Julia Chuzhoy, Jeff Erickson, Ken-ichi Kawarabayashi, Yury Makarychev, and Amir Nayyeri.

Fall 2015 Schedule