APROXIMATION ALGORITHM BASED ON MULTI-START METHOD TO SOLVE THE MINIMUM S-CLUB COVER

Abstract

Covering graph is one of the classical topics in theoretical research in computer science. For research on the vertex cover of graphs, the
s-club model is widely used in social network analysis, protein interaction analysis, etc., where the Minimum s-club cover problem has recently received attention. Although there is an approximate algorithm to solve the Minimum s-club cover problem, this algorithm can only be applied to the case s = 2. In addition, the previous algorithm uses a greedy strategy, so the quality of the obtained solution is not good and depends on the input graph. Therefore, this study proposes an approximate algorithm based on multi-start method to solve the Minimum s-club cover problem. To improve the quality of the received solutions, this study also proposes a greedy strategy to find the best club at each step, as well as a method for creating and evaluating neighbors of the current solution. The effectiveness of the proposed algorithm is demonstrated through comparison with a previously published approximation algorithm on two different data sets from the DIMACS library. Experimental results show that the proposed algorithm finds better solutions in one-third of the tested cases, and the two algorithms are equal in two-thirds of the tested cases.