A fixed parameter tractable approximation scheme for the optimal cut graph of a surface Conference Paper


Author(s): Cohen-Addad, Vincent; de Mesmay, Arnaud
Title: A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
Title Series: LNCS
Affiliation IST Austria
Abstract: Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3. Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest.
Conference Title: ESA: European Symposium on Algorithms
Volume: 9294
Conference Dates: September 14-16, 2015
Conference Location: Patras, Greece
ISBN: 9783662483497
Publisher: Springer  
Date Published: 2015-09-01
Start Page: 386
End Page: 398
URL:
DOI: 10.1007/978-3-662-48350-3
Notes: The research of the first author was partially supported by ANR RDAM. The research of the second author leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement n◦ [291734].
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work