Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

This paper is concerned with one of the fundamental questions of algorithm design. When do we regard an algorithm as being efficient? In the past 60 years, the most important measure of the efficiency of exact algorithms is their running time. We usually regard an algorithm to be efficient, if its worst-case running time can be bounded by a polynomial in the input size. To reason that there is most probably no efficient, i.e., polynomial-time algorithm for a given problem at hand, \(\mathbf {NP} \)-hardness theory has proven to be a very valuable tool especially for (combinatorial) optimization.

In multiobjective optimization the notion of \(\mathbf {NP} \)-hardness has been adopted since the pioneering work by Serafini in 1986 [17]. Many papers cite Serafini to show that the multiobjective version of the shortest path, matching or matroid optimization problem are hard to solve. We will take the multiobjective shortest path problem as an example how \(\mathbf {NP} \)-hardness is usually applied in multiobjective optimization.

The multiobjective shortest path (MOSP) problem is defined in the following way: We are given a directed graph G, consisting of a node set V and an arc set A. Formally, \(A\subseteq V\times V\), i.e., we write an arc from a node v to a node w as an ordered pair (v, w). And we are given a source node s and a target node t. A solution is an s-t-path, i.e., a sequence of edges \(((v_1, v_2), (v_2, v_3), \dots , (v_{k-1}, v_k))\) from A, such that for each subsequent edges \(a_1\) and \(a_2\), the second component of \(a_1\) is equal to the first component of \(a_2\) and \(v_1=s\) and \(v_k = t\). We denote the set of all s-t-paths as \(\mathcal {P}_{s,t}\). Moreover, we are given a multiobjective edge-cost function \(c: A \rightarrow \mathbb {N}^d\), where for a path \(p\in \mathcal {P}_{s,t}\) the function is extended to \(c(p) := \sum _{e \in p} c(e)\). We want to find the minimal elements of \(c(\mathcal {P}_{s,t}) := \{ c(p) \mid p \in \mathcal {P}_{s,t}\}\) with respect to the component-wise less-or-equal partial order “\(\le \)”. Usually, we also want to find a representative solution path \(p\in \mathcal {P}_{s,t}\) for every minimal element y, such that \(c(p) = y\).

One of the first papers which is concerned with the MOSP problem is the work by Hansen [9]. He defines a version of the biobjective shortest path problem where \(d=2\). And he finds the first proof of intractability, i.e., he shows that the Pareto-front can be of exponential size in the input size. He also mentions that intractability must not be confused with \(\mathbf {NP} \)-hardness as it is still possible to solve \(\mathbf {NP} \)-hard problems “in polynomial time in the very improbable case of \(\mathbf {P} = \mathbf {NP} \)” [9].

Warburton [23] and Serafini [17] are the first authors who discuss the following decision problem:

Definition 1

(Canonical Decision Problem ( \({\mathbf{MOSP}}^\textsc {Dec}\) )). Given a digraph \(G=(V, A)\), an edge-cost function \(c: A\rightarrow \mathbb {N}^d\), a vector \(k\in \mathbb {N}^d\) and nodes \(s,t\in V\). Decide whether there exists an s-t-path p in G for which \(c(p) \le k\) holds.

Both authors show that \(\text {MOSP} ^\textsc {Dec}\) is \(\mathbf {NP} \)-hard and state this as an informal evidence that MOSP is a hard problem, while they also state that MOSP is actually intractable.

Later, in many papers, e.g., [6, 8, 10, 12, 13, 15, 16, 18,19,20,21,22], it is claimed that MOSP is \(\mathbf {NP} \)-hard. Therein, the arguments are based on the paper by Serafini, or the argument is given that since the output is exponential, the problem is \(\mathbf {NP} \)-hard. Of course, the latter argument is not a formal proof of \(\mathbf {NP} \)-hardness. In fact, it is what Hansen warned against, that \(\mathbf {NP} \)-hardness should not be confused with intractability. It is by no means clear, why an output of exponential size implies that there is a polynomial-time reduction from every problem in \(\mathbf {NP} \) to MOSP.

Similar examples can be found for the multiobjective versions of the bipartite matching (or assignment) problem and the spanning tree and matroid optimization problems. In this paper, we will rigorously look into the \(\mathbf {NP} \)-hardness of these problems, focusing on the paper by P. Serafini. First, we define multiobjective combinatorial optimization problems and other concepts which will be needed in this paper in Sect. 2. Then, in Sect. 3, we will give a short introduction to \(\mathbf {NP} \)-hardness theory. In Sect. 4, we will be concerned with the paper by P. Serafini and clarify what he has actually shown in his paper and what not. In Sect. 5, we discuss \(\mathbf {NP} \)-hardness of multiobjective optimization problems in the light of the previous sections and then in Sect. 6 we discuss further means to investigate the complexity of multiobjective optimization problems.

2 Preliminaries

With [n] we denote the set \(\{1, \dots , n\}\). For a set \(M\subseteq \mathbb {Z}^d\), the set \(\min M\) denotes the minimal elements of M, or \(\min M := \{ x\in M \mid \text {there is no } x'\in M\backslash \{x\} \text { with } x' \le x\}\), where “\(\le \)” is the component-wise less-or-equal partial order. For an n-polyhedron P, \({{\mathrm{vert}}}P := \{ x \in P \mid \exists a \in \mathbb {R}^n : a^Tx > a^Tx' \text { for all } x' \in P\}\), the set of extreme points of P. We will be concerned with the following problems.

Definition 2

(Multiobjective Combinatorial Optimization Problem). A Multiobjective Combinatorial Optimization (MOCO) problem consists of a set of instances \(\mathcal {I}\). An instance of a multiobjective combinatorial optimization problem \((\mathcal {S}, C)\) consists of

  • a set of solutions \(\mathcal {S}\subseteq \{0,1\}^n\),

  • an objective function matrix \(C\in \mathbb {Z}^{d\times n}\).

The goal is to output for a given instance \((\mathcal {S}, C)\) the set \(\mathcal {Y}_N := \min C\cdot \mathcal {S} = \min \{Cx \mid x \in \mathcal {S}\}\). The input size is measured in n and the encoding length of C.

For an instance \(I = (\mathcal {S}, C)\) of a MOCO problem P, we call the set \(\mathcal {Y}_N\) the Pareto-front of I. A solution \(x\in \mathcal {S}\) is called efficient or Pareto-optimal, if \(Cx\in \mathcal {Y}_N\). Usually, we expect algorithms also to produce an efficient solution \(x\in \mathcal {S}\) for every \(y\in \mathcal {Y}_N\), such that \(Cx = y\), though we do not require this formally. Observe, that this definition also subsumes single objective combinatorial optimization problems.

Generalizing \(\text {MOSP} ^\textsc {Dec}\), we define the canonical decision problem for MOCO problems:

Definition 3

(Canonical Decision Problem ( \({\varvec{P}}^\textsc {Dec}\) )). Given a multiobjective combinatorial optimization problem P with instances \(\mathcal {I}\). Then \(P^\textsc {Dec}\) is the following decision problem: For an instance \((\mathcal {S}, C)\in \mathcal {I}\) and a vector \(k\in \mathbb {Z}^d\), decide whether there exists a feasible solution \(x\in \mathcal {S}\) for which \(Cx \le k\) holds.

3 Revisiting the Theory of \(\mathbf {NP} \)-Hardness

Let us first recall formally what \(\mathbf {NP} \)-hardness means. For a deeper understanding of this topic, we refer the reader to the textbook by Arora and Barak [1].

The notion of C-hardness bases on two things: The complexity class C and an often implicit reduction notion \(\preceq \). A complexity class can be perceived as a set of computational problems and a reduction is a binary relation on computational problems. For a complexity class C, a problem P is said to be C-hard w.r.t. to a reduction \(\preceq \) if for every problem \(P'\in C\) we can reduce \(P'\) to P or \(P'\preceq P\). For \(\mathbf {NP} \)-hardness, we usually implicitly use Karp-reductions, or polynomial-time many-one reductions, when we reduce among decision problems and Cook-reductions, or polynomial-time Turing-reductions, if we reduce to other problems, e.g., optimization problems.

A decision problem \(P'\) can be Karp-reduced to a decision problem P, if there exists a polynomial-time transformation f from the inputs x of \(P'\) to the inputs of P, such that \(x\in P' \Leftrightarrow f(x) \in P\). A computational problem \(P'\) can be Cook-reduced to a computational problem P if there exists a polynomial-time algorithm solving \(P'\) which may use an oracle solving P which accounts only for a constant in the running time analysis.

So, the first question is what reduction concept to use? Since MOCO problems are certainly not decision problems, only Cook-reduction is feasible. Hence, if we want to prove \(\mathbf {NP} \)-hardness of a MOCO problem P, we are looking for problems which we can solve by an algorithm which has access to an oracle solving P.

As an example, imagine a biobjective version of the travelling salesperson problem (TSP): We are given a complete graph on n nodes. The feasible solutions are all edge sets which describe a cycle, or tour, in the graph, containing each node exactly once. Each column of the objective function matrix describes the costs of an edge between two nodes of the graph. Thus, the cost of a feasible tour is the (vector-valued) sum of the costs of the edges in the tour. The single objective version is well-known and \(\mathbf {NP} \)-hard due to [7] and we will review the proof in the next subsection. Now, we can solve the single objective problem by an algorithm which has access to an oracle solving the biobjective problem in the following way: We copy the objective function of the single objective problem twice to get the two objectives of the biobjective problem. This biobjective problem has a Pareto-front size of at most 1. If the problem is feasible (i.e., is a valid instance), we can make this transformation, look at the Pareto-front and at the efficient solution and output it as a solution and value for the single objective problem. Since TSP is \(\mathbf {NP} \)-hard, so is biobjective TSP.

But what if the single objective problem of a given MOCO problem is not \(\mathbf {NP} \)-hard? For example the multiobjective versions of the shortest path, spanning tree or assignment problems? It is well-known that the Pareto-fronts can be exponential in the input size in the worst case. So, in general, looking at the Pareto-front cannot be done in polynomial time in a Cook-reduction, even though computing it accounts only for constant time.

3.1 \(\mathbf {NP} \)-Hardness of Single Objective Optimization Problems

In single objective optimization, we usually prove \(\mathbf {NP} \)-hardness of an optimization problem by showing the \(\mathbf {NP} \)-hardness of a certain decision problem. Let us consider the TSP again as an example: To show that single-objective TSP is \(\mathbf {NP} \)-hard, we show that \(TSP^\textsc {Dec}\) is \(\mathbf {NP} \)-hard. Recall, that \(TSP^\textsc {Dec}\) is the decision problem whether there exists a feasible tour of cost less than a given number \(k\in \mathbb {Z}\). The classical reduction is by reduction from the Hamiltonian cycle problem. In the Hamiltonian cycle problem, we are given a graph G and have to decide if there exists a cycle in the graph which contains every node exactly once. We get an instance of the TSP problem by giving each edge the cost 1 and add for each edge which does not exist in G an edge of cost 2. Thus, there exists a Hamiltonian cycle in G iff there exists a feasible tour of costs at most n in the new graph. But why does showing that \(TSP^\textsc {Dec}\) is \(\mathbf {NP} \)-hard show that TSP is \(\mathbf {NP} \)-hard?

The key is that there is a canonical Cook-reduction from \(P^\textsc {Dec}\) to P for every (single objective) optimization problem P. Given an instance of \(P^\textsc {Dec}\), we can solve the optimization problem and check if k is at least the value of an optimal solution. If it is, then there exists a solution with cost at most k, i.e., each optimal solution. If it is not then since every solution has at least the optimal cost which is already higher than k, there does not exist a solution with cost less than k.

Again, since the Pareto-front can be of exponential size, the same reduction does not seem to generally hold in the context of multiobjective optimization.

4 The Paper by P. Serafini

Serafini is the first author doing a deep complexity analysis of multiobjective combinatorial optimization problems in 1986. In his paper [17], Serafini investigates the computational complexity of the general multiobjective combinatorial optimization problem

$$\begin{aligned} (\text {S1})&\min \ f(x)\\&\text {s.t. } x \in F \end{aligned}$$

for \(f: \{0,1\}^n \rightarrow \mathbb {Z}^d\), \(F\subseteq \{0,1\}^n\) and \(n,d\in \mathbb {N}\). He leaves the actual solution concept open. Observe that if the goal is to find the Pareto-front, this is a generalization of MOCO problems of Definition 2 to the case of general objective functions. We will identify problem S1 with the problem of finding the Pareto-front to ensure consistency to Definition 2.

In the aforementioned paper, Serafini is generally interested in problems were the set of solutions F is too large to be scanned exhaustively. He also points out that Pareto-front sizes can be exponential in n and thus they cannot be enumerated in polynomial time. So, he restricts the problems he studies to problems with Pareto-fronts of polynomial size by requiring that the differences in solution values are bounded by a polynomial in the input, i.e.,

$$\begin{aligned} \max \limits _{x,y\in F} ||f(x) - f(y)||_\infty = K\in \mathcal {O}(n^k), \text {for }k>1. \end{aligned}$$
(1)

Here, \(||x||_\infty \) for a vector \(x\in \mathbb {Q}^d\) denotes the maximum-norm or \(\ell _\infty \)-norm: \(||x||_\infty := \max _{i\in [d]} |x_i|\). He then shows reductions among several solution concepts of problem S1, e.g., finding the Pareto-front only, finding all Pareto-optimal solutions and \(\text {S1}^\textsc {Dec}\). His general conclusion is that, assuming (1), finding the Pareto-front of problem S1 is equivalent to \(\text {S1}^\textsc {Dec}\). He argues that because of this equivalence we can identify MOCO problems with their canonical decision problem. He also puts two other (non mathematical) reasons forward to support this conclusion: The first being that the canonical decision problem is also studied in single objective optimization. The second is that the canonical decision problem often plays a role in methods to solve MOCO problems in a posteriori or interactive approaches. In the following sections, Serafini shows for several well-known MOCO problems that their canonical decision problem is \(\mathbf {NP} \)-hard and, in the light of the above argumentation, states that the MOCO problem itself is \(\mathbf {NP} \)-hard.

He starts by studying S1 with linear objective functions, which are MOCO problems by Definition 2, and for which the feasible set F contains the extreme points of a polyhedron P which again contains F, i.e., \({{\mathrm{vert}}}P \subseteq F \subseteq P\):

$$\begin{aligned} (\text {S2}) \min \ C&x\\ \text {s.t. }&x \in F \end{aligned}$$

for \(C\in \mathbb {Z}^{d\times n}\). He investigates the complexity status of this general problem by looking at the following special case, the biobjective unconstrained combinatorial optimization (BUCO) problem.

$$\begin{aligned} (\text {BUCO})&\min \ (c^1, -c^2)^Tx\\&x\in \{0,1\}^n \end{aligned}$$

Serafini concludes that S2 is \(\mathbf {NP} \)-hard, because \(\text {BUCO}^\textsc {Dec}\) is the binary knapsack problem, which is well-known to be \(\mathbf {NP} \)-hard. He then goes on and investigates the biobjective shortest path and biobjective assignment problems as special cases of S2.

In the last section, Serafini proves \(\mathbf {NP} \)-hardness for the biobjective matroid optimization problem and discusses neighborhoods induced by topological sorting and locally nondominated solutions.

5 Discussion of \(\mathbf {NP} \)-Hardness in Multiobjective Optimization

Let us first state that Serafini did write that S2, the biobjective shortest path, assignment and matroid optimization problems are \(\mathbf {NP} \)-hard, but he proves it only for the respective decision problems. The reason for this is the identification of a MOCO problem with its canonical decision problem, which was based on the informal reasons stated above and the equivalence of the problems under (1).

Hence, let us revisit the three reasons Serafini offers why a MOCO problem P can be identified with its canonical decision problem \(P^\textsc {Dec}\). The third reason being that the hardness of \(P^\textsc {Dec}\) influences the choice of solution method to use to solve a problem at hand. This is a very important reason why the complexity status of \(P^\textsc {Dec}\) is interesting. But the incapability of one or a set of solution methods for solving a problem does not determine the complexity status of problem itself.

The second reason is that the problem is also investigated in single-objective optimization. But in single-objective optimization this is well justified as we discussed in Sect. 3.1. And the justification might not transfer to the multiobjective case.

The first reason that the solution concept of finding the Pareto-front and solving the canonical decision problem is equivalent under the bound (1) is solid on the first glance, but only applies if (1) holds. So in the general case, in which it is stated that, e.g., the biobjective shortest path problem is \(\mathbf {NP} \)-hard, the bound does not apply.

Now we can ask the question, whether these problems are indeed \(\mathbf {NP} \)-hard using the solution concept of Definition 2. If the output is exponential there does not seem to be hope. Since we do not impose an ordering on the output, it can be given in any order by an oracle. Finding a specific item in the Pareto-front cannot be done faster than \(\varOmega (|\mathcal {Y}_N|)\).

Thus, Serafini’s bound (1) is a very interesting possibility to restrict the Pareto-front to a size which is searchable in polynomial time. So, we can ask the question if the above problems are \(\mathbf {NP} \)-hard under this restriction.

In the case of the BUCO problem with nonnegative \(c^1\) and \(c^2\), we can prove that if it is \(\mathbf {NP} \)-hard under (1), then \(\mathbf {P} =\mathbf {NP} \) despite the fact that \(\text {BUCO}^\textsc {Dec}\) with nonnegative \(c^1\) and \(c^2\) is \(\mathbf {NP} \)-hard in general. This is a strong evidence that the assumption that from \(\mathbf {NP} \)-hardness of \(P^\textsc {Dec}\) follows \(\mathbf {NP} \)-hardness of P under (1) for MOCO problems P does not hold. We will prove this by showing that the Nemhauser-Ullmann algorithm [14] for the knapsack problem solves BUCO in polynomial time if (1) is assumed.

Let us first discuss the Nemhauser-Ullmann algorithm in some detail. We are given an instance of the knapsack problem, i.e., \(c^1, c^2\in \mathbb {N}^n, W^1,W^2\in \mathbb {N}\) and we are to decide whether there exists \(x\in \{0,1\}^n\) with \({c^1}^Tx \ge W_1\) and \({c^2}^Tx \le W_2\). We will use the following interpretation: The vector \((c^1_i, c^2_i)^T\) encodes the gain and loss if we pack item \(i \in [n]\), thus we can view this decision problem as a biobjective optimization problem with objective functions \(\max {c^1}^Tx\) and \(\min {c^2}^Tx\) and get a BUCO-instance. We observe that if there is a feasible packing, then there is one which is also Pareto-optimal.

The algorithm follows a dynamic programming scheme: Assuming an arbitrary ordering of the items, we look at the Pareto-optimal packings for the first i items. We get the Pareto-optimal packings for the first \(i+1\) items by adding the \((i+1)\)-th item to each of our packings, retaining the old ones. We can now delete all packings which are dominated, since they will never be a subsolution of a Pareto-optimal packing. To solve the knapsack problem, we can delete all solutions for which \({c^2}^Tx > W_2\). This algorithm is well known to be pseudo-polynomial and has a running time of \(\mathcal {O}(nW_2)\).

Proposition 4

If the \(\text {BUCO} \) problem with nonnegative \(c^1\) and \(c^2\) is \(\mathbf {NP} \)-hard assuming (1) then \(\mathbf {P} = \mathbf {NP} \).

Proof

To solve the BUCO problem, we will set \(W_2 := {c^2}^T\mathbf {1}\) and thus keep all Pareto-optimal solutions. Observe, that packing nothing, i.e., the solution \(x=\mathbf {0}\), is always a Pareto-optimal packing. Using this and because of (1), we have for some \(k>1\)

$$\begin{aligned} \mathcal {O}(n^k) \ni K&= \max \limits _{y,z\in F} ||f(y)-f(z)||_\infty \\&= \max \limits _{x\in F}||C\mathbf {0} - Cx||_\infty \\&= \max \limits _{x\in F} ||Cx||_\infty \\&= \max \{\sum \limits _{i\in [n]} c_i^1,\sum \limits _{i\in [n]} c_i^2\} \ge c_i^j \text {, for } j\in \{1,2\} \text { and } i \in [n]. \end{aligned}$$

And since \(nW_2 = n\cdot {c^2}^T\mathbf {1} \in \mathcal {O}(n^{k+1})\), the Nemhauser-Ullmann algorithm runs in polynomial time on BUCO instances.    \(\square \)

As for the other problems, the MOSP problem, the multiobjective assignment and biobjective matroid optimization problem, it is not obvious what happens if (1) is assumed.

Regarding the MOSP problem, there do exist pseudo-polynomial time algorithms based on the generation of Pareto-optimal paths from s to the other nodes (cf. e.g. [11]). Using the bound (1), we can restrict the size of the labels at the target node t, but we are not able to directly bound the number of candidate paths at intermediate nodes \(v\in V\backslash \{s,t\}\). Moreover, the bound we showed in the proof of Proposition 4 does not apply.

In conclusion, while the \(\mathbf {NP} \)-hardness of canonical decision problems is interesting, it does not seem to have (mathematical) implications on the \(\mathbf {NP} \)-hardness of the MOCO problem. Further, we might even want to ask the question what we can draw from the insight of a MOCO problem with exponential Pareto-front size actually being \(\mathbf {NP} \)-hard. On one hand, \(\mathbf {NP} \)-hardness of a problem is a good reason to believe that the problem cannot be solved in polynomial time. On the other hand, intractability proves that there is no polynomial-time algorithm in general.

6 Open Problems

The theory of \(\mathbf {NP} \)-hardness in multiobjective optimization is still very interesting, if we cannot rule out polynomial-time algorithms by other means. The bound by Serafini is one possibility to restrict problems to Pareto-fronts of polynomial size. A more theoretical option is to restrict a problem to all instances which have polynomial Pareto-front size. But similar to Serafini’s bound (1), it might be impossible to test this property in polynomial time in general and thus even testing the feasibility of an instance becomes hard.

It could also be interesting to modify MOCO problems by imposing an ordering on the Pareto-front to output. That is, requiring to output the Pareto-front of a MOCO problem in an ordering which is part of the problem, i.e., output the Pareto-front in lexicographic order. Then again, \(\mathbf {NP} \)-hardness can be an interesting tool eventhough the output is exponential in the worst-case.

But there are also other kinds of running time analyses, which we want to discuss in short. These are smoothed analysis and output-sensitive complexity. In smoothed analysis, we try to depart from classic worst-case analysis by looking at worst-case inputs which are then perturbed by some source of randomness. In the work by Beier, Röglin and Vöcking from 2007 [2], the following game-theoretic model was introduced: We choose a number \(\phi >1\). Then, an adversary chooses a solution set \(S\subseteq \{0,1\}^n\) and the coefficients of the first row of C and fixes for each coefficient of the other rows a probability density function \(f_{i,j} : [-1, 1] \rightarrow \mathbb {R}\). From this distribution we draw our instances. Beier, Röglin and Vöcking showed that the expected Pareto-front size is at most \(\mathcal {O}(\phi n^2)\) for biobjective combinatorial problems. This bound was generalized by Brunsch and Röglin who showed in [5] that the expected Pareto-front size is \(\mathcal {O}(n^{2d}\phi ^d)\) for general multiobjective problems. In this framework, the Nemhauser-Ullmann algorithm has an expected polynomial running time for the knapsack problem and also for solving the BUCO problem [2]. It is also easy to see that the well-known algorithm by Martins [11] has an expected polynomial running time for solving the MOSP problem.

Output-sensitive complexity in multiobjective optimization is a very young field of research. Here, the worst-case perspective is retained. The target is to express the worst-case running time of algorithms for multiobjective optimization problems not only in terms of the input size, but also the output size. An algorithm is said to be output-sensitive, if it runs in time polynomial in \(\mathcal {Y}_N + \langle C \rangle \), where \(\langle C \rangle \) denotes the encoding lenght of C. In [4], Bökler and Mutzel show that there is an output-sensitive algorithm for the multiobjective linear programming problem and finding extreme points of the Pareto-front of multiobjective combinatorial optimization problems. In contrast to smoothed analysis it has also been shown that certain problems are not solvable in an output-sensitive way: In [3], Bökler, Morris, Ehrgott and Mutzel show that there is no output-sensitive algorithm for the MOSP problem unless \(\mathbf {P} = \mathbf {NP} \).

The bound Serafini considers in his paper is interesting also in the context of output-sensitive complexity. It can be seen that if a multiobjective optimization problem is hard under (1), then there does not exist an output-sensitive algorithm unless \(\mathbf {P} = \mathbf {NP} \).

In both theories the complexity status of many multiobjective optimization problems is unknown. For smoothed analysis a challenging problem is to find a smoothed polynomial algorithm for the multiobjective spanning tree problem. In output-sensitive complexity even an output-sensitive algorithm for the BUCO problem, or showing that no such algorithm exists, seems to be a challenge.