C&SA | Contents

Volume 62 >>> № 5 SEPTEMBER — OCTOBER 2026

-->

UDC 519.854

P. Shylo
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine,
Kyiv, Ukraine, petershylo@gmail.com

A HYBRID ALGORITHM FOR SOLVING THE MAXIMUM INDEPENDENT SET PROBLEM

Abstract. The maximum independent set problem is an NP-hard combinatorial optimization problem with a wide range of practical applications. Despite the considerable number of solution methods proposed in the literature, the development of efficient algorithms capable of obtaining high-quality solutions within reasonable time remains an open challenge. This paper presents a hybrid approximate algorithm that combines several search mechanisms for effective solving of this problem.

Keywords: maximum independent set, tabu search, guided local search, path relinking, hybrid algorithms.

full text

REFERENCES

Sergienko I.V., Shilo V.P. Problems of discrete optimization: problems, methods of solution, research [in Ukrainian]. Kyiv: Nauk. dumka, 2003. 264 p.
Butenko S. Maximum independent set and related problems with applications. PhD thesis, University of Florida, 2003. Р. 155.
Zheng M., Hao J.-K., Wu Q. Exact and heuristic solution approaches for the Generalized Independent Set Problem. Computers & Operations Research. 2024. Vol. 164. Article number 106561. https://doi.org/10.1016/j.cor.2024.106561.
Glover F. Tabu search (part I). ORSA Journal on Computing. 1989. Vol. 1, N 3. P. 190–206. https://doi.org/10.1287/ijoc.1.3.190.
Glover F. Tabu search (part II). ORSA Journal on Computing. 1990. Vol. 2, N 1. P. 4–32. https://doi.org/10.1287/ijoc.2.1.4.
Alsheddy A., Voudouris C., Tsang E.P.K., Alhindi A. Guided Local Search. Handbook of Heuristics. Marti R., Pardalos P., Resende M. (Eds.). Cham, Springer, 2018. P. 261–297. https://doi.org/10.1007/978-3-319-07124-4_2.
Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem. European Journal of Operational Research. 1999. Vol. 113, N 2. P. 469–499. https://doi.org/10.1016/S0377-2217(98)00099-X.
Glover F., Laguna M., Martн R. Fundamentals of scatter search and path relinking. Control and Cybernetics. 2000. Vol. 29, N 3. P. 653–684.
Carraghan R., Pardalos P.M. An exact algorithm for the maximum clique problem. Operations Research Letters. 1990. Vol. 9, N 6. P. 375–382. https://doi.org/10.1016/0167-6377(90)90057-C.
San Segundo P., Rodrнguez-Losada D., Jimйnez A. An exact bit-parallel algorithm for the maximum clique problem. Computers & Operations Research. 2011. Vol. 38, N 2. P. 571–581. https://doi.org/10.1016/j.cor.2010.07.019.
Grosso A., Locatelli M., Pullan W. Simple ingredients leading to very efficient heuristics for the maximum clique problem. Journal of Heuristics. 2008. Vol. 14, N 6. P. 587–612. https://doi.org/10.1007/s10732-007-9055-x.
Katayama K., Hamamoto A., Narihisa H. An effective local search for the maximum clique problem. Information Processing Letters. 2005. Vol. 95, N 5. P. 503–511. https://doi.org/10.1016/j.ipl.2005.05.010.
Hansen P., Mladenovi N., Uroevi D. Variable neighborhood search for the maximum clique. Discrete Applied Mathematics. 2004. Vol. 145, N 1. P. 117–125. https://doi.org/10.1016/j.dam.2003.09.012.
Brunato M., Battiti R. R-EVO: A reactive evolutionary algorithm for the maximum clique problem. IEEE Transactions on Evolutionary Computation. 2011. Vol. 15, N 6. P. 770–782. https://doi.org/10.1109/TEVC.2010.2043363.
Zhang Q., Sun J., Tsang E. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation. 2005. Vol. 9, N 2. P. 192–200. https://doi.org/10.1109/TEVC.2004.840835.
Johnson D.S., Trick M.A. (Eds.) Cliques, coloring, and satisfiability: second DIMACS implementation challenge. Providence, American Mathematical Society. 1996. Vol. 26. P. 657. https://doi.org/10.1090/dimacs/026.
Andrade D.V., Resende M.G.C., Werneck R.F. Fast local search for the maximum independent set problem. Journal of Heuristics. 2012. Vol. 18, N 4. P. 525–547. https://doi.org/10.1007/s10732-012-9196-4.
Benlic U., Hao J.-K. Breakout local search for maximum clique problems. Computers & Operations Research. 2013. Vol. 40, N 1. P. 192–206. https://doi.org/10.1016/j.cor.2012.06.002.
Cai S., Su K., Luo C., Sattar A. NuMVC: An efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research. 2013. Vol. 46. P. 687–716. https://doi.org/10.1613/jair.3907.
Pullan W. Phased local search for the maximum clique problem. Journal of Combinatorial Optimization. 2006. Vol. 12, N 3. P. 303–323. https://doi.org/10.1007/s10878-006-9635-y.
Pullan W., Mascia F., Brunato M. Cooperating local search for the maximum clique problem. Journal of Heuristics. 2011. Vol. 17, N 2. P. 181–199. https://doi.org/10.1007/s10732-010-9131-5.
Richter S., Helmert M., Gretton C. A stochastic local search approach to vertex cover. KI 2007: Advances in Artificial Intelligence. J. Hertzberg, M. Beetz, R. Englert (Eds.). Berlin, Heidelberg, Springer. 2007. P. 412–426. https://doi.org/10.1007/978-3-540-74565-5_31.
Wu Q., Hao J.-K., Glover F. Multi-neighborhood tabu search for the maximum weight clique problem. Annals of Operations Research. 2012. Vol. 196, N 1. P. 611–634. https://doi.org/10.1007/s10479-012-1124-3.
Wu Q., Hao J.-K. An adaptive multistart tabu search approach to solve the maximum clique problem. Journal of Combinatorial Optimization. 2013. Vol. 26, N 1. P. 86–108. https://doi.org/10.1007/s10878-011-9437-8.
Jin Y., Hao J.-K. General swap-based multiple neighborhood tabu search for the maximum independent set problem. Engineering Applications of Artificial Intelligence. 2015. Vol. 37. P. 20–33. https://doi.org/10.1016/j.engappai.2014.08.007.