Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

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 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 of 13 / 17. The currently best approximation algorithm for MwIST only has a performance ratio of \(1/3 - \epsilon \), for any \(\epsilon > 0\). In this paper, we present a simple algorithm based on a novel relationship between MwIST and maximum weight matching, and show that it achieves a significantly better approximation ratio of 1/2. When restricted to claw-free graphs, a special case previously studied, we design a 7/12-approximation algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24

Similar content being viewed by others

References

  1. Binkele-Raible, D., Fernau, H., Gaspers, S., Liedloff, M.: Exact and parameterized algorithms for max internal spanning tree. Algorithmica 65, 95–128 (2013)

    Article  MathSciNet  Google Scholar 

  2. Chen, Z.-Z., Harada, Y., Guo, F., Wang, L.: An approximation algorithm for maximum internal spanning tree. J. Comb. Optim. 35, 955–979 (2018)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Fomin, F.V., Lokshtanov, D., Grandoni, F., Saurabh, S.: Sharp separation and applications to exact and parameterized algorithms. Algorithmica 63, 692–706 (2012)

    Article  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  7. Knauer, M., Spoerhase, J.: Better approximation algorithms for the maximum internal spanning tree problem. In: Proceedings of WADS 2009, LNCS 5664, pp. 489–470 (2009)

    Google Scholar 

  8. Li, W., Chen, J., Wang, J.: Deeper local search for better approximation on maximum internal spanning tree. In: Proceedings of ESA 2014, LNCS 8737, pp. 642–653 (2014)

  9. Li, W., Wang, J., Chen, J., Cao, Y.: A \(2k\)-vertex kernel for maximum internal spanning tree. In: Proceedings of WADS 2015, LNCS 9214, pp. 495–505 (2015)

  10. Li, X., Jiang, H., Feng, H.: Polynomial time for finding a spanning tree with maximum number of internal vertices on interval graphs. In: Proceedings of FAW 2016, LNCS 9711, pp. 92–101 (2016)

  11. Li, X., Zhu, D.: A \(4/3\)-approximation algorithm for the maximum internal spanning tree problem. CoRR, arXiv:1409.3700 (2014)

  12. Li, X., Zhu, D.: Approximating the maximum internal spanning tree problem via a maximum path-cycle cover. In: Proceedings of ISAAC 2014, LNCS 8889, pp. 467–478 (2014)

  13. Prieto, E.: Systematic kernelization in FPT algorithm design. In: Ph.D. Thesis, The University of Newcastle, Australia (2005)

  14. Prieto, E., Sloper, C.: Either/or: using vertex cover structure in designing FPT-algorithms—the case of \(k\)-internal spanning tree. In: Proceedings of WADS 2003, LNCS 2748, pp. 474–483 (2003)

  15. Prieto, E., Sloper, C.: Reducing to independent set structure—the case of \(k\)-internal spanning tree. Nord. J. Comput. 12, 308–318 (2005)

    MathSciNet  MATH  Google Scholar 

  16. Salamon, G.: Approximating the maximum internal spanning tree problem. Theor. Comput. Sci. 410, 5273–5284 (2009)

    Article  MathSciNet  Google Scholar 

  17. Salamon, G.: Degree-based spanning tree optimization. In: Ph.D. Thesis, Budapest University of Technology and Economics, Hungary (2009)

  18. Salamon, G., Wiener, G.: On finding spanning trees with few leaves. Inf. Process. Lett. 105, 164–169 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the reviewers for their insightful comments and for their suggested changes that improve the presentation greatly. ZZC was supported in part by the Grant-in-Aid for Scientific Research of the Ministry of Education, Culture, Sports, Science and Technology of Japan, under Grant No. 24500023. GL was supported by the NSERC Canada and the NSFC Grant No. 61672323; most of his work was done while visiting ZZC at the Tokyo Denki University at Hatoyama. LW is fully supported by a Grant from the Research Grants Council of the Hong Kong Special Administrative Region, China, CityU 11256116. YC was supported in part by the NSERC Canada, the NSFC Grants Nos. 11771114 and 11571252, and the China Scholarship Council Grant No. 201508330054.

Author information

Authors and Affiliations

  1. Division of Information System Design, Tokyo Denki University, Hatoyama, Saitama, 350-0394, Japan

    Zhi-Zhong Chen

  2. Department of Computing Science, University of Alberta, Edmonton, AB, T6G 2E8, Canada

    Guohui Lin & Yong Chen

  3. Department of Computer Science, City University of Hong Kong, 83 Tat Chee Avenue, Kowloon, Hong Kong, China

    Lusheng Wang & Dan Wang

  4. City University of Hong Kong Shenzhen Research Institute, Shenzhen Hi-Tech Industrial Park, Nanshan District, Shenzhen, China

    Lusheng Wang

  5. Institute of Operational Research and Cybernetics, Hangzhou Dianzi University, Hangzhou, 310018, Zhejiang, China

    Yong Chen

Authors
  1. Zhi-Zhong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guohui Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lusheng Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Yong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Dan Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Zhi-Zhong Chen or Guohui Lin.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

An extended abstract appears in the Proceedings of COCOON 2017. LNCS 10392, pp. 124–136.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, ZZ., Lin, G., Wang, L. et al. Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem. Algorithmica 81, 4167–4199 (2019). https://doi.org/10.1007/s00453-018-00533-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-018-00533-w

Keywords

Search

Navigation