Abstract
Finding minimum vertex covers (MinVC) for simple undirected graphs is a well-known NP-hard problem. In the literature there have been many heuristics for obtaining good vertex covers. However, most of them focus on solving this problem in relatively small graphs. Recently, a local search solver called FastVC is designed to solve the MinVC problem on real-world massive graphs. Since the traditional best-picking heuristic was believed to be of high complexity, FastVC replaces it with an approximate best-picking strategy. However, since best-picking has been proved to be powerful for a wide range of problems, abandoning it may be a great sacrifice. In this paper we have developed a local search MinVC solver which utilizes best-picking with noise to remove vertices. Experiments conducted on a broad range of real-world massive graphs show that our proposed method finds better vertex covers than state-of-the-art local search algorithms on many graphs.
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
Andrade, D.V., Resende, M.G.C., Werneck, R.F.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525–547 (2012)
Barbosa, V.C., Campos, L.C.D.: A novel evolutionary formulation of the maximum independent set problem. J. Comb. Optim. 8(4), 419–437 (2004)
Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI, pp. 25–31 (2015)
Cai, S., Su, K., Chen, Q.: EWLS: a new local search for minimum vertex cover. In: AAAI (2010)
Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: an efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. 46, 687–716 (2013)
Cai, S., Su, K., Sattar, A.: Local search with edge weighting and configuration checking heuristics for minimum vertex cover. Artif. Intell. 175(9), 1672–1696 (2011)
Chung Graham, F., Lu, L.: Complex graphs and networks american mathematical society (2006)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, vol. 6. MIT Press, Cambridge (2001)
Eubank, S., Kumar, V., Marathe, M.V., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 718–727. Society for Industrial and Applied Mathematics (2004)
Ji, Y., Xu, X., Stormo, G.D.: A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences. Bioinformatics 20(10), 1603–1611 (2004)
Jin, Y., Hao, J.: General swap-based multiple neighborhood tabu search for the maximum independent set problem. Eng. Appl. AI 37, 20–33 (2015)
Johnson, D.S., Trick, M.A.: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, vol. 26. American Mathematical Society, Providence (1996)
Katayama, K., Hamamoto, A., Narihisa, H.: An effective local search for the maximum clique problem. Inf. Process. Lett. 95(5), 503–511 (2005)
Li, C.M., Quan, Z.: An efficient branch-and-bound algorithm based on maxsat for the maximum clique problem. In: Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, vol. 10, pp. 128–133. AAAI Press, Atlanta (2010)
Pullan, W.J., Hoos, H.H.: Dynamic local search for the maximum clique problem. J. Artif. Intell. Res. (JAIR) 25, 159–185 (2006)
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)
Rossi, R., Ahmed, N.: The network data repository with interactive graph analytics and visualization. In: AAAI, pp. 4292–4293 (2015)
Rossi, R.A., Ahmed, N.K.: Coloring large complex networks. Soc. Netw. Anal. Min. 4(1), 1–37 (2014)
Rossi, R.A., Gleich, D.F., Gebremedhin, A.H., Patwary, M.M.A.: Fast maximum clique algorithms for large graphs. In: Proceedings of the Companion Publication of the 23rd International Conference on World Wide Web Companion, pp. 365–366. International World Wide Web Conferences Steering Committee (2014)
Segundo, P.S., Rodríguez-Losada, D., Jiménez, A.: An exact bit-parallel algorithm for the maximum clique problem. Comput. OR 38(2), 571–581 (2011)
Traud, A.L., Mucha, P.J., Porter, M.A.: Social structure of facebook networks. Phys. A Stat. Mech. Appl. 391(16), 4165–4180 (2012)
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015)
Acknowledgment
This work is supported by ARC Grant FT0991785, NSF Grant No. 61463044 and Grant No. [2014]7421 from the Joint Fund of the NSF of Guizhou province of China.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Ma, Z., Fan, Y., Su, K., Li, C., Sattar, A. (2016). Local Search with Noisy Strategy for Minimum Vertex Cover in Massive Graphs. In: Booth, R., Zhang, ML. (eds) PRICAI 2016: Trends in Artificial Intelligence. PRICAI 2016. Lecture Notes in Computer Science(), vol 9810. Springer, Cham. https://doi.org/10.1007/978-3-319-42911-3_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-42911-3_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-42910-6
Online ISBN: 978-3-319-42911-3
eBook Packages: Computer ScienceComputer Science (R0)