research-article

Public Access

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs

Authors:

Glencora Borradaile,

Philip KleinAuthors Info & Claims

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

Article No.: 30, Pages 1 - 29

https://doi.org/10.1145/2831235

Published: 25 April 2016 Publication History

Abstract

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement) r(v) ∈ {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min {r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices.

We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O(nlog n).

Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

References

[1]

B. Baker. 1994. Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 1 (1994), 153--180.

Digital Library

[2]

M. Bateni, C. Chekuri, A. Ene, M. Hajiaghayi, N. Korula, and D. Marx. 2011a. Prize-collecting Steiner problems on planar graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. 1028--1049.

Digital Library

[3]

M. Bateni, M. Hajiaghayi, and D. Marx. 2011b. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58, 5 (2011), 21.

Digital Library

[4]

A. Berger, A. Czumaj, M. Grigni, and H. Zhao. 2005. Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. In Proceedings of the 13th European Symposium on Algorithms. Lecture Notes in Computer Science, Vol. 3669. 472--483.

Digital Library

[5]

A. Berger and M. Grigni. 2007. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, Vol. 4596. 90--101.

Digital Library

[6]

G. Borradaile, E. Demaine, and S. Tazari. 2012. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica (2012). Online.

[7]

G. Borradaile, C. Kenyon-Mathieu, and P. Klein. 2007a. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1285--1294.

Digital Library

[8]

G. Borradaile, P. Klein, and C. Mathieu. 2007b. Steiner tree in planar graphs: An O(nlog n) approximation scheme with singly exponential dependence on epsilon. In Proceedings of the 10th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, Vol. 4619. 275--286.

Digital Library

[9]

G. Borradaile, P. Klein, and C. Mathieu. 2009. An O(nlog n) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algor. 5, 3 (2009), 1--31.

Digital Library

[10]

A. Czumaj and A. Lingas. 1999. On approximability of the minimum cost k-connected spanning subgraph problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. 281--290.

Digital Library

[11]

R. Erickson, C. Monma, and A. Veinott. 1987. Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12 (1987), 634--664.

Digital Library

[12]

K. Eswaran and R. Tarjan. 1976. Augmentation problems. SIAM J. Comput. 5, 4 (1976), 653--665.

Digital Library

[13]

G. Frederickson and J. Jájá. 1981. Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10, 2 (1981), 270--283.

Digital Library

[14]

M. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, É. Tardos, and D. Williamson. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms. 223--232.

Digital Library

[15]

M. Henzinger, P. Klein, S. Rao, and S. Subramanian. 1997. Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55, 1 (1997), 3--23.

Digital Library

[16]

K. Jain. 2001. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 2001, 1 (21), 39--60.

[17]

S. Khuller and U. Vishkin. 1994. Biconnectivity approximations and graph carvings. J. ACM 41, 2 (1994), 214--235.

Digital Library

[18]

P. Klein. 2006. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. 749--756.

Digital Library

[19]

P. Klein. 2008. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37, 6 (2008), 1926--1952.

Digital Library

[20]

P. Klein and R. Ravi. 1993. When cycles collapse: A general approximation technique for constrained two-connectivity problems. In Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization. 39--55.

[21]

K. Mehlhorn. 1988. A faster approximation algorithm for the Steiner problem in graphs. Inform. Process. Lett. 27, 3 (1988), 125--128.

Digital Library

[22]

S. Nakano and T. Uno. 2003. Efficient Generation of Rooted Trees. Technical Report NII-2003-005E. National Institute of Informatics.

[23]

R. Ravi. 1992. Approximation Algorithms for Steiner Augmentations for Two-Connectivity. Technical Report TR-CS-92-21. Brown University.

Digital Library

[24]

M. Resende and P. Pardalos (Eds.). 2006. Handbook of Optimization in Telecommunications. Springer.

[25]

H. Whitney. 1932. Non-separable and planar graphs. Trans. Amer. Math. Soc. 34 (1932), 339--362.

[26]

P. Widmayer. 1986. A fast approximation algorithm for Steiner’s problem in graphs. In Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, Vol. 246. Springer-Verlag, 17--28.

Digital Library

[27]

D. Williamson, M. Goemans, M. Mihail, and V. Vazirani. 1993. A primal-dual approximation algorithm for generalized Steiner network problems. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing. 708--717.

Digital Library

[28]

Y. Wu, P. Widmayer, and C. Wong. 1986. A faster approximation algorithm for the Steiner problem in graphs. Acta Inf. 23, 2 (1986), 223--229.

Digital Library

Cited By

Marx DPilipczuk MPilipczuk M(2022)A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar GraphsSIAM Journal on Computing10.1137/19M130408851:2(254-289)Online publication date: 7-Apr-2022
https://doi.org/10.1137/19M1304088
Marx DPilipczuk MPilipczuk M(2018)On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00052(474-484)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00052

Index Terms

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Routing and network design problems

Recommendations

Total domination in planar graphs of diameter two

MacGillivary and Seyffarth [G. MacGillivray, K. Seyffarth, Domination numbers of planar graphs, J. Graph Theory 22 (1996) 213-229] proved that planar graphs of diameter two have domination number at most three. Goddard and Henning [W. Goddard, M.A. ...
Edge choosability and total choosability of planar graphs with no 3-cycles adjacent 4-cycles

Two cycles are said to be adjacent if they share a common edge. Let G be a planar graph without triangles adjacent 4-cycles. We prove that l ( G ) Δ ( G ) + 2 if Δ ( G ) 6 , and l ' ( G ) = Δ ( G ) and l ( G ) = Δ ( G ) + 1 if Δ ( G ) 8 , where l ' ( G )...
Acyclic Edge Coloring of Triangle-Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 12, Issue 3

June 2016

408 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2930058

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2016 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: 25 April 2016

Accepted: 01 September 2015

Revised: 01 May 2015

Received: 01 February 2013

Published in TALG Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
568
Total Downloads

Downloads (Last 12 months)85
Downloads (Last 6 weeks)11

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Marx DPilipczuk MPilipczuk M(2022)A Subexponential Parameterized Algorithm for Directed Subset Traveling Salesman Problem on Planar GraphsSIAM Journal on Computing10.1137/19M130408851:2(254-289)Online publication date: 7-Apr-2022
https://doi.org/10.1137/19M1304088
Marx DPilipczuk MPilipczuk M(2018)On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2018.00052(474-484)Online publication date: Oct-2018
https://doi.org/10.1109/FOCS.2018.00052

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents