  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. By showing that this problem is NP-hard in general, we
answer an open question stated by Shi et al. We prove that BMST remains hard
even in the special case where the follower only controls a matching. Moreover,
by a polynomial reduction from the vertex-disjoint Steiner trees problem, 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 polynomial-time $(n-1)$-approximation
algorithm for BMST, where $n$ is the number of vertices in the input graph.
Moreover, considering the number of edges controlled by the follower as
parameter, 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.
