  In this paper, we investigate the weighted tree augmentation problem (TAP),
where the goal is to augment a tree with a minimum cost set of edges such that
the graph becomes two edge connected. First we show that in weighted TAP, we
can restrict our attention to trees which are binary and where all the non-tree
edges go between two leaves of the tree. We then give two different top-down
coloring algorithms. Both algorithms differ from known techniques for a
3/2-approximation in unweighted TAP and current attempts to reach a
3/2-approximation for weighted TAP.
  The first algorithm we describe always gives a 2-approximation for any
feasible fractional solution to the natural edge cover LP. When the fractional
solution is such that all the edges with non-zero weight are at least $\alpha$,
then this algorithm achieves a $2/(1+\alpha)$-approximation. We propose a new
conjecture on extreme points of LP relaxations for the problem, which if true,
will lead to a constructive proof of an integrality gap of at most 3/2 for
weighted TAP. In the second algorithm, we introduce simple valid constraints to
the edge cover LP. In this algorithm, we focus on deficient edges, edges
covered to an extent less than 4/3 in the fractional solution. We show that for
fractional feasible solutions, deficient edges occur in node-disjoint paths in
the tree. When the number of such paths is at most two, we give a top-down
coloring algorithm which decomposes 3/2 times the fractional solution into a
convex combination of integer solutions. We believe our algorithms will be
useful in eventually resolving the integrality gap of linear programming
formulations for TAP.
  We also investigate a variant of TAP where each edge in the solution must be
covered by a cycle of length three. We give a $\Theta(\log n)$-approximation
algorithm for this problem in the weighted case and a 4-approximation in the
unweighted case.
