  In this paper, we take an in-depth look at the complexity of a hitherto
unexplored Multiobjective Spanner (MSp) problem. The MSp is a multiobjective
generalization of the well-studied Minimum t-Spanner problem. This
multiobjective approach allows us to find solutions that offer a viable
compromise between cost and utility. Thus, the MSp can be a powerful modeling
tool when it comes to the planning of, e.g., infrastructure. We show that for
degree-3 bounded outerplanar instances the MSp is intractable and computing the
non-dominated set is BUCO-hard. Additionally, we prove that if P != NP, neither
the non-dominated set nor the set of extreme points can be computed in
output-polynomial time, for instances with unit costs and arbitrary graphs.
Furthermore, we consider the directed versions of the cases above.
