Network sparsification for Steiner problems on planar and bounded-genus graphs

DOI10.1145/3239560MaRDI QIDQ4629967zbMATH OpenOpenAlexWikidataFDO

Authors Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.6593, http://wrap.warwick.ac.uk/66068/1/WRAP_1371795-cs-270115-pst-kernel.pdf

zbMATH Keywords

kernelizationplanar graphspolynomial kernelsparsificationSteiner tree

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

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 $FsubseteqE(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 $SsubseteqV(G)$, one can in polynomial time find a set $FsubseteqE(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 $SsubseteqV(G)$, one can in polynomial time find a set $FsubseteqE(G)$ that contains an optimal (edge) multiway cut $C$ separating $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.

Recommendations

• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth

Cited in

(25)

• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• Revising Johnson's table for the 21st century
• Linear kernels for outbranching problems in sparse digraphs
• Extending the kernel for planar Steiner tree to the number of Steiner vertices
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Bounds on half graph orders in powers of sparse graphs
• Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Parameterized approximation algorithms for bidirected Steiner network problems
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• A subexponential parameterized algorithm for directed subset traveling salesman problem on planar graphs
• Stronger ILPs for the Graph Genus Problem.
• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• A deterministic polynomial kernel for odd cycle transversal and vertex multiway cut in planar graphs
• A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs
• Parameterized complexity of directed Steiner tree on sparse graphs
• Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
• An exponential time parameterized algorithm for planar disjoint paths
• A polynomial time algorithm for Steiner tree when terminals avoid a rooted K₄-minor

This page was built for publication: Network sparsification for Steiner problems on planar and bounded-genus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629967)