In multiple criteria optimization an important research topic is the topological structure of the set Xe of efficient solutions. Of major interest is the connectedness of Xe, since it would allow the determination of Xe without considering non-efficient solutions in the process. We review general results on the subject, including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.
