The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation

Abstract

Bi-level optimisation problems have gained increasing inter- est in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolu- tionary algorithms for bi-level optimisation problems. We examine the NP-hard generalised minimum spanning tree problem and analyse the two approaches presented by Hu and Raidl [7] in the context of parameterised complexity (with respect to the number of clusters) that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure rep- resentation enables to solve the problem in fixed-parameter time. Furthermore, we present hard instances for each ap- proach and show that the two approaches are highly com- plementary by proving that they solve each other’s hard in- stances very efficiently.