On the Algorithmic Intractability of Computing Distance-Approximating Spanning Trees

This work presents novel results concerning the algorithmic intractability and inapproximability of computing \textsc{Minimum Distance-Approximating Spanning Trees (DAST)} with respect to a range of common matrix norms. Formally, we analyze the problem of computing a spanning tree $T$ for a given graph $G$ such that the difference $(D_T-D_G)$ of the respective distance matrices is minimal with respect to the matrix norms \emph{maximum-entry}, \emph{Minkowski-distance}, \emph{maximum column-sum}, and \emph{maximum row-sum}. Although various characteristic versions of this problem have appeared in the literature for almost three decades with important applications, e.g., in the design of networks, routing-tables, and asynchronous networks, this work is the first to provide NP-completeness results for all of these problems and various extensions, presenting them in a unifying framework. Furthermore, we complement previous results concerning the computation of distance-minimal spanning trees. Finally, it is shown that a variant of \textsc{DAST}, where some edges of $G$ are required to be in the spanning tree, has no constant-factor approximation algorithm with respect to any of the analyzed matrix norms unless P=NP.     «

This work presents novel results concerning the algorithmic intractability and inapproximability of computing \textsc{Minimum Distance-Approximating Spanning Trees (DAST)} with respect to a range of common matrix norms. Formally, we analyze the problem of computing a spanning tree $T$ for a given graph $G$ such that the difference $(D_T-D_G)$ of the respective distance matrices is minimal with respect to the matrix norms \emph{maximum-entry}, \emph{Minkowski-distance}, \emph{maximum column-sum},...     »