Abstract:
We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. Fischer \cite{FISCH93} has shown how to compute a minimum spanning tree of degree at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time $O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of an optimal solution. We model our generalization as a multi-objective optimization problem and give a deterministic algorithm that computes for each number of connected components a solution with the same approximation quality as the algorithm of Fischer and runs in time $O(n^{3 + 1/ \ln b})$. After that, we take a multi-objective view on the problem of computing minimum spanning trees with nonuniform degree bounds, which has been examined by K{\"o}nemann and Ravi \cite{KOE03}. Given degree bounds $B_v$ for each vertex $v \in V$, we construct an algorithm that computes for each number of connected components a spanning forest in which each vertex $v$ has degree $O(B_v + \log n)$ and whose weight is at most a constant times the weight of a minimum spanning forest obeying the degree bounds. The total runtime of our algorithm is $O(n^{3 + 2 / \ln b})$ for an arbitrary constant $b>1$. Setting $b=e^k$, $k > 2/3$ an arbitrary constant, the runtime is by a factor $n^{3- 2/k} \log n$ less than the given bound by K{\"o}nemann and Ravi.

Abstract:
We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. The task is to compute for each number of connected components a minimum spanning forest whose degree is as small as possible. Fischer has shown how to compute a minimum spanning tree of degree at most $b \cdot \Delta^* + \lceil \log_b n \rceil$ in time $O(n^{4 + 1/ \ln b})$ for any $b>1$, where $\Delta^*$ is the value of an optimal solution. We model our generalization as a multi-objective optimization problem and give a deterministic algorithm that computes for each number of connected components a solution with the same approximation quality as the algorithm of Fischer and runs in time $O(n^{3 + 1/ \ln b})$. After that, we take a multi-objective view on the problem of computing minimum spanning trees with nonuniform degree bounds, which has been examined by K{\"o}nemann and Ravi. Given degree bounds $B_v$ for each vertex $v \in V$, we construct an algorithm that computes for each number of connected components a spanning forest in which each vertex $v$ has degree $O(B_v + \log n)$ and whose weight is at most a constant times the weight of a minimum spanning forest obeying the degree bounds. The total runtime of our algorithm is $O(n^5)$, which is by a factor of $n \log n$ less than the algorithm of K{\"o}nemann and Ravi.