Metaheuristics for finding threshold graphs with maximum spectral radius

Luka Radanović, Abdelkadir Fellague, Dragutin Ostojić, Dragan Stevanović, Tatjana Davidović

Published 2024-06-27Version 1

We consider the problem of characterizing graphs with the maximum spectral radius among the connected graphs with given numbers of vertices and edges. It is well-known that the candidates for extremal graphs are threshold graphs, but only a few partial theoretical results have been obtained so far. Therefore, we approach to this problem from a novel perspective that involves incomplete enumeration of different threshold graphs with a given characteristic. Our methodology defines the considered problem as an optimization task and utilizes two metaheuristic methods, Variable Neighborhood Search (VNS), which relies on iterative improvements of a single current best solution and Bee Colony Optimization (BCO), a population-based metaheuristic from the Swarm Intelligence (SI) class. We use compact solution representation and several auxiliary data structures that should enable efficient search of the solution space. In addition, we define several types of transformations that preserve the feasibility of the resulting solution. The proposed methods are compared on the graphs with a moderate number of vertices. Preliminary results are in favor of the VNS approach, however, we believe that both methods could be improved.