A genetic algorithm for the maximum 2-packing set problem

Trejo-Sánchez, Joel Antonio ; Fajardo-Delgado, Daniel ; Gutierrez-Garcia, J. Octavio

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 1, pp. 173-184.

Résumé

Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.

Détail

Keywords: maximum 2-packing set, genetic algorithms, graph algorithms
Mots-clés : algorytm genetyczny, algorytm grafowy

Bibliographie

[1] Adacher, L. and Gemma, A. (2017). A robust algorithm to solve the signal setting problem considering different traffic assignment approaches, International Journal of Applied Mathematics and Computer Science 27(4): 815–826, DOI: 10.1515/amcs-2017-0057.

[2] Adamic, L.A. and Huberman, B.A. (2000). Power-law distribution of the world wide web, Science 287(5461): 2115–2115.

[3] Agrawal, A., Klein, P. and Ravi, R. (1995). When trees collide: An approximation algorithm for the generalized Steiner problem on networks, SIAM Journal on Computing 24(3): 440–456.

[4] Alon, U. (2007). An Introduction to Systems Biology: Design Principles of Biological Circuits, Chapman Hall/CRC, Boca Raton, FL.

[5] Amaral, L.A.N., Scala, A., Barthélémy, M. and Stanley, H.E. (2000). Classes of small-world networks, Proceedings of the National Academy of Sciences 97(21): 11149–11152.

[6] Andrade, D.V., Resende, M.G. and Werneck, R.F. (2012). Fast local search for the maximum independent set problem, Journal of Heuristics 18(4): 525–547.

[7] Back, T. and Khuri, S. (1994). An evolutionary heuristic for the maximum independent set problem, IEEE World Congress on Computational Intelligence, Orlando, FL, USA, pp. 531–535.

[8] Baran, M. (2018). Closest paths in graph drawings under an elastic metric, International Journal of Applied Mathematics and Computer Science 28(2): 387–397, DOI: 10.2478/amcs-2018-0029.

[9] Eiben, A.E. and Smith, J.E. (2015). Introduction to Evolutionary Computing, Natural Computing Series, 2nd Edn, Springer-Verlag, Berlin/Heidelberg.

[10] Feitelson, D.G. (1996). Packing schemes for gang scheduling, in D. G. Feitelson and L. Rudolph (Eds), Workshop on Job Scheduling Strategies for Parallel Processing, Springer, Berlin/Heidelberg, pp. 89–110.

[11] Flores-Lamas, A., Fernández-Zepeda, J.A. and Trejo-Sánchez, J.A. (2018). Algorithm to find a maximum 2-packing set in a cactus, Theoretical Computer Science 725: 31–51.

[12] Fortin, F.-A., De Rainville, F.-M., Gardner, M.-A., Parizeau, M. and Gagné, C. (2012). DEAP: Evolutionary algorithms made easy, Journal of Machine Learning Research 13(7): 2171–2175.

[13] Gairing, M., Geist, R.M., Hedetniemi, S.T. and Kristiansen, P. (2004a). A self-stabilizing algorithm for maximal 2-packing, Nordic Journal of Computing 11(1): 1–11.

[14] Gairing, M., Goddard, W., Hedetniemi, S.T., Kristiansen, P. and McRae, A.A. (2004b). Distance-two information in self-stabilizing algorithms, Parallel Processing Letters 14(03n04): 387–398.

[15] Garey, M.R. and Johnson, D.S. (2002). Computers and Intractability, Vol. 29, WH Freeman New York, NY.

[16] Gregor, D. and Lumsdaine, A. (2005). The parallel BGL: A generic library for distributed graph computations, Parallel Object-Oriented Scientific Computing (POOSC), Glasgow, UK, pp. 1–18.

[17] Hale, W.K. (1980). Frequency assignment: Theory and applications, Proceedings of the IEEE 68(12): 1497–1514.

[18] Hochbaum, D.S. and Shmoys, D.B. (1985). A best possible heuristic for the k-center problem, Mathematics of Operations Research 10(2): 180–184.

[19] Holland, J.H. (1975). Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, MI.

[20] Karp, R.M. (1972). Reducibility among combinatorial problems, in R.E. Miller et al. (Eds), Complexity of Computer Computations, Springer, Boston, MA, pp. 85–103.

[21] Knudsen, M. and Wiuf, C. (2008). A Markov chain approach to randomly grown graphs, Journal of Applied Mathematics 2008: 1–14.

[22] Lamm, S., Sanders, P., Schulz, C., Strash, D. and Werneck, R.F. (2017). Finding near-optimal independent sets at scale, Journal of Heuristics 23(4): 207–229.

[23] Manne, F. and Mjelde, M. (2006). A memory efficient self-stabilizing algorithm for maximal k-packing, in A.K. Datta and M. Gradinariu (Eds), Symposium on Self-Stabilizing Systems, Springer, Berlin/Heidelberg, pp. 428–439.

[24] Mjelde, M. (2004). k-Packing and k-Domination on Tree Graphs, Master’s thesis, University of Bergen, Bergen.

[25] Newman, M.E.J. (2002). Handbook of Graphs and Networks, Wiley-VCH Verlag GmbH Co. KGaA, Weinheim, DOI: 10.1002/3527602755.

[26] Nogueira, B., Pinheiro, R.G. and Subramanian, A. (2018). A hybrid iterated local search heuristic for the maximum weight independent set problem, Optimization Letters 12(3): 567–583.

[27] Shi, Z. (2012). A self-stabilizing algorithm to maximal 2-packing with improved complexity, Information Processing Letters 112(13): 525–531.

[28] Soto, J.G., Leanos, J., Ríos-Castro, L. and Rivera, L. (2018). The packing number of the double vertex graph of the path graph, Discrete Applied Mathematics 247: 327–340.

[29] Trejo-Sánchez, J. A., Vela-Navarro, A., Flores-Lamas, A., López-Martínez, J.L., Bermejo-Sabbagh, C., Cuevas-Cuevas, N.L. and Toral-Cruz, H. (2018). Fast random cactus graph generation, in M. Torres et al. (Eds), International Conference on Supercomputing in Mexico, Springer, Cham, pp. 129–136.

[30] Trejo-Sánchez, J.A. and Fernández-Zepeda, J.A. (2012). A self-stabilizing algorithm for the maximal 2-packing in a cactus graph, 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops PhD Forum (IPDPSW), Shanghai, China, pp. 863–871.

[31] Trejo-Sánchez, J.A. and Fernández-Zepeda, J.A. (2014). Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs, Journal of Parallel and Distributed Computing 74(3): 2193–2202.

[32] Trejo-Sánchez, J.A., Fernández-Zepeda, J.A. and Ramírez-Pacheco, J.C. (2017). A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler, International Journal of Foundations of Computer Science 28(08): 1021–1045.

[33] Turau, V. (2012). Efficient transformation of distance-2 self-stabilizing algorithms, Journal of Parallel and Distributed Computing 72(4): 603–612.