A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees\footnote{A preliminary version of this paper appeared in the Proceedings of the 5th International Integer Programming and Combinatorial Optimization Conference (IPCO), June 1996, pages 105-117.}
S\'andor P.~Fekete \thanks{Center for Parallel Computing
Universit\"at zu K\"oln
D-50923 K\"oln
College Park
Monika Klemmstein \thanks{Center for Parallel Computing
Balaji Raghavachari \thanks{Department of Computer Science
Box 830688
Richardson
Neal Young \thanks{Dept. of Computer Science
Dartmouth College
Hanover NH 03755-3510. Part of this research was done while at School of ORIE
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at most its specified bound is considered. %% ney2 - reworded next paras *again* In particular, modifying a given spanning tree $T$ using {\em adoptions} to meet the degree constraints is considered. %rbk2 removed the following since it has no place in an abstract. % Previous algorithms have also used adoptions. A novel network-flow based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. %samir3 changed prev line to read ``any previous algorithm'' %rbk4 The performance guarantee is the following. If the degree constraint $\goal(v)$ for each $v$ is at least $2$, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times $2 - \min\Big\{\frac{\goal(v)-2}{\degree_T(v)-2} : \degree_{T}(v)>2\Big\},$ where $\degree_T(v)$ is the initial degree of $v$. %rbk4 -- moved the following from the previous paragraph as per %referee's request. %rbk2 rewrote the following sentence and changed it back based on %Neal's valid objection. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for {\em any} algorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. Choosing $T$ to be a minimum spanning tree yields approximation algorithms with factors less than 2 %samir3 added ``with factors less than 2'' for the general problem on geometric graphs with distances induced by various $L_p$ norms. %rbk2 For geometric graphs, with distances induced by various $L_p$ norms, %samir2 -- i checked the RS paper, the bound for any Lp is constant %rbk2 if $T$ is a minimum spanning tree, %rbk2 our algorithms yield approximate solutions for the general problem %rbk2 (independent of a given tree). %$L_1$, $L_2$, and $L_\infty$ norms. %rbk3 removed the following since it is not true. % These are the first non-trivial performance guarantees for geometric graphs. %rbk3 %samir2 -- do we really want to say this? it sounds a little odd, how about this? % Finally, we disprove the following conjecture of \cite{KRY2}: % ``In Euclidean graphs, perhaps a Traveling Salesman path % of weight at most $(2-\eps)$ times the minimum spanning-tree % weight always exists...'' % ney2 - what do you think of the following (added stuff before the comma) %rbk2 -- don't cite papers in an abstract unless necessary. % Finally, we close an open problem posed in \cite{KRY2} % by giving an example showing that in Euclidean graphs, % the ratio of the length of an optimal Traveling Salesman path % to the minimum spanning tree weight can be arbitrarily close to two. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to~2.
adopt.tex
\strut\psfig{figure=adopt1.ps}

biblio.tex
\begin{thebibliography}{CDNS}

\bibitem{AMO}
R.~K.~Ahuja, T.~L.~Magnanti and J.~B.~Orlin.
\newblock {\em Network flows (theory, algorithms and applications)}.
\newblock Prentice Hall, Englewood Cliffs, NJ, 1993.

\uncited{
\bibitem{BGMRZ}
T.~Barrera, J.~Griffith, A.~McKee, G.~Robins, and T.~Zhang.
\newblock Toward a Steiner engine: enhanced serial and parallel
        implementations of the iterated 1-Steiner algorithm.
\newblock {\em Proc.\ Great Lakes Symp.\ VLSI}.
\newblock Kalamazoo, MI, March 1993, pp.\ 90--94.
}

%rbk2 -- can we cite a software as a publication?
\uncited{
\bibitem{B}
Bellcore.
\newblock {\em FIBER OPTIONS}.
Software for designing survivable optimal fiber networks.
Software package, 1988.
}

%\bibitem{Be}
%J.~L.~Bentley.
%\newblock Communicated through David Johnson.

\bibitem{BCG}
C.~Brezovec, G.~Cornu\'ejols, F.~Glover.
\newblock A matroid algorithm and its application
to the efficient solution of two optimization
problems in graphs.
\newblock {\em Math.\ Programming} {\bf 42} (1988), pp.\ 471--487.

\bibitem{Fi}
T.~Fischer.
\newblock {\em Optimizing the degree of minimum weight spanning trees}.
\newblock Tech.\ Rep.\ 93-1338, Dept.\ of Computer Science,
        Cornell University, April 1993.

\bibitem{FR}
M.~F\"urer and B.~Raghavachari.
\newblock Approximating the minimum-degree Steiner tree to within one of
optimal.
\newblock  {\em J.\ Algorithms} {\bf 17} (1994), pp.\ 409--423.

\bibitem{Ga}
H.~N.~Gabow.
\newblock A good algorithm for smallest spanning trees with
    a degree constraint.
\newblock {\em Networks} {\bf 8} (1978), pp.\ 201--208.

\bibitem{GT}
H.~N.~Gabow and R.~E.~Tarjan.
\newblock Efficient algorithms for a family of matroid intersection problems.
\newblock {\em J.\ Algorithms} {\bf 5} (1984), pp.\ 80--131.

\bibitem{GJ}
M.~R.~Garey and D.~S.~Johnson.
\newblock {\em Computers and intractability: a guide to the
theory of NP-completeness}.
\newblock Freeman, San Francisco, CA, 1979.

\bibitem{Gv}
B.~Gavish.
\newblock Topological design of centralized
        computer networks --- formulations and algorithms.
\newblock {\em Networks} {\bf 12} (1982), pp.\ 355--377.

\uncited{
\bibitem{GP}
G.~Georgakopoulos and C.~H.~Papadimitriou
\newblock The 1-Steiner tree problem.
\newblock {\em J.~Algorithms}, {\bf 8} (1987), pp.\ 122--130.
}

\bibitem{GlKl}
F.~Glover, D.~Klingman.
\newblock Finding minimum spanning trees with a fixed number of links at
a node.
\newblock In: B.\ Roy (ed.), {\em Combinatorial Programming: Methods and
Applications}.
\newblock D.~Reidel Publishing Company, Dordrecht-Holland, 1975. pp.\ 191--201.

\uncited{
\bibitem{Go}
M.~C.~Goldstein.
\newblock Design of long-distance telecommunication networks
-- the Telepak problem.
\newblock {\em IEEE Trans.\ Circuit Theor.} CT-20 (1973), pp.\ 186--192.
}

\uncited{
\bibitem{Ha}
A.~C.~Harter.
\newblock {\em Three-dimensional circuit layout}.
\newblock Cambridge University Press, New York, 1991.
}

\uncited{
\bibitem{H}
J.~A.~Hoogeveen.
\newblock Analysis of Christofides' heuristic: some paths are
more difficult than cycles.
\newblock {\em Operations Research Letters}, {\bf 10}, 291--295, 1991.
}

\uncited{
\bibitem{KR}
A.~B.~Kahng and G.~Robins.
\newblock A new class of iterative Steiner tree heuristics
with good performance.
\newblock {\em IEEE Trans.\ Computer-Aided Design}, {\bf 11} (1992), 893--902.
}

\bibitem{KRY}
S.~Khuller, B.~Raghavachari and N.~Young.
\newblock Low degree spanning trees of small weight.
%\newblock {\em Proc.~of 26th Annual ACM Symp. on the Theory of
%Computing}, pp.~412--421, May 1994.
\newblock {\em SIAM J.\ Comput.} {\bf 25} (1996), pp.\ 355--368. 
%samir3 added full ref

\bibitem{KRY2}
S.~Khuller, B.~Raghavachari, N.~Young,
\newblock Balancing minimum spanning trees and shortest-path trees.
\newblock {\em Algorithmica} {\bf 14} (1995), pp.\ 305--321.

\uncited{
\bibitem{Le}
T.~Lengauer.
{\em Combinatorial algorithms for integrated circuit layout}.
B.~G.~Teubner, Stuttgart, 1990.  %, p.\ 281.
}

\bibitem{MSh}
C.~L.~Monma, D.~Shallcross.
\newblock Methods for designing communication networks with certain
two-connected survivability constraints.
\newblock {\em Oper.\ Res.} {\bf 37} (1989), pp.~531--541.

\bibitem{MS}
C.~L.~Monma, S.~Suri,
\newblock
 Transitions in geometric minimum spanning trees.
\newblock
 {\em Discrete \& Computational Geometry} {\bf 8} (1992), pp.\ 265--293.

\bibitem{NH}
S.~C.~Narula and C.~A.~Ho.
\newblock Degree-constrained minimum spanning tree.
\newblock {\em Comput.\ Ops.\ Res.} {\bf 7} (1980), pp. 239--249.

\bibitem{PV}
C.~H.~Papadimitriou, U.~V.~Vazirani,
\newblock
 On two geometric problems related to the traveling salesman problem.
\newblock
 {\em J. Algorithms} {\bf 5} (1984), pp.\ 231--246.

\uncited{
\bibitem{PL}
B.~T.~Preas and M.~J.~Lorenzetti.
{\em Physical design automation of VLSI systems}.
Benjamin/Cummings, Menlo Park, CA, 1988.
}

\uncited{
\bibitem{Pr}
R.~C.~Prim.
\newblock Shortest connection networks and some generalizations.
\newblock {\em Bell Systems Tech.~J.} {\bf 36} (1957), pp.\ 1389--1401.
}

%rbk2 -- do we really need to cite this twice?  After all RMRRH2 is a
%``manuscript'' which means that it is not really available.
\bibitem{RMRRH}
R.\ Ravi, M.\ V.\ Marathe, S.\ S.\ Ravi, D.\ J.\ Rosen\-krantz
        and H.\ B.\ Hunt\ III.
\newblock
Many birds with one stone: multi-objective approximation algorithms.
\newblock Manuscript.
\newblock A preliminary version appeared in
{\em Proc.~25th Annual ACM Symp. on the Theory of Computing},
pp.~438--447, May 1993.

\uncited{
\bibitem{RMRRH2}
R.\ Ravi, M.\ V.\ Marathe, S.\ S.\ Ravi, D.\ J.\ Rosen\-krantz
        and H.\ B.\ Hunt\ III.
\newblock
Many birds with one stone: multi-objective approximation algorithms.
\newblock
Manuscript (full version of 1993 STOC paper).
}

\bibitem{RS}
G.~Robins and J.~S.~Salowe.
\newblock Low-degree minimum spanning trees.
\newblock {\em Discrete and  Computational Geometry} {\bf 14} (1995),
                pp.\ 151--166.

\bibitem{Sal}
J.~S.~Salowe.
\newblock Euclidean spanner graphs with degree four.
%samir2 -- changed to upper case (DAM)
\newblock {\em Discrete Appl. Math.} {\bf 54} (1994), pp.\ 55--66.

\bibitem{SaVo}
M.~Savelsbergh and A.~Volgenant.
\newblock Edge exchanges in the degree-constrained minimum
 spanning tree problem.
\newblock {\em Comput.\ Ops.\ Res.} {\bf 12} (1985), pp.\ 341--348.

\bibitem{St}
M.~Stoer.
\newblock {\em Design of survivable networks}.
\newblock Lecture Notes on Mathematics \# 1531.
\newblock Springer, Heidelberg, 1992.

\bibitem{Vo}
A.~Volgenant.
\newblock A Lagrangean approach to the degree-constrained minimum
 spanning tree problem.
\newblock {\em Europ.\ J.\ Ops.\ Res.} {\bf 39} (1989), pp.\ 325--331.

\uncited{
\bibitem{Y}
Y.~Yamamoto.
\newblock The Held-Karp algorithm and degree-constrained
minimum 1-trees.
newblock {\em Mathematical Programming \/} {\bf 15} (1978), pp.\ 228--231.
}

\end{thebibliography}


final.tex
\documentstyle[12pt,fullpage]{article}
%rbk5 -- changes made based on Neal's comments.
%samir3 -- changes after rbk4 Dec 96
%rbk4 -- changes made in December 1996.
%rbk3 -- changes made Dec 5.
%rbk2 -- changes made Dec 4.  I removed major chunks of \iffalse \fi.
%Contact me if you want them.

%samir2 -- THESE ARE MADE ON NEAL'S DRAFT OF NOV 23, PLEASE READ 
%sandor -- changes made by sandor on Oct 11
%samir -- changes made by Samir on Oct 8th
%% ney - changes made by neal nov 20

%% ney2 - changes made by neal dec 1

\newcommand{\uncited}[1]{}
%jalg
%\setstretch{1.6}

\date{}

% Sandor's macros begin
%------------
\input{psfig.sty}
\iffalse
\newtheorem{theo}{Theorem}[section]
\newtheorem{lemm}[theo]{Lemma}
\newtheorem{coro}[theo]{Corollary}
\fi

\newcommand{\fig}[4]% usage: \fig{file}{label}{caption}{height}
{\begin{figure}[htbp]
 \centerline{ \psfig{file=#1,height=#4}}
 \caption{#3}
 \label{#2}
 \end{figure}
}
\newcommand{\ol}{\overline}
\newcommand{\eps}{\varepsilon}
%------------
% Sandor's macros end


\newtheorem{theorem}{Theorem}%[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{definition}{Definition}%[section]
\newtheorem{definitions}[definition]{Definitions}
\newtheorem{notation}[definition]{Notation}

\def\myendproof{\hfill{\vbox{\hrule\hbox{%
   \vrule height1.3ex\hskip0.8ex\vrule}\hrule}}}

\newcommand\real{{\rm I\kern-0.2em\rm R}}
\newcommand\itreal{{\it I\kern-0.35em\it R}}

\newenvironment{proof}{

\noindent{\bf Proof:}\ }{
\hfill \myendproof

}

\newenvironment{tabAlgorithm}[1]{
\setcounter{algorithmLine}{1}
\samepage
\begin{tabbing}
999\=\kill
#1
}{
\end{tabbing}
}
\newcounter{algorithmLine}
\newcommand{\algline}{\\\thealgorithmLine\hfil\>\stepcounter{algorithmLine}}
\newcommand{\algnono}{\\ \>}

\title{A Network-Flow Technique
  for Finding Low-Weight Bounded-Degree Spanning Trees\footnote{A preliminary 
version of this paper appeared in the
Proceedings of the 5th International Integer Programming and
Combinatorial Optimization Conference (IPCO), June 1996, pages 105-117.}}
%samir3: added footnote 
\author{
    S\'andor P.~Fekete
  \thanks{Center for Parallel Computing, Universit\"at zu K\"oln,
          D-50923 K\"oln, Germany. E-Mail: {\tt sandor@zpr.uni-koeln.de.}}
   \and  Samir Khuller
  \thanks{Computer Science Department and Institute for Advanced Computer
    Studies, University of Maryland, College Park, MD~20742.
    Research supported by NSF Research Initiation Award CCR-9307462 and
    an NSF CAREER Award CCR-9501355.
    E-mail~: {\tt samir@cs.umd.edu}.}
  \and Monika Klemmstein
  \thanks{Center for Parallel Computing, Universit\"at zu K\"oln,
          D-50923 K\"oln, Germany. E-Mail: {\tt mklemmst@zpr.uni-koeln.de.}}
  \and Balaji Raghavachari
  \thanks{Department of Computer Science, The University of Texas at Dallas,
    Box 830688, Richardson, TX 75083-0688.
%rbk support information added.
    Research supported in part by NSF Research Initiation Award CCR-9409625.
    E-mail : {\tt rbk@utdallas.edu}.}
  \and Neal Young
  \thanks{Dept. of Computer Science, Dartmouth College, Hanover NH 03755-3510. 
    Part of this research was done while at
    School of ORIE, Cornell University, Ithaca NY 14853
    and supported by \'Eva Tardos' NSF PYI grant DDM-9157199.
    E-mail : {\tt ney@cs.dartmouth.edu}.}
}

\begin{document}

\maketitle

\newcommand{\todo}[1]{{\bf [#1]}\marginpar{**}}

\newcommand{\mathfn}[1]{{\mathop{\rm #1}\nolimits }}
\newcommand{\goal}{\mathfn{d}} % \goal(v) is degree constraint of v
\newcommand{\degree}{\mathfn{deg}} % \degree_T(v) is initial degree of v

%rbk2 changed the abstract to be impersonal (no "we").
\begin{abstract}
  Given a graph with edge weights satisfying the triangle inequality,
  and a degree bound for each vertex,
  the problem of computing a low weight spanning tree
  such that the degree of each vertex is at most its specified bound
  is considered.
  %% ney2 - reworded next paras *again*
  In particular, modifying a given spanning tree $T$
  using {\em adoptions} to meet the degree constraints is considered.
%rbk2 removed the following since it has no place in an abstract.
%  Previous algorithms have also used adoptions.
  A novel network-flow based algorithm for finding
  a good sequence of adoptions is introduced.
  The method yields a better performance guarantee
  than any previous algorithm.
%samir3 changed prev line to read ``any previous algorithm''
%rbk4  The performance guarantee is the following.
  If the degree constraint $\goal(v)$ for each $v$ is at least $2$,
  the algorithm is guaranteed to find a tree whose weight is at most
  the weight of the given tree times
  $2 - \min\Big\{\frac{\goal(v)-2}{\degree_T(v)-2} : \degree_{T}(v)>2\Big\},$
  where $\degree_T(v)$ is the initial degree of $v$.
%rbk4 -- moved the following from the previous paragraph as per
%referee's request.
%rbk2 rewrote the following sentence and changed it back based on
%Neal's valid objection.
  Equally importantly,
  it takes this approach to the limit in the following sense:
  if any performance guarantee that is solely
  a function of the topology and edge weights of a given tree
  holds for {\em any} algorithm at all, then it also holds for the given algorithm.
  Examples are provided in which no lighter tree
  meeting the degree constraint exists.
  Linear-time algorithms are provided with the same worst-case
  performance guarantee.

  Choosing $T$ to be a minimum spanning tree yields approximation
  algorithms with factors less than 2
%samir3 added ``with factors less than 2''
   for the general problem on geometric graphs with
  distances induced by various $L_p$ norms.
%rbk2  For geometric graphs, with distances induced by various $L_p$ norms,
%samir2 -- i checked the RS paper, the bound for any Lp is constant
%rbk2  if $T$ is a minimum spanning tree,
%rbk2  our algorithms yield approximate solutions for the general problem
%rbk2  (independent of a given tree).
%$L_1$, $L_2$, and $L_\infty$ norms.
%rbk3 removed the following since it is not true.
%  These are the first non-trivial performance guarantees for geometric graphs.
%rbk3
%samir2 -- do we really want to say this? it sounds a little odd, how about this?
%  Finally, we disprove the following conjecture of \cite{KRY2}:
%  ``In Euclidean graphs, perhaps a Traveling Salesman path
%  of weight at most $(2-\eps)$ times the minimum spanning-tree
%  weight always exists...''
% ney2 - what do you think of the following (added stuff before the comma)
%rbk2 -- don't cite papers in an abstract unless necessary.
%  Finally, we close an open problem posed in \cite{KRY2}
%  by giving an example showing that in Euclidean graphs,
%  the ratio of the length of an optimal Traveling Salesman path 
%  to the minimum spanning tree weight can be arbitrarily close to two.
  Finally, examples of Euclidean graphs are provided in which
  the ratio of the lengths of an optimal Traveling Salesman path
  and a minimum spanning tree can be arbitrarily close to~2.
\end{abstract}

%jalg
%\newpage

\section{Introduction}
Given a complete graph with edge weights satisfying the triangle inequality,
%samir3: added , in prev line
and a degree bound for each vertex,
we consider the problem of computing a low-weight spanning tree
in which the degree of each vertex is at most its given bound.
In general, it is NP-hard to find such a tree.
%rbk2 -- Are all these citations relevant?
There are various practical motivations: the problem arises in the
context of VLSI layout and  %~\cite{Ha,Le,PL}
%rbk2 (see~\cite{BGMRZ,Ha,Le,PL}) and
network design~\cite{Gv,MSh,St}
%rbk2 (see~\cite{Gv,Go,Pr})
(such as in the Bellcore software {\em FIBER OPTIONS}, used for
designing survivable optimal fiber networks).
%rbk2 (see~\cite{B,MSh,St}.
%rbk2 -- our algorithm cuts the degree by a half, and saves a constant
%factor in the running time.  So the following sentence was deleted.
%It also plays a role in the context of heuristics for other optimization
%problems where the running time depends on the maximal degree of a minimum
%spanning tree (see~\cite{BGMRZ,GP,KR,Le}).
The special case of only one vertex with a degree-constraint
has been examined~\cite{Ga,GT,GlKl}; 
a polynomial time algorithm for the case of a fixed number of
nodes with a constrained degree was given by Brezovec et al.~\cite{BCG}. 
Computational results for
some heuristics for the general problem are presented
in~\cite{NH,SaVo,Vo}.
%rbk2 replaced the following sentence -- too conversational.
\iffalse
More recently, new attention has been directed at geometric
aspects of the problem, mostly motivated by the (still unanswered)
question raised
in~\cite{PV}: ``Is it hard to find a small weight spanning tree for a set
of points in the Euclidean plane, such that no point has degree
higher than 4?'' Some geometric aspects are
considered in~\cite{KRY},~\cite{MS},~\cite{RS}; we will get back to these
later.
\fi
Papadimitriou and Vazirani~\cite{PV} raised the problem of finding the
complexity of computing a minimum-weight degree-4 spanning tree of
points in the plane.  Some geometric aspects are
considered in~\cite{KRY,MS,RS}.

%rbk4 added an objective to the following paragraph.
In this paper, we consider modifying a given spanning tree $T$,
to meet the degree constraints without increasing its weight considerably.
We introduce a novel network-flow based algorithm
that does this optimally in the following sense:
if for some algorithm a worst-case performance guarantee
can be proved that is solely
a function of the topology and edge weights of $T$,
then that performance guarantee also holds for our algorithm.
We prove this by showing that our algorithm
finds the {\em optimal} solution for graphs in which
the weight of each edge $(u,v)$
equals the cost of the $u\leadsto v$ path in $T$.

We also show the following more concrete performance guarantee:
If the degree constraint $\goal(v)$ for each $v$ is at least $2$,
our algorithm finds a tree whose weight is at most
%rbk4 removed "the" after "of".
the weight of $T$ times
$$2 - \min\Big\{\frac{\goal(v)-2}{\degree_T(v)-2} : \degree_{T}(v)>2\Big\},$$
where $\degree_T(v)$ is the initial degree of $v$.
For instance, the degree of each vertex $v$ can be reduced by
nearly half, to $1+\lceil\degree_T(v)/2\rceil$, without increasing
the weight of the tree by more than $50 \%$.
(For comparison,
note that a factor of 2 is straightforward with standard shortcutting
techniques.)
%rbk2 -- no need for a separate para for one line.
We also describe {\em linear-time} algorithms that achieve this ratio.

This performance guarantee is optimal in the sense that for any $D\ge d \ge 2$,
if $T$ is a complete rooted $(D-1)$-ary tree with unit edge weights
and the edge weights in $G$ are those induced by paths in $T$,
then the weight of any spanning tree with maximum degree $d$ is at least
the weight of $T$ times $2- \frac{d-2}{D-2} - o(1)$.

The restriction $\goal(v) \ge 2$ is necessary to obtain constant
performance bounds.
Consider the case when $T$ is a simple path of unit weight edges, with
the remaining edge weights again induced by $T$.
Any spanning tree in which all but one vertex has degree one
%rbk2 -- What does a "linear" factor mean?
%is heavier by a linear factor.
is heavier than $T$ by a factor of $\Omega(n)$, the number of vertices in $T$.

For many metric spaces, graphs induced by points in the space
have minimum spanning trees of bounded maximum degree.
In such cases our algorithms can be used to find
spanning trees of even smaller degree
with weight bounded by a factor strictly smaller than 2 times
the weight of a minimum spanning tree (MST).
For example, in the $L_1$ metric,
a degree-4 MST can be found~\cite{RS},
so that we can find a degree-3 tree with weight at most $1.5$
times the weight of an MST.
We discuss similar results for the $L_1$, $L_2$, and $L_\infty$ norms.
For some of these norms, this improves the best current performance guarantees.

Finally, we disprove the following conjecture of \cite{KRY2}:
``In Euclidean graphs, perhaps a Traveling Salesman path
of weight at most $(2-\eps)$ times the minimum spanning-tree
weight always exists...''

%rbk2 -- The following line makes everything cited above look unrelated.
%\paragraph{Related Work:}
Our algorithms modify the given tree by performing a sequence of {\em
adoptions}.
Our polynomial-time algorithm performs an optimal sequence of adoptions.
Adoptions have been previously used
to obtain bounded-degree trees in weighted graphs~\cite{KRY,RMRRH,Sal}.
The main contributions of this paper are a careful analysis
of the power of adoptions and a network-flow technique
for selecting an optimal sequence of adoptions.
The method yields a stronger performance guarantee
and may yield better results in practice.
The analysis of adoptions shows that different
techniques will be necessary if better bounds are to be obtained.

%jalg
%\newpage

In the full version of their paper, Ravi et al.~\cite[Thm.~1.9]{RMRRH}
(if slightly generalized and improved\footnote{To obtain the improved bound
one has to change the proof slightly by
upper bounding $c(v_1v_2) - c(vv_2)$ by $c(v v_1)$ and not $c(v v_2)$
as is done in \cite{RMRRH}.})
gave an algorithm with a performance guarantee of
\[ 2- \min\left\{\frac{\goal(v)-2}{\degree_T(v)-1}
        : v\in V, \degree_{T}(v)>2\right\}
\]
provided each $\goal(v) \ge 3$.
The performance guarantee of our algorithm is better.

In Euclidean graphs (induced by points in $\real^d$),
minimum spanning trees are known to have bounded degree.
For such graphs, Khuller, Raghavachari and Young~\cite{KRY}
%rbk changed `degree-three' with `degree-3' since it reads better.
gave a linear-time algorithm to find a degree-3 spanning tree
of weight at most $5/3$ times the weight of a minimum spanning tree.
For points in the plane, the performance guarantee of their algorithm
improves to $1.5$; if the tree is allowed to have degree four,
the ratio improves further to $1.25$.

In unweighted graphs, F\"urer and Raghavachari \cite{FR}
gave a polynomial-time algorithm to find a spanning tree
of maximum degree exceeding the minimum possible by at most one.
In arbitrary weighted graphs, Fischer \cite{Fi} showed
that a minimum spanning tree
with maximum degree $O(\delta^*+ \log n)$ can be computed in polynomial time,
where $\delta^*$ is the minimum maximum degree
of any minimum spanning tree.  He also provided an algorithm
that finds a minimum spanning tree with degree
$k(\delta^*+1)$ where $k$ is the number of distinct edge weights.


\section{Adoption}
Fix the graph $G=(V,V\times V)$
and the edge weights $w:V\times V\rightarrow \real$.
The algorithm starts with a given tree $T$
and modifies it by performing a sequence of {\em adoptions}.
%rbk2 -- no need to name the output.
%to obtain the final tree $T'$.
The adoption operation (illustrated in Figure~\ref{adopt}) is as follows:

\begin{tabAlgorithm}{$\mbox{\sc Adopt}(u,v)$}
  \algnono {\bf Precondition:}
  Vertex $v$ has degree at least two in the current tree.
  \algline Choose a neighbor $x$ of $v$ in the current tree
  other than the neighbor on the 
%jalg
\algnono current $u\leadsto v$ path.
  \algline Modify the current tree by replacing edge $(v,x)$ by $(u,x)$.
\end{tabAlgorithm}

\begin{figure}[ht]
  \begin{center}
%    \leavevmode
    \input{adopt}
  \end{center}
  \caption{Vertex $u$ {\em adopts} a neighbor of $v$}
  \label{adopt}
\end{figure}

%rbk4 added the following:
The effect of $\mbox{\sc Adopt}(u,v)$ is that $u$ adopts a neighbor of
$v$.  For the purpose of the algorithm, it makes no difference which
neighbor of $v$ is adopted, since the differences in cost are hidden
by assigning $w(u,v)$ as the cost of the adoption as shown below.
%
$\mbox{\sc Adopt}(u,v)$ decreases the degree of $v$ by one,
at the expense of increasing the degree of $u$ by one
and increasing the weight of the tree by $w(x,u) - w(x,v) \le w(u,v)$.

%samir3 added the foll comment..

\noindent
{\bf Comment:} In practice, we would wish to optimize the choice of
neighbor of $v$ we choose to be adopted, as this changes the weight
of the tree found. 

%\newpage

\subsection{The Adoption Network}
\begin{definitions}
  The {\em deficit}\/ of vertex $v$ with respect to $T$
  is $\degree_T(v)-\goal(v)$.
%jalg
%\\
  Starting with a given tree, consider a sequence of adoptions
  $\mbox{\sc Adopt}(u_1,v_1),\mbox{\sc Adopt}(u_2,v_2),\ldots$
  \begin{itemize}
  \item The sequence is {\em legal}\/ if the precondition
    for each adoption is met.

%rbk2 -- "children" below is defined only if the tree is rooted.  Any
%ideas on how to fix it without making it long?
\iffalse
  \item A sequence is {\em feasible}\/ if, for each vertex,
    the number of times its children are adopted,
    minus the number of times it adopts other vertices,
    is at least its deficit.
\fi
  \item A sequence is {\em feasible}\/ if, for each vertex,
%rbk4 replaced "change" by "decrease" and switched "old" and "new"
    the decrease in its degree, i.e., its old degree minus its new degree,
    is at least its deficit.

  \item The {\em cost}\/ of the sequence is $\sum_i w(u_i,v_i)$.

  \end{itemize}
\end{definitions}

The legal, feasible adoption sequences
are precisely those that yield a tree
meeting the degree constraints.
The cost of a sequence is an upper bound
on the resulting increase in the weight of the tree.
Our goal is to find a feasible legal sequence of minimum cost.
For brevity, we call such a sequence a minimum-cost sequence.

The problem reduces to a minimum-cost flow problem \cite{AMO} in a flow network
that we call the {\em adoption network}\/ for $T$.
The adoption network is defined as follows.
Starting with $G$, replace each edge $(u,v)$
by two directed edges $(u,v)$ and $(v,u)$,
each with cost $w(u,v)$ and infinite capacity.
Assign each vertex a demand equal to its deficit.

%rbk4 removed "non-negative" requirement from flows.
A {\em flow}\/ is an assignment of a real value
(called the flow on the edge) to each edge of the network.
%rbk5 added following sentence. (QQQQQQ)
The flow satisfies the following property, known as {\em skew
symmetry}~\cite{AMO}: $f(u,v) = -f(v,u)$ for any edge $(u,v)$.
For each vertex $v$, the {\em surplus}\/ at $v$
is the net flow assigned to incoming edges
minus the net flow assigned to outgoing edges.
%rbk5 added following sentence.
Only edges with positive flow are considered in computing the surplus
flow into a vertex.
A flow is {\em legal}\/ if the surplus at each vertex
is at most one less than its degree.
A flow is {\em feasible}\/ if the surplus at each vertex
is at least its demand.
The {\em cost}\/ of the flow is the sum, over all edges,
of the cost of the edge times the flow on the edge.

%rbk2 rewrote the first sentence.
%It is well known \cite{AMO} that (because the demands are integers)
%there exists an integer-valued minimum-cost feasible flow.
Since the demands are integers,
there exists an integer-valued minimum-cost feasible flow~\cite{AMO}.
%rbk3
Assuming that each degree constraint is at least 1,
%samir3 changed their to there in next line
there exists such a flow that is also legal.
For brevity, we call such a flow a minimum-cost flow.

%rbk2 added enumerate.
\begin{lemma} \label{correspondence-lemma}
The following statements are true:
\begin{enumerate}
  \item
  The adoption sequences correspond to integer-valued flows.
  The correspondence preserves legality, feasibility, and cost.
  \item
  The integer-valued flows correspond to adoption sequences.
  The correspondence preserves legality and feasibility;
  it does not increase cost.
\end{enumerate}
\end{lemma}
\begin{proof}
  Given a sequence of adoptions,
  the corresponding flow $f$ assigns a flow to each edge $(u,v)$
  equal to the number of times $u$ adopts a neighbor of $v$.
  It can be verified that this correspondence
  preserves legality, feasibility, and cost.

  Conversely, given an integer-valued flow $f$,
  modify it if necessary (by canceling flow around cycles)
  so that the set of edges with positive flow is acyclic.
  This does not increase the cost.
  Next, order the vertices so that, for each directed edge $(u,v)$
  with positive flow, $u$ precedes $v$ in the order.
  Consider the vertices in reverse order.
  For each vertex $u$, for each edge $(u,v)$ with positive flow,
  have $u$ adopt $f(u,v)$ neighbors of $v$.
%rbk4  -- referee wanted this.  Should we move the explanation to the
%prelude of the lemma?
Note that when an edge directed out of a vertex $v$ is processed by
{\sc Adopt}, $v$'s degree increases by one.  Similarly when an edge
directed into $v$ is processed, $v$'s degree decreases by one.
The order imposed above processes all outgoing edges (in the flow) of
a vertex before it processes any of its incoming edges.  Hence during
the course of the algorithm, $v$'s degree initially increases when its
outgoing edges are processed and subsequently decreases as its
incoming edges are processed.  Therefore, when {\sc Adopt} processes
an edge $(u,v)$, the precondition imposed by the procedure that $v$'s
degree be at least 2 always holds.
%rbk4 changed "this" to "the above"
  It can be verified that the above sequence of adoptions
  preserves legality and feasibility
  and does not increase cost.
\end{proof}

%% ney - moved this section up, linear-time algorithms still later though
\section{Polynomial-Time Algorithm}
An acyclic, integer, minimum-cost flow can be found in polynomial time~\cite{AMO}.
%rbk[Q] -- we should add a reference here. OK. samir
%rbk2 deleted using standard algorithms 
The corresponding legal, feasible adoption sequence
can be performed in polynomial time
as described in the proof
of the second part of Lemma~\ref{correspondence-lemma}.
This gives a polynomial-time algorithm.

%% ney - added subsection here, replacing sandor's later proof
\subsection{Optimality in Tree-Induced Metrics}
The following lemma shows that this algorithm is optimal
among algorithms that examine only the weights of edges
of the given tree.

\begin{lemma} \label{tree-optimal-lemma}
Given a weighted graph $G=(V,E)$ and a spanning tree $T$
such that the weight of each edge in $G$ equals
the weight of the corresponding path in $T$,
a minimum-cost sequence of adoptions yields an optimal tree.
\end{lemma}
\begin{proof}
%samir2 -- I havent changed it yet, isnt d_T(S) better than deg_T(S)?
  %%ney2 -- do you mean everywhere?  I'd go for that, yes.
  %% i like D(v) and d(v) for the initial and desired degrees
  %% or perhaps d(v) and d'(v) (yes, redefining \degree and \goal)
%rbk4 : referee wants many changes in this proof.  I have copied the
%old proof to the end of the file.  I am not marking individual changes.
Fix an optimal tree.
Note that the degree of $v$ in the optimal tree is at most
$\goal(v)$;  let it be ${\rm d}^*(v)$.
%rbk5 changed \goal(S) to d^*(S).
For each subset $S$ of vertices, let $\degree_T(S)$ and ${\rm d}^*(S)$
denote the sum of the degrees of vertices in $S$ in $T$ and in the optimal
tree, respectively.
Define a flow on the edges of $T$ as follows:
%rbk5 changed \goal(S_u) to d^*(S_u).
for each edge $(u,v)$ in $T$, let $f(u,v) = {\rm d}^*(S_u)-\degree_T(S_u)$,
where $S_u$ is the set of vertices that are reachable from $u$ using
edges in $T$ other than $(u,v)$.
Note that $f(u,v) = -f(v,u)$.  Intuitively, a negative flow of $x$
units from $u$ to $v$ means that $x$ units of flow go from $v$ to $u$.
This is known as the {\em skew symmetry} property of flows~\cite{AMO}.
Inductively it can be shown that for each vertex $v$,
the net flow into it is $\degree_T(v) - {\rm d}^*(v)$,
so that the adoption sequence determined by the flow $f$
achieves a tree with the same degrees as the optimal tree.

We will show that the cost of the flow, and therefore the cost
of the adoption sequence, is at most the difference in the weights
of the two trees.  This implies that the tree obtained by the adoption
sequence is also an optimal tree.

To bound the cost of the flow, we claim that the flow is ``necessary''
in the following sense:
for each edge $(u,v)$ in $T$, at least $f(u,v)+1$ edges in the optimal tree
%rbk3 -- Hmmmm. I know it is the same, but what is S_v here later becomes S_u.
%have one endpoint in $S_v$ and the other in $V-S_v$.
have one endpoint in $S_u$ and the other in $V-S_u$.
To prove this,
%%ney2 redundant 'fix an edge $(u,v)$ in $T$.'
let $c$ be the number of edges in the optimal tree crossing the cut $(S_u,V-S_u)$.
Note that $\degree_T(S_u) = 2(|S_u|-1) + 1$.
Since the optimal tree is acyclic,
the number of edges in the optimal tree
with both endpoints in $S_u$ is at most $|S_u|-1$.
%rbk5 changed \goal(S_u) to d^*(S_u) in 2 lines.
Thus ${\rm d}^*(S_u) \le 2(|S_u|-1) + c = \degree_T(S_u)-1 + c$.
Rewriting gives $c \ge {\rm d}^*(S_u) - \degree_T(S_u) + 1 = f(u,v) + 1$.
This proves the claim.

%samir2 -- what about edges with 0 flow? Don't we want to charge them as well?
%In fact, the next line claims that they have been charged as well. 
%%ney (yes, fixed it)
To bound the cost of the flow, for each edge $(u,v)$,
charge $w(u,v)$ units to each edge in the optimal tree crossing
the cut $(S_u,V-S_u)$.
By the claim, at least the cost of the flow, plus the cost of $T$, is charged.
However, since the cost of each edge in the optimal tree
equals the weight of the corresponding path in $T$,
each edge in the optimal tree is charged at most its weight.
%rbk4 replaced "cost" by "weight" since trees have been defined to
%have only weight.  Costs have been given to flows.  Also the referee
%pointed out that "net charge" is undefined.  I have replaced it.
Thus, the total charge assigned to the edges
is bounded by the weight of the optimal tree.
\end{proof}

%%ney2 - added comment
Note that given the exact degrees of the desired tree
(for instance, if the degree constraints sum to $2(|V|-1)$),
the optimal flow in Lemma~\ref{tree-optimal-lemma}
can be computed in linear time.

%% ney - reorganized this a bit... (hope it's okay! :-)
\subsection{Worst-Case Performance Guarantee}
%rbk2 made the following a theorem since it is the main result of the paper.
The next theorem establishes a worst-case performance guarantee for
the algorithm in general graphs satisfying the triangle inequality.
\begin{theorem} \label{performance-theorem}
Given a graph $G=(V,E)$ with edge weights satisfying the triangle inequality,
a spanning tree $T$, and, for each vertex $v$, a degree constraint $\goal(v) \ge 2$,
the algorithm produces a tree whose weight is at most the weight of $T$ times
\begin{displaymath}
%samir2 (changed 1 to 2)
%1- \min\left\{\frac{\goal(v)-2}{\degree_T(v)-2} : v\in V, \degree_{T}(v)>2\right\}.
2- \min\left\{\frac{\goal(v)-2}{\degree_T(v)-2} : v\in V, \degree_{T}(v)>2\right\}.
\end{displaymath}
\end{theorem}
\begin{proof}
The increase in the cost of the tree
is at most the cost of the best sequence.
By Lemma~\ref{correspondence-lemma}, 
this is bounded by the cost of the minimum-cost flow.
%rbk2 -- What does "flow of bounded cost" mean?
%We exhibit a fractional feasible, legal flow of bounded cost.
We exhibit a fractional feasible, legal flow whose cost is
appropriately bounded.
The minimum-cost flow is guaranteed to be at least as good.

  Root the tree $T$ at an arbitrary vertex $r$.
  Push a uniform amount of flow along each edge towards the root
  as follows.  Let $p(v)$ be the parent of each non-root vertex $v$.
  For a constant $c$ to be determined later, define
  \begin{displaymath}
    f(u,v) = \cases{c & if $v = p(u)$ \cr 0 & otherwise.}
  \end{displaymath}
  The cost of the flow is $c$ times the weight of $T$.
  Let $v$ be any vertex.
  The surplus at $v$ is at least $c(\degree_T(v)-2)$.
  We choose $c$ just large enough so that the flow is feasible.

  There are three cases.
  If $\degree_T(v) = 1$,
  the deficit at $v$ will be satisfied provided $c \le 1$ and $\goal(v)\ge 2$.
  If $\degree_T(v) = 2$,
  the deficit at $v$ will be satisfied provided $\goal(v)\ge 2$.
  For $\degree_T(v) > 2$, the deficit will be satisfied provided
  \begin{displaymath}
    c \ge \frac{\degree_T(v)-\goal(v)}{\degree_T(v)-2}
    = 1-\frac{\goal(v)-2}{\degree_T(v)-2}.
  \end{displaymath}
  Thus, taking
  \begin{displaymath}
    c = 1- \min\left\{\frac{\goal(v)-2}{\degree_T(v)-2}
                         : v\in V, \degree_{T}(v)>2\right\}
  \end{displaymath}
  gives the result.
\end{proof}

%% ney - added following section from parts of Sandor's separate write-up
%% ney - Sandor, I tried a simpler write-up and took out your (beautiful!)
%% ney - picture, see what you think... if you prefer I'll put it back as it was!

\section{Optimality of Performance Guarantee}
In this section, we show that the worst-case performance guarantee established
in Theorem~\ref{performance-theorem} is the best 
%rbk2 -- I didn't like "of that form that is"
obtainable.

\begin{lemma}
Consider an $n$-vertex weighted graph $G$ with a spanning tree $T$
such that the weight of each edge in $T$ is $1$ and
the weight of each remaining edge
is the weight of the corresponding path in $T$.
%samir2 added parens
%%ney2 changed \degree and \deg to D and \goal to d for this lemma
If $T$ corresponds to a complete rooted $(D-1)$-ary tree of depth $k$,
then the weight of any spanning tree with maximum degree $d$ is at least
the weight of $T$ times
\begin{displaymath}
2- \frac{d-2}{D-2} - o(1),
\end{displaymath}
where $o(1)$ tends to $0$ as $n$ grows. 
\end{lemma}
\begin{proof}
%rbk4: several changes in this proof that the referee asked.
%S_i are the vertices at distance at most i from the root.
%k is undefined.  The flow in Lemma 2 needs to be generalized to
%handle arbitrary cuts instead of cutting a single edge in the tree.
%The algebra needs some fixing too.  Old proof copied to the end.
%samir3  I made changes on top of Balaji's changes!
Fix any spanning tree $T'$ of maximum degree $d$.
Let $S_i$ denote the vertices at distance at most $i$ from the root in $T$.
The flow on the edges of $T$ corresponding to $T'$, as defined in
Lemma~\ref{tree-optimal-lemma}, can be generalized to arbitrary cuts
$(V-S,S)$ in the tree, and it can be shown that the flow crossing this
cut is at least $\degree_{T}(S) - \degree_{T'}(S)$.
For any $i<k$, the cut $(V-S_i,S_i)$ is crossed by at least
$|S_i|(D-d)-1$ units of flow.
Thus the total cost of the flow is at least $\sum_{i=0}^{k-1}(|S_i|(D-d)-1)$.
The cost of $T$ is $|S_k|-1$, which can be written as
$\sum_{i=0}^{k-1} |S_{i+1}|-|S_i|$.
It can be verified that $|S_{i+1}|-|S_i| = |S_i|(D-2) + 1$.
Hence the ratio of the cost of the flow to the cost of $T$ is at least
%rbk5 added () around denominator.
$$\frac{\sum_{i=0}^{k-1}(|S_i|(D-d)-1)}{\sum_{i=0}^{k-1}(|S_i|(D-2)+1)}.$$
On simplification, it can be seen that the ratio is
at least $(D-d)/(D-2) - o(1)$.
Since the ratio of the cost of $T'$ to the cost of $T$
is $1$ more than this, the result follows.
\end{proof}

%% ney - added this observation
Next we observe that the $\goal(v) \ge 2$ constraint 
%samir2 -- should we not say what the constraint is? (>=2), havent made the 
%change
is necessary to obtain any constant performance guarantee:

%rbk2 spotted a strange lemma; looks more like a proof to me. :-)
\begin{lemma}
Consider an $n$-vertex weighted graph $G$ with a spanning tree $T$
such that the weight of each edge in $T$ is $1$ and
the weight of each remaining edge
is the weight of the corresponding path in $T$.
If $T$ corresponds to a path of length $n$ with endpoint $r$,
then the weight of any spanning tree in which each vertex other than $r$
has degree $1$ is at least the weight of $T$ times $n/2$.
\end{lemma}
The proof is straightforward.

%\newpage

\section{Linear-Time Algorithms}
Note that to obtain the worst-case performance guarantee
a minimum-cost flow is not required.
It suffices to find a feasible integer flow
of cost bounded by the cost of the fractional flow $f$
defined in the proof of Theorem~\ref{performance-theorem}.
We describe two methods to find such a flow,
and to implement the corresponding sequence of adoptions,
in linear time.

\paragraph{Algorithm 1:}
%rbk4 added motivation as asked by the referee:
The first algorithm exploits the special structure of the flow in the
proof of Theorem~\ref{performance-theorem} to construct an integral
flow without solving the flow problem to optimality.  Observe that the
flow along each edge of the tree is the same ($c$ units).  Since the
graph satisfies the triangle inequality, flow along a path of more
than a single edge can be replaced by a single edge that connects the
end vertices of the path without increasing the total cost of the
flow.  This ensures that all of the fractional flows are sent from the
sources to the destinations directly.  The following greedy rounding scheme finds
an integral flow that is no more expensive than the fractional flow.

Let $f$ be the fractional flow defined in Theorem~\ref{performance-theorem}.
Modify $f$ by repeatedly performing the following short-cutting step:
choose a maximal path in the set of edges with positive flow;
replace the ($c$ units of) flow on the path
by ($c$ units of) flow on the single new edge $(u,v)$,
where the path goes from $u$ to $v$.
%samir2 changed the sentence
%Record for later the child $q(u)$ of $v$ on the path.
Let $q(u)$ be the child of $v$ on the path.
Stop when all paths have been replaced by new edges.
This phase requires linear time,
because each step requires time
proportional to the number of edges short-cut.

In the resulting flow, the only edges with positive flow
are edges from leaves of the (rooted) tree $T$ to interior vertices.
Round the flow to an integer flow as follows.
Consider each vertex $v$ with positive deficit, say $D$.
Using a linear-time selection algorithm,
among the edges $(u,v)$ sending flow to $v$,
find the $D$ smallest-weighted edges.
Assign one unit of flow to each of these $D$ edges.
The resulting flow is integer-valued, feasible, legal, and has cost
bounded by the cost of $f$.
This phase requires linear time.

Assume that each vertex maintains a doubly linked list of its children.
Given a pointer to any vertex, we can obtain its sibling in constant
time. As adoptions are done, this list is maintained dynamically.
Perform the adoptions corresponding to the flow in any order:
for each edge $(u,v)$ with a unit of flow,
%samir2 -- what if the right sibling doesnt exist? Perhaps you are assuming
% a circular list of siblings -- should we say that?
have $u$ adopt the right sibling of $q(u)$ (in the original tree $T$).
The tree remains connected because $\goal(v) \ge 2$,
so at least one child of $v$ is not adopted.

\paragraph{Algorithm 2:}
Consider the following restricted adoption network.
Root the tree $T$ as in the proof of Theorem~\ref{performance-theorem}.
Direct each edge $(u,v)$ of the tree towards the root.
(Non-tree edges are not used.)
Assign each edge a capacity of 1 and a cost equal to its weight.
Assign each vertex a demand equal to its deficit.

We show below that an integer-valued minimum-cost flow
in this network can be found in linear time.
Because the fractional flow
defined in the proof of Theorem~\ref{performance-theorem}
is a feasible legal flow in this network,
the minimum-cost flow that we find is at least as good.

Find the flow via dynamic programming.
For each vertex $v$,
consider the subnetwork corresponding to the subtree rooted at $v$.
Let $C_j(v)$ denote the minimum cost of a flow in this subnetwork
such that the surplus at $v$ exceeds its demand $D$ by $j$, for $j=0,1$.
%rbk4 added a note why j=0,1 is sufficient as asked by the referee.
Since the flow problem has been restricted to the tree, with a
capacity constraint of 1 on all the edges, there is no need to
consider flow surpluses greater than 1 at any vertex.
For each child $u$ of $v$,
let $\delta(u)$ denote $w(u,v)+C_1(u)-C_0(u)$ ---
the additional cost incurred for $v$ to obtain
a unit of flow along edge $(u,v)$.
Let $U_j$ denote the $D+j$ children with smallest $\delta(u)$, for $j=0,1$.
Then, for $j=0,1$,
$$C_j(v) = \sum_{u\in U_j} \delta(u) + \sum_u C_0(u).$$
Using this equation, compute the $C_j$'s bottom-up in linear time.
The cost of the minimum-cost flow in the restricted network
is given by $C_0(r)$, where $r$ is the root.
The flow itself is easily recovered in linear time.

To finish, shortcut the flow as in
the first phase of the previous algorithm
and perform the adoptions as in the last phase of that algorithm.

%rbk3 replaced "Geometric Questions" by
\section{Geometric Problems}
Our general result has several implications for cases of particular
distance functions where it is possible to give a priori bounds on the
maximum degree of an MST.
For the case of $L_2$ distances in the plane,
there always is an MST of maximum degree 5~\cite{MS};
for the case of $L_1$ or $L_{\infty}$ distances
there always exists a
MST of maximum degree $4$~\cite{MS,RS}.
Without using any specific structure of the involved distance functions,
we note as a corollary:

\begin{corollary}
\label{geo}
%rbk2 -- looks like T_3 abd T_{\min} are used for the first time here.
Let $T_{\min}$ be an MST and $T_k$ be a tree whose maximal degree is
at most $k$.
For $L_1$ or $L_{\infty}$ distances in $\real^2$, we get a degree-3
tree $T_3$ with
\begin{itemize}
\item $w(T_3)<\frac{3}{2}w(T_{\min})$.
\end{itemize}
\end{corollary}

\noindent
For the case of Euclidean distances in the plane, we get bounded degree
trees that satisfy
\begin{itemize}
\item $w(T_3)<\frac{5}{3} w(T_{\min})$
\item $w(T_4)<\frac{4}{3} w(T_{\min})$.
\end{itemize}
%% ney2 ``These bounds'' was ambigous.. also ``the ratios'' -> ``those''
The latter two bounds are worse than those shown by
Khuller, Raghavachari and Young~\cite{KRY}
%%ney2 ``which used more of the special geometry of point''
using the geometry of point
arrangements. (It was shown that $\frac{3}{2}$ and $\frac{5}{4}$
are upper bounds.) We conjecture that the following are
the optimal ratios:

\begin{conj}
\label{bounds}
For the case of Euclidean distances in the plane, we conjecture
that there exist bounded degree trees that satisfy
\begin{itemize}
%rbk added the expression for the fractions.
\item $\frac{w(T_3)}{w(T_{\min})}\leq \frac{\sqrt{2}+3}{4} \approx 1.103\ldots$
%rbk[Q] -- I am getting 1.035.  Could you please verify? I got the same, samir
% An algebraic expression (?) for sin(pi/10) is \sqrt{\frac{5-\sqrt{5}}{8}}.
% I found this very confusing, and so didn't use it below.
%\item $\frac{w(T_4)}{w(T_{\min})}\leq 1.070\ldots$
%safe - 1.035 is correct, I also have that in some old notes. No idea
%       what happened.
\item $\frac{w(T_4)}{w(T_{\min})}\leq \frac{2\sin(\frac{\pi}{10})+4}{5}
                                        \approx 1.035\ldots$
\end{itemize}
For $L_1$ and $L_{\infty}$ distances in $\real^2$, we conjecture
\begin{itemize}
\item $\frac{w(T_3)}{w(T_{\min})}\leq\frac{5}{4}$
\end{itemize}
\end{conj}

%rbk4 -- modified the statement below to address the referee's concern
%that the best known and worst known are the same!
%The best known lower bounds (yielding the ratios
The worst examples we know (matching the ratios
%
of Conjecture~\ref{bounds}) are shown in Figure~\ref{best}.
%safe - added the following note)
(Note that the example for $L_{\infty}$ metric is obtained
by rotating the arrangement in (c) by 45 degrees.)
%rbk[Q] -- picture does not show an example for L_\infty metric.  Samir
%pointed out that the example for L_1 can be rotated by 45 degrees to
%get the 5/4 example for L_\infty.  Should we mention this fact or
%include the picture in the figure?

\fig{figs/best.eps}{best}{The worst known examples for:
(a) $\frac{w(T_3)}{w(T_{\min})}$, $L_2$ distances
\newline\hspace*{2.79in}(b) $\frac{w(T_4)}{w(T_{\min})}$, $L_2$ distances
\newline\hspace*{2.79in}(c) $\frac{w(T_3)}{w(T_{\min})}$, $L_1$
distances.}{2.5in}

\vspace{1ex}
\subsection{Geometric Hamiltonian Paths}
We conclude this paper by settling a question
raised in~\cite{KRY2}, in the negative:

{\em ``In Euclidean graphs, perhaps a Traveling Salesman path
of weight at most $(2-\eps)$ times the minimum spanning-tree
weight always exists and can be found in polynomial time.''}

\begin{theorem}
\label{T2}
For an arrangement of points in the plane with Euclidean
distances, the ratio $\frac{w(T_2)}{w(T_{\min})}$
can be arbitrarily close to 2.
\end{theorem}



\fig{figs/T2.new.bw.eps}{T2.bw}{A class of examples showing 
$\frac{w(T_2)}{w({T_{\min}})}\rightarrow 2$}{2.0in}


\begin{proof}
%rbk2 moved "(See Figure~\ref{T2.bw}.)".
Let $n$ and $k$ be sufficiently large.
Construct a point set as follows (see Figure~\ref{T2.bw}):


Take base points at $(0,0)$ and $(2n^k,0)$.

%sandor: Added "base points" to make the spanning tree more obvious
%For $j=0,\ldots, k$, add points (called {\em level} $j$ points) as follows:
For $j=0,\ldots, k$, add points as follows:

\ \ For $i=1,\ldots, n^j$

%\ \ \ \ Add point $i$ at $((2i-1)n^{k-j},n^{k-j})$.
%sandor: Added "base points" to make the spanning tree more obvious
\ \ \ \ Add {\em level} $j$ point at $((2i-1)n^{k-j},n^{k-j})$;

\ \ \ \ add {\em base} point at $((2i-1)n^{k-j},0)$.

The  points at level $j$, i.e., at height $n^{k-j}$, have nearest neighbors at
distance at least $n^{k-j-1}(n-1)$. To prove the lower bound,
we draw a circle centered at each point at level $j<k$. For the points
%sandor regrouped the writing of the radii
at level $j$, the radius of the circle is $(n^{k-j-1}(n-2))$.
The circles corresponding to two points do not intersect.
Since each point has degree two in a Hamilton cycle, twice the sum of the
radii of the circles gives us a lower bound on the length of the
Hamilton cycle. This can be computed as follows (observe that we can
always pick $n \geq 2k$).
\[ 2 \sum_{j=0}^{k-1} n^j (n^{k-j-1}(n-2)) = 2 k n^{k-1}(n-2)
\geq 2 (k-1)n^k .\]
Since no edge can have
length more than $2n^k$, we conclude that no Hamilton {\em path}
can have a weight smaller than $2 (k-1)n^k-2n^k = 2(k-2) n^k$.

%rbk2 deleted one more "easy" item.   It is easy to find a
It can be verified that there is a tree of weight $(k+3)n^k$ that spans
the points. Hence this is an upper bound on the weight of $T_{\min}$.
%sandor: changed k+2 to k+3 to reflect the addition of base points.
It follows that $\frac{w(T_2)}{w(T_{\min})}>\frac{2(k-2)}{k+3}$,
which can be arbitrarily close to 2, concluding the proof.
\end{proof}



%% ney - changed wording from ``it is clear''
The above class of examples establishes
the same lower bound for $L_1$ and $L_{\infty}$
distances.
%samir3: did someone verify this? No reason why it shouldnt work, just 
% wanting to make sure someone checked this claim.



%\vspace*{0.7cm}

%\noindent
\section*{Acknowledgements}
We thank Joe Mitchell for establishing the transatlantic
connection between the authors.
We thank Chandra Chekuri for asking us about degree 3 trees
in the $L_1$ metric.

\input biblio.tex

\end{document}


%rbk4:  Here is the old Proof of Lemma 2:
%samir2 -- I havent changed it yet, isnt d_T(S) better than deg_T(S)?
  %%ney2 -- do you mean everywhere?  I'd go for that, yes.
  %% i like D(v) and d(v) for the initial and desired degrees
  %% or perhaps d(v) and d'(v) (yes, redefining \degree and \goal)
Fix an optimal tree.
Note that the degree of $v$ in the optimal tree is at most
$\goal(v)$;
assume without loss of generality that it is exactly $\goal(v)$.
For each subset $S$ of vertices, let $\degree_T(S)$ and $\goal(S)$
denote the sum of the degrees of vertices in $S$ in $T$ and in the optimal
tree, respectively.
Define a flow on the edges of $T$ as follows:
%samir2 I changed S_v to S_u -- i think thats what it should be.
%for each edge $(u,v)$ in $T$, let $f(u,v) = \goal(S_u)-\degree_T(S_v)$,
for each edge $(u,v)$ in $T$, let $f(u,v) = \goal(S_u)-\degree_T(S_u)$,
where $S_u$ is the set of vertices that are reachable from $u$ using
edges in $T$ other than $(u,v)$,
%%ney2 changed ``Note that $f(u,v) = -f(v,u)$.'' to:
provided $f(u,v)$ as defined is non-negative.
%% because before we defined flow as an assignment of non-neg wts to vertices
Inductively it can be shown that for each vertex $v$,
the net flow into it is $\degree_T(v) - \goal(v)$,
so that the adoption sequence determined by the flow $f$
achieves a tree with the same degrees as the optimal tree.

We will show that the cost of the flow, and therefore the cost
of the adoption sequence, is at most the difference in the weights
of the two trees.  This implies that the tree obtained by the adoption
sequence is also an optimal tree.

To bound the cost of the flow, we claim that the flow is ``necessary''
in the following sense:
for each edge $(u,v)$ in $T$, at least $f(u,v)+1$ edges in the optimal tree
%rbk3 -- Hmmmm. I know it is the same, but what is S_v here later becomes S_u.
%have one endpoint in $S_v$ and the other in $V-S_v$.
have one endpoint in $S_u$ and the other in $V-S_u$.
To prove this,
%%ney2 redundant 'fix an edge $(u,v)$ in $T$.'
let $c$ be the number of edges in the optimal tree crossing the cut $(S_u,V-S_u)$.
Note that $\degree_T(S_u) = 2(|S_u|-1) + 1$.
Since the optimal tree is acyclic,
the number of edges in the optimal tree
with both endpoints in $S_u$ is at most $|S_u|-1$.
Thus $\goal(S_u) \le 2(|S_u|-1) + c = \degree_T(S_u)-1 + c$.
Rewriting gives $c \ge \goal(S_u) - \degree_T(S_u) + 1 = f(u,v) + 1$.
This proves the claim.

%samir2 -- what about edges with 0 flow? Don't we want to charge them as well?
%In fact, the next line claims that they have been charged as well. 
%%ney (yes, fixed it)
To bound the cost of the flow, for each edge $(u,v)$,
charge $w(u,v)$ units to each edge in the optimal tree crossing
the cut $(S_u,V-S_u)$.
By the claim, at least the cost of the flow, plus the cost of $T$, is charged.
However, since the cost of each edge in the optimal tree
equals the weight of the corresponding path in $T$,
each edge in the optimal tree is charged at most its weight.
%rbk4 replaced "cost" by "weight" since trees have been defined to
%have only weight.  Costs have been given to flows.  Also the referee
%pointed out that "net charge" is undefined.  I have replaced it.
Thus, the total charge assigned to the edges
is bounded by the weight of the optimal tree.
%rbk4 -- end of proof of lemma 2.


%rbk4: Proof of Lemma 4:
Fix any spanning tree $T'$ of maximum degree $d$.
Let $S_i$ denote the vertices at distance $i$ from the root in $T$.
Consider the flow on the edges of $T$ corresponding to $T'$,
as defined in the proof of Lemma~\ref{tree-optimal-lemma}.
%rbk2 changed "The argument used in that proof" to
The proof
shows that at least $|S_i|(d-D)-1$
units of flow cross the cut $(V-S_i,S_i)$.
Thus the net cost of the flow is at least $\sum_{i=0}^{k-1}|S_i|(d-D)-1$.
The cost of $T$ is $\sum_{i=0}^{k-1} |S_{i+1}|-|S_i|$.
Since $|S_{i+1}| = |S_i|(D-1) + 1$,
so $|S_{i+1}|-|S_i| = |S_i|(D-2) + 1$,
the ratio of the cost of the flow to the cost of $T$ is at least
$$\frac{\sum_{i=0}^{k-1}|S_i|(d-D)-1}{\sum_{i=0}^{k-1} |S_i|(D-2)+1}.$$
Simplifying shows that the ratio is at least $(d-D)/(D-2) - o(1)$.
Since the ratio of the cost of $T'$ to the cost of $T$
is $1$ more than this, the result follows.
%rbk4 end of proof



>From samir@cs.umd.edu Tue Dec 10 17:11 CST 1996
Received: from birdy.cs.umd.edu (12208@birdy.cs.umd.edu [128.8.128.188]) by utdallas.edu (8.7.6/8.7.3) with ESMTP id RAA24466 for <rbk@utdallas.edu>; Tue, 10 Dec 1996 17:11:18 -0600 (CST)
Received: by birdy.cs.umd.edu (8.8.4/UMIACS-0.9/04-05-88)
        id SAA16135; Tue, 10 Dec 1996 18:05:06 -0500 (EST)
Date: Tue, 10 Dec 1996 18:05:06 -0500 (EST)
From: samir@cs.umd.edu (Samir Khuller)
Message-Id: <199612102305.SAA16135@birdy.cs.umd.edu>
To: fekete@zpr.uni-koeln.de, ney@cs.dartmouth.edu, rbk@utdallas.edu
Subject: hi
Content-Type: text
Content-Length: 47714
Status: R


Enclosed is the revised version of the paper. 
My changes are marked with %samir3. Please mark your changes
VERY CLEARLY so that it is easy for Balaji and me to find them
and check that we are happy with them.....If you are happy with the
paper, we will be happy to send it as it is! 

next email has the updated bibliography

Happy New Year!

PS: balaji leaves on Dec 25th for India. Lets get the paper
done before he leaves so it will not sit until end jan.

samir

---------------------------------------------------------------

cs0205050.extracted_bib
\begin{thebibliography}{CDNS}

\bibitem{AMO}
R.~K.~Ahuja, T.~L.~Magnanti and J.~B.~Orlin.
\newblock {\em Network flows (theory, algorithms and applications)}.
\newblock Prentice Hall, Englewood Cliffs, NJ, 1993.

\uncited{
\bibitem{BGMRZ}
T.~Barrera, J.~Griffith, A.~McKee, G.~Robins, and T.~Zhang.
\newblock Toward a Steiner engine: enhanced serial and parallel
        implementations of the iterated 1-Steiner algorithm.
\newblock {\em Proc.\ Great Lakes Symp.\ VLSI}.
\newblock Kalamazoo, MI, March 1993, pp.\ 90--94.
}

%rbk2 -- can we cite a software as a publication?
\uncited{
\bibitem{B}
Bellcore.
\newblock {\em FIBER OPTIONS}.
Software for designing survivable optimal fiber networks.
Software package, 1988.
}

%\bibitem{Be}
%J.~L.~Bentley.
%\newblock Communicated through David Johnson.

\bibitem{BCG}
C.~Brezovec, G.~Cornu\'ejols, F.~Glover.
\newblock A matroid algorithm and its application
to the efficient solution of two optimization
problems in graphs.
\newblock {\em Math.\ Programming} {\bf 42} (1988), pp.\ 471--487.

\bibitem{Fi}
T.~Fischer.
\newblock {\em Optimizing the degree of minimum weight spanning trees}.
\newblock Tech.\ Rep.\ 93-1338, Dept.\ of Computer Science,
        Cornell University, April 1993.

\bibitem{FR}
M.~F\"urer and B.~Raghavachari.
\newblock Approximating the minimum-degree Steiner tree to within one of
optimal.
\newblock  {\em J.\ Algorithms} {\bf 17} (1994), pp.\ 409--423.

\bibitem{Ga}
H.~N.~Gabow.
\newblock A good algorithm for smallest spanning trees with
    a degree constraint.
\newblock {\em Networks} {\bf 8} (1978), pp.\ 201--208.

\bibitem{GT}
H.~N.~Gabow and R.~E.~Tarjan.
\newblock Efficient algorithms for a family of matroid intersection problems.
\newblock {\em J.\ Algorithms} {\bf 5} (1984), pp.\ 80--131.

\bibitem{GJ}
M.~R.~Garey and D.~S.~Johnson.
\newblock {\em Computers and intractability: a guide to the
theory of NP-completeness}.
\newblock Freeman, San Francisco, CA, 1979.

\bibitem{Gv}
B.~Gavish.
\newblock Topological design of centralized
        computer networks --- formulations and algorithms.
\newblock {\em Networks} {\bf 12} (1982), pp.\ 355--377.

\uncited{
\bibitem{GP}
G.~Georgakopoulos and C.~H.~Papadimitriou
\newblock The 1-Steiner tree problem.
\newblock {\em J.~Algorithms}, {\bf 8} (1987), pp.\ 122--130.
}

\bibitem{GlKl}
F.~Glover, D.~Klingman.
\newblock Finding minimum spanning trees with a fixed number of links at
a node.
\newblock In: B.\ Roy (ed.), {\em Combinatorial Programming: Methods and
Applications}.
\newblock D.~Reidel Publishing Company, Dordrecht-Holland, 1975. pp.\ 191--201.

\uncited{
\bibitem{Go}
M.~C.~Goldstein.
\newblock Design of long-distance telecommunication networks
-- the Telepak problem.
\newblock {\em IEEE Trans.\ Circuit Theor.} CT-20 (1973), pp.\ 186--192.
}

\uncited{
\bibitem{Ha}
A.~C.~Harter.
\newblock {\em Three-dimensional circuit layout}.
\newblock Cambridge University Press, New York, 1991.
}

\uncited{
\bibitem{H}
J.~A.~Hoogeveen.
\newblock Analysis of Christofides' heuristic: some paths are
more difficult than cycles.
\newblock {\em Operations Research Letters}, {\bf 10}, 291--295, 1991.
}

\uncited{
\bibitem{KR}
A.~B.~Kahng and G.~Robins.
\newblock A new class of iterative Steiner tree heuristics
with good performance.
\newblock {\em IEEE Trans.\ Computer-Aided Design}, {\bf 11} (1992), 893--902.
}

\bibitem{KRY}
S.~Khuller, B.~Raghavachari and N.~Young.
\newblock Low degree spanning trees of small weight.
%\newblock {\em Proc.~of 26th Annual ACM Symp. on the Theory of
%Computing}, pp.~412--421, May 1994.
\newblock {\em SIAM J.\ Comput.} {\bf 25} (1996), pp.\ 355--368. 
%samir3 added full ref

\bibitem{KRY2}
S.~Khuller, B.~Raghavachari, N.~Young,
\newblock Balancing minimum spanning trees and shortest-path trees.
\newblock {\em Algorithmica} {\bf 14} (1995), pp.\ 305--321.

\uncited{
\bibitem{Le}
T.~Lengauer.
{\em Combinatorial algorithms for integrated circuit layout}.
B.~G.~Teubner, Stuttgart, 1990.  %, p.\ 281.
}

\bibitem{MSh}
C.~L.~Monma, D.~Shallcross.
\newblock Methods for designing communication networks with certain
two-connected survivability constraints.
\newblock {\em Oper.\ Res.} {\bf 37} (1989), pp.~531--541.

\bibitem{MS}
C.~L.~Monma, S.~Suri,
\newblock
 Transitions in geometric minimum spanning trees.
\newblock
 {\em Discrete \& Computational Geometry} {\bf 8} (1992), pp.\ 265--293.

\bibitem{NH}
S.~C.~Narula and C.~A.~Ho.
\newblock Degree-constrained minimum spanning tree.
\newblock {\em Comput.\ Ops.\ Res.} {\bf 7} (1980), pp. 239--249.

\bibitem{PV}
C.~H.~Papadimitriou, U.~V.~Vazirani,
\newblock
 On two geometric problems related to the traveling salesman problem.
\newblock
 {\em J. Algorithms} {\bf 5} (1984), pp.\ 231--246.

\uncited{
\bibitem{PL}
B.~T.~Preas and M.~J.~Lorenzetti.
{\em Physical design automation of VLSI systems}.
Benjamin/Cummings, Menlo Park, CA, 1988.
}

\uncited{
\bibitem{Pr}
R.~C.~Prim.
\newblock Shortest connection networks and some generalizations.
\newblock {\em Bell Systems Tech.~J.} {\bf 36} (1957), pp.\ 1389--1401.
}

%rbk2 -- do we really need to cite this twice?  After all RMRRH2 is a
%``manuscript'' which means that it is not really available.
\bibitem{RMRRH}
R.\ Ravi, M.\ V.\ Marathe, S.\ S.\ Ravi, D.\ J.\ Rosen\-krantz
        and H.\ B.\ Hunt\ III.
\newblock
Many birds with one stone: multi-objective approximation algorithms.
\newblock Manuscript.
\newblock A preliminary version appeared in
{\em Proc.~25th Annual ACM Symp. on the Theory of Computing},
pp.~438--447, May 1993.

\uncited{
\bibitem{RMRRH2}
R.\ Ravi, M.\ V.\ Marathe, S.\ S.\ Ravi, D.\ J.\ Rosen\-krantz
        and H.\ B.\ Hunt\ III.
\newblock
Many birds with one stone: multi-objective approximation algorithms.
\newblock
Manuscript (full version of 1993 STOC paper).
}

\bibitem{RS}
G.~Robins and J.~S.~Salowe.
\newblock Low-degree minimum spanning trees.
\newblock {\em Discrete and  Computational Geometry} {\bf 14} (1995),
                pp.\ 151--166.

\bibitem{Sal}
J.~S.~Salowe.
\newblock Euclidean spanner graphs with degree four.
%samir2 -- changed to upper case (DAM)
\newblock {\em Discrete Appl. Math.} {\bf 54} (1994), pp.\ 55--66.

\bibitem{SaVo}
M.~Savelsbergh and A.~Volgenant.
\newblock Edge exchanges in the degree-constrained minimum
 spanning tree problem.
\newblock {\em Comput.\ Ops.\ Res.} {\bf 12} (1985), pp.\ 341--348.

\bibitem{St}
M.~Stoer.
\newblock {\em Design of survivable networks}.
\newblock Lecture Notes on Mathematics \# 1531.
\newblock Springer, Heidelberg, 1992.

\bibitem{Vo}
A.~Volgenant.
\newblock A Lagrangean approach to the degree-constrained minimum
 spanning tree problem.
\newblock {\em Europ.\ J.\ Ops.\ Res.} {\bf 39} (1989), pp.\ 325--331.

\uncited{
\bibitem{Y}
Y.~Yamamoto.
\newblock The Held-Karp algorithm and degree-constrained
minimum 1-trees.
newblock {\em Mathematical Programming \/} {\bf 15} (1978), pp.\ 228--231.
}

\end{thebibliography}