11institutetext: Universität Osnabrück, Osnabrück Niedersachen 49074, Germany
11email: {fboekler<EMAIL_ADDRESS>
# Complexity of the Multiobjective Spanner Problem

Fritz Bökler  0000-0002-7950-6965 Henning Jasper  0000-0002-9821-8600

# Complexity of the Multiobjective Spanner Problem

Fritz Bökler  0000-0002-7950-6965 Henning Jasper  0000-0002-9821-8600

###### Abstract

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
$\mathbf{P}\neq\mathbf{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.

###### Keywords:

Multiobjective Optimization Graph Spanners Output-Sensitive Complexity Extreme
Points Parametric Optimization

##  1 Introduction

The _Multiobjective Spanner (MSp)_ problem is a multiobjective generalization
of the _Minimum t-Spanner_ problem. Given a connected, simple graph $G=(V,E)$
where every edge has a cost and length of $1$, a subset of edges $S$ is a _t-
spanner_ of $G$ if for every pair of vertices $u,v\in V$,
$\frac{d^{S}(u,v)}{d^{E}(u,v)}\leq t$ holds, with $d^{S}(u,v)$ being the
distance from $u$ to $v$ in $S$ and $d^{E}(u,v)$ their respective distance in
$E$ [29]. For a given graph, the problem of finding the cheapest t-Spanner,
with regard to the sum over all edge-costs, is commonly known as the Minimum
t-Spanner problem. We refer to $t$ as the _stretch factor_. The MSp
generalizes the Minimum t-Spanner problem by introducing two edge-weight
functions, allowing us to assign each edge a cost independent of its length.
Furthermore, in contrast to the Minimum t-Spanner problem, the goal of the MSp
is not to find a minimum weight spanner for a given stretch factor. Instead,
the stretch factor is another objective we aim to minimize. The stretch factor
is an interesting objective function in itself that is to be minimized in,
e.g., the _Minimum Max-Stretch Spanning Tree (MMST)_ problem [12]. Feasible
solutions for the MSp are defined less restrictive than t-Spanners. We define
a _spanner_ of a connected, undirected graph $G=(V,E)$, as a subset of edges
$S\subseteq E$, such that $G^{\prime}=(V,S)$ is a connected subgraph. Since
the MSp is a _Multiobjective Combinatorial Optimization (MOCO)_ problem,
solutions are mapped to a _value vector_ instead of a single value. Due to
conflicts among objectives, there does not necessarily exist a solution that
achieves the best value in all objective functions simultaneously. Instead, we
look for value vectors for which there are no other value vectors that
dominate them. This set of value vectors is called _non-dominated set_ (or
Pareto-front) $\mathcal{Y}_{N}$.

######  Definition 1 (Multiobjective Spanner (MSp) Problem)

The input is a connected, undirected graph $G=(V,E)$ and edge-weight functions
$c_{1}\colon E\rightarrow\mathbb{Z}$ and $c_{2}\colon
E\rightarrow\mathbb{N}_{+}$. Feasible solutions are spanners $S$ of $G$ and
are assessed based on the two objective functions

$f_{1}(S)=\sum_{e\in S}c_{1}(e)\text{ and }f_{2}(S)=\max_{u,v\in
V}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)},$

with $d^{S}_{c_{2}}(u,v)$ and $d^{E}_{c_{2}}(u,v)$ being the length of the
shortest u-v-path in $S$ and $E$ respectively, regarding the $c_{2}$-length.
We consider an instance of the MSp to be solved if we output its non-dominated
set $\mathcal{Y}_{N}$.

A possible field of application for the MSp is the planning of emergency
infrastructure. Natural disasters require a significant logistical effort to
provide relief to victims and to distribute equipment and humanitarian goods.
The efficient design of emergency infrastructure therefore forms the basis for
initial responses, as well as for long-term measures taken to stabilise
affected communities. Many optimization models used in emergency logistics
only focus on either cost-effectiveness or responsiveness [15, 9, 28], as
multiobjective approaches are considered too computationally expensive to
solve. A recent literature review by Caunhye et al. [14] concluded, that these
singleobjective models may hamper relief services by causing an oversupply of
resources leading to difficulty with coordination, greater traffic, and
complex scheduling. Therefore, the MSp could help to address this shortcoming.

The concept of t-Spanners and their related problems were first introduced by
Peleg, Schäffer and Ullman in the context of synchronization in distributed
systems and communication networks [29, 30] and have since been explored in a
variety of publications. A greedy algorithm with one of the best cost-
guarantees was developed by Althöfer [1]. For a graph $G$ and a stretch factor
of $t=2k-1(k\in\mathbb{N}_{\geq 1})$, it creates a t-Spanner $S$ of $G$
containing $\mathcal{O}(n^{1+1/k})$ edges in $\mathcal{O}(m(n^{1+1/k}+n\log
n))$. This algorithm can even be applied to the _Weighted Minimum t-Spanner_
problem, where every edge is assigned an arbitrary positive cost. Then the
algorithm additionally guarantees that $S$ has a cost of at most
$\mathcal{O}(n/k)$ times the cost of the minimum spanning tree of $G$. For
undirected Minimum 2-Spanners, Kortsarz and Peleg [26] published a
$\mathcal{O}(\log(m/n))$-approximation with a theoretical running time of
$\mathcal{O}(m^{2}n^{2}\log(n^{2}/m))$. Baswana and Sen [3] give a method
that, for a weighted, undirected graph, computes a $t=2k-1$ spanner $S$ that
contains at most $\mathcal{O}(kn^{1+1/k})$ edges in an expected running time
of $\mathcal{O}(km)$, but with no cost guarantee. For unweighted graphs the
size of $S$ is bounded by $\mathcal{O}(n^{1+1/k}+kn)$. Cai and Keil [13]
focused on the complexity of the Minimum t-Spanner problem for degree bounded
graphs and showed, among others, that if the maximum degree of the graph is at
most $4$, the Minimum 2-Spanner problem can be solved in linear time, whereas
the problem is NP-hard even if the maximum degree is at most $9$. A recent
paper by Kobayashi [25] focuses on the complexity of the Minimum t-Spanner
problem in planar graphs and, as a byproduct, improves the degree bounds for
NP-hardness found by Cai and Keil.

As many decisions require the consideration of multiple goals and conflicting
demands, MOCO problems are an important modelling tool in a variety of fields.
Practical applications include routing problems in public transport [16, 32],
the planning of radiotherapy [21, 31, 20] and the determination of control
strategies for vaccine administration in COVID-19 pandemic treatment [27]. In
the multiobjective context, a problem is called _intractable_ , if there is no
algorithm capable of solving it in polynomial time [18]. Due to the
exponential size of their non-dominated sets, many interesting MOCO problems
are intractable, e.g., multiobjective variants of the Traveling Salesperson
[19], Shortest Path [23] or Spanning Tree [22] problem. Therefore, it makes
sense to consider a complexity class that distinguishes between problems that
cannot be solved in polynomial time due to the size of their output and the
ones that are genuinely hard to solve. Moreover, in experimental studies, the
non-dominated sets are much smaller (e.g., [4]). There is also a theoretical
reason for this behavior: In a smoothed analysis setting, Brunsch and Röglin
showed that the size of the non-dominated set is at most polynomial in the
input size for each fixed number of objectives [10]. We say a MOCO problem $O$
is solvable in _output-polynomial time_ if there is an algorithm that, for any
given instance $I$ of $O$ outputs every $y\in\mathcal{Y}_{N}$ exactly once, in
polynomial time depending on the size of the input $I$ and the output
$\mathcal{Y}_{N}$ [24]. Such an algorithm is called _output-polynomial_. We
denote the class of problems for which an output-polynomial algorithm exists
as OP.

An interesting subset of the non-dominated set is the set of extreme points
$\mathcal{Y}_{X}$. Since making decisions based on a potentially exponentially
sized non-dominated set is generally not practical, many MOCO problems are
approached by combining all the objective functions into one singleobjective
scalar (or preference) function. One method to accomplish this is called
_weighted sum scalarization (WSS)_ , where each objective function is weighted
according to its importance. Note that in general not all non-dominated points
can be found in this way. The extreme points of a MOCO problem instance are
exactly the points that can be the solution to any WSS of the instance.
Therefore, if every decision maker has a linear preference function, computing
the extreme points suffices. Note, however, determining weights accurately
reflecting the preferences of the deciders is not trivial. As every extreme
point is non-dominated, while not every non-dominated value vector is an
extreme point, solving the MSp could be hard, while the problem of only
computing the set of extreme points could be in OP. This is the case for,
e.g., _Multiobjective Shortest Path_ [8, 6]. For more information on MOCOs and
related topics cf. the book by M. Ehrgott [18].

###  1.0.1 Contribution and Organisation.

In the remainder of this paper, we first give some definitions and establish
basic concepts and results in Section 2. In Section 3, we study the classic
tractability of MSp.

###### Theorem 1.1

MSp is intractable even on degree-3 bounded outerplanar graphs.

This is an interesting result, as there are non-trivial stretch factors for
which the Minimum t-Spanner problem is solvable in linear time, under such
restrictions. In Section 4, we first consider the output-sensitive complexity
of computing the non-dominated set for unweighted instances of the MSp, where
each edge has a cost and length of $1$.

###### Theorem 1.2

If P $\neq$ NP, then MSp $\notin$ OP, even for unweighted instances.

Afterwards, we consider the _BUCO_ problem that can be interpreted as an
unrestricted version of the Knapsack problem and discuss the output-sensitive
complexity of computing the non-dominated set for degree bounded outerplanar
instances of the MSp. While BUCO appears to be a straight forward problem, it
is currently unknown whether it can be solved in output-polynomial time [7].
However, it has been shown that there are other problems of unknown output-
sensitive complexity that the BUCO problem can be reduced to. This motivated
the introduction of the complexity-class of BUCO-hard problems [5].

###### Theorem 1.3

MSp is BUCO-hard even on degree-3 bounded outerplanar graphs.

Moreover, this theorem implies that if there is a polynomial time algorithm
for the minimum $t$-spanner problem on degree-3 bounded outerplaner graphs
where $t>1$ is part of the input then BUCO can be solved in output polynomial
time.

As Theorem 1.2 states that we cannot compute the entire non-dominated set of
unweighted MSp instances in output-polynomial time, in Section 5 we define the
problem of computing the set of extreme points for instances of the MSp
(MSpYEx) and show its hardness with regard to output-sensitive complexity.

###### Theorem 1.4

If P $\neq$ NP, then MSpYEx $\notin$ OP, even for unweighted instances.

Finally, Section 6 has concluding remarks. More details can be found in the
appendix. Note that we also define a directed version of the MSp (diMSp), for
which the same results are proven. The only exemption being Theorem 1.3. The
diMSp is BUCO-hard, even for degree-4 bounded outerplanar instances.

##  2 Preliminaries

We denote $\mathbb{N}=\\{0,1,2,...\\}$,
$\mathbb{N}_{+}\coloneqq\mathbb{N}\setminus\\{0\\}$ and non-negative real
numbers as $\mathbb{R}_{\geq}$. For $n\in\mathbb{N}$, we denote the set
$\\{1,...,n\\}$ as $[n]$. For a graph $G=(V,E)$, an edge $\\{u,v\\}\subseteq
E$ and an edge-weight function $c_{i}\colon E\rightarrow\mathbb{Z}$, $i\in[2]$
we abbreviate $c_{i}(\\{u,v\\})$ by $c_{i}(u,v)$. Furthermore, for a set of
edges $S\subseteq E$, we denote $c_{i}(S)=\sum_{e\in S}c_{i}(e)$. In order to
simplify the input of the (di)MSp, we sometimes combine the edge-weight
functions $c_{1}$ and $c_{2}$ into one function $c\colon
E\rightarrow\mathbb{Z}\times\mathbb{N}_{+}$ with
$c(e)=(c_{1}(e),c_{2}(e))^{\mathsf{T}}$. Similarly, for an instance of the
(di)MSp and a feasible (directed) spanner $S$, we combine the two objective
functions $f_{1}(S)$ and $f_{2}(S)$ into one single function
$f(S)=(f_{1}(S),f_{2}(S))^{\mathsf{T}}$ that directly maps $S$ to its value
vector. We sometimes refer to $c\colon E\rightarrow\\{(1,1)^{\mathsf{T}}\\}$
with $c(e)=(c_{1}(e),c_{2}(e))^{\mathsf{T}}=(1,1)^{\mathsf{T}}$ for all $e\in
E$ as the _trivial edge-weight function_ and call instances of the MSp with
these edge-weight functions _unweighted_.

The degree of a vertex in an undirected graph is the number of vertices it is
adjacent to. The degree of a vertex in a directed graph is the number of its
in- and out-going edges. For $\delta\in\mathbb{N}$, we call any graph
$G=(V,E)$ _degree- $\delta$ bounded_ if for all $v\in V$ their degree is less
than or equal to $\delta$. We call graphs _outerplanar_ if they have a
drawing, in which every vertex lies on the boundary of the outer face. We call
undirected graphs _connected_ if they are non-empty and any two of their
vertices are linked by a path. A directed graph is called _weakly connected_
if replacing all of its arcs with undirected edges results in a connected
(undirected) graph. See also [17, 2]. For an instance of a MOCO problem with
an objective function $f$, we denote the set of all its value vectors as
$\mathcal{Y}$. For unequal value vectors $y,y^{\prime}\in\mathcal{Y}$, we say
$y$ is dominated by $y^{\prime}$ if $y^{\prime}$ is component wise less than
or equal to $y$. Analogously, for feasible solutions $S,S^{\prime}$ we say $S$
is dominated by $S^{\prime}$ if $f(S)$ is dominated by $f(S^{\prime})$. If a
value vector is not dominated by any value vector, the associated solution is
called _Pareto-optimal_.

For a weakly connected, directed graph $G=(V,A)$, we call a subset of arcs
$S\subseteq A$ a _directed spanner_ of $G$, if $G^{\prime}=(V,S)$ is a
subgraph such that, for every pair of vertices $u,v\in V$, if there is a
directed u-v-path in $E$, there is one in $S$ as well.

Note, that the definition of a (directed) spanner does not require the
resulting subgraph to be acyclic. Analogously to the MSp, we define the
_Directed Multiobjective Spanner (diMSp)_ problem. The only differences being
that the input is a weakly connected, directed graph, solutions are now
directed spanners and that in the second objective function, we only consider
pairs of vertices that are connected in the initial graph. This guarantees the
well-definedness of the objective function values.

###### Lemma 1

For a set of (di)MSp instances $\mathcal{I}$, if there is a polynomial
$p\colon\mathbb{N}\rightarrow\mathbb{N}$, such that for every instance
$I\in\mathcal{I}$ and its set of solutions
$\mathcal{S}\colon|f_{i}(\mathcal{S})|\leq p(|I|)$ for $i=1$ or $i=2$, then
$|\mathcal{Y}_{N}|\leq p(|I|)$.

###### Proof

Without loss of generality, we can assume that $f_{1}$ only has polynomially
many different values in its image. For every $a\in f_{1}(\mathcal{S})$, there
is one $s^{\prime}\in S$ with $f_{1}(s^{\prime})=a$ and $f_{2}(s^{\prime})\leq
f_{2}(s)$ for all $s\in S$ with $f_{1}(s)=a$. Hence,
$(a,f_{2}(s^{\prime}))^{\mathsf{T}}$ dominates $(a,f_{2}(s))^{\mathsf{T}}$ for
all $s\in S$ with $f_{1}(s)=a$. Thus, for each $a\in f_{1}(\mathcal{S})$ there
is only one non-dominated value vector. ∎

###### Observation 1

It is clear that adding edges to a spanner never increases its stretch factor
and that therefore, for every non-dominated value vector $y\in\mathcal{Y}_{N}$
there is a spanner $S$ with $f(S)=y$ and $e\in S$ for all $e\in E$ with
$c_{1}(e)=0$.

We call the decision problem corresponding to the Minimum t-Spanner problem
t-SpannerDEC. For it, verifying the stretch factor $t$ of a spanner only
requires considering pairs of vertices that are connected in the underlying
graph [29]. In case of the MSp an analogous statement can be made.

###### Lemma 2

Let $I=(G=(V,E),c_{1},c_{2})$ be a MSp instance with a connected, undirected
graph $G$ and edge-weight functions $c_{1}$ and $c_{2}$. For any spanner $S$
of $G$, $f_{2}(S)=\max_{u,v\in
V}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}=\max_{\\{u,v\\}\in
E}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}$ holds.

###### Proof

Let $S$ be a spanner of $G$ and assume
$f_{2}(S)=\frac{d^{S}_{c_{2}}(r,z)}{d^{E}_{c_{2}}(r,z)}$ with $\\{r,z\\}\notin
E$. Let $\\{r=u_{0},u_{1}\\},\\{u_{1},u_{2}\\},...,\\{u_{m-1},u_{m}=z\\}$ be
the shortest r-z-path in $E$. Denote the set of pairs of vertices
$(u_{i},u_{i+1})$, $0\leq i\leq m-1$ as $U$. We get

$\displaystyle\frac{d^{S}_{c_{2}}(r,z)}{d^{E}_{c_{2}}(r,z)}$
$\displaystyle\leq\frac{\sum_{i=0}^{m-1}d^{S}_{c_{2}}(u_{i},u_{i+1})}{\sum_{i=0}^{m-1}d^{E}_{c_{2}}(u_{i},u_{i+1})}\leq\max_{(u_{i},u_{i+1})\in
U}\frac{d^{S}_{c_{2}}(u_{i},u_{i+1})}{d^{E}_{c_{2}}(u_{i},u_{i+1})}\cdot\frac{\sum_{i=0}^{m-1}d^{E}_{c_{2}}(u_{i},u_{i+1})}{\sum_{i=0}^{m-1}d^{E}_{c_{2}}(u_{i},u_{i+1})}$
$\displaystyle=\max_{(u_{i},u_{i+1})\in
U}\frac{d^{S}_{c_{2}}(u_{i},u_{i+1})}{d^{E}_{c_{2}}(u_{i},u_{i+1})}.\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leavevmode\nobreak\
\squareforqed$

It is clear that the same arguments hold for the directed case.

##  3 Intractability

We begin by proving that no algorithm is capable of solving the MSp in
polynomial time, even if we restrict the considered graphs to be both degree-3
bounded and outerplanar. We do this by showing that there is a family of
instances, complying to these restrictions, for which the size of the non-
dominated set $\mathcal{Y}_{N}$ is exponential in the size of the instance,
proving the intractability of the MSp.

Consider the following family of instances for $2\leq n\in\mathbb{N}$, of
connected, undirected graphs $G=(V,E)$ and edge-weight functions $c_{1}\colon
E\rightarrow\mathbb{Z}$ and $c_{2}\colon E\rightarrow\mathbb{N}_{+}$. For
every $i\in[n]$, we create vertices $v_{i},v_{i}^{\prime}$ and $w_{i}$, and
add edges $\\{v_{i},w_{i}\\}$ with weights $(2^{i},2^{i})^{\mathsf{T}}$, as
well as edges $\\{v_{i},v_{i}^{\prime}\\}$ and $\\{v_{i}^{\prime},w_{i}\\}$
with respective weights of $(0,2^{i})^{\mathsf{T}}$. Furthermore, we introduce
edges $\\{w_{i},v_{i+1}\\}$ with weights $(0,1)^{\mathsf{T}}$, for
$i\in[n-1]$. Finally, we define $v_{1}\coloneqq s$ and $w_{n}\coloneqq t$ and
add the edge $\\{s,t\\}$ with weights $(2^{n+1},1)^{\mathsf{T}}$. An example
of this construction can be seen in Figure 1. Note, that every so constructed
graph is degree-$3$ bounded and outerplanar.

Figure 1: The family of instances constructed for Theorem 1.1. Thick edges
hold weights $(0,1)^{\mathsf{T}}$.

Note that the graph $G$ contains at least $2^{n}$ spanners that do not contain
the edge $\\{s,t\\}$. With 1, we know that for every non-dominated value
vector $y$, there is a Pareto-optimal spanner $S$ of $G$ that contains every
$e\in E$ with $c_{1}(e)=0$, with $f(S)=y$. Define $X$ as the set of all
feasible spanners $S$ of $G$, that contain every $e\in E$ with $c_{1}(e)=0$
and do not contain the edge $\\{s,t\\}$. We now simplify the second objective
function $f_{2}(S)$, for every $S\in X$, using Lemma 2.

###### Lemma 3

For all spanners $S\in X$, $f_{2}(S)=\max_{u,v\in
V}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}=\frac{d^{S}_{c_{2}}(s,t)}{d^{E}_{c_{2}}(s,t)}$.

###### Proof

Let $S\in X$ be a spanner. With Lemma 2, we know that we only have to consider
pairs of vertices $u,v\in V$ with $\\{u,v\\}\in E$ and $\\{u,v\\}\notin S$ in
order to determine $f_{2}(S)$. We know that $\\{s,t\\}\notin S$ holds. Thus,

$\frac{d^{S}_{c_{2}}(s,t)}{d^{E}_{c_{2}}(s,t)}\geq\frac{\Bigl{(}\sum_{i=1}^{n}c_{2}(v_{i},w_{i})\Bigr{)}+\left(\sum_{i=1}^{n-1}c_{2}(w_{i},v_{i+1})\right)}{1}=2^{n+1}+n-3.$

The only other pairs of vertices $u,v\in V$ with $\\{u,v\\}\in E$ for which
$\\{u,v\\}\notin S$ might hold are $v_{i},w_{i}$, for every $i\in[n]$. We get

$\frac{d^{S}_{c_{2}}(v_{i},w_{i})}{d^{E}_{c_{2}}(v_{i},w_{i})}\leq\frac{c_{2}(v_{i},v_{i}^{\prime})+c_{2}(v_{i}^{\prime},w_{i})}{c_{2}(v_{i},w_{i})}=\frac{2\cdot
2^{i}}{2^{i}}=2<2^{n+1}+n-3\leq\frac{d^{S}_{c_{2}}(s,t)}{d^{E}_{c_{2}}(s,t)}.\qquad\squareforqed$

We now conduct a proof by contradiction to show that two different spanners
$S,S^{\prime}\in X$ do not dominate each other and do not have the same value
vector. An expanded proof can be found in Appendix 0.A.

###### Lemma 4

For all $S,S^{\prime}\in X$ with $S\neq S^{\prime}$, $S$ and $S^{\prime}$ do
not dominate each other and have different value vectors.

###### Proof

Let $S,S^{\prime}\in X$ be two different spanners and assume $S$ dominates
$S^{\prime}$. Therefore, either $f_{1}(S)<f_{1}(S^{\prime})$ or
$f_{1}(S)=f_{1}(S^{\prime})$ holds. We begin by considering the first case.
Let $j\in[n]$ be the greatest index at which the shortest s-t-paths in $S$ and
$S^{\prime}$ differ. Since $f_{1}(S)<f_{1}(S^{\prime})$ holds, $S$ must not
contain the edge $\\{v_{j},w_{j}\\}$ while $S^{\prime}$ has to contain it. Let
$P$ be the remaining path that is identical for $S$ and $S^{\prime}$. Thus,
with Lemma 3,

$\displaystyle f_{2}(S^{\prime})$
$\displaystyle\leq\left(\sum_{i=1}^{j-1}c_{2}(v_{i},v_{i}^{\prime})+c_{2}(v_{i}^{\prime},w_{i})+c_{2}(w_{i},v_{i+1})\right)+c_{2}(v_{j},w_{j})+c_{2}(P)$
$\displaystyle=\left(\sum_{i=1}^{j-1}2\cdot
2^{i}+1\right)+2^{j}+c_{2}(P)<\left(\sum_{i=1}^{j-1}2^{i}+1\right)+2^{j}+2^{j}+c_{2}(P)$
$\displaystyle=\left(\sum_{i=1}^{j-1}c_{2}(v_{i},w_{i})+c_{2}(w_{i},v_{i+1})\right)+c_{2}(v_{j},v_{j}^{\prime})+c_{2}(v_{j}^{\prime},w_{j})+c_{2}(P)$
$\displaystyle=f_{2}(S).$

This contradicts the assumed domination.

Let us now consider the second case, in which $f_{1}(S)=f_{1}(S^{\prime})$
holds. Then, in order for $S$ to dominate $S^{\prime}$,
$f_{2}(S)<f_{2}(S^{\prime})$ must hold as well. By design of the $c_{1}$-edge-
weights, we know that in order for $f_{1}(S)=f_{1}(S^{\prime})$ to hold, it is
true for every edge $\\{v_{i},w_{i}\\}\in E$ that $\\{v_{i},w_{i}\\}\in
S\Leftrightarrow\\{v_{i},w_{i}\\}\in S^{\prime}$. This claim can be verified
by considering that every edge $\\{v_{i},w_{i}\\}$ has a unique $c_{1}$-cost
that cannot be reproduced by any combination of edges $e\in
E\setminus\\{v_{i},w_{i}\\}$. Consequently, the shortest s-t-paths in $S$ and
$S^{\prime}$ are exactly the same and therefore $f_{2}(S)=f_{2}(S^{\prime})$
holds, which contradicts the assumed domination. ∎

Finally, consider that no $S\in X$ can be dominated by any $\widehat{S}\notin
X$. This is clearly the case, due to the high $c_{1}$-cost of the edge
$\\{s,t\\}$. Concluding, we have shown that the set $X$ contains $2^{n}$
spanners, all of which have different value vectors that are not dominated.
Thus, $|\mathcal{Y}_{N}|\geq|X|=2^{n}$ and, consequently, Theorem 1.1 hold.

Note that an analogous proof can be conducted for the diMSp. The only
difference to the undirected case lies in the construction of the family of
instances. We turn the family of MSp instances into a family of diMSp
instances. For every $i\in[n]$, we replace edges $\\{v_{i},w_{i}\\}$ with arcs
$(v_{i},w_{i})$, edges $\\{v_{i},v_{i}^{\prime}\\}$ with arcs
$(v_{i},v_{i}^{\prime})$, edges $\\{v_{i}^{\prime},w_{i}\\}$ with arcs
$(v_{i}^{\prime},w_{i})$. Additionally, we replace edges $\\{w_{i},v_{i+1}\\}$
with arcs $(w_{i},v_{i+1})$, for $i\in[n-1]$. Finally, we replace $\\{s,t\\}$
with $(s,t)$. Every arc holds the same edge-weights as the undirected edge it
replaced.

##  4 Non-Dominated Set

In this section, we first consider the output-sensitive complexity of
computing the non-dominated set of unweighted (di)MSp instances. Afterwards,
we prove that if the (di)MSp can be solved by an output-polynomial algorithm,
one can also solve the BUCO problem in output-polynomial time. Therefore,
proving that the (di)MSp is _BUCO -hard_.

###### Observation 2

As the trivial edge-weight function only allows linear many values in the
range of either of the two objective functions, with Lemma 1, we can infer
that the non-dominated set of unweighted MSp instances is only polynomially
sized.

This observation directly infers that the non-dominated set of the (di)MSp
cannot be computed in output-polynomial time, as this would enable us to solve
the (directed) t-SpannerDEC in polynomial time. Thus, Theorem 1.2 holds.

We now study the output-sensitive complexity of degree bounded outerplanar
instances. For a set of vectors $M$, $\min M$ refers to its non-dominated
subset.

######  Definition 2 (Biobjective Unconstrained Optimization (BUCO) Problem
[5])

The input are vectors $c^{1},c^{2}\in\mathbb{N}^{n}$. A feasible solution is
an element of $\\{0,1\\}^{n}$. The goal is to find the set of the non-
dominated vectors

$\mathcal{Y}_{N}=\min\left\\{\left(\begin{array}[]{c}-c^{1^{\mathsf{T}}}\\\
c^{2^{\mathsf{T}}}\end{array}\right)x\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ x\in\\{0,1\\}^{n}\right\\}.$

The BUCO problem can be interpreted as an unrestricted Knapsack problem.
Without loss of generality, we can assume $c_{i}^{1}>0$ for every $i\in[n]$,
since any item that does not contribute value is never part of a viable
solution. Similarly, we can assume $c_{i}^{2}>0$ for every $i\in[n]$.

We prove that the MSp is BUCO-hard by showing that if there is an output-
polynomial algorithm $\mathcal{A}$ for the MSp, we could use it to solve the
BUCO problem in output-polynomial time. We start by constructing an algorithm
that transforms any BUCO instance $I$ into a valid MSp instance $I^{\prime}$
in polynomial time. Subsequently, we show that the set of non-dominated value
vectors of the constructed MSp instance $I^{\prime}$, that can be found using
the algorithm $\mathcal{A}$, can be transformed into the set of non-dominated
value vectors of the BUCO instance $I$, using an output-polynomial filter-
algorithm.

Let $I$ be an instance of the BUCO problem given by
$c^{1},c^{2}\in\mathbb{N}^{n}_{+}$. We construct an instance $I^{\prime}$ of
the MSp with a connected, undirected graph $G$, and edge-weight functions
$c_{1}\colon E\rightarrow\mathbb{Z}$ and $c_{2}\colon
E\rightarrow\mathbb{N}_{+}$. Define the constants
$C^{1}\coloneqq\sum_{i=1}^{n}c_{i}^{1}$ and $M\coloneqq C^{1}+1$ and construct
the graph $G=(V,E)$ in the following way: Create vertices $v_{i}$, $w_{i}$ and
$v_{i}^{\prime}$ for $i\in[n]$ and connect them with edges $\\{v_{i},w_{i}\\}$
with weights $(0,c_{i}^{2}+2)^{\mathsf{T}}$, edges
$\\{v_{i},v_{i}^{\prime}\\}$ with weights $(0,1)^{\mathsf{T}}$ and edges
$\\{v_{i}^{\prime},w_{i}\\}$ with weights $(c_{i}^{1},1)^{\mathsf{T}}$.
Furthermore, we add edges $\\{w_{i},v_{i+1}\\}$ with weights
$(0,1)^{\mathsf{T}}$ for $i\in[n-1]$. Define $v_{1}\coloneqq s$ and
$w_{n}\coloneqq t$. Finally, we add the edge $\\{s,t\\}$ with weights
$(M,1)^{\mathsf{T}}$. An example of this construction can be seen in Figure 2.

Figure 2: Showing the reduction for Theorem 1.3. Thick edges hold weights
$(0,1)^{\mathsf{T}}$.

We observe that every so constructed instance is a valid MSp instance and that
all steps can be performed in polynomial time in the size of the instance $I$.
Clearly, the constructed graph $G$ is degree-3 bounded and outerplanar. In
order to show that the reduction is correct, we now have to prove that the
non-dominated set of the constructed MSp instance can be transformed into the
non-dominated set of the initial BUCO instance in output-polynomial time with
regard to the instance $I$.

Let $y$ be a value vector of a BUCO instance given by
$c^{1},c^{2}\in\mathbb{N}^{n}_{+}$ and let $x\in\\{0,1\\}^{n}$ be a solution
that is mapped to $y$ with
$y=(-c^{1^{\mathsf{T}}}x,c^{2^{\mathsf{T}}}x)^{\mathsf{T}}$. There is a
spanner $S_{x}$ of $G$ with the following properties: For every $i\in[n]$,
$S_{x}$ contains edges $\\{v_{i},w_{i}\\}$ and $\\{v_{i},v_{i}^{\prime}\\}$,
as well as edges $\\{w_{i},v_{i+1}\\}$, for all $i\in[n-1]$. In addition, if
$x_{i}=0$: $S_{x}$ contains the edge $\\{v_{i}^{\prime},w_{i}\\}$. We observe
that for every $x\in\\{0,1\\}^{n}$ the resulting set of edges $S_{x}$ is a
feasible spanner of $G$ and that none of these spanners contains the edge
$\\{s,t\\}$. Denote the set of all the spanners generated this way as $X$.

With 1, we know that for every non-dominated value vector $y$, there is a
Pareto-optimal spanner $S$ of $G$ that contains every $e\in E$ with
$c_{1}(e)=0$, with $f(S)=y$. Thus, clearly analogously to Lemma 3,
$f_{2}(S)=\max_{u,v\in
V}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}=\frac{d^{S}_{c_{2}}(s,t)}{d^{E}_{c_{2}}(s,t)}$
holds for every spanner $S\in X$. We denote the set of edges
$\\{w_{i},v_{i+1}\\}$ for $i\in[n-1]$ as $W$.

We now examine how the value vector $y$ of a BUCO solution $x\in\\{0,1\\}^{n}$
is connected to the value vector $f(S_{x})$ of the corresponding spanner
$S_{x}$.

###### Lemma 5

For any value vector
$y=(-c^{1^{\mathsf{T}}}x,c^{2^{\mathsf{T}}}x)^{\mathsf{T}}$ of a BUCO instance
and its associated solution $x\in\\{0,1\\}^{n}$, for the constructed
corresponding spanner $S_{x}\in X$, $f_{1}(S_{x})=C^{1}+y^{1}$ and
$f_{2}(S_{x})=y^{2}+3n-1$ hold.

###### Proof

Let $y=(-c^{1^{\mathsf{T}}}x,c^{2^{\mathsf{T}}}x)^{\mathsf{T}}$ be a value
vector of a BUCO instance and let $x\in\\{0,1\\}^{n}$ be its associated
solution. Let $S_{x}\in X$ be the spanner in the constructed MSp instance that
is based on $x$. Consider the two objective functions.

$\displaystyle f_{1}(S_{x})$
$\displaystyle=\left(\sum_{i=1}^{n}c_{1}(v_{i}^{\prime},w_{i})\cdot(1-x_{i})\right)=\left(\sum_{i=1}^{n}c_{i}^{1}\cdot(1-x_{i})\right)=C^{1}+\sum_{i=1}^{n}-c_{i}^{1}x_{i}$
$\displaystyle=C^{1}+y^{1}$ $\displaystyle f_{2}(S_{x})$
$\displaystyle=\left(\sum_{i=1}^{n}c_{2}(v_{i},w_{i})\cdot
x_{i}+(c_{2}(v_{i},v_{i}^{\prime})+c_{2}(v_{i}^{\prime},w_{i}))(1-x_{i})\right)+c_{2}(W)$
$\displaystyle=\left(\sum_{i=1}^{n}(c_{i}^{2}+2)x_{i}+(1+1)(1-x_{i})\right)+(n-1)\cdot
1$
$\displaystyle=\left(\sum_{i=1}^{n}c_{i}^{2}x_{i}+2\right)+n-1=y^{2}+3n-1\qquad\qquad\qquad\qquad\qquad\qquad\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \squareforqed$

Let us now consider the relationship between spanners $S_{x}\in X$ and
spanners $S$ with $\\{s,t\\}\in S$.

###### Lemma 6

If $x\in\\{0,1\\}^{n}$ is a Pareto-optimal solution for the BUCO instance, its
associated spanner $S_{x}$ is a Pareto-optimal solution for the constructed
MSp instance.

###### Proof

Let $x\in\\{0,1\\}^{n}$ be a Pareto-optimal solution for the BUCO instance and
let $y=(-c^{1^{\mathsf{T}}}x,c^{2^{\mathsf{T}}}x)^{\mathsf{T}}$ be the
corresponding value vector. Let $S_{x}\in X$ be the spanner generated
according to the algorithm defined above. Assume there is a feasible spanner
$\widehat{S}$ that dominates $S_{x}$. It is clear that due to the $c_{1}$-cost
of the edge $\\{s,t\\}$, if $\\{s,t\\}\in\widehat{S}$ holds, $\widehat{S}$
does not dominate $S_{x}$. Therefore, we can assume that
$\\{s,t\\}\notin\widehat{S}$ holds. Furthermore, with 1 and w.l.o.g., we can
assume that $\widehat{S}$ contains the edges $\\{v_{i},v_{i}^{\prime}\\}$,
$\\{v_{i},w_{i}\\}$ for all $i\in[n]$ and $\\{w_{i},v_{i+1}\\}$ for
$i\in[n-1]$. Based on these observations, we can say that $\widehat{S}$ meets
the specifications for a spanner that corresponds to a BUCO solution. Let us
denote this BUCO solution as $\widehat{x}$ and its value vector as
$\widehat{y}$. From now on we refer to $\widehat{S}$ as $S_{\widehat{x}}$. We
use Lemma 5 to show that if $S_{x}$ is dominated by $S_{\widehat{x}}$,
$\widehat{x}$ dominates $x$. Therefore, causing a contradiction. Assume
$S_{\widehat{x}}$ dominates $S_{x}$, then $f_{1}(S_{\widehat{x}})\leq
f_{1}(S_{x})$ and $f_{2}(S_{\widehat{x}})\leq f_{2}(S_{x})$ hold. We know that
for all spanners $S\in X$ based on a BUCO solution $x^{\prime}$ with value
vector $y_{x^{\prime}}$, $f_{1}(S)=C^{1}+y^{1}_{x^{\prime}}\text{ and
}f_{2}(S_{x})=y^{2}_{x^{\prime}}+3n-1$ hold. In the first objective function,
we therefore get:

$f_{1}(S_{\widehat{x}})\leq f_{1}(S_{x})\Leftrightarrow
C^{1}+\widehat{y}^{1}\leq C^{1}+y^{1}\Leftrightarrow\widehat{y}^{1}\leq
y^{1}.$

In the second objective function, we get:

$f_{2}(S_{\widehat{x}})\leq
f_{2}(S_{x})\Leftrightarrow\widehat{y}^{2}+3n-1\leq
y^{2}+3n-1\Leftrightarrow\widehat{y}^{2}\leq y^{2}.$

Therefore, either $\widehat{x}$ dominates $x$, which contradicts the
assumption that $x$ is Pareto-optimal or $\widehat{x}$ has the same evaluation
as $x$, but in that case $S_{\widehat{x}}$ and $S_{x}$ also have the same
evaluation. Hence, the value vector of $S_{\widehat{x}}$ does not dominate the
value vector of $S_{x}$. Therefore, $S_{x}$ is Pareto-optimal. ∎

In order to complete the verification of this reduction, we now prove that
there are only polynomially many non-dominated value vectors in the non-
dominated set of $I$ that are not based on a Pareto-optimal solution of the
BUCO instance. Consider that the only way a spanner $S$ can divert from the
form of a BUCO solution based spanner, without its value vector being
dominated, is by containing the edge $\\{s,t\\}$. Hence, combining Lemma 1
with the following Lemma proves the aforementioned claim.

###### Lemma 7

For every Pareto-optimal spanner $S$ with $\\{s,t\\}\in S$ and $l\in[n]$ being
the index of the BUCO item with the greatest $c_{2}$-weight for which
$\\{v_{l}^{\prime},w_{l}\\}\notin S$ holds,
$f_{2}(S)=\frac{d^{S}_{c_{2}}(v_{l}^{\prime},w_{l})}{d^{E}_{c_{2}}(v_{l}^{\prime},w_{l})}=d^{S}_{c_{2}}(v_{l}^{\prime},w_{l})$.

###### Proof

Let $S$ with $\\{s,t\\}\in S$ be a Pareto-optimal spanner and let $l\in[n]$ be
the index of the BUCO item with the greatest $c_{2}$-weight for which
$\\{v_{l}^{\prime},w_{l}\\}\notin S$ holds. With Lemma 2, and since
$\\{s,t\\}\in S$ and 1 hold, we know that in order to determine $f_{2}(S)$, we
only have to consider edges $\\{v_{i}^{\prime},w_{i}\\}$, for all $i\in[n]$.
Thus,

$\displaystyle f_{2}(S)=\max_{u,v\in
V}\frac{d^{S}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}=\max_{v_{i}^{\prime},w_{i}\in
V}\frac{d^{S}_{c_{2}}(v_{i}^{\prime},w_{i})}{d^{E}_{c_{2}}(v_{i}^{\prime},w_{i})}=\max_{v_{i}^{\prime},w_{i}\in
V}\frac{d^{S}_{c_{2}}(v_{i}^{\prime},w_{i})}{1}=d^{S}_{c_{2}}(v_{l}^{\prime},w_{l}).$

Note, that there is an additional edge-case, in which the spanner $S$ contains
every $e\in E$. Hence, there are only $n+1$ possible values in the range of
the second objective function if the considered spanner contains the edge
$\\{s,t\\}$. ∎

With Lemma 1, we infer there are only $n+1$ non-dominated value vectors, in
the non-dominated set of the constructed MSp instance, that do not correspond
to a Pareto-optimal BUCO solution. Finally, we describe the algorithm that
solves any BUCO instance in output-polynomial time, assuming that there is an
output-polynomial algorithm $\mathcal{A}$ capable of solving any MSp instance.

Let $I$ be a BUCO instance, and let $\mathcal{A}$ be an algorithm capable of
solving a MSp instance in output-polynomial time. We begin by using the
algorithm described above to transform $I$ into the corresponding MSp instance
$I^{\prime}$. Subsequently, we solve $I^{\prime}$ using the algorithm
$\mathcal{A}$ and receive the set of non-dominated value vectors
$\mathcal{Y}_{N}^{\text{MSp}}$. We know that for every Pareto-optimal solution
$x\in\\{0,1\\}^{n}$ of the BUCO instance, the constructed MSp instance
contains a corresponding Pareto-optimal spanner $S_{x}$. Therefore, we can
assume that for every such $x$,
$f(S_{x})=(f_{1}(S_{x}),f_{2}(S_{x}))^{\mathsf{T}}\in\mathcal{Y}_{N}^{\text{MSp}}$
holds. Now, we have to filter out all the non-dominated value vectors that do
not correspond to a feasible BUCO solution. We do this by inspecting the
$y^{1}$ value for each $y\in\mathcal{Y}_{N}^{\text{MSp}}$. If $y^{1}\geq M$
holds, then the spanner corresponding to $y$ contains the edge $\\{s,t\\}$ and
consequently is not based on a feasible BUCO solution. If $y^{1}\leq C^{1}<M$
holds, we transform $y$ according to Lemma 5, so that its values match the
ones of the corresponding BUCO solution. We construct
$\hat{y}=(y^{1}-C^{1},y^{2}-3n+1)$ and add it to the set of non-dominated
value vectors of the initial BUCO instance $\mathcal{Y}_{N}^{\text{BUCO}}$.
All of these steps are output-polynomial with regard to the BUCO instance $I$
and therefore, the existence of an output-polynomial algorithm for the MSp
directly implies the existence of an output-polynomial algorithm for the BUCO
problem. Thus, Theorem 1.3 holds.

An analogous reduction can be conducted for the diMSp, by replacing every
undirected edge with an arc. This transformation works similar to the one
conducted at the end of Section 3. Note that the diMSp instances require an
additional arc $(v_{i}^{\prime},v_{i})$ with edge-weights
$(0,1)^{\mathsf{T}}$, for every $i\in[n]$. These arcs ensure that the directed
spanners constructed during the reduction are feasible. Observe that the
resulting diMSp instances remain outerplanar but are only degree-4 bounded.

##  5 Extreme Points

In this section we define the problem of determining the set of extreme points
of a given (di)MSp instance and consider its output-sensitive complexity.

For all $y^{\prime}\in\mathcal{Y}$, define $W(y^{\prime})$ as the set of
vectors $\lambda\in\mathbb{R}^{d}_{\geq},\lambda\neq 0$, so that
$\min_{y\in\mathcal{Y}}\lambda^{\mathsf{T}}y=\lambda^{\mathsf{T}}y^{\prime}$.
A value vector $y^{\prime}\in\mathcal{Y}$ is called an _extreme point_ if
there is a $\lambda\in\mathbb{R}^{d}_{\geq},\lambda\neq 0$ with $\lambda\in
W(y^{\prime})$ and $\forall
y\in\mathcal{Y}_{N}\setminus\\{y^{\prime}\\}\colon\lambda\notin W(y)$ [18,
Definition 8.7]. For an instance of the (di)MSp, we define _(di)MSp YEx_ to be
the problem of computing its set of extreme points $\mathcal{Y}_{X}$.

We now show that if P $\neq$ NP, even the unweighted MSpYEx cannot be solved
in output-polynomial time. With Theorem 1.2, we know that we cannot compute
the entire non-dominated set of MSp instances in output-polynomial time.
However, this does not imply the output-sensitive complexity of computing
their set of extreme points.

We do this by conducting an indirect reduction of 3SAT. Consider Cai’s
reduction of 3SAT to t-SpannerDEC[11] for every $2\leq t\in\mathbb{N}$. We
turn Cai’s constructed 2-SpannerDEC instances into MSpYEx instances and show
that iff the initial 3SAT instance is a yes-instance, the yes-witness for the
2-SpannerDEC instance creates an extreme point in the corresponding MSpYEx
instance. In consideration of 2, any output-polynomial algorithm capable of
solving unweighted MSpYEx instances in output-polynomial time could solve 3SAT
in polynomial time. We begin with a quick summary of Cai’s proof for the
special case of $t=2$.

###  5.0.1 Revisiting Cai’s Proof.

Cai transforms 3SAT to 2-SpannerDEC. Given an instance $I=(U,C)$ of 3SAT
consisting of a set $U$ of $n$ distinct variables and a collection $C$ of $m$
3-element clauses over $U$. They construct a 2-SpannerDEC instance $\hat{I}$,
with a graph $G=(V,E)$ and a positive integer $K\in\mathbb{N}_{+}$, such that
$G$ contains a 2-spanner with at most $K$ edges if and only if $C$ is
satisfiable. They define a _2-path_ as a path with 2 edges. One can force an
edge to be in any minimum 2-spanner of a graph by the addition of two distinct
2-paths between the two ends of the edge [11, Lemma 3]. This operation is
called _forcing an edge_. Such an edge is called a _forced edge_ and the two
2-paths are called _forcing paths_.

They construct the _truth-setting component_ $T$ as follows: They take five
vertices $z$, the literal vertices $x$ and $\bar{x}$, and the y-type vertices
$y$ and $y^{\prime}$; and join $z$ to each of the remaining four vertices by
an edge. Finally, they add forced edges
$\\{x,\bar{x}\\},\\{x,y\\},\\{x,y^{\prime}\\},\\{\bar{x},y\\},\\{\bar{x},y^{\prime}\\}$.

They assign each variable $u_{i}\in U$, $i\in[n]$ a distinct copy $T_{i}$ of
$T$ and identify all vertices $z_{i}$ into a single vertex $z$ to form a
subgraph $T^{\prime}$ of $G$. To finish the construction of $G$, they create a
new vertex $v_{i}$ for each clause $c_{i}\in C$, $i\in[m]$, join it to vertex
$z$ with an edge and add a forced edge between $v_{i}$ and each of the three
literal vertices in $T^{\prime}$ corresponding to the three literals of
$c_{i}$.

They finish the construction of the 2-SpannerDEC instance, by setting
$K=16n+9m$. For the constructed graph $G$, it holds that any minimum 2-spanner
$S$ of $G$ contains at least $K$ edges. Furthermore, if $S$ contains exactly
$K$ edges, then for each $T_{i}$, $i\in[n]$ exactly one of the two literal
edges $\\{z,x_{i}\\}$ and $\\{z,\bar{x_{i}}\\}$ belongs in $S$ [11, Lemma 4].
Examples of the described constructions can be seen in Figures 3 and 4 in the
appendix.

Now, suppose that $C$ is satisfiable and let $\phi$ be a satisfying truth
assignment for $C$. They construct a yes-witness-spanner $S_{w}$ as follows:
put every forced edge in $S_{w}$. For each forcing path, put one of the two
edges in $S_{w}$. Finally, for each variable $u_{i}\in U$, if $u$ is “true”
under $\phi$ then put edge $\\{z,x_{i}\\}$, in $S_{w}$ else put edge
$\\{z,\bar{x_{i}}\\}$ in $S_{w}$. The complete proof that this is a correct
reduction goes beyond the scope of this paper and can be found in the original
paper [11]. Instead, let us now construct an equivalent MSpYEx instance and
prove that if the initial 2-SpannerDEC instance is a yes-instance, the value
vector of the yes-witness-spanner is an extreme point.

###  5.0.2 The Associated MSpYEx Instance.

First, let $I$ be a 3SAT instance and let $\hat{I}=(G=(V,E),K)$ be the
associated 2-SpannerDEC instance, constructed according to the algorithm
described in Cai’s proof. We turn $\hat{I}$ into an instance
$I^{\prime}=(G,c)$ of the unweighted MSpYEx by copying $G$ and adding the
trivial edge-weight function $c\colon E\rightarrow\\{(1,1)^{\mathsf{T}}\\}$,
$c(e)=(1,1)^{\mathsf{T}}$ for all $e\in E$. Clearly, this can be done in
polynomial time. Note, that $I^{\prime}$ is a valid, unweighted MSpYEx
instance. Now, let $\hat{I}$ be a yes-instance and let $S_{w}$ be the yes-
witness-spanner. It is clear that the same spanner exists in $I^{\prime}$ and
that

$f_{1}(S_{w})=\sum_{e\in S_{w}}c_{1}(e)=\sum_{e\in S_{w}}1=|S_{w}|=K\text{ and
}f_{2}(S_{w})=\max_{u,v\in
V}\frac{d^{S_{w}}_{c_{2}}(u,v)}{d^{E}_{c_{2}}(u,v)}=2$

hold. We now show that the value vector of the yes-witness-spanner $f(S_{w})$
is an extreme point by finding the non-dominated value vectors
$\mathcal{Y}_{N}$ and showing that there is a
$\lambda_{w}\in\mathbb{R}^{d}_{\geq},\lambda_{w}\neq 0$, so that
$\lambda_{w}\in W(f(S_{w}))\text{ and }\forall
y\in\mathcal{Y}_{N}\setminus\\{f(S_{w})\\}\colon\lambda_{w}\notin W(y)$ hold.

Note that $f(S_{w})$ dominates or is equal to every value vector
$y\in\mathcal{Y}$ with $y^{1}\geq K$ and $y^{2}\geq 2$. Let us first find the
non-dominated value vectors $y\in\mathcal{Y}_{N}$ with $y^{2}<2$. We begin by
constructing the spanner $S_{1}\subseteq E$ that contains the fewest edges for
which $f_{2}(S_{1})<f_{2}(S_{w})=2$ holds. Consider $S_{1}=E$ and observe that
if we remove any edge $e\in E$ from $S_{1}$, $f_{2}(S_{1}\setminus\\{e\\})=2$
holds. Hence, $S_{1}=E$ and we conclude that for every feasible spanner
$S\subseteq E$ with $K<f_{1}(S)<|E|$, $f(S_{w})$ dominates $f(S)$. Consider
the amount of edges in $G$. For every truth-setting component $T_{i}$,
$i\in[n]$ there are $20$ forcing edges, $5$ forced edges and $4$ edges
connecting to the vertex $z$. Furthermore, for each clause $c_{i}\in C$,
$i\in[m]$ there are $12$ forcing edges, $3$ forced edges and one edge
connecting to $z$. Hence,

$f_{1}(S_{1})=|E|=29n+16m\text{ and }f_{2}(S_{1})=1.$

We now construct a hypothetical value vector $y_{h}$ that either dominates or
is equal to every value vector $f(S)$ of feasible spanners $S$ with
$f_{1}(S)<K$. We begin by constructing $y^{1}_{h}$. Consider the number of
vertices in $G$. For every truth-setting component $T_{i}$, $i\in[n]$ there
are $10$ vertices that are part of forcing paths and $4$ vertices
$x_{i},\bar{x_{i}},y_{i},y_{i}^{\prime}$. Furthermore, for each clause
$c_{i}\in C$, $i\in[m]$ there is one vertex $v_{i}$ and $6$ vertices that are
part of forcing paths. Finally, there is the vertex $z$. Thus, there are
$14n+7m+1$ vertices in the $G$. Therefore, for every feasible spanner $S$ of
$G$, $f_{1}(S)=|S|\geq 14n+7m$. Hence, we set $y^{1}_{h}=14n+7m$. Let us now
focus on $y^{2}_{h}$. We know that there are no spanners $S$ that contain
fewer edges than $S_{w}$ for which $f_{2}(S)\leq 2$ hold. Hence, we set
$y^{2}_{h}=3$. Thus,

$y_{h}^{1}=14n+7m\text{ and }y_{h}^{2}=3.$

Clearly, for every value vector $f(S)$ of a feasible spanner $S$ with
$f_{1}(S)<K$, $y^{1}_{h}\leq f_{1}(S)$ and $y^{2}_{h}\leq f_{2}(S)$ hold.
Hence, $y_{h}$ either dominates or is equal to every such value vector and
thus, for every $\lambda\in\mathbb{R}^{d}_{\geq},\lambda\neq 0$,
$\lambda^{\mathsf{T}}y_{h}\leq\lambda^{\mathsf{T}}\cdot f(S)$ holds. An
expanded proof for the following Lemma can be found in Appendix 0.B.

###### Lemma 8

The value vector of the yes-witness-spanner is an extreme point.

###### Proof

Consider the vector
$\lambda_{w}=(2,15n+9m)^{\mathsf{T}}\in\mathbb{R}^{d}_{\geq},\lambda_{w}\neq
0$. We show that $\lambda_{w}\in W(f(S_{w}))$ holds and that for all
$y\in\mathcal{Y}_{N}\setminus\\{f(S_{w})\\}\colon\lambda_{w}\notin W(y)$.

$\displaystyle\lambda_{w}^{\mathsf{T}}\cdot
f(S_{1})=73n+41m=\lambda_{w}^{\mathsf{T}}y_{h}$
$\displaystyle\lambda_{w}^{\mathsf{T}}\cdot
f(S_{w})=62n+36m<73n+41m=\lambda_{w}^{\mathsf{T}}\cdot
f(S_{1})=\lambda_{w}^{\mathsf{T}}y_{h},$

for $n,m>0$. Hence, $\lambda_{w}\in W(f(S_{w}))$ and for all
$y\in\mathcal{Y}_{N}\setminus\\{f(S_{w})\\}\colon\lambda_{w}\notin W(y)$. ∎

A sketch of the relevant value vectors can be seen in Figure 5 in the
appendix.

Finally, let us consider the entire reduction. Suppose there is an algorithm
$\mathcal{A}$ capable of solving unweighted MSpYEx instances in output-
polynomial time. We know that iff the initial 3SAT instance $I$ is a yes-
instance, the 2-SpannerDEC instance $\hat{I}$ constructed according to Cai’s
proof is a yes-instance too. Therefore, the yes-witness-spanner $S_{w}$ exists
in $\hat{I}$ and thus, also in the associated MSpYEx instance $I^{\prime}$.
Since the value vector $f(S_{w})$ of $S_{w}$ is an extreme point, it is
therefore part of the output $\mathcal{Y}_{X}$ of algorithm $\mathcal{A}$,
when applied to $I^{\prime}$. In consideration of
$\mathcal{Y}_{X}\subseteq\mathcal{Y}_{N}$ and Lemma 1 we infer that solving
$I^{\prime}$ with $\mathcal{A}$ and checking whether
$f(S_{w})\in\mathcal{Y}_{X}$ holds is possible in polynomial time in the size
of $I$. In conclusion, if $\mathcal{A}$ existed, we could solve 3SAT in
polynomial time. Thus, Theorem 1.4 holds.

Similarly, based on Cai’s reduction of 3SAT to directed 2-SpannerDEC [11,
Section 3], we can show the same results for the diMSpYEx. The only difference
to the undirected case lies in the construction of the directed 2-SpannerDEC
instance by Cai. These differences in turn cause slightly different values in
the objective functions of the considered spanners in the diMSpYEx instance
that we construct analogously to the undirected case. It is easy to see that
these differences have no influence on the validity of the statement. Due to
the analogy of the proofs, we leave the details to the reader.

##  6 Conclusion

What remains open is the output-sensitive complexity of computing the set of
extreme points for degree-3 bounded outerplanar instances, as it is currently
unknown whether there is a stretch factor $t$, such that the t-SpannerDEC
problem is NP-hard under these restrictions. Thus, such a prove requires a
different approach than the one used in Section 5.

Future work might include the development of approximation techniques for the
MSp and related problems, as well as investigating what existing approaches
can be applied to them.

## References

  * [1] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph and José Soares  “On Sparse Spanners of Weighted Graphs”  In _Discrete & Computational Geometry_ 9.1 Springer, 1993, pp. 81–100
  * [2] Jørgen Bang-Jensen and Gregory Z. Gutin  “Digraphs: Theory, Algorithms and Applications”, Springer Monographs in Mathematics  Springer Science & Business Media, London, England, 2008
  * [3] Surender Baswana and Sandeep Sen  “A Simple and Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs”  In _Random Structures & Algorithms_ 30.4 Wiley Online Library, 2007, pp. 532–563
  * [4] F. Bökler and M. Chimani  “Approximating Multiobjective Shortest Path in Practice”  In _SIAM ALENEX_ , 2020, pp. 120–133
  * [5] Fritz Bökler  “Output-sensitive Complexity of Multiobjective Combinatorial Optimization with an Application to the Multiobjective Shortest Path Problem”, 2018
  * [6] Fritz Bökler, Matthias Ehrgott, Christopher Morris and Petra Mutzel  “Output-sensitive complexity of multiobjective combinatorial optimization”  In _Journal of Multi-Criteria Decision Analysis_ 24.1-2 Wiley Online Library, 2017, pp. 25–36
  * [7] Fritz Bökler, Matthias Ehrgott, José Rui Figueira, Andreia P. Guerreiro, Kathrin Klamroth, Britta Schulze and Daniel Vanderpooten  “The Output-sensitive Complexity of the BUCO Problem”  In _Scalability in Multiobjective Optimization_ 10.1 Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020, pp. 76–78  DOI: 10.4230/DagRep.10.1.52
  * [8] Fritz Bökler and Petra Mutzel  “Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems”  In _Algorithms - ESA 2015_ Springer, Berlin, Heidelberg, 2015, pp. 288–299
  * [9] Chawis Boonmee, Mikiharu Arimura and Takumi Asada  “Facility location optimization model for emergency humanitarian logistics”  In _International Journal of Disaster Risk Reduction_ 24 Elsevier, 2017, pp. 485–498
  * [10] Tobias Brunsch and Heiko Röglin  “Improved Smoothed Analysis of Multiobjective Optimization”  In _J. ACM_ 62.1, 2015, pp. 4:1–4:58
  * [11] Leizhen Cai  “NP-completeness of minimum spanner problems”  In _Discrete Applied Mathematics_ 48.2, 1994, pp. 187–194  DOI: https://doi.org/10.1016/0166-218X(94)90073-6
  * [12] Leizhen Cai and Derek G. Corneil  “Tree Spanners”  In _SIAM Journal on Discrete Mathematics_ 8.3, 1995, pp. 359–387  DOI: 10.1137/S0895480192237403
  * [13] Leizhen Cai and Mark Keil  “Spanners in graphs of bounded degree”  In _Networks_ 24.4, 1994, pp. 233–249  DOI: https://doi.org/10.1002/net.3230240406
  * [14] Aakil M. Caunhye, Xiaofeng Nie and Shaligram Pokharel  “Optimization models in emergency logistics: A literature review”  In _Socio-economic Planning Sciences_ 46.1 Elsevier, 2012, pp. 4–13
  * [15] Yanyu Chen, Wenzhe Zheng, Wenbo Li and Yimiao Huang  “The Robustness and Sustainability of Port Logistics Systems for Emergency Supplies from Overseas”  In _Journal of Advanced Transportation_ 2020 Hindawi, 2020, pp. 1–10
  * [16] Daniel Delling, Thomas Pajor and Renato F. Werneck  “Round-Based Public Transit Routing”  In _Transportation Science_ 49.3 INFORMS, 2015, pp. 591–604
  * [17] Reinhard Diestel  “Graph Theory”  In _Graph Theory_ , Graduate Texts in Mathematics 173  Springer, Berlin, Heidelberg, 2017
  * [18] Matthias Ehrgott  “Multicriteria optimization”  Springer Science & Business Media, Berlin, Heidelberg, 2005
  * [19] Vladimir A. Emelichev and V. A. Perepelitsa  “On cardinality of the set of alternatives in discrete many-criterion problems”  In _Discrete Mathematics and Applications_ 2.5 Walter de Gruyter, Berlin/New York, 1992, pp. 461–471
  * [20] Drosoula Giantsoudi, Clemens Grassberger, David Craft, Andrzej Niemierko, Alexei Trofimov and Harald Paganetti  “Linear energy transfer-guided optimization in intensity modulated proton therapy: feasibility study and clinical potential”  In _International Journal of Radiation Oncology Biology Physics_ 87.1 Elsevier, 2013, pp. 216–222
  * [21] Horst W. Hamacher and Karl-Heinz Küfer  “Inverse radiation therapy planning: A multiple objective optimisation approach”  In _Monitoring, Evaluating, Planning Health Services_ World Scientific, 1999, pp. 177–189
  * [22] Horst W. Hamacher and Günter Ruhe  “On spanning tree problems with multiple objectives”  In _Annals of Operations Research_ 52.4 Springer, 1994, pp. 209–230
  * [23] Pierre Hansen  “Bicriterion Path Problems”  In _Multiple Criteria Decision Making Theory and Application_ 177 Springer, Berlin, Heidelberg, 1980, pp. 109–127
  * [24] David S Johnson, Mihalis Yannakakis and Christos H Papadimitriou  “On generating all maximal independent sets”  In _Information Processing Letters_ 27.3 Elsevier, 1988, pp. 119–123
  * [25] Yusuke Kobayashi  “NP-hardness and fixed-parameter tractability of the minimum spanner problem”  In _Theoretical Computer Science_ 746 Elsevier, 2018, pp. 88–97
  * [26] Guy Kortsarz and David Peleg  “Generating Sparse 2-Spanners”  In _Journal of Algorithms_ 17.2 Elsevier, 1994, pp. 222–236
  * [27] Gustavo Barbosa Libotte, Fran Sérgio Lobato, Gustavo Mendes Platt and Antônio J. Silva Neto  “Determination of an optimal control strategy for vaccine administration in COVID-19 pandemic treatment”  In _Computer methods and programs in biomedicine_ 196 Elsevier, 2020
  * [28] Linet Özdamar, Ediz Ekinci and Beste Küçükyazici  “Emergency logistics planning in natural disasters”  In _Annals of Operations Research_ 129.1 Springer, 2004, pp. 217–245
  * [29] David Peleg and Alejandro A. Schäffer  “Graph spanners”  In _Journal of graph theory_ 13.1 Wiley Online Library, 1989, pp. 99–116
  * [30] David Peleg and Jeffrey D. Ullman  “An optimal synchronizer for the hypercube”  In _SIAM Journal on Computing_ 18.4, 1989, pp. 740–747
  * [31] Christian Thieke, Karl-Heinz Küfer, Michael Monz, Alexander Scherrer, Fernando Alonso, Uwe Oelfke, Peter E. Huber, Jürgen Debus and Thomas Bortfeld  “A new concept for interactive radiotherapy planning with multicriteria optimization: First clinical evaluation”  In _Radiotherapy and Oncology_ 85.2 Elsevier, 2007, pp. 292–298
  * [32] Dorothea Wagner and Tobias Zündorf  “Public Transit Routing with Unrestricted Walking”  In _Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems_ , 2017  Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

##  Appendix 0.A Intractabilty

###### Lemma 4

For all $S,S^{\prime}\in X$ with $S\neq S^{\prime}$, $S$ and $S^{\prime}$ do
not dominate each other and have different value vectors.

###### Proof

Let $S,S^{\prime}\in X$ be two different spanners and assume $S$ dominates
$S^{\prime}$. Therefore, either $f_{1}(S)<f_{1}(S^{\prime})$ or
$f_{1}(S)=f_{1}(S^{\prime})$ holds. We begin by considering the first case.
Let $j\in[n]$ be the greatest index at which the shortest s-t-paths in $S$ and
$S^{\prime}$ differ. Since $f_{1}(S)<f_{1}(S^{\prime})$ holds, $S$ must not
contain the edge $\\{v_{j},w_{j}\\}$ while $S^{\prime}$ has to contain it. Let
$P$ be the remaining path that is identical for $S$ and $S^{\prime}$. Thus,

$\displaystyle f_{2}(S^{\prime})$ $\displaystyle=d^{S^{\prime}}_{c_{2}}(s,t)$
$\displaystyle\leq\left(\sum_{i=1}^{j-1}c_{2}(v_{i},v_{i}^{\prime})+c_{2}(v_{i}^{\prime},w_{i})+c_{2}(w_{i},v_{i+1})\right)+c_{2}(v_{j},w_{j})+c_{2}(P)$
$\displaystyle=\left(\sum_{i=1}^{j-1}2\cdot
2^{i}+1\right)+2^{j}+c_{2}(P)=\left(\sum_{i=2}^{j}2^{i}+1\right)+2^{j}+c_{2}(P)$
$\displaystyle<\left(\sum_{i=1}^{j-1}2^{i}+1\right)+2^{j}+2^{j}+c_{2}(P)$
$\displaystyle=\left(\sum_{i=1}^{j-1}c_{2}(v_{i},w_{i})+c_{2}(w_{i},v_{i+1})\right)+c_{2}(v_{j},v_{j}^{\prime})+c_{2}(v_{j}^{\prime},w_{j})+c_{2}(P)$
$\displaystyle\leq d^{S}_{c_{2}}(s,t)=f_{2}(S).$

This contradicts the assumed domination.

Let us now consider the second case, in which $f_{1}(S)=f_{1}(S^{\prime})$
holds. Then, in order for $S$ to dominate $S^{\prime}$,
$f_{2}(S)<f_{2}(S^{\prime})$ must hold as well. By design of the $c_{1}$-edge-
weights, we know that in order for $f_{1}(S)=f_{1}(S^{\prime})$ to hold, it is
true for every edge $\\{v_{i},w_{i}\\}\in E$ that $\\{v_{i},w_{i}\\}\in
S\Leftrightarrow\\{v_{i},w_{i}\\}\in S^{\prime}$. This claim can be verified
by considering that every edge $\\{v_{i},w_{i}\\}$ has a unique $c_{1}$-cost
that cannot be reproduced by any combination of edges $e\in
E\setminus\\{v_{i},w_{i}\\}$. Consequently, the shortest s-t-paths in $S$ and
$S^{\prime}$ are exactly the same and therefore $f_{2}(S)=f_{2}(S^{\prime})$
holds, which contradicts the assumed domination. ∎

##  Appendix 0.B Extreme Points

###### Lemma 8

The value vector of the yes-witness-spanner $f(S_{w})$ is an extreme point.

###### Proof

Consider the vector
$\lambda_{w}=(2,15n+9m)^{\mathsf{T}}\in\mathbb{R}^{d}_{\geq},\lambda_{w}\neq
0$. We show that $\lambda_{w}\in W(f(S_{w}))$ holds and that for all
$y\in\mathcal{Y}_{N}\setminus\\{f(S_{w})\\}\colon\lambda_{w}\notin W(y)$.
Begin by considering $\lambda_{w}^{\mathsf{T}}\cdot f(S_{1})$ and
$\lambda_{w}^{\mathsf{T}}y_{h}$.

$\displaystyle\lambda_{w}^{\mathsf{T}}\cdot f(S_{1})$
$\displaystyle=\begin{pmatrix}2&15n+9m\end{pmatrix}\cdot\begin{pmatrix}29n+16m\\\
1\end{pmatrix}=73n+41m$
$\displaystyle=\begin{pmatrix}2&15n+9m\end{pmatrix}\cdot\begin{pmatrix}14n+7m\\\
3\end{pmatrix}=\lambda_{w}^{\mathsf{T}}y_{h}$

Now, consider $\lambda_{w}^{\mathsf{T}}\cdot f(S_{w})$. We get

$\displaystyle\lambda_{w}^{\mathsf{T}}\cdot f(S_{w})$
$\displaystyle=\begin{pmatrix}2&15n+9m\end{pmatrix}\cdot\begin{pmatrix}K\\\
2\end{pmatrix}=\begin{pmatrix}2&15n+9m\end{pmatrix}\cdot\begin{pmatrix}16n+9m\\\
2\end{pmatrix}$ $\displaystyle=62n+36m<73n+41m=\lambda_{w}^{\mathsf{T}}\cdot
f(S_{1})=\lambda_{w}^{\mathsf{T}}y_{h},$

for $n,m>0$. Hence, $\lambda_{w}\in W(f(S_{w}))$ and for all
$y\in\mathcal{Y}_{N}\setminus\\{f(S_{w})\\}\colon\lambda_{w}\notin W(y)$. ∎

Figure 3: A truth-setting component $T$ and its symbolic representation. Thick
edges indicate forced edges. For clarity, forcing paths have been omitted from
the figure. Figure 4: The graph $G$ for
$C=\\{\\{\bar{u_{1}},u_{2},u_{3}\\},\\{u_{1},u_{2},\bar{u_{3}}\\}\\}$. Thick
edges indicate forced edges. For clarity, forcing paths have been omitted from
the figure. Figure 5: The value vectors $y_{h},f(S_{w}),f(S_{1})$ and slopes
visualized.