
The Library
Network sparsification for Steiner problems on planar and bounded-genus graphs
Tools
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. doi:10.1109/FOCS.2014.37 ISSN 0272-5428.
|
PDF
WRAP_1371795-cs-270115-pst-kernel.pdf - Accepted Version - Requires a PDF viewer. Download (1053Kb) | Preview |
Official URL: http://dx.doi.org/10.1109/FOCS.2014.37
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, Engineering and Medicine > 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: |
|
||||
Page Range: | pp. 276-285 | ||||
DOI: | 10.1109/FOCS.2014.37 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Date of first compliant deposit: | 28 December 2015 | ||||
Date of first compliant Open Access: | 28 December 2015 | ||||
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
Downloads per month over past year