Deleting Vertices to Graphs of Bounded Genus

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time 2C(g).k(2) log kn O(1), where k is the size of the deletion set, Cg is a constant depending on the Euler genus g of the target surface, and n is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time 2 O((t+ g) log(t+ g)) n given a tree decomposition of the input graph of width t. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter (Algorithmica 62(3-4): 807-822, 2012. https://doi. org/10.1007/s00453010-9484-z), Kawarabayashi (in: 50th annual IEEE symposium on foundations of computer science, FOCS 2009, IEEE Computer Society, pp 639-648, 2009. https://doi. org/10.1109/FOCS. 2009.45) and Jansen et al. (in: Chekuri (ed) 25th annualACMSIAM symposium on discrete algorithms, SODA 2014, SIAM, pp 1802-1811, 2014. https://doi. org/10.1137/1.9781611973402.130).