A Path-Relinking-based Heuristic for the Multiobjective Subgraph Problem
Daniela Scherer dos Santos, Kathrin Klamroth, Pedro Martins, Luís Paquete · Proceedings of the Genetic and Evolutionary Computation Conference · 2025
Given a simple undirected graph G, the Multiobjective Subgraph (MOS) problem aims to find a subgraph in G that maximizes the number of edges while minimizing the number of vertices. Addressing the MOS problem allows to solve the related Multiobjective Quasi-clique problem, which seeks a quasi-clique with maximum density and number of vertices and has many real-life applications. These problems have only been addressed using exact methods, which can be computationally intensive due to their NP-hard nature. In this paper, we introduce a heuristic method for solving the MOS problem. We show that a subset of optimal MOS subgraphs exhibits a nestedness property, meaning they satisfy an inclusion-wise relation. We explore this property to develop a path-relinking-based heuristic, where subgraphs from this subset serve as starting and ending points of a path to find new high-quality subgraphs. Additionally, we derive an upper bound on the number of edges for MOS subgraphs, which is used to evaluate the quality of the subgraphs generated by our heuristic. Experimental results on synthetic and real-life sparse graphs indicate that our heuristic produces high-quality subgraphs, with an average error of 2.3 edges compared to the exact method, while spending only 6.2% of its runtime.