Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:25:00Z
dc.abstract.enWe 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 undirected 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 ⊆ 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: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and |E(T)|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S⊆ V(G), one can in polynomial time find a set F ⊆ 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 that 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). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w(f), and an accuracy parameter ε > 0, uncovers a set F ⊆ 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.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorPilipczuk, Michał
dc.contributor.authorLeeuwen, Erik Jan van
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorSankowski, Piotr
dc.date.accessioned2024-01-25T13:44:29Z
dc.date.available2024-01-25T13:44:29Z
dc.date.issued2018
dc.description.financeNie dotyczy
dc.description.number4
dc.description.volume14
dc.identifier.doi10.1145/3239560
dc.identifier.issn1549-6325
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/113500
dc.identifier.weblinkhttps://dl.acm.org/doi/10.1145/3239560
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofACM Transactions on Algorithms
dc.relation.pages53:1-53:73
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleNetwork Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
dc.typeJournalArticle
dspace.entity.typePublication