Sebastian Wernicke: Distanzapproximierende Spannbäume

Attributes such as structural simplicity and sparseness make spanning trees an attractive tool for representing a network througha small number of edges whilst maintainingconnectivity. Several optimization problems have been considered that try to find a spanning tree which approximates certain properties of the underlying network (e.g., the diameter or the sum of all distances). In this work, we consider the optimality criterion of distance-approximation, i.e., vertices that have a small distance to each other in the original graph should maintain this property in the spanning tree. Integrating the problems into a unifying framework based on matrix norms, we show that all of the optimization problems related to distance-approximationare not only NP hard---unless P=NP some of them even do not allow for a constant-factor approximation in polynomial time.