On the complexity of the bilevel minimum spanning tree problem

Abstract

We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. We show that this problem is NP-hard, even in the special case where the follower only controls a matching. Moreover, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a (|V|-1)-approximation algorithm for BMST, where |V| is the number of vertices. Moreover, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed-parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.