BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1338
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: Optimizing the Degree of Minimum Weight Spanning Trees
AUTHOR:: Fischer, Ted
DATE:: April 1993
PAGES:: 5
ABSTRACT::
This paper presents two algorithms to construct minimum weight spanning trees 
with approximately minimum degree. The first method gives a spanning tree 
whose maximum degree is $O(\delta^{*} + logn)$ where $\delta^{*}$ is the 
minimum possible, and $n$ is the number of vertices. The second method gives 
a spanning tree of degree no more than $k \cdot (\delta^{*} + 1)$, where $k$ 
is the number of distinct weights in the graph. Finding the exact minimum is 
NP-hard.
END:: CORNELLCS//TR93-1338
BODY::
Optimizing the Degree of Minimum
Weight Spanning Trees
led Fischer*
IR 93-1338
April 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
7Depa7tment of Computer Science, Cornell University, Ithaca, NY 14853. Research
supported by ONR Graduate Fellowship.
Optimizing the Degree of Minimum Weight Spanning
Trees
Ted Fischer*
April15, 1993
Abstract
This paper presents two algorithms to construct minimum weight spanning trees with ap-
proximately minimum degree. The first method gives a spanning tree whose maximum degree
is 0(6* + logn) where 6* is the minimum possible, and n is the number of vertices. The second
method gives a spanning tree of degree no more than k (6* + 1), where k is the number of
distinct weights in the graph. Finding the exact minimum is NP-hard.
*Department of Computer Science, Cornell University, Ithaca NY 14853. Research supported by ONR Graduate
Fellowship.
0
1 Introduction
While it is easy enough to optimize the weight of a spanning tree, it is often more difficult to satisfy
constraints which involve the degrees of the vertices. The problem of minimizing the maximum
degree of a spanning tree is known to be NP-complete, as the Hamiltonian path problem is merely
a special case of this problem. Other related NP-complete problems include finding a spanning tree
with the maximum number of leaves [3], one that is isomorphic to a given tree [3], or one where
the paths between all pairs of vertices produces the minimum congestion [1]. More NP-complete
spanning tree problems can be found in [3] and [5]. Other related problems involve the simultaneous
optimization of two parameters, such as the problem of finding the cheapest tree bounded by a
given diameter [3].
Approximation algorithms are known for some of these problems. Goemans and Williamson
developed a technique that applies to a variety of constrained forest problems, including the gen-
eralized Steiner tree problem, and the non-fixed point-to-point connection problem [4]. A result of
Khuller, Raghavachari, and Young balances the cost and diameter for spanning trees [6].
Fiirer and Raghavachari recently published an polynomial time approximation algorithm which
constructs a spanning tree of degree no more than 6* + 1, where 6* is the optimum degree [2]. In
the same paper, they give a second algorithm for the same problem; this algorithm only produces
a tree of degree 0(6* + log n) (where n is the number of vertices in the graph), but the techniques
may be more generally applicable.
We consider a generalization of the problem addressed by Fiirer and Raghavachari. Let G =
(V, E) be a graph with weights w(e) on the edges e E E. ff there exists a minimum weight spanning
tree of degree 6*, the first algorithm presented here will construct a minimum weight spanning tree
(MWST) of degree 0(6* + log n), extending the second algorithm of Fu?rer and Raghavachari.
Also presented here is an algorithm to construct a MWST of degree at most k(6* + 1) where k
is the number of different weights in the graph. This method uses the first algorithm of Fu?rer and
Raghavachari as a subroutine.
2 An Additive log n Approximation
Definition 2.1 Define the rank of a tree T to be the the ordered n-tuple ....... , t1) where tj ?
the nnmber of vertices of degree i in T. Define a lexicographic order on these ranks; a tree S is of
tower rank than tree T if s? < tj for some j and s? = tj for i = j + 1, . . ,
When an edge is added to a spanning tree, it creates a cycle. Removing any edge from the
induced cycle, we are again left with a spanning tree. Define a swap to be any such exchange of
edges. A swap is cost-neutral if the edges exchanged are of equal weight.
Consider a swap of the tree edge (x,w) E T for the edge (u,v) ? T, with x distinct from u,v.
Such a swap may increase the degree in T of both u and v by one, but it will decrease the degree of
x. This will decrease the rank of T if the degree of x in T is at least two more than the maximum
degree of u and v.
Definition 2.2 A locally optimal minimum weight spanning tree is a MWST in which no cost-
neutrai swap decreases the rank of the tree.
Theorem 2.3 If T is a iocali? optimal MWST, and ? is the degree of T, then 6 < b 6* + [log6n]
for an? constant b> 1.
Proof:
Consider a locally optimal MWST, T. Let Sj denote the set of vertices of degree i in T,
Uj = u;=? Sj, and a? = lUil. By definition, U? is non-empty, so a? > 1. Since ? < n for all i, the
ratio ai--Hi/ai can not be greater than b for log6 n consecutive values of i.
Claim 2.4 For any constant b > 1, there exists some x in the range 6 --H [log6n] < x < 6 such that
a:--Hi/ax ?
Suppose we choose x to satisfy this property, and remove from T the edges adjacent to vertices
of Ux. Let T? denote the remaining edges ofT. How many connected components (counting isolated
vertices) are there in the subgraph Tx? Initially, T is entirely connected, and each edge removed
creates a new connected component. There are at least x edges adjacent to each vertex of Ux and,
since there are no cycles, we have at most a? --H 1 edges which are adjacent to two vertices of Ux
and counted twice. Therefore there must be at least 1 + x			--H (?x --H 1), or (x --H 1)a? + 2 connected
components in Tx.
Consider the graph G formed by contracting every component of Tx. Since any MWST of G
must contain a MWST of G, any MWST must include at least (x --H 1)?x + 1 edges from 0.
Consider an edge, (v, w) E E --H T, between two components of Tx. Let P4,w) denote the path
from v to w in T, and denote those edges of which appear in 0, the edges on the path
which are adjacent to a vertex in Ux. Suppose neither v nor w is in Ux?i. Since T is locally optimal,
no cost-neutral swap can reduce the rank of T, ?o (v, w) must be more expensive than any edge in
pT
(v,iv) Since (v,w) and pT form a cycle in 0, this implies that (v, w) may not participate in a
MWST of 0. Therefore only those edges which are adjacent to Ux--H1 may participate in a MWST
of 0, and any MWST of 0 must contain at least (x --H 1)?x + 1 edges that are adjacent to Ux?i.
Earlier we chose x to satisfy the inequality ax?i/b < ?x Substituting, we see there must be at
least ((x --H l)xx--Hi/b) + 1 edges adjacent to ?x--H1 Therefore the average degree of a vertex in Ux--Hi
must be at least (xW??%-11+6 Therefore 6* >
Combining this with the possible range for x, we find 6 ? b 6* + [log6 ni. I
Now constructing a locally optimal tree might take exponential time, but in the proof we only
used the local optimality condition for the high degree vertices: those in Uk with k = 6 --H [log6 ni.
Say that such a tree is pseudo-optimal for parameter b. We can compute a pseudo-optimal tree
in polynomial time with the algorithm on the next page.
2
Algorithm 2.5 How to construct a pseudo-optimal MWST.
o Start with any MWST, T. Let b > 1 be the desired approximation parameter. Let 1 < n be
the number of distinct edge weights, Wi ...wt, ?n T
1. Let d be the current maximum degree in T.
2. For every vertex, v, in G, check for appropriate improvements. Conduct a depth first traversal
of T starting from v.
(a) Let w be the current vertex on the traversal of T, and Pw be the path in T between v and
(b) Assign variables ..... M1 such that Mj denotes the maximum degree of those vertices
adjacent to edges of weight Wj in Pw. For a depth first traversal, this is easily maintained
using stacks.
(c) If there is an edge (v, w) E E, let Wj be its weight. If M? is at least two greater than
the degree of v and w, and M? is at least 6 --H [log?n?, then the edge (v,w) can be used
to reduce the high-degree rank of T. Conduct the appropriate swap on T, and repeat to
step (1) for the next iteration.
(d) If no appropriate cost-neutral swap was found involving v and w, continue the traversal.
3. If no appropriate cost-neutral swap was found in any of the traversals, terminate.
The tree produced, T, is clearly pseudo-optimal; any cost-neutral swap that can reduce the high-
degree rank will be found. Since we are conducting 0(n) depth first traversals, and can maintain
the Mi variables in constant time per step of the traversal, no more than 0(n2) time will be spent
on any iteration.
Lemma 2.6 Algorithm 2.5 will terminate in O(n2+l/lllb) iterations.
Proof: We use a potential function identical to that of Fiirer and Raghavachari. Define the poten-
tial of a vertex v to be p? for some fixed base P > 2 where dv is the degree of v in the current tree.
Define ? = ?vEV pdv. Let i = 6 --H [log? ni,the lower limit on the degree for our improvements.
Since we only perform swaps which improve the degree of some vertex in U?,the reduction in
? resulting from a swap is at least:
+ 2.			--H 3			= (P --H 1) (p --H 2). P??2 > c P? for some constant c.
Now ? < n ?5, so each swap reduces ? by at least a fraction of:
c.?lo+ _ c.p?fl0&n1			c'			I
--H			for some constant c
n.?5			n			--H n1+10g?P
Since this argument holds for any P > 2, we can choose P = e. Therefore in 0(n1+1/1116) itera-
tions, the potential reduces by a constant fraction, and after O(n2+l/Inb) iterations, the algorithm
must halt. I
This completes the proof of the main theorem:
3
Theorem 2.7 The above algorithm computes, in 0(n4+1/inb) time, a minimum weight spanning
tree of degree no more than b .6* + [log? ni, where 6* is the minimum possible degree of any minimum
weight spanning tree.
3 A k-factor Approximation
A MWST can be described as a tree containing an edge of minimum cost in any cut. Those nodes
that can be connected by edges of cost c or less, must be connected by such edges. This property
is applied to build a MWST of low degree.
Notation 3.1 Let k be the number of distinct weights used in a MWST. Let .... . Wk denote the
different weights in increasing order, and Ej be the set of edges of weight Wj or less. Let the w1-
degree of a node, v, in a tree denote the number of edges adjacent to v in the tree which are of
weight w?.
In phase i, we will use the edges of weight w, to join the components already spanned by edges
of lesser weight. Using an algorithm for the following claim as a subroutine, we approximately
minimize the maximum number of weight Wj edges adjacent to any given node.
Claim 3.2 Given a forest, F, in a graph G = (v,E), we can extend F in polynomial time to a
forest F' such that F C F', F' is a spanning forest of G, and the number of edges in F' --H F adjacent
to any given node of V is at most one more than the minimum possible.
This result follows immediately from the techniques used to prove the second algorithm of Furer
and Ragavachari [2].
In the first phase, we merely run the subroutine to find an approximately minimum degree
spanning forest, F1, for the graph G1 = (V, E1). In phase i, for i ..... k, we run the subroutine
on the graph Gj = (V, Ej) with initial forest 1%--Hi Note that this guarantees that any subgraph
of G that can be spanned by edges in E, *will* be spanned by edges of weight E2 in the forest
generated. Since we know that the edges Ek span G, the tree produced is a MWST.
Theorem 3.3 The MWST produced by the above algorithm has maximum degree 6 < k. (6* + 1).
Proof: Suppose there there is a MWST T of degree 6*, yet the tree T produced by our algorithm
has some vertex of degree greater than k (6* + 1). By the pigeonhole principle, there is some i
such that the w,-degree of that vertex is at least 6* +2.
Now, any vertices connected by edges in Ej?1 are also connected in F??l, since Fj?1 spans Gi--H1.
And any MWST must span Gj with edges in Ej. Since our subroutine uses 6* +2 edges of weight
w? adjacent to a single vertex, any MWST must have some vertex with w?-degree at least 6* + 1,
implying that no MWST of degree 6* is possible. By contradiction, the degree of T is no more than
k.(6*+1). I
4
4 Acknowledgements
I would like to thank Eva Tardos for her advice and direction.
References
[1] P.M. Camerini, G. Galbiati, and F. Maffloli. Complexity of spanning tree problems: Part i.
European J. Op. Res., 5:346--H352, 1980.
[2] M. Purer and B. Raghavachari. Approximating the minimum degree spanning tree to within
one from the optimal degree. In Proceedings of the Third Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 317--H324, 1992.
[3] M. R. Garey and D. 5. Johnson. Computers and Intractabihty: A guide to the theory of NP-
completeness. W. H. Preeman, San Prancisco, 1979.
[4]
M.X. Goemans and D.P. Williamson. A general approximation technique for constrained forest
problems. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 307--H316, 1992.
[5] D.S. Johnson. The npcompleteness column: An ongoing guide. J. Algorithms, 6:145--H159, 1985.
[6] Balancing minimum spanning and shortest path
ACM?SIAM Symposium on Discrete Algorithms,
5
5. Khuller, B. Rachavachari, and N. Young.
trees. In Proceedings of the Fourth Annual
pages 243--H250, 1993.
