Skip to main content
Springer Nature Link
Log in

An Efficient Local Search Algorithm for Minimum Weighted Vertex Cover on Massive Graphs

  • Conference paper
  • First Online:
Simulated Evolution and Learning (SEAL 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10593))

Included in the following conference series:

Abstract

The minimum weighted vertex cover (MWVC) problem is a well known NP-hard problem with various real-world applications. In this paper, we design an efficient algorithm named FastWVC to solve MWVC problem in massive graphs. Two strategies are proposed. One is the ConstructWVC procedure, aiming to generate a quality initial vertex cover. The other is a new exchange step for reconstructing a vertex cover. Experiments on 102 instances were conducted to confirm the effectiveness of our algorithm. The results show that the FastWVC algorithm outperforms other algorithms in terms of both solution quality and computational time in most of the instances.

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

Access this chapter

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

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 84.99
Price excludes VAT (USA)
Softcover Book
USD 109.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bouamama, S., Blum, C., Boukerram, A.: A population-based iterated greedy algorithm for the minimum weight vertex cover problem. Appl. Soft Comput. 12, 1632–1639 (2012). Elsevier Science Publishers B. V

    Google Scholar 

  2. Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: International Conference on Artificial Intelligence, pp. 747–753 (2015)

    Google Scholar 

  3. Cai, S., Su, K., Chen, Q.: EWLS: a new local search for minimum vertex cover. In: Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July (2010)

    Google Scholar 

  4. Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: an efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. 46(1), 687–716 (2014)

    MathSciNet  MATH  Google Scholar 

  5. Cai, S., Su, K., Sattar, A.: Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif. Intell. 175(9–10), 1672–1696 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Jovanovic, R., Tuba, M.: An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Appl. Soft Comput. 11(8), 5360–5366 (2011)

    Article  Google Scholar 

  9. Katzmann, M., Komusiewicz, C.: Systematic exploration of larger local search neighborhoods for the minimum vertex cover problem (2017)

    Google Scholar 

  10. Li, R., Hu, S., Zhang, H., Yin, M.: An efficient local search framework for the minimum weighted vertex cover problem. Inf. Sci. 372, 428–445 (2016)

    Article  Google Scholar 

  11. Ma, Z., Fan, Y., Su, K., Li, C., Sattar, A.: Local search with noisy strategy for minimum vertex cover in massive graphs. In: Booth, R., Zhang, M.-L. (eds.) PRICAI 2016. LNCS, vol. 9810, pp. 283–294. Springer, Cham (2016). doi:10.1007/978-3-319-42911-3_24

    Chapter  Google Scholar 

  12. Ma, Z., Fan, Y., Su, K., Li, C., Sattar, A.: Random walk in large real-world graphs for finding smaller vertex cover. In: IEEE International Conference on TOOLS with Artificial Intelligence, pp. 686–690 (2016)

    Google Scholar 

  13. Richter, S., Helmert, M., Gretton, C.: A stochastic local search approach to vertex cover. In: Hertzberg, J., Beetz, M., Englert, R. (eds.) KI 2007. LNCS (LNAI), vol. 4667, pp. 412–426. Springer, Heidelberg (2007). doi:10.1007/978-3-540-74565-5_31

    Chapter  Google Scholar 

  14. Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015). http://networkrepository.com

  15. Shyu, S.J., Yin, P.Y., Lin, B.M.T.: An ant colony optimization algorithm for the minimum weight vertex cover problem. Ann. Oper. Res. 131(1), 283–304 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  16. Singh, A., Gupta, A.K.: A hybrid heuristic for the minimum weight vertex cover problem. Asia-Pac. J. Oper. Res. (APJOR) 23(2), 273–285 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  17. Zhou, T., Lü, Z., Wang, Y., Ding, J., Peng, B.: Multi-start iterated tabu search for the minimum weight vertex cover problem. J. Comb. Optim. 32(2), 368–384 (2016)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgement

This work is supported by National Natural Science Foundation of China 61502464. Shaowei Cai is also supported by Youth Innovation Promotion Association, Chinese Academy of Sciences.

Author information

Authors and Affiliations

  1. State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China

    Yuanjie Li & Shaowei Cai

  2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing, China

    Yuanjie Li & Shaowei Cai

  3. School of Information Technology and Management, University of International Business and Economics, Beijing, China

    Wenying Hou

Authors
  1. Yuanjie Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shaowei Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wenying Hou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shaowei Cai .

Editor information

Editors and Affiliations

  1. Southern University of Science and Technology, Shenzhen, China

    Yuhui Shi

  2. City University of Hong Kong, Hong Kong, Kowloon, Hong Kong

    Kay Chen Tan

  3. Victoria University of Wellington, Wellington, Wellington, New Zealand

    Mengjie Zhang

  4. Southern University of Science and Technology, Shenzhen, China

    Ke Tang

  5. RMIT University, Melbourne, Victoria, Australia

    Xiaodong Li

  6. City University of Hong Kong, Kowloon Tong, Hong Kong

    Qingfu Zhang

  7. Peking University, Beijing, China

    Ying Tan

  8. University of Leipzig, Leipzig, Germany

    Martin Middendorf

  9. University of Surrey, Guildford, Surrey, United Kingdom

    Yaochu Jin

Rights and permissions

Reprints and permissions

Copyright information

© 2017 Springer International Publishing AG

About this paper

Cite this paper

Li, Y., Cai, S., Hou, W. (2017). An Efficient Local Search Algorithm for Minimum Weighted Vertex Cover on Massive Graphs. In: Shi, Y., et al. Simulated Evolution and Learning. SEAL 2017. Lecture Notes in Computer Science(), vol 10593. Springer, Cham. https://doi.org/10.1007/978-3-319-68759-9_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-68759-9_13

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-68758-2

  • Online ISBN: 978-3-319-68759-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation