Algorithm to find a maximum 2-packing set in a cactus

In this paper, we address the problem of finding a maximum 2-packing set in a cactus. Let G=(VG,EG) be an undirected connected graph; then a subset S⊆VG is a 2-packing set if for every pair of vertices u,v∈S, the shortest path between them is at least three edges long. This type of sets results in a wide range of applications such as the study of molecules, network modeling, allocation of facilities, and frequency assignment. The cactus is a planar graph such that any edge belongs to at most one cycle. Hitherto, to the best of the authors' knowledge, no algorithm finds a maximum 2-packing set in a cactus. This problem is NP-Hard in arbitrary graphs. Our approach to solving this problem was first finding a maximum 2-packing set in a unicyclic graph. Then, we adapted this algorithm to run in a cactus. The time complexity of the resulting algorithm is O(n2), where n=|VG|.