The Library
Network sparsification for Steiner problems on planar and boundedgenus graphs
Tools
Pilipczuk, Marcin, Pilipczuk, Michał, Sankowski, Piotr and Leeuwen, Erik Jan van (2014) Network sparsification for Steiner problems on planar and boundedgenus graphs. In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, 1821 Oct 2014. Published in: Proceedings of 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) pp. 276285. ISBN 9781479965175. ISSN 02725428. doi:10.1109/FOCS.2014.37

PDF
WRAP_1371795cs270115pstkernel.pdf  Accepted Version  Requires a PDF viewer. Download (1053Kb)  Preview 
Official URL: http://dx.doi.org/10.1109/FOCS.2014.37
Abstract
We propose polynomialtime algorithms that sparsify planar and boundedgenus graphs while preserving optimal or nearoptimal solutions to Steiner problems. Our main contribution is a polynomialtime algorithm that, given an unweighted graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F in E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: (2) given an unweighted graph G embedded on a surface of genus g and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and E(T); (2) an analogous result holds for an optimal Steiner forest for a set S of terminal pairs, (3) given an unweighted planar graph G and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and has size polynomial in C. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and boundedgenus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Steiner Tree and similar "subset" problems were identified in [Demaine, Hajiaghayi, Computer J., 2008] as important to the quest to widen the reach of the theory of bidimensionality ([Demaine et al., JACM 2005], [Fomin et al., SODA 2010]). Therefore, our results can be seen as a leap forward to achieve this broader goal. Additionally, we obtain a weighted variant of our main contribution: a polynomialtime algorithm that, given an edgeweighted planar graph G, a designated face f bounded by a simple cycle of weig t w(f), and an accuracy parameter ε > 0, uncovers a set F in E(G) of total weight at most poly(1/ε) w(f) that, for any set of terminal pairs that lie on f, contains a Steiner forest within additive error ε w(f) from the optimal Steiner forest. This result deepens the understanding of the recent framework of approximation schemes for network design problems on planar graphs ([Klein, SICOMP 2008], [Borradaile, Klein, Mathieu, ACM TALG 2009], and later works) by explaining the structure of the solution space within a brick of the socalled mortar graph  the central notion of this framework.
Item Type:  Conference Item (Paper)  

Subjects:  Q Science > QA Mathematics  
Divisions:  Faculty of Science > Computer Science  
Library of Congress Subject Headings (LCSH):  Graph theory, Steiner systems  
Journal or Publication Title:  Proceedings of 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS)  
Publisher:  IEEE Computer Society  
ISBN:  9781479965175  
ISSN:  02725428  
Book Title:  2014 IEEE 55th Annual Symposium on Foundations of Computer Science  
Official Date:  11 December 2014  
Dates: 


Date of first compliant deposit:  28 December 2015  
Page Range:  pp. 276285  
DOI:  10.1109/FOCS.2014.37  
Status:  Peer Reviewed  
Publication Status:  Published  
Funder:  Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP)  
Grant number:  267959 (ERC), 259515 (ERC)  
Embodied As:  1  
Conference Paper Type:  Paper  
Title of Event:  55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014)  
Type of Event:  Conference  
Location of Event:  Philadelphia, PA  
Date(s) of Event:  1821 Oct 2014 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year