Pilipczuk, Marcin, Pilipczuk, Michał, Sankowski, Piotr and Leeuwen, Erik Jan van (2014) Network sparsification for Steiner problems on planar and bounded-genus graphs. In: 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), Philadelphia, PA, 18-21 Oct 2014. Published in: Proceedings of 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS) pp. 276-285. ISBN 9781479965175. ISSN 0272-5428. doi:10.1109/FOCS.2014.37

Preview

PDF WRAP_1371795-cs-270115-pst-kernel.pdf - Accepted Version - Requires a PDF viewer. Download (1053Kb) | Preview

Request Changes to record.

Abstract

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time 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 bounded-genus 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 polynomial-time algorithm that, given an edge-weighted 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 so-called 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:	0272-5428
Book Title:	2014 IEEE 55th Annual Symposium on Foundations of Computer Science
Official Date:	11 December 2014
Dates:	Date Event 11 December 2014 Published
Date of first compliant deposit:	28 December 2015
Page Range:	pp. 276-285
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:	18-21 Oct 2014

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads