Abstract
Given a vertex-weighted connected graph \(G = (V, E)\), the maximum weight internal spanning tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of the internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NP-hard and APX-hard, and the currently best approximation algorithm has a proven performance ratio 13/17. The currently best approximation algorithm for MwIST only has a performance ratio \(1/3 - \epsilon \), for any \(\epsilon > 0\). In this paper, we present a simple algorithm based on a novel relationship between MwIST and the maximum weight matching, and show that it achieves a better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been previously studied, we design a 7/12-approximation algorithm.
This work was supported by KAKENHI Japan Grant No. 24500023 (ZZC), NSERC Canada (GL), GRF Hong Kong Grants CityU 114012 and CityU 123013 (LW), NSFC Grant No. 61672323 (GL), CSC Grant No. 201508330054 (YC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Binkele-Raible, D., Fernau, H., Gaspers, S., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65, 95–128 (2013)
Chen, Z.-Z., Harada, Y., Wang, L.: An approximation algorithm for maximum internal spanning tree. CoRR, abs/1608.00196 (2016)
Chen, Z.-Z., Lin, G., Wang, L., Chen, Y., Wang, D.: Approximation algorithms for the maximum weight internal spanning tree problem. arXiv, 1608.03299 (2016)
Coben, N., Fomin, F.V., Gutin, G., Kim, E.J., Saurabh, S., Yeo, A.: Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem. J. Comput. Syst. Sci. 76, 650–662 (2010)
Fomin, F.V., Gaspers, S., Saurabh, S., Thomasse, S.: A linear vertex kernel for maximum internal spanning tree. J. Comput. Syst. Sci. 79, 1–6 (2013)
Fomin, F.V., Lokshtanov, D., Grandoni, F., Saurabh, S.: Sharp separation and applications to exact and parameterized algorithms. Algorithmica 63, 692–706 (2012)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, San Francisco (1979)
Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 459–470. Springer, Heidelberg (2009). doi:10.1007/978-3-642-03367-4_40
Li, W., Chen, J., Wang, J.: Deeper local search for better approximation on maximum internal spanning trees. In: Schulz, A.S., Wagner, D. (eds.) ESA 2014. LNCS, vol. 8737, pp. 642–653. Springer, Heidelberg (2014). doi:10.1007/978-3-662-44777-2_53
Li, W., Wang, J., Chen, J., Cao, Y.: A 2k-vertex kernel for maximum internal spanning tree. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 495–505. Springer, Cham (2015). doi:10.1007/978-3-319-21840-3_41
Li, X., Jiang, H., Feng, H.: Polynomial time for finding a spanning tree with maximum number of internal vertices on interval graphs. In: Zhu, D., Bereg, S. (eds.) FAW 2016. LNCS, vol. 9711, pp. 92–101. Springer, Cham (2016). doi:10.1007/978-3-319-39817-4_10
Li, X., Zhu, D.: A \(4/3\)-approximation algorithm for the maximum internal spanning tree problem. CoRR, abs/1409.3700 (2014)
Li, X., Zhu, D.: Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Ahn, H.-K., Shin, C.-S. (eds.) ISAAC 2014. LNCS, vol. 8889, pp. 467–478. Springer, Cham (2014). doi:10.1007/978-3-319-13075-0_37
Prieto, E.: Systematic kernelization in FPT algorithm design. Ph.D. thesis. The University of Newcastle, Australia (2005)
Prieto, E., Sloper, C.: Either/or: using Vertex Cover structure in designing FPT-algorithms — the case of k-Internal Spanning Tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 474–483. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45078-8_41
Prieto, E., Sloper, C.: Reducing to independent set structure - the case of \(k\)-internal spanning tree. Nordic J. Comput. 12, 308–318 (2005)
Salamon, G.: Approximating the maximum internal spanning tree problem. Theoret. Comput. Sci. 410, 5273–5284 (2009)
Salamon, G.: Degree-based spanning tree optimization. Ph.D. thesis. Budapest University of Technology and Economics, Hungary (2009)
Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105, 164–169 (2008)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Chen, ZZ., Lin, G., Wang, L., Chen, Y., Wang, D. (2017). Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem. In: Cao, Y., Chen, J. (eds) Computing and Combinatorics. COCOON 2017. Lecture Notes in Computer Science(), vol 10392. Springer, Cham. https://doi.org/10.1007/978-3-319-62389-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-62389-4_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-62388-7
Online ISBN: 978-3-319-62389-4
eBook Packages: Computer ScienceComputer Science (R0)