More Web Proxy on the site http://driver.im/

research-article

Open access

Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces

Authors:

Sándor Kisfaludi-Bak,

Jesper Nederlof,

Erik Jan van LeeuwenAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 16, Issue 3

Article No.: 28, Pages 1 - 30

https://doi.org/10.1145/3371389

Published: 06 June 2020 Publication History

All formats PDF

Abstract

The STEINER TREE problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987{ considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using n^O(k) time and n^O(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts.

In this work, we give an algorithm for PLANAR STEINER TREE with running time 2^O(k)n^O(√k) with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: We prove that there is no f(k)n^o(√k) algorithm for PLANAR STEINER TREE for any computable function f, unless the Exponential Time Hypothesis fails.

References

[1]

MohammadHossein Bateni, Chandra Chekuri, Alina Ene, MohammadTaghi Hajiaghayi, Nitish Korula, and Dániel Marx. 2011. Prize-collecting Steiner problems on planar graphs. In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA’11). SIAM, 1028--1049.

[2]

MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Dániel Marx. 2011. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58, 5 (2011), 21:1–21:37.

Digital Library

[3]

Marshall W. Bern. 1987. Network Design Problems: Steiner Trees and Spanning -trees. Ph.D. Dissertation. University of California, Berkeley.

[4]

Marshall W. Bern. 1990. Faster exact algorithms for Steiner trees in planar networks. Networks 20, 1 (1990), 109--120.

[5]

Marshall W. Bern and Daniel Bienstock. 1991. Polynomially solvable special cases of the Steiner problem in planar networks. Annals OR 33, 6 (1991), 403--418.

[6]

Daniel Bienstock and Clyde L. Monma. 1988. On the complexity of covering vertices by faces in a planar graph. SIAM J. Comput. 17, 1 (1988), 53--76.

Digital Library

[7]

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2007. Fourier meets Möbius: Fast subset convolution. In Proceedings of the 39th ACM Symposium on Theory of Computing, David S. Johnson and Uriel Feige (Eds.). ACM, 67--74.

Digital Library

[8]

Glencora Borradaile, Claire Kenyon-Mathieu, and Philip N. Klein. 2007. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA’07), Nikhil Bansal, Kirk Pruhs, and Clifford Stein (Eds.). SIAM, 1285--1294. Retrieved from http://dl.acm.org/citation.cfm?id=1283383.1283521.

[9]

Glencora Borradaile, Philip N. Klein, and Claire Mathieu. 2007. Steiner tree in planar graphs: An O(nlogn) approximation scheme with singly-exponential dependence on epsilon. In Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS’07) (Lecture Notes in Computer Science), Frank K. H. A. Dehne, Jörg-Rüdiger Sack, and Norbert Zeh (Eds.), Vol. 4619. Springer, 275--286.

[10]

Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca. 2001. Treewidth of planar graphs: Connections with duality. Electron. Notes Disc. Math. 10 (2001), 34--38.

[11]

Danny Z. Chen and Xiaodong Wu. 2004. Efficient algorithms for k-terminal cuts on planar graphs. Algorithmica 38, 2 (2004), 299--316.

[12]

Danny Z. Chen and Jinhui Xu. 2000. Shortest path queries in planar graphs. In Proceedings of the 32nd ACM Symposium on Theory of Computing, F. Frances Yao and Eugene M. Luks (Eds.). ACM, 469--478.

[13]

Siu-Wing Cheng. 2000. Exact Steiner trees in graphs and grid graphs. In Advances in Steiner Trees, Ding-Zhu Du, J. M. Smith, and J. H. Rubinstein (Eds.). Springer US, 137--162.

[14]

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.

[15]

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM 52, 6 (2005), 866--893.

Digital Library

[16]

Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. 2005. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algor. 1, 1 (2005), 33--47.

Digital Library

[17]

Reinhard Diestel. 2012. Graph Theory, 4th Edition. Graduate texts in mathematics, Vol. 173. Springer.

[18]

S. E. Dreyfus and R. A. Wagner. 1971. The Steiner problem in graphs. Networks 1, 3 (1971), 195--207.

[19]

Ding-Zhu Du and Xiaodong Hu. 2008. Steiner Tree Problems in Computer Communication Networks. World Scientific.

[20]

Ranel E. Erickson, Clyde L. Monma, and Arthur F. Veinott Jr. 1987. Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12, 4 (1987), 634--664.

Digital Library

[21]

Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, Daniel Lokshtanov, and Saket Saurabh. 2013. Computing optimal Steiner trees in polynomial space. Algorithmica 65, 3 (2013), 584--604.

Digital Library

[22]

Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2015. Parameterized single-exponential time polynomial space algorithm for Steiner tree. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP’15) (Lecture Notes in Computer Science), Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann (Eds.), Vol. 9134. Springer, 494--505.

[23]

Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2016. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In Proceedings of the IEEE 57th Symposium on Foundations of Computer Science (FOCS’16), Irit Dinur (Ed.). IEEE Computer Society, 515--524.

[24]

L. R. Ford and D. R. Fulkerson. 1954. Maximal flow through a network. Canadian J. Math. 8 (1954), 399--404. Retrieved from http://www.rand.org/pubs/papers/P605/.

[25]

Greg N. Frederickson. 1991. Planar graph decomposition and all pairs shortest paths. J. ACM 38, 1 (1991), 162--204.

Digital Library

[26]

Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. 2007. Dynamic programming for minimum Steiner trees. Theory Comput. Syst. 41, 3 (2007), 493--500.

Digital Library

[27]

Frank K. Hwang, Dana S. Richards, and Pawel Winter. 1992. The Steiner Tree Problem. Annals of Discrete Mathematics, Vol. 53. Elsevier.

[28]

Robert Krauthgamer, James R. Lee, and Havana Rika. 2019. Flow-cut gaps and face covers in planar graphs. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA’19), Timothy M. Chan (Ed.). SIAM, 525--534.

[29]

Robert Krauthgamer and Inbal Rika. 2017. Refined vertex sparsifiers of planar graphs. CoRR abs/1702.05951 (2017).

[30]

A. Yu. Levin. 1971. Algorithm for the shortest connection of a group of graph vertices. Soviet Math. Dok. 12 (1971), 1477--1481.

[31]

Daniel Lokshtanov and Jesper Nederlof. 2010. Saving space by algebraization. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10), Leonard J. Schulman (Ed.). ACM, 321--330.

Digital Library

[32]

Dániel Marx. 2012. A tight lower bound for planar multiway cut with fixed number of terminals. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP’12), (Lecture Notes in Computer Science), Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (Eds.), Vol. 7391. Springer, 677--688.

Digital Library

[33]

Dániel Marx and Michał Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In Proceedings of the 23rd European Symposium on Algorithms (ESA’15), (Lecture Notes in Computer Science), Nikhil Bansal and Irene Finocchi (Eds.), Vol. 9294. Springer, 865--877.

[34]

Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. 2017. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. CoRR abs/1707.02190 (2017).

[35]

Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. 2018. On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS’18), Mikkel Thorup (Ed.). IEEE Computer Society, 474--484.

[36]

Kazuhiko Matsumoto, Takao Nishizeki, and Nobuji Saito. 1985. An efficient algorithm for finding multicommodity flows in planar networks. SIAM J. Comput. 14, 2 (1985), 289--302.

Digital Library

[37]

Jesper Nederlof. 2013. Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65, 4 (2013), 868--884.

Digital Library

[38]

Haruko Okamura and Paul D. Seymour. 1981. Multicommodity flows in planar graphs. J. Combin. Theory, Series B 31, 1 (1981), 75--81.

[39]

Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. 2013. Subexponential-time parameterized algorithm for Steiner tree on planar graphs. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS’13), (LIPIcs), Natacha Portier and Thomas Wilke (Eds.), Vol. 20. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 353--364.

[40]

Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. 2018. Network sparsification for Steiner problems on planar and bounded-genus graphs. ACM Trans. Algor. 14, 4 (2018), 53:1–53:73.

[41]

H. J. Prömel and A. Steger. 2012. The Steiner Tree Problem: A Tour through Graphs, Algorithms, and Complexity. Vieweg+Teubner Verlag.

[42]

J. Scott Provan. 1988. An approximation scheme for finding Steiner trees with obstacles. SIAM J. Comput. 17, 5 (1988), 920--934.

Digital Library

[43]

J. Scott Provan. 1988. Convexity and the Steiner tree problem. Networks 18, 1 (1988), 55--72.

Digital Library

Cited By

Filtser A(2024)A Face Cover Perspective to ℓ1 Embeddings of Planar GraphsACM Transactions on Algorithms10.1145/368680021:1(1-21)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3686800
Rehfeldt DKoch T(2023)Implications, conflicts, and reductions for Steiner treesMathematical Programming: Series A and B10.1007/s10107-021-01757-5197:2(903-966)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s10107-021-01757-5
Rehfeldt DKoch T(2021)Implications, Conflicts, and Reductions for Steiner TreesInteger Programming and Combinatorial Optimization10.1007/978-3-030-73879-2_33(473-487)Online publication date: 5-May-2021
https://doi.org/10.1007/978-3-030-73879-2_33

Index Terms

Nearly ETH-tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
1. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
    2. Parameterized complexity and exact algorithms

Recommendations

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

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 ...
Extending the Kernel for Planar Steiner Tree to the Number of Steiner Vertices

In the Steiner Tree problem one is given an undirected graph, a subset T of its vertices, and an integer k and the question is whether there is a connected subgraph of the given graph containing all the vertices of T and at most k other vertices. The ...
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science

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

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 16, Issue 3

July 2020

368 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3403658

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2020

Accepted: 01 November 2019

Revised: 01 November 2019

Received: 01 January 2019

Published in TALG Volume 16, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
504
Total Downloads

Downloads (Last 12 months)217
Downloads (Last 6 weeks)32

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Filtser A(2024)A Face Cover Perspective to ℓ1 Embeddings of Planar GraphsACM Transactions on Algorithms10.1145/368680021:1(1-21)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1145/3686800
Rehfeldt DKoch T(2023)Implications, conflicts, and reductions for Steiner treesMathematical Programming: Series A and B10.1007/s10107-021-01757-5197:2(903-966)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1007/s10107-021-01757-5
Rehfeldt DKoch T(2021)Implications, Conflicts, and Reductions for Steiner TreesInteger Programming and Combinatorial Optimization10.1007/978-3-030-73879-2_33(473-487)Online publication date: 5-May-2021
https://doi.org/10.1007/978-3-030-73879-2_33

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents