TY - JOUR

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

AU - Pilipczuk, Marcin

AU - Pilipczuk, Michal

AU - Sankowski, Piotr

AU - Leeuwen, Erik Jan van

PY - 2018

Y1 - 2018

N2 - 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 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.

AB - 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 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.

U2 - 10.1145/3239560

DO - 10.1145/3239560

M3 - Article

SN - 1549-6333

VL - 14

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 4

M1 - 53

ER -