# online read us now

Paper details

Number 1 - March 2020

Volume 30 - 2020

**A genetic algorithm for the maximum 2-packing set problem**

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

**Abstract**

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.

**Keywords**

maximum 2-packing set, genetic algorithms, graph algorithms