Local and variable neighborhood search for the k-cardinality subgraph problem

Abstract

The minimum weighted k-cardinality subgraph problem consists of finding a connected subgraph of a given graph with exactly k edges whose sum of weights is minimum. For this NP-hard combinatorial problem, only constructive types of heuristics have been suggested in the literature. In this paper we propose a new heuristic based on variable neighborhood search metaheuristic rules. This procedure uses a new local search developed by us. Extensive numerical results that include graphs with up to 5,000 vertices are reported. It appears that VNS outperforms all previous methods.