Coloring Down: 3/2-approximation for special cases of the weighted
tree augmentation problem∗

arXiv:1707.05240v1 [cs.DS] 17 Jul 2017

Jennifer Iglesias

†

R. Ravi‡

July 18, 2017

Abstract
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 of our algorithms differ from known
techniques for obtaining a 23 -approximation in unweighted TAP and current attempts to reach
a 32 -approximation for weighted TAP.
The first algorithm we describe always gives a 2-approximation starting from any feasible
fractional solution to the natural tree cut covering LP. When the structure of the fractional
solution is such that all the edges with non-zero weight are at least α, then this algorithm achieves
2
a 1+α
-approximation. We propose a new conjecture on extreme points of LP relaxations for the
problem, which if true, will lead to a potentially constructive proof of an integrality gap of at
most 23 for weighted TAP. In the second algorithm, we introduce simple extra valid constraints to
the tree edge covering LP. In this algorithm, we focus on deficient edges, edges which get covered
to an extent less than 43 in the fractional solution. We show that in the support of extreme
points for this LP, deficient edges occurs 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 23 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 (triangle). We give a Θ(log n)-approximation algorithm for this problem
in the weighted case and a 4-approximation in the unweighted case.

Keywords: approximation algorithms, tree augmentation, linear programming, spanning tree,
two-edge connectivity, LP rounding

∗
We would like to acknowledge Robert Carr and László Végh for their numerous discussions on this problem. In
addition, we would like to thank Sinziana Munteanu for her developments on the structure of the trees.
†
This material is based upon work supported by the National Science Foundation Graduate Research Fellowship
Program under Grant No. 2013170941.
‡
This material is based upon research supported in part by the U. S. National Science Foundation under award
number CCF-1527032.

1

1

Introduction

We consider the weighted tree augmentation problem (TAP): Given an undirected graph G = (V, E)
with non-negative weights c on the edges, and a spanning tree T , find a minimum cost subset of
edges A ⊆ E(G) \ E(T ) such that (V, E(T ) ∪ A) is two-edge-connected. We will call the elements
of E(T ) as (tree) edges and those of E(G) \ E(T ) as links for convenience. A graph is two-edge
connected if the removal of any edge does not disconnect the graph, i.e., it does not have any cut
edges. Since cut edges are also sometimes called bridges, this problem has also been called bridge
connectivity augmentation in prior work [10].
While TAP is well studied in both the weighted and unweighted case [10, 15, 20, 8, 4, 17, 1, 9],
it is NP-hard even when the tree has diameter 4 [10] or when the set of available links form a single
cycle on the leaves of the tree T [6]. Weighted TAP remains one of the simplest network design
problems without a better than 2-approximation. TAP can also be viewed as a covering problem.
The cuts in a tree which have a single edge crossing them are exactly the cuts that must be covered.
A link ℓ is said to cover an edge e if the unique cycle of ℓ + T contains e. Here we use δ(e) for
a tree edge e to denote the set of links which cover e. The natural covering linear programming
relaxation for the problem, EDGE-LP, is a special instance of a set covering problem with one
requirement (element) corresponding to each cut edge in the tree (Since the tree edges define
shores that form a laminar family, this is also equivalent to a laminar cover problem [6]).
X
min
cℓ xℓ
ℓ∈E

x(δ(e)) ≥ 1

∀e ∈ T

(1)

xℓ ≥ 0

∀ℓ ∈ E

(2)

Fredrickson and Jájá showed that the integrality gap for EDGE-LP can not exceed 2 [10] and also
studied the related problem of augmenting the tree to be two-node-connected (biconnectivity versus
bridge-connectivity augmentation) [11]. Cheriyan, Jordán, and Ravi, who studied half-integral
solutions to EDGE-LP and proved an integrality gap of 34 for such solutions, also conjectured that
the overall integrality gap of EDGE-LP was at most 43 [6]. However, Cheriyan et al. [7] demonstrated
an instance for which the integrality gap of EDGE-LP is at least 3/2.
We study the integrality gap of the EDGE-LP and its generalizations in this work. We first
show that without loss of generality, we can focus our attention on binary trees where every node
has degree 1 or 3 (and every link goes between a pair of leaves). By focusing on the internal nodes
of degree 3, we can add a simple valid constraint. In particular, at any node of degree 3, since no
link can cover all three edges which meet at this node, the total number of (integral) links which
must cover its neighbors is at least 2. This gives one additional constraint per internal node that
we can add to the EDGE-LP. The resulting LP, called the NODE-LP follows where we use δT (v)
for a node v to refer to its three incident edges in the tree T .
min

X
cℓ xℓ
ℓ∈E

x(δ(e)) ≥ 1

∀e ∈ T

x(δ(e1 ) ∪ δ(e2 ) ∪ δ(e3 )) ≥ 2

∀v ∈ T and δT (v) = {e1 , e2 , e3 }

xℓ ≥ 0

∀ℓ ∈ E

(3)

Fiorini et. al extended node constraints for all classes of odd subsets of tree edges as {0, 21 }Chvátal-Gomory cuts of EDGE-LP to obtain new constraints on all odd sets of edges [9]. We call
2

their extended linear program the ODD-LP. Since we will show that we can assume the tree is
binary, every node has odd degree (1 or 3) in the input tree, so if S ⊆ V is odd, then it follows
that δ(S) ∩ T is also odd. Using this observation, we can write the ODD-LP as follows. Recall that
δ(S) for S ⊂ V is the set of all edges and links with exactly one endpoint in S.
X
min
cℓ xℓ
X

x(δ(S)) +

ℓ∈E

x(δ(e)) ≥ |δ(S) ∩ T | + 1

∀S ⊆ V, |S| odd

(4)

e∈δ(S)∩T

xℓ ≥ 0

∀ℓ ∈ E

In Appendix A, we provide a simple independent proof of validity of these odd set constraints
due to Robert Carr.
In addition to the standard version, we also study the problem of 3TAP in which every tree
edge in the final solution must be in a cycle of length 3 (instead of every tree edge being in a cycle
of any length). This is a natural variant of TAP. While TAP models increasing the resilience of
a tree network, 3TAP requires local resilience: i.e., in case of any edge failure, the overhead of
implementing a rerouting protocol is not too high (3TAP solutions only need the identity of the
midpoint of the alternate 2-path for every edge in the solution).

1.1

Related Work

Weighted TAP has several 2-approximation algorithms. The earliest proof of this result used
methods that were tailored for this problem: Frederickson and JáJá [10] convert the problem into
one of finding a minimum weight arborescence in an appropriate directed graph: First, they root
the given tree at an arbitrary node and direct it outwards; Links that go from a node to an ancestor
are directed upward in the tree, while cross links are replaced by two links of the same weight going
from each endpoint to their least common ancestor in the tree. After given the original tree edges
directed downward weight zero, their method finds a minimum weight in-arborescence pointing
to the root, which they argue is of cost at most twice the optimal weighted TAP solution for
this instance (coming from the duplication of cross links). Khuller and Thurimella improved the
runtime of this algorithm [15]. It is also worth noting that the directed instance when viewed as
an undirected instance of TAP consists of all links going top-down in the tree (since cross links
are replaced with two such links from their ends to their lca). The EDGE-LP for all links going
top-down in a tree is totally unimodular (see, e.g., Section 2 of [13]). Hence this version can be
solved to optimality (providing an alternate to the use of the in-arborescence algorithm). Later,
other 2-approximation algorithms have been devised for weighted TAP using other techniques such
as the primal-dual method [20] and iterative rounding [14].
Special cases of weighted TAP has also been investigated. Cheriyan, Jordán and Ravi [6]
developed a 34 -approximation for TAP when the optimal fractional solution is half-integral. Another
special case of weighted TAP is when the tree has bounded depth. In this special case, Cohen and
Nutov showed there exists a (1 + ln 2)-approximation [8]. Recently, Adjiashvili [1] showed a 1.96approximation for another special case of weighted TAP where all link weights are between 1 and
some constant M by using a bundling type linear program. Building off this work, Fiorini et.
al [9] generalized the constraints from [16] and combined them with the bundle constraints from [1]
to propose the ODD-LP we described above and achieved a 32 + ǫ approximation for the same
special case (when all the costs are between 1 and some constant M ). Another recent paper by
Nutov takes a subset of Adjiashvili’s constraints and achieves a 12
7 + ǫ approximation when all the
3

costs are between 1 and some constant M [19]. All of these techniques rely heavily on the bundle
constraints that are focused on link weights being in a bounded range; hence they do not seem to
be generalizable to the case of arbitrary weights. We believe the general problem requires a more
polyhedral approach of the type we investigate.
Numerous papers attempted to reach a target 32 -approximation in the unweighted case of TAP
when all links have the same weight. One paper by Kortsarz and Nutov [16] presents a new linear
program with a 1.75-approximation for the unweighted case, in the hope that this linear program
could help break the 2-approximation barrier for the weighted case. This LP used properties of
an optimal solution for the unweighted case to add multiple new constraints; In retrospect, these
additional constraints are all included in the ODD-LP. Two papers achieved a 23 -approximation
for the unweighted case with very different approaches; one paper by Kortsarz and Nutov relies
on a unique token giving argument [17]. The other paper by Cheriyan and Gao uses semi-definite
programming [4, 5] to arrive at an initial fractional solution for which this integrality gap is proved.
While both of these approaches are very different, they still heavily rely on the fact that all the
links have the same weight.

1.2

Our Results

Our results gives new approaches to determine the integrality gap of weighted TAP: our methods
provide constructive proofs of convex decompositions of given fractional solutions appropriately
scaled into integer solutions.
1. We show that any instance of weighted TAP can be reduced to equivalent instances where
the underlying tree is binary and all the links have their endpoints at leaves (Theorem 2.1 in
Section 2). The simpler structure of input instances help us in several of our proofs and may
also be key in future approaches in settling the integrality gap of weighted TAP.
2. We give a simple new top-down coloring algorithm that gives a constructive proof of the
integrality gap of 2 for EDGE-LP by providing a convex decomposition. Furthermore, if the
minimum non-zero value in the solution for any link is α then we can achieve an improved
2
1+α -approximation (Theorem 3.1 in Section 3). This result generalizes the result of Cheriyan
et al. [6]which we can recover by setting α = 21 . Even more interestingly, this provides a new
1
3
2 -approximation when all nonzero values in the solution are at least 3 .
3. We provide a new conjecture on the ODD-LP (Conjecture 3.3) that says that every vertex
solution to this LP has all large nonzero entries (greater than 13 ) or there is a single very
large valued entry (at least 23 ). In the former case, we can use the previous theorem to get
a 23 -approximation while in the latter, we can apply one step of iterative rounding [18], and
reapply the conjecture to prove a 32 -approximation.
4. We provide a 32 -approximation for weighted TAP based on fractional solutions to NODE-LP
with a particular structure. Let a deficient edge be an edge which gets covered to the extent
less than 34 by this fractional solution. In Section 4, we show that if the deficient edges for the
NODE-LP form at most two paths in the tree, then we can extend our coloring construction
to give a 32 -approximation.
5. Even though we provide improved approximations for specially structured extreme points of
NODE-LP, we can show that such constraints do not strengthen EDGE-LP. In particular,
in Section 5, we show how to transform any TAP instance to a slightly bigger one by a
gadget expansion at every node so that any feasible solution to the EDGE-LP on the original
4

v0′
v1′

v0
v0
v1

v2

v2′

v1
v3

v3′

v2
v3

v4′

Figure 1: An example of a v node with three children before and after the transformation.
instance is feasible to the NODE-LP in the expanded instance. Moreover, EDGE-LP has
extreme points which violate our conjecture above, motivating a deeper study of ODD-LP
for future work.
6. In Section 6, we provide a complete study of 3TAP in which every tree edge must be in a triangle in the final solution. Via a reduction from set cover, we show an Ω(log n)-inapproximability
result and give a matching approximation algorithm. In the unweighted case, we show that
any minimal solution gives a 4-approximation.
Our approach is a top-down coloring algorithm on the scaled fractional solution where each
color class is a feasible solution. In particular, 23 times the fractional solution is decomposed into
a convex combination of integer solutions. This provides not only an approximation algorithm but
also directly proves the integrality gaps for the corresponding covering LPs [3]. In addition, this
technique of top-down coloring differs from all current 23 -approximation algorithms on unweighted
TAP and all current algorithms which achieve better than 2-approximations for special cases of
weighted TAP. Since our methods decompose scaled fractional solutions, they also have the potential
to extend to give tight integrality gap proofs - we propose some ideas for doing this in Section 5.

2

Problem Structure

In this section, we show that we can restrict our attention to only certain instances of weighted
TAP. This structure restricts not only the structure of the links but also the structure of the tree
itself.
Theorem 2.1. Any instance of weighted TAP (T, c, L) can be reduced to a corresponding instance of
weighted TAP (T ′ , c′ , L′ ) of roughly the same size where the tree T ′ is binary and all the leaves in L′
go between two leaves. In addition, every feasible solution to (T, c, L) provides a feasible solution to
(T ′ , c′ , L′ ) of equal cost and vice versa.
The construction is a local operation performed on all the nodes of T in a top-down fashion. Let
v0 be a node in the tree with children v1 , v2 , . . . vk (if v0 is a leaf then no operation will be done).
Let (T, c, L) be the initial tree, the transformation on v will give us a new instance (Tv , cv , Lv ). We
′
for v. We remove the
will add dummy nodes vi′ for v and all its children and a dummy nodes vk+1
5

′ } . We leave all the existing links at
edges X = {v0 vi }i and add the edges Y = {vi vi′ }i ∪ {vi′ vi+1
i
′
of cost 0. The
their corresponding nodes. The only link we add is a link called ℓv from v0 to vk+1
new instance has changed as follows:

V (Tv ) = V (T ) ∪ {vi′ }i
E(Tv ) = E(T ) − X + Y
′
}
Lv = L ∪ {v0 vk+1

Figure 1 gives an example of this transformation on a node with three children.
We will now show that performing this transformation on every non-leaf vertex of T produces
an instance of TAP with a binary tree and leaf-to-leaf links with corresponding feasible solutions
to the original problem.
Proof. First we observe that this transformation adds nodes v0′ , v1′ , . . . vk′ all of degree 3, adds node
′
vk+1
of degree 1, and node v0 ends with degree 1. The transformation also keeps the degree of
v1 , v2 . . . vk unchanged. Once this transformation has been applied to all non-leaves of T then the
resulting tree T ′ will have only nodes of degree 1 and 3; giving a binary tree as desired.
Now observe that every original node is a leaf in T ′ . The only links we added were ℓv which
′
′
is also a leaf under the transformation. The resulting set of
to v0 where vk+1
have the form vk+1
′
links L is leaf-to-leaf.
We will now consider any feasible solution A to (T, c, L). Let A′ = A ∪ {ℓv }v∈V . The cost of
A and A′ are the same as we added only links ℓv which were given cost 0. First observe that ℓv
′
covers all the edges of the form vi′ vi+1
and v0′ v0 . Now consider an edge vi′ vi after the transformation.
There is some link ℓ ∈ A which covers v0 vi in T and now that same link must cover vi′ vi in T ′ . So,
A′ is a valid solution to (T ′ , c′ , L′ ) of the same cost.
Now let A′ be a feasible solution (T ′ , c′ , L′ ) now consider there is a vertex v0 which was not
initially a leaf node in T . It must be the case that A′ contains ℓv as this is the only link in L′
′
. So, let A = A′ − {ℓv }v∈V . Now by the same argument as previously, as A′ is
which covers vk′ vk+1
a feasible solution for T ′ and the only edges in T ′ not in T are those covered by the ℓv then A is
a valid solution to (T, c, L). Notice that A and A′ have the same cost as we only removed links of
cost 0 from the solution.

3

Large Links

The main result of this section is the following theorem.
Theorem 3.1. Given a solution x to the EDGE-LP with xℓ ≥ α when xℓ > 0 and m is the number of
non-zero links then there exists integer solutions x1 , x2 , . . . x2m and λ1 , . . . , λ2m such that:
X
2
λi x i
x≤
1+α
2m

i=1

and this convex combination can be found in strongly polynomial time.
This gives an alternative proof of Cheriyan, Jordán and Ravi [6]. In particular, it gives a 34 approximation when we start with a fractional solution where all non-zero links have weight at
least 12 .

6

3.1

Algorithm

We will be working with a tree rooted at an arbitrary node, r. The least common ancestor (LCA)
of a link, is the least common ancestor of its endpoints. We let Lℓ (Rℓ ) be the path in the tree
from the LCA of ℓ to the left (right) endpoint of ℓ (this path could be empty).
2
. Let k be the smallest
Given a fractional solution, x let α = minℓ:xℓ 6=0 xℓ , and let β = 1+α
integer such that kβx is an even integer for all entries. In order to find our convex decomposition
in the algorithm below, we will decompose kβx into k different color such that each color is a
feasible tree augmentation.
The main idea of how the algorithm works is that it goes down the tree looking at links which
have their LCA at the current node and colors all the copies of each link with different colors so
as to help cover the edges as much as possible with new colors. This guarantees that the first αβk
links (copies of one link) which are colored through an edge all get distinct colors. Afterward, we
only guarantee that of the remaining links that cover an edge half of them give a new color to that
edge.
Data: T a tree, x LP solution, β approximation factor, k colors
Result: Decomposition of kβx into k different colors where each color is a feasible tree
augmentation
Make kβxℓ copies of each link ℓ;
while some link is not colored do
ℓ has the highest LCA among uncolored links;
while not all copies of ℓ colored do
Color a copy of ℓ with the first color not present on Lℓ ;
if all edges of Lℓ are covered by all k colors then
Color a copy of ℓ with any color not already on a copy of ℓ;
end
Color a copy of ℓ with the first color not present on Rℓ ;
if all edges of Rℓ are covered by all k colors then
Color a copy of ℓ with any color not already on a copy of ℓ;
end
end
end
Algorithm 1: The simple coloring algorithm
We will now show that this coloring does indeed give us a convex combination as desired.
Theorem 3.2. Algorithm 1 guarantees that every edge is covered by a link in every one of the k colors.
Proof. For a given e without all k colors, every time a link through e receives a pair of colors, then
one of those colors is new to e. Let us consider some link ℓ through e. Each inner while loop of
the algorithm gives two colors to copies of ℓ. One of the two paths Lℓ , Rℓ must contain e; without
loss of generality let e ∈ Lℓ . Consider the highest edge f ∈ Lℓ without all k colors. If f is missing
a color c, then e must also be missing color c. We have only colored links whose LCA is above f ,
therefore any link with a color which covers e must also cover f . So, for each pair of colors chosen
for a link through e, at least one of them is a new color for e. In other words, half of the time a
link covering e gets colored, it is a new color for e.
The first time a link through an edge e is colored, then all its colors are distinct (unless βxℓ > 1).
For a given link ℓ, every time a color is picked for a copy of ℓ it has to be a color not on one of the
7

edges ℓ covers or a color not on any copy of ℓ.
k colors and all the edges which ℓ covers will
all k colors.
Thus the first time an edge has one of its
Combining this with the fact that every edge
of colors e receives in this process is at least
αβk +

If βxℓ > 1, then we can color the copies of ℓ with all
be covered by all k colors. In this case, e would get
links colored it receives at least αβk distinct colors.
gets colors at rate 21 subsequently, the total number

1−α
1+α
βk =
βk = k.
2
2

Now we will show how this implies Theorem 3.1.
Proof of Theorem 3.1. By scaling our x up by kβ we can write this scaled version as the sum of k
different feasible colors (integer solutions). This gives us that:
kβx =

k
X

xi

i=1

where the xi are integer solutions. Dividing by k gives the desired result.
Algorithm 1 does not need to first multiply by βk before being run. The algorithm can be
run by just multiplying the solution by β. As the algorithm runs, it will keep track of a convex
combination of integer partial solutions. In each while loop when a link ℓ is added, ℓ will be fully
added to some integer partial solutions and added to a fraction of at most two partial integer
solutions (one for Rℓ and one for Lℓ ). This creates at most two more integer partial solutions. The
number of different integer solutions at the end can be bounded by 2m where m is the number of
non-zero links. This guarantees this algorithm can be run in strongly polynomial time.

3.2

Conjecture

Theorem 3.1 deals with the case when x does not have fractional parts which are very small. In
particular, the case where α = 13 gives a 32 approximation with this algorithm. Another approach
to this problem would be to iteratively round when a solution has a link with fractional value at
least 32 (See e.g., [18]).
In particular, when a fractional solution has xℓ ≥ 32 we can immediately round up xℓ to 1 and
resolve the linear program with this added constraint. This approach combined with using our
approximation when xℓ ≥ 13 for all ℓ would achieve a 32 approximation as every individual link gets
rounded up by at most 23 and the cost of the residual LPs do not increase in the process.
By combining these two approaches one would be able to provide a 32 approximation to weighted
TAP. It would be very convenient if every fractional solution had one of these two properties: a
link ℓ with xℓ ≥ 2/3, or xℓ ≥ 1/3 for all non-zero xℓ . Unfortunately, there exists extreme points
of the EDGE-LP which satisfy neither of these properties as shown in Section 5. Therefore, we
propose the following conjecture.
Conjecture 3.3. Every extreme point solution x∗ to the ODD-LP has one of the two properties:
x∗ℓ ≥ 1/3 for all non-zero x∗ℓ or there is some ℓ such that x∗ℓ ≥ 2/3.

8

4

Deficient Paths

In this section, we will start with a solution to NODE-LP and use the additional structure from
the constraints 3 to help us. Due to our previous observation as we will assume that the TAP
instance is a binary tree with all links going from leaf-to-leaf. We will break edges into two groups
depending on how much coverage they receive.
Definition 4.1. An edge e ∈ T is considered deficient if x(δ(e)) < 4/3 and abundant if x(δ(e)) ≥ 4/3.
The deficient edges in a solution to the NODE-LP can not be too dense; this would violate the
node constraint 3.
Lemma 4.2. The deficient edges form paths in T .
Proof. Suppose there was a node, v, adjacent to three deficient edges: e1 , e2 , e3 . By the node
inequality 3, we know that:
x(δ(e1 ) ∪ δ(e2 ) ∪ δ(e3 )) ≥ 2
In this particular case, every link through v goes through exactly 2 of e1 , e2 , e3 . So, we have:
1
x(δ(e1 ) ∪ δ(e2 ) ∪ δ(e3 )) ≤ (x(δ(e1 )) + x(δ(e2 )) + x(δ(e3 ))) < 2
2
This is a contradiction to the feasibility of x for the NODE-LP. So, there is no node with three
deficient edges in a solution to the NODE-LP, and the deficient edges form paths as desired.

4.1

A Top-Down Greedy 2-approximation and Ramifications

In this section, we present a simple 2-approximation which will be used to deal with the abundant
edges in future cases. There are numerous 2-approximations for TAP, but we will use a specific
coloring one as it allows us to extend colorings.
Choose any vertex r to be the root. Let k be the smallest non-negative integer such that kxℓ
is an integer for all links ℓ. For this approach, we will multiply our fractional solution by 4k and
then break it up into 2k integral solutions. The cost of the cheapest such solution will be at most
4k/2k = 2 times the cost of the original.
We will be using LCA(ℓ), Rℓ and Lℓ as defined in the previous section.
Input: Tree T , root r, feasible solution x to EDGE-LP, least common multiple k
Output: Breaks 4kx into 2k colors each of which is a solution
for Links ℓ do
Break the 4kxℓ into 2kxℓ copies of Rℓ and 2kx(f ) copies of Lℓ ;
end
while Not all 2k colors are solutions do
Let e be the highest edge without all 2k colors;
Choose an uncolored link ℓ in x(δ(e));
Choose a color ci not on e;
Color ℓ with ci ;
end
Transfer the colors of Lℓ , Rℓ back to ℓ;
Algorithm 2: Greedily colors the links representing of the EDGE-LP top-down to give 2k solutions.
9

The top-down algorithm is given in 2. The main idea is to double each link and use one copy
to cover the left path from its lca and the other for its right path. In this sense, it is reminiscent of
the approach of Frederickson and JáJá [10] of splitting each cross link in the tree to two up links
to devise a 2-approximation algorithm. The main idea of the coloring algorithm is to only supply
colors to links that are missing at one of the edges it covers. Since the links are colored top down,
this ensures that any color missing at an edge is also missing in all its descendant edges.
Lemma 4.3. The 2k colors returned by 2 are valid solutions.
Proof. Consider any e ∈ T . When the algorithm starts, there are at least 4k links which cover e,
because x(δ(e)) ≥ 1. After the transformation of the links, there are at least 2k edges which cover
e.
As the algorithm progresses, the colors covering every edge are a subset of those covering its
parent. Let p be the parent of e. The first time we color a link through e that is not through p,
then we must have given p all 2k colors already.
Every time a link through e gets a color, it is because some edge e′ above e was missing that
color. By the above observation, the colors missing from e′ are also missing from e. Therefore, e
also got a new color. Hence, every time e gets one of it’s 2k links colored, it gets a new color.
Every edge is covered by all 2k colors, so every color is a solution as desired.
The correctness of the algorithm implies that taking the cheapest color (in terms of total link
cost) is a valid solution, leading to the following result.
Corollary 4.4. There is a greedy top-down coloring based 2-approximation for TAP.
When none of the edges are deficient, then we can push this result even further.
Corollary 4.5. Given a solution x to TAP with no deficient edges, 3kx can be decomposed into 2k
feasible colors.
Proof. We can re-use Algorithm 2 and its proof. The only thing we have to change is that we break
3kxℓ into two parts of size 23 kxℓ . Since all edges are abundant, x(δ(e)) ≥ 4/3 and so after the split,
every edge e has 2k links covering it.
We will strengthen this further to allow us to finish off the abundant parts after we deal with
the deficient parts of the tree in later proofs.
Definition 4.6. A rooted subtree is considered abundant if all its edges are abundant.
Definition 4.7. A partial coloring of 3kx causes a conflict if there is an edge e which is covered by
three links of the same color c and e does not yet have all 2k colors covering it. A partial coloring is
considered conflict-free if it causes no conflicts.
In particular, we show that given the start of the coloring we can finish it off if we didn’t do
too much wrong.
Theorem 4.8. Given a partial conflict-free coloring of 3kx on some links through the root of an
abundant subtree, it can be extended to cover all the edges in the subtree.
Proof. We can simply start the greedy algorithm at the root and finish every edge off. Every edge
in the subtree has at least 4k links covering it originally. For every color c through an edge e, if
there are two copies of that color, then e can pretend that one link with color c was originally given
to the side of the cycle formed by the link not through e.
10

4.2

One Deficient Path

We now extend the greedy coloring algorithm to show that if the deficient edges only form one path
in the tree, then there exists a 32 approximation.
Consider we have a solution x to NODE-LP with only one deficient path P ; let u1 , u2 , . . . uj be
the deficient path. We will deal with this case by first coloring some links such that every edge in
P gets all 2k colors. Then we will split up all the uncolored links that go through P . We root the
tree at u1 , then we will use Theorem 4.8 to finish all the abundant subtrees.
Input: Tree T with one deficient path P = u1 u2 . . . uj , feasible solution x to NODE-LP,
least common multiple k
Output: Breaks 3kx into 2k colors which cover P and is conflict-free at all abundant edges
for ui ui+1 an edge in P do
for Color c not covering ui ui+1 do
Pick an uncolored link, ℓ, through ui ui+1 ;
Color ℓ with color c;
end
end
while There is some ui ui+1 with at least three links of color c do
Let the three links through ui ui+1 of color c be ℓ1 , ℓ2 , ℓ3 ;
With respect to the edges in P , let ℓ1 cover only a subset of the edges covered by ℓ2 and
ℓ3 ;
(At least one such labeling exists by making ℓ2 and ℓ3 the two links with the furthest
coverage in the two sides of ui ui+1 respectively) Uncolor ℓ1 ;
end
Algorithm 3: Greedily colors the links to give 2k solutions that cover the path. Also, it avoids
overcoloring the links through abundant edges and results in a conflict-free coloring.
Theorem 4.9. Algorithm 3 provides all 2k colors to all the edges in P and is conflict-free.
Proof. As the algorithm progresses, an edge in P either has all 2k colors or all of the colored links
covering it are distinct colors. If a edge e in P were to receive a duplicate color c before all 2k
colors, then there were two edges e1 , e2 that both needed c. Without loss of generality let e2 lie
between e and e1 . When e1 takes color c on a link that also covers e, then the link must cover e2 .
This contradicts that e2 would need color c. Therefore, every edge in P gets all 2k colors in the
first part of the iteration.
The clean-up phase does not remove any colors from edges in P . A link ℓ of color c that becomes
uncolored, is uncolored only if all the edges in P it covers have color c from other links. So, the
clean-up phase never removes any colors from edges of P .
The clean-up phase guarantees that for all the rooted subtree, the coloring induces at most two
links of that color and therefore causes no conflicts.
Now by combining the previous theorem, and Theorem 4.8 there is a
there is only one deficient path.

3
2

approximation when

Corollary 4.10. Given a solution x for NODE-LP on tree T which induces at most one deficient path,
there is an integral solution of cost at most 32 the cost of x.

11

4.3

Two Deficient Paths

We’ve shown how to deal with a single deficient path. To extend our approach to two deficient
paths, we need to deal with the abundant path of tree edges which connects the two deficient paths
in the binary tree . The goal is to color links to cover the two deficient paths and the abundant
path between them, and maintain that every remaining abundant subtree doesn’t receive too many
copies of each color. We will prove the following in this section:
Theorem 4.11. Given a solution x on tree T which induces at most two deficient paths, there is an
integral solution of cost at most 23 the cost of x.
To deal with the deficient edges and the abundant path between them, we will have to examine
the structure of links near deficient edges.
Lemma 4.12. Given a solution x to the NODE-LP and a deficient edge e = uv where u is an internal
node, then the total weight of links through u but not e is at least 32 .
Proof. Let the neighbors of u be v, w1 , w2 . The triangle constraint on edges uv, uw1 , uw2 says the
total weight of the links that cover these edges is at least 2. All the links that cover uv, uw1 , or uw2
also go through u. So, the total weight of links through u is at least 2. The weight of links through
the deficient edge uv is less than 43 by definition; this gives the total weight of links through u but
not through uv is at least 23 as desired.
Consider x is a solution to NODE-LP with two deficient paths; let P1 , P2 be the deficient paths
and let Q = q1 q2 . . . qj be the abundant path which connects them. In order to deal with this case,
we will first color the links that form the intersections of Q with P1 and P2 . Then, we will finish
coloring Q. Lastly, we will color P1 , P2 . Throughout the whole process we will also guarantee that
the coloring is conflict free, i.e., every abundant edge not in Q gets all 2k colors or has at most two
copies of every color. In order to deal with this coloring, we will have to treat links which cover all
of Q differently.
Definition 4.13. A link ℓ is considered to be a long link if ℓ covers all the edges of Q. A link ℓ which
is not a long link, is considered to be a short link.
Let e1 , e2 be the edges of P1 adjacent to Q. Let e3 , e4 be the edges of P2 adjacent to Q. If P1 or
P2 only has one edge adjacent to Q this simplifies the case greatly. We will address this case last.
Algorithm 4 finds a coloring starting at the ends of Q.
Lemma 4.14. Algorithm 4 finds a pairing such that every edge not on Q is either covered by all 2k
pairs or is only covered by at most one link in every pair.
Proof. We only need to check that a swap can not cause an edge e′ not on Q to have more pairs
with both links covering e. Consider that some swap occurred because e was covered by both fi , gj
but not covered by fi′ , gj ′ . If e′ is covered by both links in both pairs fi , gj ′ and fi′ , gj then it was
covered by both links in the pairs before the swap. So, consider that e′ is covered by both links
fi , gj ′ after the swap but was not covered by both links in either of the pairs before the swap. So,
neither of fi′ , gj cover e′ .
Right now we have that fi covers e1 , e′ , e but not e2 ; gj covers e2 , e but not e1 , e′ ; fi′ covers only
e1 ; gj ′ covers e2 , e′ and not e1 , e.
Consider the tree T ′ which is all the edges of T contracted except for e, e′ , e1 , e2 . The edges
e1 , e2 were adjacent in T so they are still adjacent in T ′ . e1 can’t separate e2 and e as gj covers e
and e2 . Similarly, e2 can’t separate e1 and e because of fi . Likewise, e1 can’t separate e2 and e′
12

Input: Tree T , feasible solution x to NODE-LP, least common multiple k, adjacent deficient
edges e1 , e2 in P1 between which the abundant path Q to the other deficient path P2
originates
Output: Pairs up 2k links covering e1 and 2k links covering e2 in a way that avoids
overusing any edge not on Q
for i = 1 to 2k do
Let fi be the link through e1 which covers the ith most number of edges of Q;
Let gi be the link through e2 which covers the ith most number of edges of Q;
end
Pair up the edges such that fi gets paired with g2k+1−i ;
for e not on Q do
while fi , gj are paired and both cover e do
Choose a second pair fi′ , gj ′ where neither covers e ;
if No such pair fi′ , gj ′ exists then
Break from the While loop;
end
Change the pairing so that fi , gj ′ are paired and fi′ , gj are paired;
end
end
Algorithm 4: Takes two adjacent deficient edges e1 , e2 and pairs up 2k of the 3kx links covering
e1 and e2 in a way that avoids any edge not in Q being covered by both links in a pair unless it
is covered by all pairs.

e1

e2

e

e′

e1

e2

e′

e

e1

e2

e

e′

Figure 2: The three possible configurations of the edges e1 , e2 , e, e′

13

because of gj ′ , and e2 can’t separate e1 and e′ because of fi . This leaves only the three possibilities
shown in Figure 2.
In the first case of Figure 2, then gj ′ must cover e as it covers e2 and e′ . This is a contradiction
as gj ′ does not cover e. In the second case of Figure 2, gj would cover e′ as it covers e2 and e.
This is a contradiction as gj does not cover e′ . Due to fi covering e′ , e1 , e, it must be the case that
e1 , e, e′ are all on a path; this removes the third case in Figure 2.
Therefore, the swaps never increase the number of pairs which both cover an edge. When the
algorithm ends, every pair covers an edge, or that edge is covered in every pair.
Note that this swapping algorithm would work regardless of which 2k links through e1 , and
through e2 were chosen and how we initially paired them.
Now we can use Algorithm 4 to start a coloring on either side of the abundant path Q. We
now need to coordinate the pairings and then finish coloring the abundant path. The first thing
to observe, we can swap any two long links as long as the two edges of e1 , e2 , e3 , e4 they cover are
the same. This will never create any edges which have two links from the same pairing but not a
link from every pairing. To coordinate the pairings on either side of Q then we need to deal with
the long links. We consider them in three mutually exclusive and collectively exhaustive cases: the
first case where there are at most 2k long links, the second when there are more than 2k long links,
and finally, when we have 2k long links covering one of e1 , e2 , e3 , e4 .
At most 2k long links. In this case, we first observe that the initial pairing will use all the long
links, and none of the long links are paired up with each other in Algorithm 4. In addition, a swap
will always be initiated by a pair of short links fi , gj ; if it were a pair of a long link and a short
link, fi , gj would have no common edges outside of Q. So, any swap involves at most one long link.
Therefore, a swap never creates a pair of two long links.
Use Algorithm 4 to pair up 2k links for e1 , e2 and 2k links for e3 , e4 . Every long link is used in
a pairing for e1 , e2 and a pairing for e3 , e4 and no pairing has two long links. We use Algorithm 5
to color the links to cover Q.
Lemma 4.15. The coloring produced by Algorithm 5 is conflict-free, when there are at most 2k long
links.
Proof. Suppose for a contradiction that there was some edge e covered by 3 links of a color c but
not covered by all 2k colors. This edge e is not on Q (as all edges of Q are covered by all 2k colors).
Let qi be the closest vertex of Q to e in T . Without loss of generality, two of the links of color
c (f1 , f2 ) through e also go through qi−1 (the other possibility is that there is two links of color c
through qi+1 . If both f1 , f2 were part of a pair from e1 , e2 , then by Algorithm 4 then it would be
the case that e has all 2k colors covering it. So, without loss of generality f1 was added to extend
the coloring of color c along Q when f2 was already colored c. If f1 covers a subset of the edges of
Q that f2 does, then f1 never would have been colored with color c by Algorithm 5. If f2 covers a
subset of the edges of Q that f1 does, then f1 would have been chosen and colored before f2 . Both
of these are a contradiction to the correct running of Algorithm 5.
This shows when there are at most 2k long links, we can form a conflict-free partial coloring
that covers all of Q, e1 , e2 , e3 , e4 .
More than 2k long links In this case, we don’t have to worry about covering Q as every pair
will have a long link. However we will have to be a little more careful with the coordination of the
two pairings. In this case, consider there are 2k + c long links. We will first show we can create c
14

Input: Tree T , solution x to NODE-LP, least common multiple k, adjacent deficient edges
e1 , e2 , 2k pairs of links through e1 , e2 , adjacent deficient edges e3 , e4 , 2k pairs of
links through e3 , e4
Output: Colors the pairs and some other links in a conflict-free way to cover Q
for fi , gi one of the 2k pairs covering e1 , e2 do
Color fi , gj with an unused color ci ;
if fi or gi is a long link then
WLOG let fi , hi be a pair of e3 , e4 ;
Color hi with ci ;
end
end
for i = 1 to j − 1 do
while qi qi+1 doesn’t have a color c do
Let f be the uncolored link covering qi qi+1 and the most number of edges on Q after
qi qi+1 ;
Color f with color c;
if f is in a pair for e3 , e4 then
Let f, g be the pair;
Color g with color c;
end
end
end
Algorithm 5: Takes the pairs from Algorithm 4 and extends them to cover all of Q, and be
conflict free

15

pairs that use two long links, and then just create the remaining 2k − c pairs with one long link
each.
Lemma 4.16. If there are 2k + c long links, and no edge of e1 , e2 , e3 , e4 has more than 2k long links,
then there exists c pairs of long links such that each of these c pairs cover e1 , e2 , e3 , e4 .
Proof. Let cij be the number of links that cover ei and ej . A pair that covers all of e1 , e2 , e3 , e4
consists of a long link through e1 , e3 and a long link through e2 , e4 or a long link through e1 , e4 and
a long link through e2 , e3 . Let cA = min(c13 , c24 ), cB = min(c14 , c23 ). If there were not c pairs that
covered all of e1 , e2 , e3 , e4 then cA + cB < c. Without loss of generality, cA = c13 , cB = c14 so the
number of long links covering e1 is less than c. But then, the total number of long links covering
e2 is more than 2k. This is a contradiction. Therefore, we can make c pairs such that each of these
c pairs cover e1 , e2 , e3 , e4 .
For this case, we simply create these c pairs of long links indicated in the lemma above as the
first c colors. Next, we can use the remaining 2k − c long links as the start to fill the remaining
colors using Algorithm 4. Now, if ei isn’t covered by a color, pick an uncolored link f that doesn’t
go through any other ej and color f with the remaining color. This creates no conflicts. Each color
consisting of two long links covers only the edges of Q twice and everywhere else once. Each color
with only one long link only has two short links, and the color covers each of e1 , e2 , e3 , e4 exactly
once; each edge can only have at most two links of this color covering it.
More than 2k long links cover a single ei In this case, without loss of generality e1 has 2k
long links. In this case, we simply start by creating and coloring the 2k pairs as in Algorithm 4 for
e3 , e4 . Each of these pairs will cover all of Q and e1 , e3 , e4 . For each color which e2 is missing, let f
be an uncolored link covering e2 but not e1 . Color f with the color that e2 is missing. This again
keeps the coloring conflict-free by the same reasoning as before. This gives a partial coloring that
covers all of Q, e1 , e2 , e3 , e4 .
Finishing the deficient paths In all the cases above, we colored the links to create a conflictfree partial coloring that covers all of Q and e1 , e2 , e3 , e4 . To finish the deficient paths, we will use
Lemma 4.12 to observe there are 2k uncolored links crossing every deficient edge. Consider starting
at e1 and moving away from Q along P1 . Let e be the deficient edge; there are 2k links through
e not through e1 . For each color e is missing, choose one of these uncolored links for this color.
Repeat this moving away from e1 along P1 . We can do this same process along P1 moving away
from e2 . This guarantees that we only add colors to the abundant subtrees hanging off of P1 (and
not to abundant subtrees hanging off of Q or P2 ). In addition, we can add each color at most twice
to every subtree. We can repeat this process similarly with e3 , e4 on P2 . This gives a conflict-free
partial coloring which gives all the edges of P1 , P2 , Q all 2k colors. By Theorem 4.8, this coloring
can be completed and there is a 23 approximation when there are only two deficient paths.
End of P1 , P2 If P1 or P2 have only one edge adjacent to Q the entire process above can be done
simply without creating a pairing on such a side. Consider P1 only has one edge e1 adjacent to Q;
instead of 2k pairs created for P1 just take the 2k links through e1 which go the furthest down Q.
This replaces Algorithm 4 for P1 and then we proceed according to the case we are in.
This proves Theorem 4.11 as in all the cases we have provided a 2k coloring of 3kx such that
every color is a feasible solution. This coloring method could potentially be extended to the general case of multiple deficient paths, with the key difficulty being that there are links that cover
16

segments of potentially several such deficient paths, and their colorings must be somehow globally
coordinated. We have no counter examples to the success of such a potential approach even though
we have no candidate algorithm that might complete the job for all feasible solutions of NODE-LP.

5

Comparing the linear programs

In section 3, we proposed a conjecture that every extreme point solution to the ODD-LP has a
link which gets xℓ ≥ 2/3 or all the non-zero xℓ are at least 1/3. This conjecture does not hold for
extreme points of the EDGE-LP. An example is given in Figure 3.
u1
1/2

v0

1/4

u2

1/4

v1

3/8

u3

3/8

v2

5/8

v3

v4

1/2
Figure 3: An example of an extreme point of EDGE-LP which doesn’t fulfill the conjecture.
We believe the conjecture to be true for extreme points of ODD-LP. We have performed exhaustive searches on all extreme points of ODD-LP to verify it on small trees (binary trees with at
most 12 nodes). In addition, Fiorini et. al [9] showed that in the special case of no in-links then
ODD-LP is integer. Given a rooted tree T with root r then an in-link is a link ℓ where ℓ does not
go through r and ℓ does not go from one node to it’s ancestor. This indicates that the ODD-LP
potentially has more structure than the EDGE-LP that might be exploited to prove the conjecture.
In this paper, we use the structure given from the NODE-LP (e.g. Lemma 4.12) to prove
theorem 4.11. While the NODE-LP does add some constraints to the EDGE-LP, the NODE-LP
is not much stronger than the EDGE-LP as we show in the next observation. In particular, we
can transform any TAP instance to a slightly bigger one by a gadget expansion at every node so
that any feasible solution to the EDGE-LP on the original instance is feasible to the NODE-LP in
the expanded instance. This shows that if we were to do the gadget expansion for any input, the
NODE-LP constraints alone (without the other ODD=LP constraints) will not add any strength
to the resulting solutions.
Lemma 5.1. After a transformation of any TAP instance that leaves the solutions unchanged, the
integrality gap for the NODE-LP on the transformed instance is the same as the integrality gap for the
EDGE-LP in the original instance.
Proof. In order to show this result, we will show that for every binary tree T we can transform it
to another binary tree T ′ such that every feasible solution of the EDGE-LP for T corresponds to a
feasible solution of the NODE-LP for T ′ .
Consider an original node v ∈ T with neighbors n1 , n2 , n3 as shown in Figure 4a. We will
transform v as shown into the structure given in Figure 4b.
Any feasible solution to the EDGE-LP on T can be made a feasible solution to the NODE-LP
on T ′ by adding all the zero-cost links with value 1 in the solution. These zero cost links guarantee
all new tree edges that we added are covered. Every degree 3 node, u has at least 2 weight of links
covering its neighbors.
17

n1
n1

n2

b1

n2

v

a2

a1
v
b3

b2

a3

n3
(a) The original internal node v and it’s neighborhood

n3
(b) The gadget which gets placed around v. The
dotted links are added and given weight zero. No
other links are added adjacent to b1 , b2 , b3

Figure 4: The left figure shows the original node, and the right figure shows the node after the
gadget transformation has been applied to it
Consider any feasible solution to the NODE-LP on T ′ . For every node vthe solution must
choose links b1 b2 and b2 b3 with value 1 for otherwise a1 b1 and a3 b3 will not be covered. To get a
feasible solution to the EDGE-LP on T we simply remove the links b1 b2 , b2 b3 around every node.
Neither of these transformations change the cost, so we have proven our result as desired. This
gadget forces b1 , b3 to be covered fully by the dotted links. These ensure that the node constraints
around v, a1 , a2 , a3 are all satisfied as long as the edge constraints are satisfied.
While the NODE-LP is not any stronger than the EDGE-LP, we believe that the ODD-LP is
stronger than both of these LPs. As noted before, the ODD-LP may add key constraints which
would allow us to extend the top-down deficient path coloring beyond just one or two deficient
paths.

6
6.1

Three-Cycle TAP
Weighted Version

In this section, we will consider the weighted version of 3TAP where the weights on the links, cf ,
can take on any value. We first present an O(log n) approximation algorithm, and then we present
a matching lower bound of Ω(log n), where n is the number of nodes in the tree.
Theorem 6.1. There is a O(log n) approximation algorithm for weighted 3TAP on n nodes.
Proof. Consider any feasible solution A to 3TAP, such that T ∪ A has every tree edge in a 3-cycle.
For a vertex v, let δ(v) be the edges of T ∪ A adjacent to v.
To turn this problem into a set cover problem, we let the edges of E(T ) be the elements. For
any subset of edges adjacent to a vertex v, Sv , we construct a set with cost c(Sv ) which covers the
edges induced by the endpoints of the edges in Sv (except for those edges adjacent to v).
By doubling each edge in the feasible solution, then we can decompose the entire solution into
these stars. So, given a solution to 3TAP of total cost C, the corresponding set cover has a solution
18

s
S1

r

S2

···

Sk

t
e1

e2

···

en

Figure 5: The 3TAP instance created from a set cover instance.
of at most 2C. Given any solution to the set cover problem, then we simply add all the edges
specified by the stars to the tree (with maybe some duplicates when edges are added from both
endpoints’ stars). Thus, any solution of cost C to the set cover gives a solution to the original
3TAP solution of cost between C/2 and C. Therefore the optimal solutions to these two problems
are within a factor of two of each other.
It is well known that minimum-cost set cover with n elements has an O(log n) approximation as
long as the densest set (that has the maximum ratio of newly covered elements divided by the cost
of the set) can be found in polynomial time. For a fixed vertex v, we can find the maximum density
star centered at v as follows. Due to a result by Goldberg, one can find the maximum density
subgraph; S ⊂ V which minimizes |E(S)|
c(S) in polynomial time [12]. For the given center v, by setting
the cost of another vertex u to be c(uv), we can use the maximum density subgraph algorithm to
find the maximum density star from v, where the edges in the subgraph are the tree edges covered
in triangles by the corresponding star. By repeating this for every choice of center vertex v, we can
find the maximum density star in polynomial time. This gives the maximum density set for the set
cover problem in polynomial time. Then we can use the greedy algorithm for set cover to get an
O(log n) approximation for 3TAP.
Notice that in the above algorithm we used no properties of the original graph T . This algorithm
will in fact work for any graph T where the goal is to augment such that every edge is in a 3-cycle.
Corollary 6.2. The problem of finding a minimum cost augmentation of any graph G where every
edge must be in a 3-cycle has an O(log n) approximation.
The above approximation is tight as the weighted 3TAP problem captures set-cover exactly.
We will now show the matching lower bound.
Theorem 6.3. 3TAP does not have a Ω(log n)-approximation unless N P ⊆ P .
Proof. Consider an instance of set cover with sets S1 , S2 , . . . , Sk and elements e1 , e2 , . . . en and cost
function c on the sets. We will have our tree be as shown in Figure 5. The vertex set is
{r, s, t} ∪ {Si }ki=1 ∪ {ej }nj=1
with the following costs on the links:
• Links from s to vertices {r, t} ∪ {Si }ki=1
• Links from t to Si have cost c(Si )
19

• If ej ∈ Si then the link from ej to Si has cost 0
P
• All remaining links have cost 1 + ki=1 c(Si ). Call the set of these remaining edges L.
In any optimal solution, we will not use any edges from L as taking all the edges not in that
set have smaller cost and give a feasible solution. The zero edges from s allow every edge except
for the tej edges to be in a three-cycle and they have cost 0. Now the only way to have an edge
tej in a three cycle is for tSi and ej Si to be used for some Si such that ej ∈ Si . So, the non-zero
edges bought correspond to sets being chosen.
Consider any feasible solution to set cover Si1 , . . . Sik , this can be turned into a feasible solution
to 3TAP of the same cost. All the zero cost edges in addition to the tSiℓ edges form a feasible
solution. We know all the edges in the tree except for the tej edges are in a three cycle with zero
cost edges. Consider any j ∈ [n]. There is some Sit that contains j. The edge tej is then in a three
cycle with tSiℓ and Siℓ ej . Hence, every feasible solution to the set cover instance gives a feasible
solution of the same cost to the 3TAP instance.
Consider any feasible solution to our 3TAP instance.
If the 3TAP solution contains an edge
P
from L then the solution has weight at least 1 + ki=1 c(Si ), by taking all the sets Si we get a
feasible solution to the set cover instance of less cost. Now consider there are no edges from L in
the feasible solution for the 3TAP instance. Let tSi1 , . . . tSit be the non-zero edges in the solution.
Therefore Si1 , . . . Sit is a feasible solution to the set cover instance. Consider any element ej . The
edge tej must be in some three cycle with tSiℓ and Siℓ therefore, Siℓ contains ej and is a set in our
solution to set cover. Therefore every feasible solution to 3TAP has a corresponding solution of set
cover with the same or smaller cost.
Any feasible solution to set cover gives a solution to 3TAP of the same cost. Any feasible
solution to 3TAP, gives a feasible solution to set cover of the same or smaller cost. Therefore, by
the hardness of set cover, it is impossible to approximate three-cycle TAP to within a Ω(log n)
factor unless N P ⊆ P [2].
Remark: Suppose we were given an empty initial graph to augment and wish to find a
minimum-cost two-edge-connected spanning subgraph where every edge is in a triangle, it is not
hard to adapt the above hardness: We give all edges in the tree zero cost. By further subdividing
the path of set nodes S1 , S2 , . . . , Sk to add new dummy nodes between every pair of set nodes, we
can ensure that every element node ej is covered only by triangles containing edge (t, ej ). This
requires that the other edges in the cycle are of the form (t, Si ), (Si , ej ) for some set Si containing
the element ej .

6.2

Unweighted Version

While weighted 3TAP has many similarities to set cover, the unweighted version admits a constant
approximation unlike set cover. Here we consider the case that every non-tree edge has cost either
1 or infinity, and every tree edge is present (and has cost 0). This 4-approximation comes from
lower bounding the cost of every feasible solution to unweighted 3TAP.
Lemma 6.4. Every feasible unweighted 3TAP solution has cost at least

n−1
2 .

Proof. Consider any solution S. Duplicate all the links of S and edges T and forming stars around
every vertex consisting of the edges adjacent to it. Call the star around v, Sv . This doubles the cost
of the solution, but now we can see that every tree edge is covered by some star. At every vertex,
we can further decompose Sv into Sv1 , . . . Svℓv such that we get stars that cover different connected
components of the tree and every star contains at most one tree edge.
20

Now consider any star Svi . If Svi has x links, then the number of tree edges it can cover with
3-cycles is at most x. So, in the doubled instance of S there must be at least n − 1 edges. Every
link is in at most 2 stars; there must be at least n−1
2 edges in any feasible solution.
Corollary 6.5. Unweighted 3TAP has a 4-approximation.
Proof. We can get a 4 approximation by simply taking any minimal feasible solution. For every edge
ab, pick a v such that av, bv both have cost 0 or 1. If no such vertex exists, then no feasible solution
exists. Otherwise, the algorithm chooses at most 2(n − 1) links. This gives a 4 approximation as
desired.

7

Conclusions

We have introduced a new top down coloring method that gives a strict improvement over existing
2-approximation algorithms for weighted TAP, with better improvements for larger minimum values
in the LP. Our methods give constructive convex combinations into feasible solutions and when
coupled with the strengthened ODD-LP for the problem have much potential to settle the integrality
gap for this fundamental network design problem. We also settled the approximation complexity
of the special case when all edges in the final solution must be in triangles – the extensions to short
constant-length cycles in place of triangles is immediate. We hope our new algorithms will provide
a stepping stone to settling the integrality gap for weighted TAP.

References
[1] David Adjiashvili. Improved approximation for weighted tree augmentation with bounded
costs. arXiv preprint arXiv:1607.03791, 2016.
[2] Sanjeev Arora and Madhu Sudan. Improved low-degree testing and its applications. Combinatorica, 23(3):365–426, 2003.
[3] Robert Carr and Santosh Vempala. Randomized metarounding. In Proceedings of the thirtysecond annual ACM symposium on Theory of computing, pages 58–62. ACM, 2000.
[4] Joseph Cheriyan and Zhihan Gao. Approximating (unweighted) tree augmentation via liftand-project, part I: stemless TAP. CoRR, abs/1508.07504, 2015.
[5] Joseph Cheriyan and Zhihan Gao. Approximating (unweighted) tree augmentation via liftand-project, part ii. arXiv preprint arXiv:1507.01309, 2015.
[6] Joseph Cheriyan, Tibor Jordán, and R Ravi. On 2-coverings and 2-packings of laminar families.
Algorithms-ESA99, pages 72–72, 1999.
[7] Joseph Cheriyan, Howard Karloff, Rohit Khandekar, and Jochen Könemann. On the integrality
ratio for tree augmentation. Operations Research Letters, 36(4):399–401, 2008.
[8] Nachshon Cohen and Zeev Nutov. A (1+ ln2)-approximation algorithm for minimum-cost 2edge-connectivity augmentation of trees with constant radius. Theoretical Computer Science,
489:67–74, 2013.

21

[9] Samuel Fiorini, Martin Groß, Jochen Könemann, and Laura Sanità. A 3/2-approximation
algorithm for tree augmentation via chvátal-gomory cuts. arXiv preprint arXiv:1702.05567,
2017.
[10] Greg N Frederickson and Joseph Jájá. Approximation algorithms for several graph augmentation problems. SIAM Journal on Computing, 10(2):270–283, 1981.
[11] Greg N Fredrickson and Joseph Jájá. On the relationship between the biconnectivity augmentation and traveling salesman problem. Theoretical Computer Science, 19(2):189–201, 1982.
[12] Andrew V Goldberg. Finding a maximum density subgraph. University of California Berkeley,
CA, 1984.
[13] Daniel Golovin, Viswanath Nagarajan, and Mohit Singh. Approximating the k-multicut problem. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm,
pages 621–630. Society for Industrial and Applied Mathematics, 2006.
[14] Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem.
Combinatorica, 21(1):39–60, 2001.
[15] Samir Khuller and Ramakrishna Thurimella. Approximation algorithms for graph augmentation. Journal of Algorithms, 14(2):214–225, 1993.
[16] Guy Kortsarz and Zeev Nutov. A 1.75 lp approximation for the tree augmentation problem.
arXiv preprint arXiv:1507.03009, 2015.
[17] Guy Kortsarz and Zeev Nutov. A simplified 3/2 ratio approximation algorithm for the tree
augmentation problem. Transaction on Algorithm, 12(2):23, 2016.
[18] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011.
[19] Zeev Nutov. A note on the tree augmentation problem. arXiv preprint arXiv:1703.07247,
2017.
[20] R. Ravi. Steiner Trees and Beyond: Approximation Algorithms for Network Design. PhD
thesis, Brown University, 1994.

A

Odd Constraints

In this section, we provide a new proof of correctness of the ODD-LP.
Lemma A.1. The constraints in ODD-LP are valid for any integer solution to TAP.
Proof by Robert Carr. Consider an odd set of vertices S. By adding together the edge constraints
for δ(S) ∩ T we get:
X
x(δ(e)) ≥ |δ(S) ∩ T |
e∈δ(S)∩T

Now we can add any non-negative terms to the left hand side and still remain feasible. Therefore
x(δ(S)) +

X

x(δ(e)) ≥ |δ(S) ∩ T |

e∈δ(S)∩T

22

P
is also feasible. Now consider any link ℓ. If xℓ appears an even number of P
times in e∈δ(S)∩T x(δ(e))
then ℓ is not in δ(S). Similarly, if xℓ appears an odd number of times in e∈δ(S)∩T x(δ(e)) then ℓ is
in δ(S). So, the coefficient of every xℓ on the left hand side of this expression is even. In particular,
for any integer solution the left hand side is even and the right hand side is odd. Therefore, we
can strengthen the right hand side by increasing it by one, and the resulting constraint will still be
feasible for any integer solution. The constraint
X
x(δ(S)) +
x(δ(e)) ≥ |δ(S) ∩ T | + 1
e∈δ(S)∩T

is valid for any integer solution to TAP as desired.

23

