Authors: Buchheim, Christoph
Henke, Dorothee
Hommelsheim, Felix
Title: On the complexity of the bilevel minimum spanning tree problem
Language (ISO): en
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.
Subject Headings: Approximation algorithms
Bilevel optimization
Combinatorial optimization
Spanning tree problem
Steiner tree
Issue Date: 2022-06-08
Rights link:
Appears in Collections:Lehrstuhl V Diskrete Optimierung

This item is protected by original copyright

This item is licensed under a Creative Commons License Creative Commons