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

Abstract In this paper, we address the problem of finding a maximum 2-packing set in a cactus. Let G = ( V G , E G ) be an undirected connected graph; then a subset S ⊆ V G 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 ( n 2 ) , where n = | V G | .