Abstract
We investigate the practicality of approximation schemes for optimization problems in planar graphs based on balanced separators. The first polynomial-time approximation schemes (PTASes) for problems in planar graphs were based on balanced separators, wherein graphs are recursively decomposed into small enough pieces in which optimal solutions can be found by brute force or other methods. However, this technique was supplanted by the more modern and (theoretically) more efficient approach of decomposing a planar graph into graphs of bounded treewidth, in which optimal solutions are found by dynamic programming. While the latter approach has been tested experimentally, the former approach has not.
To test the separator-based method, we examine the minimum feedback vertex set (FVS) problem in planar graphs. We propose a new, simple \(O(n \log n)\)-time approximation scheme for FVS using balanced separators and a linear kernel. The linear kernel reduces the size of the graph to be linear in the size of the optimal solution. In doing so, we correct a reduction rule in Bonamy and Kowalik’s linear kernel [11] for FVS. We implemented this PTAS and evaluated its performance on large synthetic and real-world planar graphs. Unlike earlier planar PTAS engineering results [8, 36], our implementation guarantees the theoretical error bounds on all tested graphs.
This material is based upon work supported by the National Science Foundation under Grant No. CCF-1252833.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Given a spanning tree for a graph, a fundamental cycle consists of a non-tree edge and a path in the tree connecting the two endpoints of that edge.
- 2.
This is to return a trivial no-instance for the decision problem when the resulting graph has more than 15k vertices.
- 3.
- 4.
References
Abu-Khzam, F.N., Bou Khuzam, M.: An improved kernel for the undirected planar feedback vertex set problem. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol. 7535, pp. 264–273. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33293-7_25
Aleksandrov, L., Djidjev, H., Guo, H., Maheshwari, A.: Partitioning planar graphs with costs and weights. J. Exp. Algorithm. (JEA) 11, 1–5 (2007)
Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. J. Am. Math. Soc. 3(4), 801–808 (1990)
Arora, S., Grigni, M., Karger, D.R., Klein, P.N., Woloszyn, A.: A polynomial-time approximation scheme for weighted planar graph TSP. In: SODA, vol. 98, pp. 33–41 (1998)
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM (JACM) 41(1), 153–180 (1994)
Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942–959 (1998)
Bateni, M.H., Hajiaghayi, M.T., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5), 21 (2011)
Becker, A., Fox-Epstein, E., Klein, P.N., Meierfrankenfeld, D.: Engineering an approximation scheme for traveling salesman in planar graphs. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 75 (2017)
Becker, A., Geiger, D.: Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83(1), 167–188 (1996)
Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. J. ACM (JACM) 63(5), 44 (2016)
Bonamy, M., Kowalik, Ł.: A 13k-kernel for planar feedback vertex set via region decomposition. Theoret. Comput. Sci. 645, 25–40 (2016)
Borradaile, G., Klein, P., Mathieu, C.: An \({O}(n \log n)\) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms (TALG) 5(3), 1–31 (2009)
Boyer, J.M., Myrvold, W.J.: On the cutting edge: simplified \({O}(n)\) planarity by edge addition. J. Graph Algorithms Appl. 8(2), 241–273 (2004)
Chiba, N., Nishizeki, T., Saito, N.: Applications of the Lipton and Tarjan’s planar separator theorem. J. Inf. Process. 4(4), 203–207 (1981)
Chiba, N., Nishizeki, T., Saito, N.: An approximation algorithm for the maximum independent set problem on planar graphs. SIAM J. Comput. 11(4), 663–675 (1982)
Cohen-Addad, V., de Verdière, É.C., Klein, P.N., Mathieu, C., Meierfrankenfeld, D.: Approximating connectivity domination in weighted bounded-genus graphs. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 584–597. ACM (2016)
Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.-i.: Algorithmic graph minor theory: decomposition, approximation, and coloring. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 637–646 (2005)
Demaine, E.D., Hajiaghayi, M.T.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 590–601 (2005)
Demetrescu, C., Goldberg, A., Johnson, D.: Implementation challenge for shortest paths. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms. Springer, Boston (2008). https://doi.org/10.1007/978-0-387-30162-4
Eisenstat, D., Klein, P., Mathieu, C.: An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 626–638. SIAM (2012)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 503–510 (2010)
Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Linear kernels for (connected) dominating set on H-minor-free graphs. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 82–93 (2012)
Fox-Epstein, E., Mozes, S., Phothilimthana, P.M., Sommer, C.: Short and simple cycle separators in planar graphs. J. Exp. Algorithm. (JEA) 21, 2 (2016)
Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23(4), 613–632 (2003)
Holzer, M., Schulz, F., Wagner, D., Prasinos, G., Zaroliagis, C.: Engineering planar separator algorithms. J. Exp. Algorithm. (JEA) 14, 5 (2009)
Iwata, Y.: Linear-time kernelization for feedback vertex set. CoRR (2016)
Iwata, Y., Wahlström, M., Yoshida, Y.: Half-integrality, LP-branching, and FPT algorithms. SIAM J. Comput. 45(4), 1377–1411 (2016)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Klein, P.N.: A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights. SIAM J. Comput. 37(6), 1926–1952 (2008)
Kozen, D.C.: The Design and Analysis of Algorithms. Springer, Heidelberg (2012)
Le, H., Zheng, B.: Local search is a PTAS for feedback vertex set in minor-free graphs. CoRR, abs/1804.06428 (2018)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)
Marzban, M., Qian-Ping, G.: Computational study on a PTAS for planar dominating set problem. Algorithms 6(1), 43–59 (2013)
Mehlhorn, K., Näher, S., Uhrig, C.: The LEDA platform for combinatorial and geometric computing. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 7–16. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63165-8_161
Tazari, S., Müller-Hannemann, M.: Dealing with large hidden constants: engineering a planar Steiner tree PTAS. J. Exp. Algorithm. (JEA) 16, 3–6 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Borradaile, G., Le, H., Zheng, B. (2019). Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs. In: Kotsireas, I., Pardalos, P., Parsopoulos, K., Souravlias, D., Tsokas, A. (eds) Analysis of Experimental Algorithms. SEA 2019. Lecture Notes in Computer Science(), vol 11544. Springer, Cham. https://doi.org/10.1007/978-3-030-34029-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-34029-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34028-5
Online ISBN: 978-3-030-34029-2
eBook Packages: Computer ScienceComputer Science (R0)