A PTAS for three-edge-connected survivable network design in planar graphs. (English) Zbl 1467.68137
Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 81, Article 3, 13 p. (2017).
Summary: We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement \(r\in\{0,1,2,3\}\) for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices \(u\) and \(v\), at least \(\min\{r(v), r(u)\}\) edge-disjoint \(u\)-to-\(v\) paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge (paying for each edge separately). This generalizes an earlier result for \(r\in\{0,1,2\}\). In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.
For the entire collection see [Zbl 1372.68012].
For the entire collection see [Zbl 1372.68012].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C40 | Connectivity |
| 68W25 | Approximation algorithms |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | S. Arora, M. Grigni, D. Karger, P. Klein, and A. Woloszyn. A polynomial-time approxima-tion scheme for weighted planar graph TSP. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33-41, 1998. · Zbl 0930.68104 |
| [2] | B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, 1994. doi:10.1145/174644.174650. · Zbl 0807.68067 · doi:10.1145/174644.174650 |
| [3] | M. Bateni, M. Hajiaghayi, and D. Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011. doi:10.1145/ 2027216.2027219. · Zbl 1281.68233 · doi:10.1145/2027216.2027219 |
| [4] | A. Berger, A. Czumaj, M. Grigni, and H. Zhao. Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. In Proceedings of the 13th European Symposium on Algorithms, volume 3669 of Lecture Notes in Computer Science, pages 472-483, 2005. · Zbl 1162.68817 |
| [5] | A. Berger and M. Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming, volume 4596 of Lecture Notes in Computer Science, pages 90-101, 2007. doi:10.1007/978-3-540-73420-8_10. · Zbl 1171.68588 · doi:10.1007/978-3-540-73420-8_10 |
| [6] | G. Borradaile, E. Demaine, and S. Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 2012. Online. doi: 10.1016/j.jda.2012.04.011. · Zbl 1262.90179 · doi:10.1016/j.jda.2012.04.011 |
| [7] | G. Borradaile, C. Kenyon-Mathieu, and P. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, volume 7, pages 1285-1294, 2007. · Zbl 1302.05178 |
| [8] | G. Borradaile and P. Klein. The two-edge connectivity survivable network problem in planar graphs. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pages 485-501, 2008. · Zbl 1153.68565 |
| [9] | G. Borradaile and P. Klein. The two-edge connectivity survivable-network design problem in planar graphs. ACM Transactions on Algorithms, 12(3):30:1-30:29, 2016. · Zbl 1445.68152 |
| [10] | G. Borradaile, P. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms, 5(3):1-31, 2009. · Zbl 1300.05294 |
| [11] | A. Czumaj and A. Lingas. A polynomial time approximation scheme for euclidean minimum cost k-connectivity. In Automata, Languages and Programming, pages 682-694. Springer, 1998. · Zbl 0913.05069 |
| [12] | A. Czumaj and A. Lingas. On approximability of the minimum cost k-connected spanning subgraph problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 281-290, 1999. · Zbl 0974.68156 |
| [13] | R. Erickson, C. Monma, and A. Veinott. Send-and-split method for minimum-concave-cost network flows. Mathematics of Operations Research, 12:634-664, 1987. · Zbl 0667.90036 |
| [14] | K. Eswaran and R. Tarjan. Augmentation problems. SIAM Journal on Computing, 5(4):653-665, 1976. · Zbl 0346.05112 |
| [15] | G. Frederickson and J. Jájá. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270-283, 1981. · Zbl 0461.05040 |
| [16] | D. A. Holton, B. Jackson, A. Saito, and N. C. Wormald. Removable edges in 3-connected graphs. J. Graph Theory, 14:465-475, 1990. · Zbl 0729.05037 |
| [17] | K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 2001(1):39-60, 21. · Zbl 1107.68533 |
| [18] | S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings. Journal of the ACM, 41(2):214-235, 1994. · Zbl 0822.68082 |
| [19] | P. Klein. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 749-756, 2006. doi: 10.1145/1132516.1132620. · Zbl 1301.05335 · doi:10.1145/1132516.1132620 |
| [20] | P. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM Journal on Computing, 37(6):1926-1952, 2008. · Zbl 1155.68090 |
| [21] | Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of Leib-niz International Proceedings in Informatics (LIPIcs), pages 554-567. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. · Zbl 1329.68033 |
| [22] | P. Klein and R. Ravi. When cycles collapse: A general approximation technique for con-straind two-connectivity problems. In Proceedings of the 3rd International Conference on Integer Programming and Combinatorial Optimization, pages 39-55, 1993. · Zbl 0942.68651 |
| [23] | A. Sebő and J. Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-tsp, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, pages 1-34, 2014. · Zbl 1340.90201 |
| [24] | H. Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc., 34:339-362, 1932. · JFM 58.0608.01 |
| [25] | B. Zheng. Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs. CoRR, abs/1701.08315, 2017. URL: http: //arxiv.org/abs/1701.08315. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
