Abstract
A vertex cover (VC) of a graph \(G\) is a subset of vertices in \(G\) such that at least one endpoint vertex of each edge in \(G\) is in this subset. The minimum VC (MVC) problem is to identify a VC of minimum size (cardinality) and is known to be NP-hard. Although many local search algorithms have been developed to solve the MVC problem close-to-optimally, their applicability on giant graphs (with no less than 100,000 vertices) is limited. For such graphs, there are two reasons why it would be beneficial to have linear-time-and-space algorithms that produce small VCs. Such algorithms can: (a) serve as preprocessing steps to produce good starting states for local search algorithms and (b) also be useful for many applications that require finding small VCs quickly. In this paper, we develop a new linear-time-and-space algorithm, called MVC-WP, for solving the MVC problem on giant graphs based on the idea of warning propagation, which has so far only been used as a theoretical tool for studying properties of MVCs on infinite random graphs. We empirically show that it outperforms other known linear-time-and-space algorithms in terms of sizes of produced VCs.
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
Notes
- 1.
A minimal VC is a VC such that no proper subset thereof is also a VC.
- 2.
We compiled these benchmark instances in the DIMACS format and made them available online at http://files.hong.me/papers/xu2018b-data.
- 3.
- 4.
- 5.
References
Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: theory and experiments. In: The Workshop on Algorithm Engineering and Experiments (2004)
Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525–547 (2012). https://doi.org/10.1007/s10732-012-9196-4
Bader, D.A., Meyerhenke, H., Sanders, P., Wagner, D. (eds.): Graph Partitioning and Graph Clustering. Discrete Mathematics and Theoretical Computer Science. American Mathematical Society and Center, Providence (2013)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). https://doi.org/10.1126/science.286.5439.509
Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: The International Joint Conference on Artificial Intelligence, pp. 747–753 (2015)
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 (2013). https://doi.org/10.1613/jair.3907
Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the LambertW function. Adv. Comput. Math. 5(1), 329–359 (1996). https://doi.org/10.1007/BF02124750
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005). https://doi.org/10.4007/annals.2005.162.439
Erdős, P., Rényi, A.: On random graphs I. Publicationes Mathematicae 6, 290–297 (1959)
Fang, Z., Li, C.M., Xu, K.: An exact algorithm based on MaxSAT reasoning for the maximum weight clique problem. J. Artif. Intell. Res. 55, 799–833 (2016). https://doi.org/10.1613/jair.4953
Filiol, E., Franc, E., Gubbioli, A., Moquet, B., Roblot, G.: Combinatorial optimisation of worm propagation on an unknown network. Int. J. Comput. Electr. Autom. Control Inf. Eng. 1(10), 2931–2937 (2007)
Finch, S.R.: Mathematical Constants, Encyclopedia of Mathematics and Its Applications, vol. 94. Cambridge University Press, Cambridge (2003)
Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-29953-X
Goyal, A., Lu, W., Lakshmanan, L.V.S.: SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: The IEEE International Conference on Data Mining, pp. 211–220 (2011). https://doi.org/10.1109/ICDM.2011.132
Haynsworth, E.V., Goldberg, K.: Bernoulli and Euler polynomials-Riemann zeta function. In: Abramowitz, M., Stegun, I.A. (eds.) Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables, pp. 803–819. Dover Publications, Inc., Mineola (1965)
Hiary, G.A.: Fast methods to compute the Riemann zeta function. Ann. Math. 174(2), 891–946 (2011). https://doi.org/10.4007/annals.2011.174.2.4
Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. American Mathematical Society, Providence (1996)
Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 5th edn. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-24488-9
Mézard, M., Montanari, A.: Information, Physics, and Computation. Oxford University Press, Oxford (2009)
Niskanen, S., Östergård, P.R.J.: Cliquer user’s guide, version 1.0. Technical report T48, Communications Laboratory, Helsinki University of Technology, Espoo, Finland (2003)
Pullan, W.: Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers. Discret. Optim. 6(2), 214–219 (2009). https://doi.org/10.1016/j.disopt.2008.12.001
Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: the AAAI Conference on Artificial Intelligence, pp. 4292–4293 (2015). http://networkrepository.com
Sherali, H.D., Rios, M.: An air force crew allocation and scheduling problem. J. Oper. Res. Soc. 35(2), 91–103 (1984)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-662-04565-7
Weigt, M., Zhou, H.: Message passing for vertex covers. Phys. Rev. E 74(4), 046110 (2006). https://doi.org/10.1103/PhysRevE.74.046110
Xu, H., Kumar, T.K.S., Koenig, S.: A new solver for the minimum weighted vertex cover problem. In: Quimper, C.-G. (ed.) CPAIOR 2016. LNCS, vol. 9676, pp. 392–405. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33954-2_28
Xu, H., Kumar, T.K.S., Koenig, S.: A linear-time and linear-space algorithm for the minimum vertex cover problem on giant graphs. In: The International Symposium on Combinatorial Search, pp. 173–174 (2017)
Yamaguchi, K., Masuda, S.: A new exact algorithm for the maximum weight clique problem. In: The International Technical Conference on Circuits/Systems, Computers and Communications. pp. 317–320 (2008)
Acknowledgment
The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant numbers 1724392, 1409987, and 1319966. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the sponsoring organizations, agencies or the U.S. government.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Xu, H., Sun, K., Koenig, S., Kumar, T.K.S. (2018). A Warning Propagation-Based Linear-Time-and-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs. In: van Hoeve, WJ. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2018. Lecture Notes in Computer Science(), vol 10848. Springer, Cham. https://doi.org/10.1007/978-3-319-93031-2_41
Download citation
DOI: https://doi.org/10.1007/978-3-319-93031-2_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93030-5
Online ISBN: 978-3-319-93031-2
eBook Packages: Computer ScienceComputer Science (R0)