APPROXIMATING (UNWEIGHTED) TREE AUGMENTATION VIA
LIFT-AND-PROJECT,
PART II

arXiv:1507.01309v2 [] 29 Aug 2015

JOSEPH CHERIYAN AND ZHIHAN GAO
Abstract. In Part II, we study the unweighted Tree Augmentation Problem (TAP) via the Lasserre
(Sum of Squares) system. We prove that the integrality ratio of an SDP relaxation (the Lasserre
tightening of an LP relaxation) is ≤ 23 + , where  > 0 can be any small constant. We obtain this
result by designing a polynomial-time algorithm for TAP that achieves an approximation guarantee
of ( 32 + ) relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP
relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of
integral solutions from the previous literature to fractional solutions by identifying some properties
of fractional solutions of the Lasserre system via the decomposition result of Karlin, Mathieu and
Nguyen (IPCO 2011).

1. Introduction
In the weighted Tree Augmentation problem we are given a connected, undirected multigraph G
bT ) of G; the goal
with non-negative costs on the edges, together with a spanning tree T = (V (G), E
bT , of minimum cost such that (V, E
bT ∪ F ) is 2-edge connected.
is to find a set of edges, F ⊆ E(G)−E
b
By a link we mean an element of E(G)−ET ; thus, a link is an edge of G that can be used to augment
bT (a tree-edge) if T + uw − ê = (V, E
bT ∪ {uw}−{ê})
T . We say that a link uw covers an edge ê ∈ E
is connected. We say that a set of links F covers the tree T if every edge of T is covered by at least
bT ∪ F ) is 2-edge-connected. Thus, the goal is
one link of F ; it can be seen that F covers T iff (V, E
to compute a set of links of minimum cost that covers T .
The weighted Tree Augmentation problem was first studied by Frederickson and Jaja in 1981
[4]. They showed that the problem is NP-hard, and they presented a 2-approximation algorithm.
Subsequently, it has been proved that even the unweighted Tree Augmentation problem is APX-hard,
see [9, Section 4]; thus the problem has no PTAS assuming P6=NP.
There have been some important advances on this problem for the corresponding unweighted
(i.e., uniform weight) problems. Following [5], we use the abbreviation TAP for the unweighted Tree
Augmentation problem. Nagamochi, see [6], presented the first algorithm for TAP that improved on
the approximation guarantee of 2; the approximation guarantee is ≈ 1.875. Subsequently, Even, et
al., [5] built on the ideas and techniques initiated by Nagamochi and presented an elegant algorithm
and analysis that achieves an approximation guarantee of 1.8. In a conference publication from
2001, Even, et al., reported a 1.5 approximation algorithm for TAP, see the extended abstract [3],
and recently, Kortsarz & Nutov [10] presented the journal version of this result.
We prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is ≤ 32 + , where  > 0 can be any small constant. We obtain this result by designing
a polynomial-time algorithm for TAP that achieves an approximation guarantee of ( 32 + ) relative
to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but
our analysis relies on the SDP relaxation. Observe that our integrality ratio (and approximation
guarantee) is proved relative to a “weaker lower bound” than the optimum value (since the feasible
Date: August 29, 2015.
Based on one chapter of the second author’s Ph.D. Thesis.
1

region of a relaxation is a superset of the convex full of integer solutions). Moreover, the approximation guarantee of 1.5 follows as a corollary of our main result (but, we cannot eliminate the “+”
in our bound on the integrality ratio by this corollary).
Linear programming relaxations for the weighted version of TAP have been studied for many
years. (We use the standard abbreviation LP to mean a linear programming relaxation or a linear
programming problem.) There is an obvious “covering” LP: we have a variable xe for each edge
bT and we have a covering constraint for each edge of T . It is well known that the
e ∈ E(G) − E
integrality ratio of this LP is ≤ 2; this can be deduced from Jain’s result [7]. A lower bound of
1.5 on the integrality ratio is known [1]; in fact, the construction for the lower bound uses uniform
bT , hence, the lower bound applies for TAP. We formulate an LP
weights for the edges in E(G) − E
that is a tightening of the obvious “covering” LP for TAP; see (LP0 ) in Section 3.
The Lasserre system applies to an initial LP, and it derives a sequence of tightenings of the initial
LP; these tightened relaxations are indexed by a number t = 0, 1, . . . called the level, where the level 0
tightening means the initial LP. A key “decomposition theorem” (see Theorem 4.1, [11, 8]) asserts
that a feasible solution at level t can be written as a convex combination of feasible solutions at a
lower level such that all of these lower-level solutions y are “locally integral.” Here, “locally integral”
bT , such that the solution y takes only zero or one
means that there is a specified subset J ⊆ E(G)− E
values on this subset (i.e., ye ∈ {0, 1}, ∀e ∈ J). A key point is that the difference in levels (between
the level t of the given feasible solution and the level of the lower-level “locally integral” solutions)
does not depend on the size of J, rather, it depends on the following “combinatorial parameter”
determined by J. Suppose that there exists a constant k such that every feasible solution x of the
initial LP has ≤ k entries in J that have value one, i.e., |{e ∈ J : xe = 1}| ≤ k for every feasible
solution x of the initial LP. Then for any t > k, a feasible solution at level t can be written as a convex
combination of “locally integral” feasible solutions at level (t − k). This property does not hold for
other weaker Lift-and-Project systems such as the Lovász-Schrijver system or the Sherali-Adams
system.
The analysis of our algorithm is based on a potential function. Our potential function is derived
from the Lasserre tightening of the initial LP.
Our algorithm is “combinatorial” and we do not need to solve the initial LP nor its Lasserre tightening to run the algorithm; but, the analysis of the algorithm relies on the Lasserre tightening. Our
algorithm essentially follows the “algorithmic scheme” of [5, Section 3.4], see Section 7 for details.
The algorithm is a greedy-type iterative algorithm that makes a leaves-to-root scan over the tree T
and (incrementally) constructs a set of links F that covers T . The algorithm starts with F := ∅, at
each major step it adds one or more links to F (it never removes links from F ), and at termination,
it outputs a set of links F that covers T such that |F | ≤ the potential function. The algorithm
incurs a cost of one unit for each link added to F . The key to the analysis is to show that for each
major step, the cost incurred (i.e., one plus the number of links added to F ) is compensated by a
part of the potential function.
Informally speaking, our analysis in Section 8 asserts the following:
if the naive algorithm gets “stuck” then the instance contains a small combinatorial
obstruction, a so-called deficient tree, see Theorems 8.7, 8.8.
This assertion is the key to this paper; it turns out that the algorithmic aspects as well as the
analysis of the approximation guarantee are straightforward consequences. Our analysis in Section
8 makes essential use of the Lasserre system and the decomposition theorem, see Figure 1.
For ease of exposition and for the sake of motivation, this paper has several discussions that
contain forward references. But, these forward references are not relevant for the correctness of our
arguments; indeed, all discussions containing forward references could be deleted, and this will have
2

Decomposition theorem
for the Lasserre system

Lemma 8.5

Lemma 7.2

Lemma 8.2

Potential function
of Lemma 5.2

Lemma 8.6

Lemma 8.3

Theorem 8.7

shows deficient trees
under appropriate conditions

Lemma 8.4

Figure 1. Illustration of the role of the decomposition theorem for the Lasserre
system (Theorem 4.1). Our analysis consists of three blocks of results: low-level,
middle-level, and high-level; these are shown from left to right in the figure. Note
that Lemmas 7.2, 8.2 are often used in the proofs of subsequent results.
no effect on the validity of our proofs. Also, Part II repeats some definitions, figures, and discussions
from Part I, but proofs from Part I are not repeated.
An outline of Part II is as follows. Section 2 has definitions and notation; several items are new
to Part II (and not needed in Part I). We adopt the notation and terms of Even, et al., [5], where
possible; this will aid readers familiar with that paper. Section 3 presents the initial LP; this is
the same LP as in Part I. Section 4 discusses the Lasserre tightening of the initial LP, and proves
some basic properties and inequalities; most of these results are from Part I, but there are two new
results. Section 5 derives our potential function, based on a solution y of the Lasserre tightening;
this potential function differs significantly from the potential function of Part I. Section 6 starts the
presentation of the algorithm (and credits) by elaborating on two preprocessing steps. Section 7
completes the discussion of the algorithm (and credits) by presenting the main loop of the algorithm.
The most important component of this paper is Section 8; this section presents the analysis of the
algorithm by first proving some low-level properties, then builds on this to prove some intermediatelevel lemmas, and then proves the key theorem on deficient trees (Theorem 8.7); this section also
presents and proves the last piece of the algorithm, namely, the handling of deficient trees.
2. Preliminaries and notation
This section presents definitions and notation.
Standard notation including tree T , link set E. Let G = (V, E(G)) be a connected, undirected
bT ) be a spanning tree of G. We assume that |V | ≥ 2. By a tree-edge
multigraph, and let T = (V, E
bT ; we call E the link set and we call an
we mean an edge of T . Let E denote the edge-set E(G)−E
element ` ∈ E a link ; thus, a link is an edge of G that can be used to augment T . An instance of
TAP consists of G and T . We assume that all instances of interest have feasible solutions, that is,
bT ∪ E) is 2-edge connected. The goal is to find a minimum-size subset F of E
we assume that (V, E
bT ∪ F ) is 2-edge
such that augmenting T by F results in a 2-edge connected multigraph, i.e., (V, E
connected.
For two nodes u, v ∈ V , we use Pu,v = Pv,u to denote the unique path of the tree T between u
and v.
For a node v ∈ V , we denote the number of tree-edges incident to v by degT (v). For any node
v ∈ V , we use δE (v) to denote the set of links incident to v.
3

For any U ⊆ V , we denote the set of links with both ends in U by E(U ), and for any two subsets
U, W of V , we denote the set of links with one end in U and the other end in W by E(U, W );
thus, E(U, W ) := {uw ∈ E : u ∈ U, w ∈ W }. We use similar notation for some subsets of
E; for example, E reg denotes a particular subset of E (defined below), and E reg (U, W ) denotes
{uw ∈ E reg : u ∈ U, w ∈ W }.
We say that a link uw covers a tree-edge ê if Pu,w 3 ê. Similarly, we say that a subtree of T is
covered by a set of links J ⊆ E if each tree-edge of the subtree is covered by some link of J. For any
bT , we use δE (ê) to denote the set of links that cover ê, thus, δE (ê) = {uw ∈ E : ê ∈
tree-edge ê ∈ E
Pu,w }.
Shadows and the shadow-closed property. For two links u1 v1 and u2 v2 , if Pu1 ,v1 ⊆ Pu2 ,v2 ,
then we call u1 v1 a shadow (or, sublink ) of u2 v2 .
For any link uv ∈ E, if all sublinks of uv also exist in E, then we call E shadow-closed. Clearly,
if E is not shadow-closed, then we can make it shadow-closed by adding all sublinks of each of the
original links. It can be seen that this preserves the optimal value of any instance of TAP.
Following Even, at al., [5], we make the next assumption (see Assumption 2.2 of [5]).
Assumption: E is shadow-closed.
Root, ancestor, descendant and rooted subtrees. One of the nodes r of T is designated as
the root; thus, we have a rooted tree (T, r).
Let v be a node of T . If a node w belongs to the path Pv,r , then w is called an ancestor of v, and
v is called a descendant of w. If a descendant w of v is adjacent to v (thus, w 6= v), then w is called
a child of v, and v is called a parent of w. Clearly, every node in V −{r} has a unique parent. If a
node v has no child, then we call v a leaf ; if v has no child, then degT (v) = 1. Note that r has at
least one child (since |V | ≥ 2), thus, r is not a leaf, even if degT (r) = 1. Throughout, we use L to
denote the set of leaves; thus, L = {v ∈ V : v is a leaf of T }.
For any leaf v of T , up(v) denotes a node q in Pv,r that is nearest to the root and adjacent to v
via a link. Since E is shadow-closed, it can be seen that up(v) is an ancestor of v, for each leaf v.
For any node v, we use Tv to denote the rooted subtree of (T, r) induced by v and its descendants.
We use L(Tv ) to denote the set of leaves of the subtree Tv . Throughout, the terms tree or subtree
refer to a rooted subtree of (T, r) that is “closed w.r.t. descendants” (if a node w is in the subtree,
then all descendants of w are in the subtree).
Property 2.1. Suppose that T̄ is a rooted tree. Let T̄v1 and T̄v2 be two (rooted) subtrees of T̄ . Then
T̄v1 and T̄v2 either share no node or one is contained in the other.
¯ etc. denote an arbitrary item/set (rather than
Remark 2.2. Throughout, symbols such as T̄ , J,
the complement of another set).
Stems and twin links. We call a node s of T a stem if s 6= r, s has exactly two children, s has
exactly two descendants that are leaves, and there exists a link in E between the two leaves of Ts ;
we call the link between the two leaves of Ts a twin link, and denote it by twinlk(s). (Our definition
of stem differs slightly from [5, Definition 3.1].) Let E twin denote the set of twin links. Observe that
there is a one-to-one correspondence between twin links and stems. Throughout, we use S to denote
the set of stems; thus, S = {v ∈ V : v is a stem of T }. Moreover, we use R to denote the set of
nodes that are neither stems nor leaves; thus R = V −(S ∪ L). (The notion of stems and twin links
is due to [6].)
up (s) = {vs ∈ E : v ∈
dn (s) =
For any stem node s, we define δE
/ V (Ts )}. Similarly, we define δE
{vs ∈ E : v ∈ V (Ts )}.
4

Contraction and compound nodes. We use the standard notion of contracting a link or a set
of links, see [5], [2, Chapter 1]. We use T 0 := T /F to denote the tree obtained by contracting
bT ∪ F ) to a single node. Each of the
each of the 2-edge connected components of T + F = (V, E
0
contracted nodes of T = T /F is called a compound node, see [5, Section 3.2]; thus, each compound
node corresponds to a set of two or more nodes of V (T ). Each of the other nodes of T /F is called
an original node.
We also call a node of T an original node. We call a link in E an original link. When we say that
` is a link w.r.t. T we mean that ` is an original link; when we say that `0 is a link w.r.t. T 0 = T /F ,
we mean that there exists an original link ` whose image in T /F is `0 .
Buds and buddy links. Besides stems and their associated subtrees, one other type of subtree
(and some of the incident links) plays an important role in this paper.
We call a leaf b0 a bud (see Figure 2) if there exists a (rooted) subtree Tv with exactly three
leaves b0 , b1 , b2 such that (i) up(b0 ) is a descendant of v (possibly, up(b0 ) = v), (ii) Tup(b0 ) contains a
stem s such that b0 , b1 are the leaves of Ts , and (iii) the link b1 b2 exists. We call b1 b2 the buddy link
of b0 and denote it by buddylk(b0 ). Observe that there exists an ancestor q of s in Tv such that
q is the least common ancestor of s and b2 ; possibly, q = v, and possibly, q = v = r; moreover,
L(Tup(b0 ) ) = {b0 , b1 } or L(Tup(b0 ) ) = {b0 , b1 , b2 }.
Note that b1 may be a bud as well. In that case, each leaf of Tup(b1 ) is in {b0 , b1 , b2 }, there exists
a link between b0 , b2 , and buddylk(b1 ) = b0 b2 .
v = up(b0 )

q

v=q
up(b0 )

s

b2
b1

s

b2
b0

b1

b0

Figure 2. Illustration of a bud b0 and the subtree Tv . The figure on the left shows
the case when up(b0 ) is an ancestor of all three leaves in Tv . The figure on the right
shows the other case.
Consider a bud b0 , and let s, q be as above; we define
Rspecial (b0 ) := V (Pb0 ,up(b0 ) )−V (Ps,q )−{b0 }.

Thus Rspecial (b0 ) contains the internal nodes in the tree-path between b0 and s; moreover, if up(b0 )
is an ancestor of all three leaves b0 , b1 , b2 , then Rspecial (b0 ) also contains all nodes on the tree-path
between the parent of q and up(b0 ); there are no other nodes in Rspecial (b0 ) (see Figure 3).
Fact 2.3. Rspecial (b0 ) is the set of nodes w such that there exists a link b0 w in E, and w is not on
the tree-path between the two ends of buddylk(b0 ). Every node in Rspecial (b0 ) has a unique child,
and is an ancestor of b0 . For two buds b, b̄ that are not the leaves of the same subtree Ts , where s
is a stem, the sets Rspecial (b) and Rspecial (b̄) are disjoint. (Thus, Rspecial (b) ∩ Rspecial (b̄) = ∅, unless
the least common ancestor (in T ) of b, b̄ is a stem s.)

We denote the set of buds and the set of buddy links by Lbud and E buddy , respectively. Observe
that there is a unique buddy link for each bud; thus, there is a bijection between Lbud and E buddy .
5

up(b0 )

q

q
up(b0 )

s

b2
b1

s

b2
b0

b1

b0

Figure 3. Illustration of Rspecial (b0 ) for a bud b0 . The nodes in Rspecial (b0 ) are
indicated by solid circles. The figure on the left shows the case when Tup(b0 ) has
three leaves. The figure on the right shows the other case.
For any node w of the tree T , we denote by Lbud (w) the set of buds in the subtree Tw . For a
stem s, note that Lbud (s) may contain zero, one, or two nodes.
Let Rspecial = ∪b∈Lbud Rspecial (b) and Rnonspcl = R−Rspecial . Thus, we partition the set R (of nodes
that are neither stems nor leafs) into two subsets, the “special” subset Rspecial and the “normal”
subset Rnonspcl .
We use E reg to denote the set E−(E twin ∪ E buddy ), namely, the set of links that are neither twin
links nor buddy links.
Vectors and convex combinations. For any vector x ∈ RE , let ones(x) denote the set of links
of x-value one, thus ones(x) = {uv ∈ E : xuv = 1}.
P
For a vector x ∈ RE and any subset J of E, x(J) denotes
e∈J xe . Given several vectors
P
i ; thus, Z is a set of indices, and
λ
v
v 1 , v 2 , . . . , we write one of their
convex
combinations
as
i∈Z i
P
we have λi ≥ 0, ∀i ∈ Z, and i∈Z λi = 1.
3. Initial LP relaxation

This section presents our initial LP relaxation of shadow-closed instances of TAP, denoted by
(LP0 ); this is the same LP as in Part I (Section 3).
Let u1 v1 and u2 v2 be a pair of links. We call it an overlapping pair of links if (i) Pu1 ,v1 , Pu2 ,v2
have one or more tree-edges in common, and (ii) either an end of u1 v1 is in Pu2 ,v2 , or an end of u2 v2
is in Pu1 ,v1 . We call a set of links J an overlapping clique if every pair of links in J is an overlapping
pair. We use the notion of overlapping pairs for stating (LP0 ).
(LP0 ) minimize :

X

xuv

uv∈E

subject to :

X

uv∈δE (ê)

bT
∀ê ∈ E

xuv ≥ 1,

xu1 v1 + xu2 v2 ≤ 1, ∀ overlapping pairs u1 v1 , u2 v2 ∈ E
0≤x≤1
4. Lasserre tightening and its properties
This section presents the Lasserre tightening of the initial LP and proves some basic properties
and inequalities; most of these results are from Part I, but there are two new results. The proofs of
the results from Part I are omitted.
6

Let Last (LP0 ) denote the level t tightening of (LP0 ) by the Lasserre system. 1 Recall that ones(x)
denotes the set of links of x-value one, where x ∈ RE is a feasible solution of (LP0 ). Rothvoß, see
[11, Theorem 2], formulated the following decomposition theorem for the Lasserre system, based
on an earlier decomposition theorem due to Karlin-Mathieu-Nguyen [8]. (We use this particular
formulation and not the original statement of [8]; hence, we reference both [8] and [11].)
Theorem 4.1. Let J ⊆ E. Let k be a positive integer such that |ones(x) ∩ J| ≤ k for every feasible
solution x of (LP0 ). Then for every P
feasible solution y ∈ Last (LP0 ), where t ≥ k + 1, y can be
written as a convex combination y = i∈Z λi xi such that xi is in Last−k (LP0 ) and xi |J is integral
(i.e., xiuv is integral for each uv ∈ J), for all i ∈ Z.
Lemma 4.2. Let J ⊆ E be an overlapping clique. For every feasible solution x of (LP0 ), we have
|ones(x) ∩ J| ≤ 1. Furthermore, for every level t ≥ 2 and every feasible solution y of Last (LP0 ), we
have y(J) ≤ 1.
Lemma 4.3. Let w be a leaf of T , and let u be an ancestor of w such that every internal node
(if any) of Pw,u has exactly one child. Let ê = vu be the tree-edge of Pw,u that is incident to u
(possibly, v = w). Then, δE (ê) is an overlapping clique. In particular, δE (w) is an overlapping
clique. Moreover, we have y(δE (w)) = 1 for any feasible solution y ∈ Last (LP0 ) where t ≥ 2.
Recall that the matching polytope of the subgraph induced by the leaves, G(L) = (L, E(L)) is
given by the following constraints:
x(δE(L) (v)) ≤ 1,
x(E(W )) ≤

∀v ∈ L

|W | − 1
, ∀W ⊆ L, |W | odd
2

x≥0
The next result is essentially the result on the matching polytope from the survey of Rothvoß,
see [12, Lemma 13, Sec 3.3], translated to our setting.
Lemma 4.4. Let  > 0, and let y ∈ Las 1 +1 (LP0 ). Then,
2
G(L) = (L, E(L)).

y|E(L)
1+

is in the matching polytope of

Lemma 4.5. Let x be a feasible solution of (LP0 ) and let s be a stem. Then |ones(x) ∩ δE (s)| ≤ 3.
Proof. Since s is a stem, s is incident to three tree-edges. Let ê1 , ê2 , ê3 be the tree-edges incident with
s. Clearly, Ji = δE (êi ) ∩ δE (s) is an overlapping clique, for each 1 ≤ i ≤ 3, and δE (s) = ∪1≤i≤3 Ji .
Then the result follows from Lemma 4.2.

Lemma 4.6. Let t ≥ 3, and let y be a feasible solution of Last (LP0 ). Suppose that s is a stem.
Then:
up (s)).
(1) y(twinlk(s)) ≤ y(δE
(2) For each bud b in Ts (if it exists), we have y(buddylk(b)) ≤ y(bs) + y(E(b, Rspecial (b))).

Proof. Let the leaves of Ts be b0 and b1 . Let J = δE (b0 ) ∪ δE (b1 ). Since b0 , b1 are leaves, by
Lemma 4.3, δE (b0 ) and δE (b1 ) are overlapping cliques. Thus, by Lemma 4.2, |ones(x) ∩ J| ≤ 2
for
solution x of (LP0 ). By Theorem 4.1, y can be written as a convex combination
P any feasible
i such that xi ∈ Las (LP ) and xi | is integral, ∀i ∈ Z.
λ
x
1
0
J
i∈Z i
1Formally speaking, Las (LP ) is a set of vectors in R2[|E|] . In what follows, we abuse the notation and take
t
0

Last (LP0 ) to be the projection on the subspace indexed by the singleton sets; thus, we take Last (LP0 ) to be a set of
vectors in R|E| .
7

(1): Consider statement (1) of the lemma. Observe that twinlk(s) = b0 b1 . Since b0 b1 ∈ J, either
xi (b0 b1 ) = 0 or xi (b0 b1 ) = 1, for all i ∈ Z. Let Z(1) = {i : xi (b0 b1 ) = 1}. Then
P
y(b0 b1 ) = i∈Z(1) λi xi (b0 b1 ). Consider xi , where i ∈ Z(1) . Let ês be the tree-edge between

s and its parent. Then, xi (δE (ês )) ≥ 1. Notice that every link in δE (ês ) with positive
xi -value must have s as its end in Ts ; otherwise, if such a link has an end at some other
node of Ts , then it will be overlapping with the link b0 b1 , and we would have a violation
of the overlapping constraints of (LP0 ). Thus, xi (δE (ês )) = xi (δE (ês ) ∩ δE (s)). Hence,
up (s)) = xi (δ (ê ) ∩ δ (s)) = xi (δ (ê )) ≥ 1 = xi (b b ), ∀i ∈ Z . Consequently,
xi (δE
0 1
E s
E
E s
(1)
P
P
P
i
i
up
i
up
up (s)).
y(b0 b1 ) = i∈Z(1) λi x (b0 b1 ) ≤ i∈Z(1) λi x (δE (s)) ≤ i∈Z λi x (δE (s)) = y(δE
(2): Consider statement (2) of the lemma. W.l.o.g., let b = b0 (the same argument applies for
i
i
b = b1 ). Let buddylk(b0 ) = b1 b2 . Since b1 b2 ∈ J, either
Px (b1 b2 ) =i 0 or x (b1 b2 ) = 1, for all
i
i ∈ Z. Let Z(2) = {i : x (b1 b2 ) = 1}. Then y(b1 b2 ) = i∈Z(2) λi x (b1 b2 ).

Consider xi , where i ∈ Z(2) . Let ` = b0 w be a link such that xi (`) = 1; such a link must
exist. If w 6= s and w is in Pb1 ,b2 , then ` is overlapping with b1 b2 , and we would have a
violation of the overlapping constraints of (LP0 ). Hence, by Fact 2.3, w ∈ Rspecial (b0 ) ∪ {s}.
special (b ))).
Then, xi (buddylk(b0 )) = 1 ≤ xi (`) P
≤ xi (b0 s) + xi (E(b0 , R
0
P
i
Consequently, y(buddylk(b0 )) = i∈Z(2) λi x (b1 b2 ) ≤ i∈Z(2) λi (xi (b0 s)+xi (E(b0 , Rspecial (b0 )))) ≤
P
i
i
special (b )))) = y(b s) + y(E(b , Rspecial (b ))).
0
0
0
0
i∈Z λi (x (b0 s) + x (E(b0 , R


For any stem s and for any x ∈ RE , we define slackx (s) to be
 1

X
1  dn
up
x(δE (s)) +
(x(E(b, Rspecial (b))) − x(buddylk(b))) +
x(δE
(s)) − x(twinlk(s)) .
2
2
bud
b∈L

(s)

Lemma 4.6 implies the following fact.
Fact 4.7. For any stem s and for any feasible solution y to Last (LP0 ) where t ≥ 3, we have
slacky (s) ≥ 0.

Remark 4.8. Although the above fact assumes that the level t is ≥ 3, observe that slackx (s) is
well defined for all levels ≥ 0.
5. Potential function
This section presents the potential function used by our algorithm. The potential function is based
on a feasible solution y to the Lasserre tightening of (LP0 ). It is essential to tighten (LP0 ) because
the potential function is not valid for feasible solutions of (LP0 ). Possibly, our potential function
may be obtained via weaker lift-and-project systems (e.g., Lovász-Schrijver, or Sherali-Adams). We
prefer to apply the Lasserre tightening because our analysis in Sections 7–8 makes essential use of
the decomposition theorem (Theorem 4.1), and this theorem is not known to hold for any weaker
lift-and-project system; see Part I (Section 10).
Our potential function is defined via a subset of the leaves that is denoted by Λ. This subset is
determined by the instance of TAP. Informally speaking, it consists of all the leaves of all occurrences
of a particular type of subtree, called a bad 2-stem tree, see Section 6. Our potential function consists
of two parts, a “preprocessing” part and a “normal” part. Our algorithm applies two preprocessing
steps; the first preprocessing step contracts all occurrences of maximal bad 2-stem trees, and for
this we have to “charge” the “preprocessing” part of our potential function.
We say that a set of leaves Λ is compatible if the following holds:
• For every twin link and for every buddy link, either both ends of the link are in Λ or no end
of the link is in Λ; in other words, no twin link and no buddy link is present in E(Λ, L − Λ).
8

In what follows, let Λ ⊆ L denote a compatible set.
We denote the set of stems with both leaves in Λ by SΛ . Similarly, let Lbud
denote the set of
Λ
bud
buds in Λ, and let L(L−Λ) denote the set of buds in L−Λ. By the definition of a compatible set, the
following fact holds.
Fact 5.1.
bud
Lbud
(s),
(L−Λ) = ∪s∈S −SΛ L

E twinlk (L−Λ) = {twinlk(s) : s ∈ S−SΛ },

E buddylk (L−Λ) = ∪s∈S −SΛ {buddylk(b) : b ∈ Lbud (s)}.
creg
b(L−Λ) deLet M
denote a maximum matching of the subgraph (L−Λ, E reg (L−Λ)), and let U
(L−Λ)
creg ; thus U
b(L−Λ) = (L−Λ)−{v ∈
note the set of nodes of this subgraph exposed by the matching M
(L−Λ)
creg }.
V : v is an end of some link ` ∈ M
(L−Λ)
We mention that our potential function (the right-hand side of the inequality in Lemma 5.2 below)
creg , U
b(L−Λ) . Thus, when we use our potential function, we have to ensure
refers to the terms Λ, M
(L−Λ)
that these terms have been defined already; we will “fix” our potential function by appropriately
creg , U
b(L−Λ) in Section 6.
defining Λ, M
(L−Λ)
Given Λ and y ∈ RE , we use lbd y (Λ) to denote the quantity

1
1 X
3
y(E(Λ)) + y(E(Λ, L−Λ)) + y(E(Λ, V −L)) +
y(δE (s));
2
2
2
s∈SΛ

this is one of the terms in our potential function; informally speaking, this is the main component
of the “preprocessing” part of the potential function.
1
+ 1, 3}. Let y ∈ Last (LP0 ). Then,
Lemma 5.2. Let  > 0 be a constant, and let t ≥ max{ 2

3
( + )y(E)
≥
2
1
+ y(E(V −L)) +
2

3 creg
b(L−Λ) | + lbdy (Λ)
|M
| + |U
2 (L−Λ)
1 X
1 X
y(δE (v)) +
y(E(v, V −Lbud
(L−Λ) (v))) +
2
2
nonspcl
special
v∈R

v∈R

Moreover, every item on the right-hand side of the inequality is nonnegative.

X

slacky (s).

s∈S −SΛ

Proof. Observe that y is feasible for Last (LP0 ) for t ≥ 3, hence, y ≥ 0 and (by Fact 4.7) slacky (s) ≥
0, ∀s ∈ S. Hence, every item on the right-hand side of the inequality is nonnegative.
For each link uw, we distribute the value 32 yuw as follows:
– if both u, w ∈ L, then uw keeps the value 32 yuw ;
– if both u, w ∈ V −L, then uw keeps the value 21 yuw and each of the ends u and w gets value
1
2 yuw ;
– if only one of u or w is in V −L, then uw keeps the value yuw and the end in V −L gets value
1
2 yuw .
(In other words, each node in V −L borrows value 21 yuw from each link uw incident to it, and the
link keeps the remaining value; links uw that are not incident to V −L keep all of the value 32 yuw .)
9

Thus, we have
3
3
3
3
y(E) =
y(E(Λ)) + y(E(L−Λ)) + y(E(Λ, L−Λ))
2
2
2
2
1
1 X
+ y(E(V −L)) + y(E(V −L, Λ)) + y(E(V −L, L−Λ)) +
y(δE (v)).
2
2
v∈V −L

Then we increase the coefficients of the twin links and buddy links in E(L − Λ) from 32 to 2 by
borrowing the value 21 y(E twin (L−Λ)) + 12 y(E buddy (L−Λ)) from the last term above, and adding it to
the term 32 y(E(L−Λ)). Thus, we replace the term 32 y(E(L−Λ)) by 2y(E(L−Λ)) − 12 y(E reg (L−Λ)),
and we replace the last term by
1 X
1
1
y(δE (v)) − y(E twin (L−Λ)) − y(E buddy (L−Λ))
2
2
2
v∈V −L
1 X
1 X
1 X
1 X
dn
up
y(δE (v)) +
y(δE (v)) +
y(δE (s)) +
=
(y(δE
(s)) + y(δE
(s)))
2
2
2
2
nonspcl
special
s∈SΛ
s∈S −SΛ
v∈R
v∈R
1
1
− y(E twin (L−Λ)) − y(E buddy (L−Λ))
2
2
1 X
1 X
1 X
1 X
1
up
y(δE (v)) +
y(δE (v)) +
=
y(δE (s)) +
y(δE
(s)) − y(E twin (L−Λ))
2
2
2
2
2
s∈SΛ
s∈S −SΛ
v∈Rnonspcl
v∈Rspecial
1
1 X
dn
y(δE
(s)) − y(E buddy (L−Λ))
+
2
2
s∈S −SΛ

1 X
X
1 X
(1) 1 X
special
(v)))
+
y(E(b,
R
(b)))
=
y(δE (s)) +
y(δE (v)) +
y(E(v, V −Lbud
(L−Λ)
2
2
2
s∈SΛ
v∈Rnonspcl
v∈Rspecial
b∈Lbud
(L−Λ)
X
X
1
1
1
1
up
dn
+
y(δE
(s)) − y(E twin (L−Λ)) +
y(δE
(s)) − y(E buddy (L−Λ))
2
2
2
2
s∈S −SΛ
s∈S −SΛ
1 X
1 X
(2) 1 X
=
y(δE (s)) +
y(δE (v)) +
y(E(v, V −Lbud
(L−Λ) (v)))
2
2
2
s∈SΛ
v∈Rnonspcl
v∈Rspecial

X
1 X  dn
y(δE (s)) +
+
(y(E(b, Rspecial (b))) − y(buddylk(b)))
2
s∈S −SΛ
b∈Lbud (s)


1 X
up
+
y(δE
(s)) − y(twinlk(s))
2
s∈S −SΛ
X
1 X
1 X
1 X
=
y(δE (s)) +
y(δE (v)) +
y(E(v, V −Lbud
(v)))
+
slacky (s),
(L−Λ)
2
2
2
nonspcl
special
s∈SΛ
s∈S −SΛ
v∈R
v∈R
where (2) follows from Fact 5.1 due to the assumption that Λ is compatible, and (1) follows from
the following equation:
[
[
E(w, Lbud
=
E(b, Rspecial (b)).
(L−Λ) (w))
w∈Rspecial

b∈Lbud
(L

−Λ)

This equation is based on some observations. First, the set on the right-hand side is clearly a subset
of the set on the left-hand side. Conversely, consider a link wa in the set on the left-hand side,
where w ∈ Rspecial and a ∈ Lbud
(w). Since w is an ancestor of a and w is not on the tree-path of
(L−Λ)
10

the link buddylk(a), by Fact 2.3, we have w is in Rspecial (a), i.e., wa ∈ E(a, Rspecial (a)). Hence, the
link wa belongs to the set on the right-hand side as well.
Thus, the expression for 23 y(E) can be written as
3
3
1
= y(E(Λ)) + y(E(Λ, L−Λ)) + 2y(E(L−Λ)) − y(E reg (L−Λ))
2
2
2
1
+ y(E(V −L)) + y(E(V −L, Λ)) + y(E(V −L, L−Λ))
2
X
1 X
1 X
1 X
y(δE (v)) +
y(E(v, V −Lbud
(v)))
+
+
y(δE (s)) +
slacky (s)
(L−Λ)
2
2
2
nonspcl
special
s∈SΛ
s∈S −SΛ
v∈R
v∈R
3

1
1 X
=
y(E(Λ)) + y(E(Λ, L−Λ)) + y(E(Λ, V −L)) +
y(δE (s))
2
2
2
s∈SΛ


+ y(E(L−Λ, Λ)) + 2y(E(L−Λ)) + y(E(L−Λ, V −L))
X
1
1 X
1 X
slacky (s)
+ y(E(V −L)) +
y(δE (v)) +
y(E(v, V −Lbud
(v))) +
(L
−
Λ)
2
2
2
nonspcl
special
s∈S −SΛ
v∈R
v∈R
1
− y(E reg (L−Λ))
2
X
1
= lbd y (Λ) +
y(δE (v)) + y(E(V −L))
2
v∈L−Λ
X
1 X
1 X
(v))) +
slacky (s)
+
y(δE (v)) +
y(E(v, V −Lbud
(L
−
Λ)
2
2
nonspcl
special
s∈S −SΛ
v∈R
v∈R
1
− y(E reg (L−Λ))
2
P
By Lemma 4.3, we have y(δE (v)) = 1 for any v ∈ L. Hence, we replace the term v∈L−Λ y(δE (v))
(the 2nd term in the displayed equation above) by |L−Λ|. Moreover, by Lemma 4.4, we have
y| reg
y|E(L)
is in the matching polytope of (L, E(L)). Thus, E (L−Λ) is in the matching polytope of
1+

1+

creg |. We derive the inequality (stated
(L−Λ, E reg (L−Λ)), which implies y(E reg (L−Λ)) ≤ (1+)|M
(L−Λ)

in the lemma) by replacing the term − 21 y(E reg (L−Λ)) (the last term in the displayed equation above)
creg |. Now, observe that |L−Λ| − 1 (1 + )|M
creg | = |U
b(L−Λ) | + 3 |M
creg | −
by − 12 (1 + )|M
2
2
(L−Λ)
(L−Λ)
(L−Λ)
reg
reg
1
c
b
c
2 ()|M(L−Λ) |, because U(L−Λ) = (L−Λ)−{v ∈ V : v is an end of some link ` ∈ M(L−Λ) }. Note
 creg
creg | ≤ 1 |L| = 1 P
that |M
v∈L y(δE (v)) ≤ y(E), hence, − 2 |M(L−Λ) | ≥ −y(E). Thus, we get our
2
2
(L−Λ)
potential function:
3
( + )y(E)
2

≥

3 creg
b(L−Λ) | + lbd y (Λ) + 1 y(E(V −L))
|M(L−Λ) | + |U
2
2
1 X
1 X
+
y(δE (v)) +
y(E(v, V −Lbud
(L−Λ) (v))) +
2
2
nonspcl
special
v∈R

v∈R

6. Algorithm and credits I: Preprocessing steps
We state our main result for (unweighted) TAP:
11

X

s∈S −SΛ

slacky (s).


1
+ 1}. Let y denote an
Theorem 6.1. Let  > 0 be any (small) constant, and let t ≥ max{17, 2
3
optimal solution of Last (LP0 ). The integrality ratio of Last (LP0 ) is ≤ 2 + . Moreover, there is a
polynomial-time algorithm for TAP that finds a feasible solution (a set of links that covers the tree
T ) of size ≤ ( 23 + )y(E).

For the rest of this paper, we let y ∈ RE denote an optimal solution of Last (LP0 ), where t ≥
1
max{17, 1 + 2
}, where  > 0 is any constant. Our goal is to show that our algorithm finds a set of
links that covers T of size ≤ ( 32 + )y(E). We achieve this goal using our potential function (this is
the right-hand side of the inequality in Lemma 5.2); we will “fix” the potential function below by
creg , U
b(L−Λ) ). Recall from Part I (Section 6) that the
defining the relevant terms (namely, Λ, M
(L−Λ)
potential function provides credit to the algorithm.
Also, recall from Part I (Section 6) that the combinatorial algorithm is a greedy-type iterative
algorithm that makes a leaves-to-root scan over the tree T and (incrementally) constructs a set of
links F that covers T . The algorithm starts with F := ∅, at each step it adds one or more links to
F (it never removes links from F ), and at termination, it outputs a cover F of T whose size is ≤
the potential function.
The algorithm incurs a cost of one unit for every link that it picks, and it incurs a cost of one unit
for each new compound node that it creates in the execution. The key to the analysis is to show
that for each step, the cost incurred is compensated by a part of the credit.
We mention that (with one exception, see Lemma 8.3) the nodes or links that get contracted into
a compound node are no longer relevant for the algorithm or the analysis. In particular, the credit
(if any) of such nodes or links may be used at the step when they get contracted into a compound
node, but after that step, any remaining credit of such nodes or links is not used at all.
0
denote the path of T 0 between u
For the current tree T 0 = T /F and nodes u, w of T 0 , let Pu,w
and w. By a fitting cover of a rooted tree Tv0 ⊆ T 0 we mean a set of links J that covers all of the
0
= Tv0 .
tree-edges of Tv0 but does not cover any other tree-edge; thus, we have ∪uw∈J Pu,w
6.1. Semiclosed trees. We recall the notion of a semiclosed tree w.r.t. an arbitrary matching. This
notion is due to Even, et al., based on earlier work by Nagamochi [6]; also, see [5, Definition 2.3].
Let Tv0 be a rooted subtree of the current tree T 0 = T /F . Let M̄ be an arbitrary matching of the
leaf-to-leaf links. Tv0 is called semiclosed w.r.t. M̄ if the following conditions hold:
(i) Each link in M̄ either has both ends in Tv0 or has no end in Tv0 .
(ii) Every link incident to an M̄ -exposed leaf of Tv0 has both ends in Tv0 .
Let M̄ (Tv0 ) denote the set of links in M̄ that have both ends in Tv0 .
We define
[
Γ(M̄ , Tv0 ) := M̄ (Tv0 ) {up(w)w : w is an M̄ -exposed leaf in Tv0 };

thus, we associate a “basic link set” with the pair M̄ , Tv0 . In general, the “basic link set” may not
be a cover of Tv0 .
By a minimally semiclosed tree Tv0 we mean that Tv0 is semiclosed but none of the proper rooted
subtrees of Tv0 is semiclosed.
Lemma 6.2 (Even, et al., [5]). Let Tv0 be a minimally semiclosed tree w.r.t M̄ . Then Γ(M̄ , Tv0 ) is
a fitting cover of Tv0 .
6.2. Maximum matching. Our algorithm and analysis are based on a maximum matching of the
leaf-to-leaf links that are neither twin links nor buddy links. Let M denote one such matching; thus,
M is a maximum matching of the subgraph (L, E reg (L)). By an M -link we mean a link that is in
M . We denote the set of M -exposed leaf nodes by U .
12

The image of M w.r.t. T 0 is {u0 w0 : uw ∈ M, u0 6= w0 }, where u0 , w0 denote the images (w.r.t.
of the original nodes u, w of T (i.e., we have u0 = u if u is an original node of T 0 , otherwise, u0
denotes the compound node of T 0 that contains u; w0 is defined similarly). We abuse the notation
and use M to denote both M and its image w.r.t. T 0 , and by an M -link of T 0 we mean the image
(w.r.t. T 0 ) of an original M -link.
For the rest of the paper, unless mentioned otherwise, a semiclosed tree means a subtree that is
semiclosed w.r.t. the matching M .

T 0)

6.3. Bad 2-stem trees. Let Tv be a semiclosed tree rooted at v that has exactly two stems s1 , s2
and four leaves, where we denote the leaves of the tree Tsi by ui , wi for i = 1, 2.
By a leafy 3-cover of Tv we mean a set of three links J such that J covers Tv , one of the links in
J has one end in Tv and one end in L−L(Tv ), and the other two links in J have both ends in Tv .
We call Tv a bad 2-stem tree if (i) one of the links in E({u1 , w1 }, {u2 , w2 }) is in M , (ii) two of
the leaves are M -exposed, (iii) one of the leaves is incident to all the links in E({u1 , w1 }, {u2 , w2 })
(thus E({u1 , w1 }, {u2 , w2 }) has one or two links), (iv) there exists a cover of Tv of size three, and
(v) there exists no leafy 3-cover of Tv . Let us fix the notation such that w1 w2 is the unique M -link
in E(L(Tv )); thus, u1 and u2 are M -exposed (see Figure 4).
By a maximal bad 2-stem tree Tv we mean a bad 2-stem tree that is not a proper subtree of
another bad 2-stem tree. (Thus, any tree Tq rooted at a proper ancestor q of v (if q exists) must
violate one of the conditions for being a bad 2-stem tree.)
v

s1

u1

s2

w1

w2

u2

Figure 4. Illustration of a bad 2-stem tree. The dashed lines indicate links and the
thick dashed line indicates an M -link.
Let F prep = {Tv1 , . . . , Tvk } denote the set of maximal bad 2-stem trees
S of T ; clearly, any two
treesSin F prep are disjoint, by Property 2.1. We use V (F prep ) to denote Tv ∈F prep V (Tv ). We define
Λ = Tv ∈F prep L(Tv ), that is, Λ consists of all the leaves of all the trees in F prep .
Since each bad 2-stem tree has a cover of size 3, the shadow-closed property implies that each
bad 2-stem tree has a fitting cover of size ≤ 3. Our algorithm applies a preprocessing step that
contracts each tree Tv ∈ F prep by a fitting cover of size ≤ 3.
Preprocessing step 1 (Λ-contraction): For every tree Tv ∈ F prep , add a fitting cover of Tv of
size ≤ 3 to F and contract Tv to a compound node.
The cost incurred for this step is ≤ 4|F prep |, since each tree in F prep incurs a cost of ≤ 3 for its
fitting cover and a cost of 1 for the resulting compound node.
This cost is charged to one part of our potential function, namely, it is charged to
X
1
y(δE (v)).
lbd y (Λ) +
2
nonspcl
prep
∩V (F

v∈R

Lemma 6.6 below shows that this quantity is ≥ 4|F prep |.
13

)

Remark 6.3. The results in this section show that Λ-contraction is valid, in the sense that the
algorithm has sufficient credits to pay for the cost of this step. Moreover, Λ-contraction is essential for the overall analysis (i.e., the algorithm cannot skip Λ-contraction), because the proof of
Theorem 8.7 (Subcase 2.2) relies on Λ-contraction.
Lemma 6.4. Let F prep and Λ be as defined above. Then, we have
lbdy (Λ) +
≥

X

Tv ∈F prep

1
2

X

y(δE (v))

v∈Rnonspcl ∩V

3

(F prep )

1
1
y(E(L(Tv ))) + y(E(L(Tv ), L−L(Tv ))) + y(E(L(Tv ), V −L)) +
2
2
2

X

u∈V (Tv )−L


y(δE (u))

P
Proof. Recall that lbd y (Λ) denotes 32 y(E(Λ))+ 21 y(E(Λ, L−Λ))+y(E(Λ, V −L))+ 21 s∈SΛ y(δE (s)).
Observe that a bad 2-stem tree has no buds, so every node of such a tree is either a leaf, or a
stem, or a node of Rnonspcl . Hence,
(Rnonspcl ∩ V (F prep )) ∪ SΛ =

[

(V (Tv )−L)

Tv ∈F prep

and so we have
1
2

X

v∈Rnonspcl ∩V

y(δE (v)) +

1 X
y(δE (s)) =
2
s∈SΛ

(F prep )

X

Tv ∈F prep

1
2

X

y(δE (u)).

u∈V (Tv )−L

We need the following claim to prove the lemma.

Claim 6.5. Let Λ1 , Λ2 , . . . , Λk be a partition of Λ. Then, we have
3
1
y(E(Λ))+ y(E(Λ, L−Λ)) + y(E(Λ, V −L))
2
2
k
k
k
X
3X
1X
≥
y(E(Λi )) +
y(E(Λi , L−Λi )) +
y(E(Λi , V −L)).
2
2
i=1

i=1

i=1

We partition Λ into the sets Λi = L(Tvi ), where Tv1 , . . . , Tvk are the maximal bad 2-stem trees in
F prep . Then, we have
lbd y (Λ) +

1
2

X

v∈Rnonspcl ∩V

y(δE (v))
(F prep )

X 1
X
3
1
= y(E(Λ)) + y(E(Λ, L−Λ)) + y(E(Λ, V −L)) +
y(δE (u))
2
2
2
prep
Tv ∈F
u∈V (Tv )−L
X 3
X
1
1
y(E(L(Tv ))) + y(E(L(Tv ), L−L(Tv ))) + y(E(L(Tv ), V −L)) +
≥
2
2
2
prep
Tv ∈F

14

u∈V (Tv )−L


y(δE (u)) .

To prove the claim, observe that
3
1
y(E(Λ)) + y(E(Λ, L−Λ)) + y(E(Λ, V −L))
2
2
k
k
k
k
3 X
 1X
X
1 XX
≥
y(E(Λi , Λi )) +
y(E(Λi , Λj )) +
y(E(Λi , L−Λ)) +
y(E(Λi , V −L))
2
2
2
i=1

=

i=1 j6=i

i=1

k

k

k

i=1

i=1

i=1

i=1

X
1X
3X
y(E(Λi )) +
y(E(Λi , L−Λi )) +
y(E(Λi , V −L)).
2
2

Lemma 6.6. Let Tv be a bad 2-stem tree. Then we have
 1

 1
3
y E(L(Tv )) + y E(L(Tv ), L−L(Tv )) + y E(L(Tv ), V −L) +
2
2
2
Hence, we have
lbdy (Λ) +

1
2

X

v∈Rnonspcl ∩V (F prep )


X

u∈V (Tv )−L

y(δE (u)) ≥ 4.

y(δE (v)) ≥ 4|F prep |.

Proof. The second statement follows immediately from the first statement and Lemma 6.4. We
focus on the first statement.
Let s1 , s2 denote the two stems in Tv , and let u1 , w1 (respectively, u2 , w2 ) denote the two leaves
in Ts1 (respectively, Ts2 ). Thus, L(Tv ) = {u1 , w1 , u2 , w2 }. W.l.o.g. let w1 w2 denote the unique
M -link in E(L(Tv )); the two twin links u1 w1 , u2 w2 are also in E(L(Tv )), and E(L(Tv )) may contain
one other link incident to w1 or w2 ; there is no link between u1 and u2 (see Figure 4). Note that
every link incident to u1 or u2 (the M -exposed leaves of Tv ) must have both ends in Tv , since Tv is
semiclosed w.r.t. M .


S
Let J denote the set of links incident to the leaves of Tv , thus, J = i=1,2 δE (ui ) ∪ δE (wi ) . For
any feasible solution x of (LP0 ), Lemmas 4.3
Pimpliesithat |ones(x)i ∩ J| ≤ 4. Hence, byi Theorem 4.1,
y can be written as a convex combination i∈Z λi x such that x ∈ Las3 (LP0 ) and x |J is integral,
∀i ∈ Z. (In what follows, we have to apply Lemma 4.6 to xi , hence, xi must be feasible for level 3
(or higher) of the Lasserre tightening.)
Thus, it suffices to show that for any i ∈ Z, we have
 1 


 1
X
3 i
x E(L(Tv )) + xi E(L(Tv ), L−L(Tv )) + xi E(L(Tv ), V −L) +
xi (δE (u)) ≥ 4;
2
2
2
u∈V (Tv )−L
let α denote the left-hand side of the above inequality.
Observe that every link in J with positive xi -value must have xi -value one. Suppose that one of
the links ` ∈ E(L(Tv )) has positive xi -value, thus xi (`) = 1; then, we have 32 xi (E(L(Tv ))) ≥ 32 , thus `
contributes value 23 to α. Also, if one of the links ` with one end in L(Tv ) and the other end at a nonP
leaf node of Tv has positive xi -value, then we have xi (E(L(Tv ), V −L))+ 21 u∈(V (Tv )−L) xi (δE (u)) ≥
1 + 21 = 23 , thus, ` contributes value 32 to α.
We complete the proof by case analysis, by considering the number of links with positive xi -value
such that one end is in L(Tv ) and the other end is not in Tv .
Case 1.: Suppose that there are no links with positive xi -value such that one end is in L(Tv ) and
the other end is not in Tv . Then, we focus on the number of links in E(L(Tv )) that have
positive xi -value; this number is zero, one, or two, because every link incident to a leaf
15

has xi -value zero or one, and moreover, xi (δE (u)) = 1 for each leaf u of Tv , by (LP0 ) and
Lemma 4.3. Thus, we have three subcases.
Subcase 1.1.: xi (E(L(Tv ))) = 0. Every link of xi -value one incident to a leaf of Tv has its
other end at a non-leaf node of Tv , hence, each such link contributes 23 to α; we have
four such links, so α ≥ 6.
Subcase 1.2.: xi (E(L(Tv ))) = 1. The link ` in E(L(Tv )) with xi -value one contributes 23
to α. The two leaves in L(Tv ) that are not incident to ` each contribute 32 to α, because
each is incident to a link of xi -value one that has its other end at a non-leaf node of Tv ,
hence, α ≥ 29 .
Subcase 1.3.: xi (E(L(Tv ))) = 2. Since xi (δE (u)) = 1 for each leaf u of Tv , the links in
E(L(Tv )) with xi -value one share no ends. By the definition of bad 2-stem trees, all the
links in E({u1 , w1 }, {u2 , w2 }) are incident to one of the four leaves. It follows that the
twin links u1 w1 and u2 w2 both have xi -value one, and each contributes 23 to α. Next,
up (s )) ≥ xi (u w ) = 1 for j = 1, 2. Thus,
focus on the stems in Tv ; by Lemma 4.6, xi (δE
j
P j j
each stem contributes at least 12 to α via the term 21 u∈(V (Tv )−L) xi (δE (u)). Hence,
α ≥ 2( 32 ) + 2( 12 ) = 4.
Case 2.: Suppose that there is at least one link with positive xi -value such that one end is in L(Tv )
and the other end is not in Tv . Again, we focus on the number of links in E(L(Tv )) that
have positive xi -value; it can be seen that this number is zero or one. (Note that every link
incident to a leaf has xi -value zero or one, and moreover, for every leaf u of Tv , we have
xi (δE (u)) = 1.) Thus, we have two subcases.
Subcase 2.1.: xi (E(L(Tv ))) = 0. Every link of xi -value one incident to u1 or u2 (the M exposed leaves of Tv ) has its other end at a non-leaf node of Tv , hence, each such link
contributes 23 to α; we have two such links. Every link of xi -value one incident to w1
or w2 (the M -covered leaves of Tv ) has its other end either in V −L, and so contributes
1 to xi (E(L(Tv ), V −L)), or else has its other end in L−L(Tv ), and so contributes 21 to
1 i
3
1
2 x (E(L(Tv ), L−L(Tv ))); again, we have two such links. Hence, α ≥ 2( 2 ) + 2( 2 ) = 4.
i
i
Subcase 2.2.: x (E(L(Tv ))) = 1. Let `v denote a link of positive x -value such that one
end is in L(Tv ) and the other end, denoted by q, is not in Tv . Note that xi (`v ) = 1.
The end of `v in L(Tv ) must be M -covered; w.l.o.g. assume that this node is w1 .
Note that xi (δE (u)) = 1 for each leaf u of Tv . Since Tv is a bad 2-stem tree, the
links in E(L(Tv )) that are not incident to w1 are the twin link u2 w2 and possibly the
link u1 w2 (there is no link between u1 , u2 ). Thus, either xi (u2 w2 ) = 1 or xi (u1 w2 ) = 1,
and this contributes 32 to α via the term 23 xi (E(L(Tv ))). In either case, one of the
M -exposed leaves u1 or u2 is incident to a link of xi -value one that has its other end at
a non-leaf node of Tv , and this contributes 32 to α via the term xi (E(L(Tv ), V −L)) +
1P
i
u∈(V (Tv )−L) x (δE (u)).
2
We have two subcases, depending on whether q (the end of `v in V −V (Tv )) is a leaf
or not.
Subcase 2.2.1.: q ∈
/ L. Then, the link `v = w1 q contributes 1 to α via the term
xi (E(L(Tv ), V −L)). Then, we have α ≥ 23 + 32 + 1 = 4.
Subcase 2.2.2.: q ∈ L. Then, the link `v = w1 q contributes 21 to α via the term
1 i
2 x (E(L(Tv ), L−L(Tv ))).
Moreover, observe that we cannot have xi (u1 w2 ) = 1, otherwise the three links
`v = w1 q, u1 w2 , u2 w2 form a leafy 3-cover of Tv (see Figure 5(a)); recall that a
bad 2-stem tree cannot have a leafy 3-cover.
16

(a)

q

v

s1

u1

w1

(b)

s2

w2

q

v

s1

u2

u1

w1

s2

w2

u2

Figure 5. Illustration of leafy 3-covers of Tv for Subcase 2.2.2 in the proof of Lemma
6.6. The dashed lines indicate links and the thick dashed lines indicate M -links.
Thus, u2 w2 is the unique link in E(L(Tv )) with xi -value one. Now, focus on the
up (s )) ≥ xi (u w ) = 1. Thus, δ up (s ) contributes at
stem s2 ; by Lemma 4.6, xi (δE
2
2
2 2
E
1
1P
least 2 to α via the term 2 u∈(V (Tv )−L) xi (δE (u)).
Finally, note that u1 s2 is not present; otherwise, we would have a leafy 3cover consisting of the (hypothetical) link u1 s2 and the links `v = w1 q, u2 w2 (see
up (s ).
Figure 5(b)). Hence, the link of xi -value one incident with u1 is not in δE
2
3
1
1
3
Thus, we have α ≥ 2 + 2 + 2 + 2 = 4.

This completes the case analysis, and completes the proof.



6.4. Credit assignment for the algorithm and the preprocessing. Recall that the algorithm starts with a number of credits equal to the potential function, namely, the right-hand side
of the inequality in Lemma 5.2. In order to specify the potential function, we need to specify
creg , U
b(L−Λ) . We take M
creg
M
to be M ∩ E(L−Λ), i.e., the restriction of M to the subgraph
(L−Λ)
(L−Λ)
(L−Λ, E reg (L−Λ)). It can be seen that M ∩ E(L−Λ) = M −E(Λ) is a maximum matching of the
creg
b(L−Λ)
subgraph (L−Λ, E reg (L−Λ)), as required by the definition of M
in Section 5. We take U
(L−Λ)
b(L−Λ) in Section 5.
to be U ∩ (L−Λ); again, this agrees with the definition of U
The cost of Λ-contraction (Preprocessing step 1) is
≤ lbd y (Λ) +

1
2

X

u∈Rnonspcl ∩V

y(δE (u)),
(F prep )

where F prep is defined above. We subtract this quantity from our potential function, and then add
the credit of the compound nodes formed by contracting the trees Tv ∈ F prep , to get the remaining
potential function (i.e., total credits available) for the rest of the execution. Clearly, the remaining
potential function is
3
|M ∩ E(L−Λ)| + |U ∩ (L−Λ)| + |F prep |+
2
X
X
1
1
1 X
y(E(V −L)) +
y(δE (u)) +
y(E(u, V −Lbud
(u))) +
slacky (s)
(L
−
Λ)
2
2
2
nonspcl
prep
special
s∈S −SΛ
u∈(R
−V (F ))
u∈R
17

By the integral potential function we mean the sum of the first three terms above (namely,
∩ E(L−Λ)| + |U ∩ (L−Λ)| + |F prep |), and by the fractional potential function we mean the sum
of the remaining terms (namely, the sum of the four terms that use y).
The following observation is useful for simplifying our notation.
3
2 |M

Fact 6.7. For the current tree T 0 (after Λ-contraction), U ∩ (L−Λ) is the same as the set of M exposed original leaves, and M ∩ E(L−Λ) = M (T 0 ).
We start with the credit given by the integral potential function, and we maintain the following
assignment of credits to the nodes of T 0 and the links of M (T 0 ) = M ∩ E(L−Λ):
•
•
•
•

every M -exposed original leaf has one credit,
every compound node has one credit,
every link of M (T 0 ) has 23 credit, and
the root r has one credit.

It can be seen that the integral potential function suffices for assigning credits to the tree T 0 that
results from Λ-contraction. (See Part I (Section 6) for a discussion on the unit credit for the root
r.)
We define the integral credit S
of a set of links J (w.r.t. T 0 ) to be the sum of the credits of the
0 ), plus the sum of the (integral) credits of the nodes
0
M -links
pq such that V (Pp,q ) ⊆ uw∈J V (Pu,w
S
S
0 .
0
in uw∈J V (Pu,w ), plus one if r occurs as an original node in uw∈J Pu,w
In otherSwords, the integral credit of J is the sum of 23 times theSnumber of M -links pq such that
0
0
0 )⊆
the number
V (Pp,q
uw∈J V (Pu,w ), plusS
uw∈J V (Pu,w ), plus the number of compound nodes in
0 .
of M -exposed original leaves in the same set, plus one if r occurs as an original node in uw∈J Pu,w
Informally speaking, when a step of the algorithm contracts all the links in J, then this amount of
integral credit is available for this step (but not for subsequent steps).
Now, consider the fractional potential function. We use it to maintain an assignment of fractional credits to the (rooted) subtrees of T 0 . For any subtree Tv0 of T 0 , observe that V (Tv0 ) ∩
(Rnonspcl −V (F prep )) = V (Tv0 ) ∩ Rnonspcl , because none of the original nodes in V (F prep ) is present
in T 0 after the Λ-contraction; similarly, we have V (Tv0 ) ∩ (S−SΛ ) = V (Tv0 ) ∩ S, because none of the
stems in SΛ is present in T 0 after the Λ-contraction. For any subtree Tv0 of T 0 and for any vector
x ∈ RE , we use Φ(x, Tv0 ) to denote
1
x(E((V −L) ∩ V (Tv0 ), (V −L) ∩ (V (T 0 )−V (Tv0 ))))+
2
X
X
1
1
x(δE (u)) +
x(E(u, V −Lbud
(L−Λ) (u))) +
2
2
0
nonspcl
0
special
u∈V (Tv )∩R

u∈V (Tv )∩R

X

s∈V

slackx (s).

(Tv0 )∩S

The first term is defined on links that have both ends at original non-leaf nodes of T 0 , and
moreover, have exactly one end in Tv0 . Similarly, the last three terms denote credits that are assigned
to original nodes in Tv0 . We mention that the credits given by these four terms cannot be used two
or more times by the algorithm. This holds because all credit (integral or fractional) associated
with an original node of T 0 can be used by a step that first contracts the original node to a new
compound node; after that, none of the credit associated with this original node is available (any
original node contained in a compound node is essentially “invisible” to the algorithm).
Informally speaking, Φ(y, Tv0 ) denotes the fractional credit of Tv0 , that is, the part of the fractional
potential function that is “owned” by Tv0 . The fractional credit of Tv0 will be used together with its
integral credit for contracting Tv0 .
18

6.5. Second preprocessing step. We apply a second preprocessing step after the Λ-contraction
and before the main loop of the algorithm. It turns out that the set of nodes contracted by this step
is disjoint from the set of nodes contracted by the Λ-contraction.
Let b0 be a bud, let b1 b2 = buddylk(b0 ), and let s denote the stem such that b0 is a leaf of Ts ;
w.l.o.g. let b1 be the other leaf of Ts . Moreover, if b1 is also a bud, then we assume w.l.o.g. that
up(b0 ) is an ancestor of up(b1 ).
Preprocessing step 2: For each bud b0 and the two ends b1 , b2 of buddylk(b0 ) such that all three
of b0 , b1 , b2 are M -exposed, we contract the two links up(b0 )b0 and b1 b2 .
Fact 6.8. Preprocessing step 2 has sufficient credits.
Proof. Consider one “triple” consisting of a bud b0 and the two ends b1 , b2 of buddylk(b0 ) such that
b0 , b1 , b2 are M -exposed. Note that each of the M -exposed leaves b0 , b1 , b2 has 1 unit of credit. Thus,
we have sufficient credit for contracting two links and forming one compound node.

Remark 6.9. The results in this section show that Preprocessing step 2 is valid, in the sense that
the algorithm has sufficient credits to pay for the cost of this step. Moreover, Preprocessing step 2
is essential for the overall analysis (i.e., the algorithm cannot skip this step), because the proof of
Lemma 8.3 relies on this step.
7. Algorithm and credits II: Overall algorithm
We present pseudo-code for the overall algorithm, after discussing some preliminaries. Also, we
state and prove several assertions, i.e., we prove some basic properties maintained by the algorithm.
These assertions are critical for the analysis in the next section.
7.1. (Up-to-5) greedy contractions and assertions on M . Recall that
credit of a
Sthe integral
0 ), plus the
0 )⊆
V
(P
set of links J is given by the credits of the MS-links pq such that V (Pp,q
u,w
uw∈J
0 ), plus one if r occurs as an original node
sum
of
the
(integral)
credits
of
the
nodes
in
V
(P
u,w
uw∈J
S
0 .
in uw∈J Pu,w
We define an (up-to-5) greedy contraction to be a contraction of a set of links J such that

(i) |J| ≤ 5;
S
0
forms a connected
(ii) the contraction of J results in a single compound node, i.e., uw∈J Pu,w
graph;
(iii) the integral credit of J is ≥ |J| + 1.

Clearly, if an (up-to-5) greedy contraction is applicable, then, in polynomial time, the algorithm
can find a set of links J that is eligible for this step (by examining all link sets of size ≤ 5).

Remark 7.1. Clearly, the algorithm has sufficient credit for every application of (up-to-5) greedy
contraction. The overall analysis relies on repeatedly applying (up-to-5) greedy contractions until
no such contractions are applicable. In fact, every lemma/theorem in Section 8 assumes that no
(up-to-5) greedy contractions are applicable.
The following assertion is similar to Lemma 6.3 of Part I.
Lemma 7.2 (Assertions on M ). Suppose that no (up-to-5) greedy contractions are applicable. Then:
0
(1) For every M -link uw, every node in Pu,w
is an original node. In particular, w.r.t. T 0 , both
ends of each M -link are original leaf nodes.
(2) There exist no links between M -exposed leaves of T 0 .
19

7.2. Good semiclosed trees. Let Tv0 be a (rooted) subtree of T 0 . Let U (Tv0 ) denote the set of
M -exposed leaves of Tv0 (including both original nodes and compound nodes). Let C(Tv0 ) denote the
set of compound non-leaf nodes of Tv0 . Recall thatSM (Tv0 ) denotes the set of M -links that have both
ends in Tv0 . Note that every node in (V (Tv0 ) ∩ R) (V (Tv0 ) ∩ S) is an original node.
Recall that a semiclosed tree means a tree that is semiclosed w.r.t. the matching M , unless
mentioned otherwise. After the preprocessing steps, whenever we mention semiclosed trees, we
assume that no (up-to-5) greedy contractions are applicable (see Section 7.1). Then, Lemma 7.2(1)
implies that M is a set of leaf-to-leaf links w.r.t. the current tree T 0 . Hence, semiclosed trees (of T 0
w.r.t. M (T 0 )) are well defined.
We define the credit of a (rooted) subtree Tv0 of the current tree T 0 to be the sum of the fractional
credit of Tv0 , namely, Φ(y, Tv0 ), and the integral credit of Tv0 . The latter is given by the sum of the
following terms: 23 |M (Tv0 )|, the number of compound nodes in Tv0 , the number of M -exposed original
leaves in Tv0 , and an additional one if the root r is in V (Tv0 ) ∩ R. We call a semiclosed tree Tv0 good
if its credit is ≥ |Γ(M, Tv0 )| + 1.
The next result can be proved using arguments similar to the arguments used for proving Lemma 6.4
of Part I (although the potential function and credits in Parts I and II are different).
Lemma 7.3. Let Tv0 be a semiclosed tree. If at least one of the following conditions is satisfied, then
Tv0 is good.
•
•
•
•
•

Tv0 = T 0
C(Tv0 ) 6= ∅
|M (Tv0 )| ≥ 2
Φ(y, Tv0 ) ≥ 1
|M (Tv0 )| = 1 and Φ(y, Tv0 ) ≥ 21 .

7.3. Summary of the algorithm. We start with F := ∅ (F is the set of links picked by the
algorithm) and T 0 := T (T 0 is the current tree T /F ).
apply Preprocessing step 1 (Λ-contraction);
apply Preprocessing step 2;
while T 0 is not a single node do
repeatedly apply (up-to-5) greedy contractions until no such contractions are applicable;
find a good semiclosed tree Tv0 with a fitting cover J of size |Γ(M, Tv0 )| (Algorithm 2 in
Section 8 presents the details for finding such a semiclosed tree);
add J to F , contract Tv0 to a new compound node, update T 0 ;
end
Algorithm 1: Find an approximately optimal solution for TAP.
7.4. Stem assertion of the algorithm. This section presents a basic assertion that is important
for our analysis.
Recall that the algorithm iteratively contracts a set of links such that the tree-paths associated
with these links form a connected graph; the set of chosen links and their associated tree-paths are
0
contracted to form a new compound node. When we say that a contraction hits
S a node v0 of T , we
mean that a step of the execution contracts a set of links J such that v is in uw∈J V (Pu,w ); thus,
at least one of the tree-edges incident with v is covered by one of the links in J.
Stem assertion: Let s be a stem. The first contraction that hits a node of Ts (during the execution
of the algorithm) must hit s.
Property 7.4. The algorithm maintains the stem assertion.
20

Proof. Let s be a stem. First, consider the two preprocessing steps. Either all of the tree Ts is
contracted or none of the tree-edges of Ts is contracted by Preprocessing step 1 (Λ-contraction).
The same statement holds for Preprocessing step 2. Hence, the stem assertion is maintained by the
two preprocessing steps.
Next, suppose that the first contraction (in the execution) that hits a node in Ts is an (up-to5) greedy contraction that contracts a set of links J. If one of the links uw ∈ J has one end
0
in Ts and the other end not in Ts , then the tree path Pu,w
(in the current tree w.r.t. the first
contraction that hits a node of Ts ) must contain s, hence, the stem assertion is maintained. The
remaining possibility is that all links of J have both ends in Ts . Then observe that the number of
integral credits available in Ts is either zero, one, or two, and, in the last case, both leaves of Ts are
M -exposed. (By definition of stem, the root r is not in Ts , since r 6= s.) The greedy contraction of
J requires |J| + 1 integral credits. Thus, |J| = 1 and J contains the twin link of s. Contracting the
twin link clearly maintains the stem assertion.
Finally, suppose that the first contraction (in the execution) that hits a node in Ts is the contraction of a good semiclosed tree Tv0 . By Property 2.1, one of Ts , Tv0 is contained in the other. It is
easily seen that no proper subtree of Ts is a semiclosed tree. (Note that there is a sublink between
each leaf of Ts and s via the twin link of s, hence, any semiclosed tree containing a leaf of Ts that
is M -exposed will contain s too. Also, any semiclosed tree containing a leaf of Ts that is M -covered
will contain s too.) The only remaining possibility is that Tv0 contains Ts ; then, the contraction of
Tv0 maintains the stem assertion.


8. Analysis of the algorithm and deficient trees
This section has our main results. Informally speaking, the key result (Theorem 8.7) asserts the
following: if a semiclosed tree Tv0 is not good, then either Tv0 is a deficient tree (defined below) or Tv0
is a particular type of tree that is easily bypassed by our analysis.
The analysis consists of two parts. In Section 8.2, using local integrality of feasible solutions to the
Lasserre system, we show that all semiclosed trees are good, except for a few cases. The nontrivial
cases give deficient trees. Section 8.3 shows how to handle deficient trees. This leads to an efficient
algorithm for finding a good semiclosed tree together with a fitting cover of appropriate size.
Deficient 3-leaf tree: Suppose that Tv0 is a semiclosed tree with exactly three leaves a, b1 , b2 .
Clearly, among the nodes w of Tv0 either there is exactly one node with degT 0 (w) = 4 or there are
two nodes with degree 3 in T 0 . In the latter case, we denote these two nodes by u and q; moreover,
we fix the notation such that u is an ancestor of q, and the leaf b1 is not a descendant of q; thus,
a, b2 (but not b1 ) are descendants of q. In the former case, we denote by u the unique node that
is incident to four tree-edges. We call Tv0 a deficient 3-leaf tree (see Figure 6) if (i) the link b1 b2 is
present and it is in M (T 0 ), (ii) the link ab1 is present, and (iii) there exists a link b2 w such that
w ∈ V (T 0 )−V (Tv0 ).
Moreover, in the first case (with a unique node u in Tv0 with degT 0 (u) = 4), if conditions (i)–(iii)
hold with both labelings (b1 , b2 ) and (b2 , b1 ) of the M -link, then we fix the notation such that up(b2 )
is an ancestor of up(b1 ). For both cases, we call b2 the ceiling leaf of Tv0 .
Deficient 4-leaf tree: Let Tv0 be a semi-closed tree with 4 leaves and exactly one stem node s
such that all nodes in Ts0 are original, |M (Tv0 )| = 1, and the link in M (Tv0 ) has exactly one end in Ts0 .
Let the four leaves of Tv0 be a, b1 , b2 , c, let the two leaves of Ts0 be a, b1 , and let the link in M (Tv0 ) be
b1 b2 . Note that c is the M -exposed leaf of Tv0 that is not in Ts0 . Let p be the least common ancestor
of s and c. Then, Tv0 is called a deficient 4-leaf tree (see Figure 7) if (i) Tp0 contains all leaves of Tv0 ,
(ii) the link cs is present, and (iii) there exists a link b2 w such that w ∈ V (T 0 )−V (Tv0 ). We call the
link cs the latch of Tv0 .
21

v

(a)

v

(b)

u

u

b2

q

b1

a
b1

a

b2

Figure 6. Illustration of deficient 3-leaf tree. The dashed lines indicate links and
the thick dashed lines indicate M -links.
The contraction of the latch cs in a deficient 4-leaf tree results in a deficient 3-leaf tree due to the
presence of the links ab1 , up(b2 )b2 (see Figure 6(a)). Let b be the ceiling leaf of the resulting tree.
Clearly, up(b) is an ancestor of up(b2 ).

v
p

v
c

q

q=p
u
s

b2

s
b2

b1

a

c
b1

a

Figure 7. Illustration of deficient 4-leaf trees. The dashed lines indicate links and
the thick dashed lines indicate M -links.
8.1. Properties from assertions. We start with an observation on compound leaf nodes. The
next result (Lemma 8.2) states some properties pertaining to stem nodes and semiclosed trees; these
properties are often used in the analysis of the algorithm. The proof relies on the stem assertion.
After that we present a key lemma that pertains to some buds (Lemma 8.3); see the discussion
preceding that lemma.
Fact 8.1. If a compound leaf node contains a node u ∈ V (T ), then that compound node contains
Tu .
Lemma 8.2. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree with C(Tv0 ) = ∅.
(1) If Tv0 contains a stem node s, i.e., s ∈ S ∩ V (Tv0 ), then every node in Ts0 is original.
(2) In the original tree T , suppose that s is a stem node, and w is a leaf of Ts . If w is contained
in a compound node hci that is an M -exposed leaf of Tv0 , then all nodes of Ts are contained
in hci.
(3) In the original tree T , suppose that s is a stem node, and w is a leaf of Ts . If w is an original
M -exposed leaf of Tv0 , then s is an original node of Tv0 .
22

Proof. The first part follows from the stem assertion.
Consider the second part. By the stem assertion, and the fact that w is contained in hci, it can
be seen that s is contained in some compound node. If s is contained in hci, then the proof is done
by Fact 8.1. Now, suppose that s is contained in a different compound node hai. Then, there exists
a link between hci and hai (w.r.t. T 0 ), because the link ws is present in E (the input) since ws
is a sublink of twinlk(s). It can be seen that Tv0 contains hai as a leaf, because Tv0 is semiclosed,
C(Tv0 ) = ∅, hci is an M -exposed leaf of Tv0 , and the link between hci and hai is present. This gives a
contradiction because the compound leaf node hai contains s so it contains Ts (by Fact 8.1), hence,
hci cannot contain w.
The third part follows from arguments similar to that used for the second part; we give a sketch.
Suppose that s is contained in a compound node hai. If hai is a leaf of T 0 , then hai would contain
the subtree Ts (by Fact 8.1), and this would contradict the fact that the leaf w is an original node.
Since C(Tv0 ) = ∅, hai cannot be a non-leaf node of Tv0 . Thus, Tv0 contains w, but it does not contain
hai. This contradicts the fact that Tv0 is semiclosed, because there is a link between the M -exposed
leaf w of Tv0 and hai (due to the sublink ws of twinlk(s)).


The next lemma addresses a subtle point in our analysis. Consider a semiclosed tree Tv0 and
its fractional credit Φ(y, Tv0 ), and observe that the links between a bud b in Tv0 and a node in
V (Tv0 ) ∩ Rspecial (b) do not contribute to the fractional credit; see the third term in the definition of
Φ(y, Tv0 ) (the last displayed equation in Section 6.4). Nevertheless, under appropriate conditions,
we can exhibit fractional credits even when such links are present (see Lemma 8.5 and its proof).
In order to do this, we have to focus on buds contained in M -exposed compound leaves such that
there exists a link between the bud and a node “outside” the compound leaf (this is one part of
the analysis that examines an original node even after it has been contracted into a compound
node). The next lemma gives a tool for “counting” such buds, and the lemma is used twice in the
subsequent analysis. The first use is in the proof of Lemma 8.4 to show that a semiclosed tree Tv0
with |M (Tv0 )| ≤ 1 has O(1) such buds, and the second use is in the proof of Lemma 8.6 to show that
a semiclosed tree Tv0 with M (Tv0 ) = ∅ has no such buds.
Lemma 8.3. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree with C(Tv0 ) = ∅. Let b0 be a bud that is contained in an M -exposed compound leaf hci of Tv0
such that there exists a link ` incident to b0 that has exactly one end (namely, b0 ) in hci. Let
buddylk(b0 ) = b1 b2 , and let b1 b0 be the twin link (w.r.t. T ) incident to b0 . Then, b2 is an original
leaf node of Tv0 and b2 is incident to a link of M (Tv0 ).

Proof. Let the original ends of ` be b0 , w; thus, w is not contained in hci. Let s be the stem associated
with b0 ; note that the leaves of Ts are b0 , b1 . By Lemma 8.2(2), Ts is contained in hci. Since b0 is
contained in an M -exposed leaf hci of Tv0 , C(Tv0 ) = ∅, and Tv0 is semiclosed, either up(b0 ) is contained
in hci, or up(b0 ) is an original non-leaf node of Tv0 . Clearly, hci cannot contain up(b0 ), otherwise, hci
would contain Tup(b0 ) (by Fact 8.1), hence, the link b0 w would be contained in hci. Thus, up(b0 ) is
an original non-leaf node of Tv0 .
Consider the node b2 . Suppose that b2 is an original leaf node of T 0 . Then, b2 is in Tv0 (since Tv0 is
semiclosed), and b2 is M -covered (by Lemma 7.2(2) and the existence of the link b1 b2 ). Moreover,
both ends of the M -link incident to b2 are in Tv0 (since Tv0 is semiclosed). Thus, the lemma holds if
b2 is an original leaf node of T 0 .
Now, we may assume that b2 is contained in a compound node hai. The hypotheses of the
lemma imply that hai is a leaf in Tv0 . We must have hai = hci. Otherwise, either hai is M -covered,
contradicting Lemma 7.2(1), or hai is M -exposed, contradicting Lemma 7.2(2) because the link b1 b2
implies a link between the M -exposed leaves hai, hci. We conclude that hci contains all three of
b0 , b1 , b2 . In what follows, we use this to derive a contradiction to the fact that up(b0 ) is an original
non-leaf node in Tv0 .
23

By Preprocessing step 2, one of b0 , b1 , b2 is M -covered w.r.t. T , otherwise, the preprocessing step
contracts two links to form a compound node that contains up(b0 ). We have two cases, depending
on the M -links incident to b0 , b1 , b2 w.r.t. T .
Case 1: There exists an M -link w.r.t. T that has one end b ∈ {b0 , b1 , b2 } and the other end u ∈
L−{b0 , b1 , b2 }. If hci does not contain u, then we get a contradiction to Lemma 7.2(1) (M link incident to compound node). Otherwise, hci contains u, hence, hci contains Pb,u ; note
that up(b0 ) is in Pb,u , so hci contains up(b0 ). This is a contradiction.
Case 2: Each M -link w.r.t. T incident to one of b0 , b1 , b2 has both ends in {b0 , b1 , b2 }. There is only
one such M -link, namely, b0 b2 , since the twin link b0 b1 and the buddy link b1 b2 cannot be
in M . Then b0 is an M -covered bud w.r.t. T (see Figure 8).
up(b0 )

q
s

b2
b1

b0

Figure 8. Illustration of an M -covered bud w.r.t. T .
We may assume that b0 b2 ∈ M and b1 is M -exposed. Suppose that up(b1 ) is a descendent
of up(b0 ); then, b1 is a bud; this follows from the definition of bud (see Section 2). Then, we
get a contradiction since b0 b2 ∈ M and b0 b2 = buddylk(b1 ) (M has no buddy links). Hence,
up(b1 ) is a proper ancestor of up(b0 ). Thus, up(b0 ) 6= r, and no (rooted) subtree of Tup(b0 )
is semiclosed since b1 is M -exposed.
The following claim gives a contradiction and completes the proof of this lemma.
Claim. Suppose that b0 b2 is an M -link and b1 is M -exposed. Then, the first
contraction that hits a node of Tup(b0 ) (during the execution of the algorithm)
must hit up(b0 ).
First, consider the two preprocessing steps. Preprocessing step 1 contracts all bad 2-stem
trees. Note that no leaf of a bad 2-stem tree is a bud, hence, by Property 2.1, Tup(b0 ) is
disjoint from every bad 2-stem tree. Preprocessing step 2 applies when a bud b and the two
ends of buddylk(b) are all M -exposed. Since b0 is M -covered, Preprocessing step 2 does not
apply to b0 , b1 , b2 . Thus, the contractions in the preprocessing steps do not hit any node of
Tup(b0 )
Next, suppose that the first contraction (in the execution) that hits a node in Tup(b0 ) is
an (up-to-5) greedy contraction that contracts a set of links J. If one of the links uw ∈ J
has one end in Tup(b0 ) and the other end not in Tup(b0 ) , then the contraction must hit up(b0 ),
0
because the tree path Pu,w
(in the current tree at that contraction) contains up(b0 ). Thus,
the claim holds. The remaining possibility is that all links of J have both ends in Tup(b0 ) .
But observe that the number of integral credits available in Tup(b0 ) (in the current tree at
that contraction) is exactly 25 (due to one M -link and one M -exposed node), and this does
not suffice for contracting two or more links; moreover, no single-link contraction applies
because no singleton set J has integral credit > 32 .
24

Finally, suppose that the first contraction (in the execution) that hits a node in Tup(b0 ) is
the contraction of a good semiclosed tree Tw0 . By Property 2.1, one of Tup(b0 ) , Tw0 is contained
in the other. Since no (rooted) subtree of Tup(b0 ) is semiclosed, it follows that Tw0 contains
Tup(b0 ) . Then, the contraction of Tw0 hits up(b0 ). This proves the claim, and completes the
proof of the lemma.

8.2. Most semiclosed trees are good. Let Tv0 be a semiclosed tree. Let Lmatched (Tv0 ) denote the
set of M -covered leaves of Tv0 .
We call a compound node hci of Tv0 open if it is an M -exposed leaf of Tv0 , and moreover, hci
contains a bud b0 such that there exists an original link between b0 and an original node that is
not contained in hci. We call such a bud an open bud (it must be contained in an open compound
node and one of the original links incident to the bud is not contained in the compound node). Let
B comp (Tv0 ) denote the set of open buds of Tv0 . Let B orig (Tv0 ) denote the set of original nodes of Tv0
that are M -exposed buds. Let B(Tv0 ) = B orig (Tv0 ) ∪ B comp (Tv0 ).

Lemma 8.4. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree with C(Tv0 ) = ∅, |M (Tv0 )| ≤ 1 and |S ∩ V (Tv0 )| ≤P2.
Then, y can be written as a convex combination i∈Z λi xi such that xi ∈ Las3 (LP0 ) and xi |J is
integral, where J = {` ∈ δE (u) : u ∈ (S ∩ V (Tv0 )) ∪ Lmatched (Tv0 ) ∪ B(Tv0 )}.

Proof. We claim that |ones(x) ∩ J| ≤ 14 for any feasible solution x of (LP0 ). The conclusion (of the
lemma) follows easily from Theorem 4.1 and this claim.
To prove the claim, observe that |S ∩ V (Tv0 )| ≤ 2 and |Lmatched (Tv0 )| = 2|M (Tv0 )| ≤ 2, hence, by
Lemmas 4.3, 4.5, we have
|ones(x) ∩ {` ∈ δE (u) : u ∈ S ∩ V (Tv0 )}| ≤ 6,

|ones(x) ∩ {` ∈ δE (u) : u ∈ Lmatched (Tv0 )}| ≤ 2;

moreover, for each u ∈ B(Tv0 ), we have |ones(x) ∩ δE (u)| ≤ 1. Thus, to complete the proof of the
claim, we have to show that |B(Tv0 )| ≤ 6.
First, consider any bud b0 ∈ B orig (Tv0 ) and its associated stem s. By Lemma 8.2(3), s is an original
node of Tv0 , and so, s ∈ S ∩ V (Tv0 ). By Lemma 8.2(1), each leaf of Ts0 is an original node in T 0 . Let
b1 be the leaf of Ts0 other than b0 . By Lemma 7.2(2), b1 is M -covered (otherwise, the twin link b0 b1
connects two M -exposed leaves). Hence, b1 ∈
/ B orig (Tv0 ). It follows that each stem in S ∩ V (Tv0 ) has
at most one leaf in B orig (Tv0 ). Since |S ∩ V (Tv0 )| ≤ 2, we have |B orig (Tv0 )| ≤ 2.
Now, consider one of the buds b0 ∈ B comp (Tv0 ); b0 is contained in some open compound node and
one of the original links incident to b0 has its other end “outside” this compound node. Then, by
Lemma 8.3, the buddy link buddylk(b0 ) shares an end with an M -link in M (Tv0 ). Since |M (Tv0 )| ≤ 1
and each end of an M -link can be incident to ≤ 2 buddy links, we have |B comp (Tv0 )| ≤ 4. Therefore,
|B(Tv0 )| = |B orig (Tv0 )| + |B comp (Tv0 )| ≤ 6. This proves the claim.


Lemma 8.5. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree with C(Tv0 ) = ∅. Let J be a set of links that each have at least one end in Tv0 and no end in
Lmatched (Tv0 ) ∪ (S ∩ V (Tv0 )). Let x be a feasible solution of Las3 (LP0 ) such that x is integral on the
links {δE (u) : u ∈ B(Tv0 )}. Then,
1 1
Φ(x, Tv0 ) ≥ min{ , x(J)}.
2 2
P
1P
0
Proof. Let g(x, Tv ) denote 2 u∈Rnonspcl ∩V (Tv0 ) x(δE (u))+ 12 u∈Rspecial ∩V (Tv0 ) x(E(u, V −Lbud (u))). By
P
Fact 4.7, we have Φ(x, Tv0 ) ≥ g(x, Tv0 ) + s∈V (Tv0 )∩S slackx (s) ≥ g(x, Tv0 ). We will show that either
each link ` ∈ J contributes 12 x(`) to g(x, Tv0 ), thereby ensuring g(x, Tv0 ) ≥ 21 x(J), or there exists a
set of links that contribute 21 to g(x, Tv0 ).
25

Consider any link ` ∈ J with x(`) > 0. By Lemma 7.2(2), ` cannot have both ends at M -exposed
leaves. Thus, ` has at least one end in V (Tv0 ) ∩ R, since it has no end in Lmatched (Tv0 ) ∪ (S ∩ V (Tv0 )),
Tv0 is semiclosed, and C(Tv0 ) = ∅. It is easily seen that, except for one case, ` contributes ≥ 12 x(`) to
g(x, Tv0 ).
The exceptional case occurs when ` has original ends b0 and w, where b0 ∈ Lbud (w) and w ∈
special
R
(b0 ) ∩ V (Tv0 ), see Fact 2.3. Since J has no links incident to Lmatched (Tv0 ), it follows that
b0 ∈ B(Tv0 ) because either b0 is an M -exposed original leaf of Tv0 , or b0 is contained in an M -exposed
compound leaf of Tv0 ; in the latter case, b0 is an open bud (w.r.t. Tv0 ). Then, we have x(`) = 1
because x is integral on the links incident with nodes in B(Tv0 ). We claim that g(x, Tv0 ) ≥ 21 . Let ê
denote the tree-edge between w (the end of ` in V (Tv0 ) ∩ R) and its parent. Let δ + (ê) denote the
set of links with positive x-value that cover ê. Clearly, x(δ + (ê)) ≥ 1. Consider any link `q = pq
that is in δ + (ê), where q is a descendent of w (possibly, q = w) and p is not in Tw0 . If q is a
proper descendant of w, then (by the definition of Rspecial (b0 )) q is a descendant of the unique
child of w (see Figure 3), hence, ` and `q form an overlapping pair such that x(`) + x(`q ) > 1;
this contradicts the overlapping constraints of (LP0 ). Hence, we have q = w. Clearly, p (the other
end of `q ) cannot belong to Lbud (q) = Lbud (w) since p is not a descendant of q. Hence, we have

g(x, Tv0 ) ≥ 21 x(E(w, V −Lbud (w))) ≥ 21 x(δ + (ê)) ≥ 21 . This completes the proof.
Let Tv0 be a semiclosed tree. We construct an auxiliary graph in order to analyze the credits
available in Tv0 . We denote the auxiliary graph by AG(Tv0 ). This is a bipartite multigraph, and the
two sets in the node bipartition are denoted by AS(Tv0 ) and AU(Tv0 ). The first set consists of the
M -covered leaves Lmatched (Tv0 ) and the stems S ∩ V (Tv0 ). The second set contains an auxiliary node
v̄ (informally speaking, v̄ represents the node set V (T 0 )−V (Tv0 )), as well as all the M -exposed leaves
of Tv0 , thus, AU(Tv0 ) = {v̄} ∪ U (Tv0 ).
We define the edge set of AG(Tv0 ) as follows: for every link pq w.r.t. T 0 with p ∈ (S ∩ V (Tv0 )) ∪
matched
L
(Tv0 ), q ∈ U (Tv0 ), the edge pq is in AG(Tv0 ), and for every link pq w.r.t. T 0 such that p ∈
(S∩V (Tv0 ))∪Lmatched (Tv0 ), q ∈ V (T 0 )−V (Tv0 ), the edge pv̄ is in AG(Tv0 ). Thus, AG(Tv0 ) is a multigraph
(multiple copies of an edge may be present), and every edge in AG(Tv0 ) corresponds to a link w.r.t.
T 0 (see Figure 9).
AG(Tv0 )

Tv0
v

c

v̄

b

a

s

d

d
s

c
b

a

Figure 9. The left figure shows a semiclosed tree Tv0 where dashed lines indicate
links and the thick dashed line indicates an M -link. The right figure shows the
auxiliary graph AG(Tv0 ) and its node bipartition {s, b, c}, {v̄, a, d}.
In what follows, we may abuse the notation by not distinguishing between edges (sets of edges)
of AG(Tv0 ) and the corresponding links (sets of links) w.r.t. T 0 .
26

Lemma 8.6. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree such that Tv0 6= T 0 , C(Tv0 ) = ∅, |M (Tv0 )| ≤ 1 and |S ∩ V (Tv0 )| ≤ 2.
(1) Suppose that M (Tv0 ) = ∅. Then for any feasible solution x for Las3 (LP0 ), we have Φ(x, Tv0 ) ≥
1. Furthermore, Tv0 is good.
(2) Suppose that |M (Tv0 )| = 1, and |U (Tv0 )| ≥ |S ∩ V (Tv0 )| + 1. Moreover, suppose that x is a
feasible solution for Las3 (LP0 ) such that x|J is integral and Φ(x, Tv0 ) < 21 , where J = {` ∈
δE (u) : u ∈ (S ∩ V (Tv0 )) ∪ Lmatched (Tv0 ) ∪ B(Tv0 )}.
Then, |U (Tv0 )| = |S ∩ V (Tv0 )| + 1. Moreover, the auxiliary graph has a perfect matching
AM(Tv0 ) such that the following conditions hold:
(i) x(`) = 1 for each link ` ∈ AM(Tv0 ),
(ii) the links of AM(Tv0 ) cover Tv0 ,
(iii) for each stem node s ∈ S ∩ V (Tv0 ), twinlk(s) is in AM(Tv0 ),
(iv) AM(Tv0 ) has no links of the form v̄s, where s ∈ S ∩ V (Tv0 ).
0
0
Proof. Let êv denote the tree-edge between v and its parent;
P êv is well defined since Tv 0 6= T .
¯
¯
Let J = δE (êv ) ∪ (∪u∈U (Tv0 ) δE (u)). Then, x(J) = x(δE (êv )) + u∈U (Tv0 ) x(δE (u)) ≥ 1 + |U (Tv )|; the
equation holds because (i) Tv0 is semiclosed so none of the links in δE (êv ) is incident to an M -exposed
leaf of Tv0 , and (ii) by Lemma 7.2(2), no link has both ends at M -exposed leaves; the inequality holds
because x(δE (ê)) ≥ 1 forP
every tree-edge ê.
P
Let g(x, Tv0 ) denote 12 u∈Rnonspcl ∩V (Tv0 ) x(δE (u)) + 12 u∈Rspecial ∩V (Tv0 ) x(E(u, V −Lbud (u))).
P
By Fact 4.7, we have Φ(x, Tv0 ) ≥ g(x, Tv0 ) + s∈V (Tv0 )∩S slackx (s) ≥ g(x, Tv0 ).

Case (1): M (Tv0 ) = ∅. Clearly, |U (Tv0 )| ≥ 1, since Tv0 has at least one leaf.
¯ ≥ 1 (1 + |U (Tv0 )|) ≥ 1. We will show that every link ` ∈ J¯ contributes
Observe that 21 x(J)
2
≥ 12 x(`) to g(x, Tv0 ).
First, we show that S∩V (Tv0 ) = ∅. Otherwise, consider any s ∈ S∩V (Tv0 ); by Lemma 8.2(1),
every node in Ts0 is original, and so the twin link of s has both ends at M -exposed nodes
(since M (Tv0 ) = ∅); this contradicts Lemma 7.2(2).
Next, we show that B(Tv0 ) = ∅. Since S∩V (Tv0 ) = ∅, Lemma 8.2(3) implies that B orig (Tv0 ) =
∅ (if a bud b0 ∈ B orig (Tv0 ) is present as an original M -exposed leaf of Tv0 , then its stem is
present as an original node of Tv0 ). Also, we have B comp (Tv0 ) = ∅, otherwise, by Lemma 8.3,
there exists a link in M (Tv0 ) (this is impossible since M (Tv0 ) = ∅). Thus, B(Tv0 ) = ∅.
Now, observe that every link ` ∈ J¯ has an end in V (Tv0 ) ∩ R, and hence, it contributes
1
0
0
2 x(`) to g(x, Tv ). Therefore, Φ(x, Tv ) ≥ 1. Since this inequality holds for every feasible
solution x of Las3 (LP0 ), we have Φ(y, Tv0 ) ≥ 1. Hence, by Lemma 7.3, Tv0 is good.
Case (2): In this case, |M (Tv0 )| = 1 and |U (Tv0 )| ≥ |S ∩ V (Tv0 )| + 1. Moreover, x|J is integral, where
J = {` ∈ δE (u) : u ∈ (S ∩ V (Tv0 )) ∪ Lmatched (Tv0 ) ∪ B(Tv0 )}.
First, we show that x(δE (s)) ≤ 1 for each stem s ∈ S ∩ V (Tv0 ). We use a contradiction
argument. Suppose that x(δE (s)) > 1. Let δ + (s) denote the set of links of positive x-value
incident to s. Note that every link ` in δ + (s) has x(`) = 1 because x|J is integral. Since
x(δE (s)) > 1, we have |δ + (s)| ≥ 2. This implies that each of the buddy links associated
with the stem s has x-value zero. To see this, note that the set of links in δ + (s) covering
each of the three tree-edges incident to s is an overlapping clique, hence, at most one link of
δ + (s) belongs to one of these overlapping cliques (by the overlapping constraints of (LP0 ));
moreover, each buddy link associated with s is overlapping with the links that belongs to
two of these overlapping cliques (see Figure 10); hence, if a buddy link ` associated with s
has x(`) > 0, then we get a violation (of an overlapping constraint of (LP0 )) for one of the
three overlapping cliques. Since the buddy links associated with s (if any) have x-value zero,
27

we have Φ(x, Tv0 ) ≥ slackx (s) ≥
contradiction.

1
2




x(δE (s)) − x(twinlk(s)) ≥ 21 , and this gives the desired

q

p
s

b2
`

b3
b1

b0

Figure 10. Illustration of a buddy link ` in the proof of Lemma 8.6. Note that `
up (s) and δ (ê) ∩ δ (s), where ê is the tree-edge
is overlapping with links in both δE
E
E
between b3 and s. For example, ` is overlapping with the links sp and sb3 .
For any M -covered leaf w in Tv0 , by Lemma 7.2(1), w is an original node, and moreover,
we have x(δE (w)) ≤ 1, by Lemma 4.3. Thus, we have x(δE (w)) ≤ 1 for each node w ∈
Lmatched (Tv0 ) ∪ (S ∩ V (Tv0 )) = AS(Tv0 ).
0
¯
¯ S
Let Je = J−
w∈AS(Tv0 ) δE (w); this is the set of links in J but not in AG(Tv ). We have
e ≥ 1 , which
e < 1; otherwise, by Lemma 8.5, we would have Φ(x, Tv0 ) ≥ min{ 1 , 1 x(J)}
x(J)
2 2
2
0
is a contradiction. Then, by the conditions in the hypothesis (|M (Tv )| = 1 and |U (Tv0 )| ≥
|S ∩ V (Tv0 )| + 1) and theX
fact that |AU(Tv0 )| = |U (Tv0 )| + 1, we have
e = x(J)
¯ −
1 > x(J)
x(J¯ ∩ δE (w)) ≥ |AU(Tv0 )| − |AS(Tv0 )|
w∈AS(Tv0 )

= |U (Tv0 )| + 1 − 2|M (Tv0 )| − |S ∩ V (Tv0 )|

= |U (Tv0 )| − (1 + |S ∩ V (Tv0 )|) ≥ 0.
Hence, we have |U (Tv0 )| = |S ∩ V (Tv0 )| + 1, and |AS(Tv0 )| = |AU(Tv0 )|. For each w ∈ AS(Tv0 ),
we have x(J¯ ∩ δE (w)) = 1 because x(`) is integral for each link ` ∈ J¯ ∩ δE (w) (otherwise,
P
0
0
0
¯
e
w∈AS(Tv0 ) x(J ∩ δE (w)) ≤ |AS(Tv )| − 1 implies that x(J) ≥ |AU(Tv )| − |AS(Tv )| + 1 ≥ 1).
0
For each w ∈ AS(Tv ), define `w to be the link in δE (w) ∩ J¯ with x(`w ) = 1. We claim
that these links form a perfect matching of the auxiliary graph, thus, AM(Tv0 ) = {lw :
w ∈ AS(Tv0 )}. Otherwise, there exist two links `w1 , `w2 (where w1 , w2 ∈ AS(Tv0 )) that are
¯ ≥ |AU(Tv0 )| + 1, which implies that
incident to the same node u ∈ AU(Tv0 ). Then, x(J)
P
0
0
e = x(J)
¯ −
¯
x(J)
w∈AS(Tv0 ) x(J ∩ δE (w)) ≥ |AU(Tv )| + 1 − |AS(Tv )| ≥ 1. This contradicts the
e < 1. Our claim follows.
fact that x(J)
We claim that AM(Tv0 ) covers Tv0 . Otherwise, there exists a tree-edge ê0 in Tv0 that is not
covered by AM(Tv0 ). Let δ + (ê0 ) denote the set of links of positive x-value in δE (ê0 ). Then, we
have x(δ + (ê0 )) ≥ 1, and none of the links in δ + (ê0 ) is incident to (S ∩ V (Tv0 )) ∪ Lmatched (Tv0 );
the latter assertion holds because x(`w ) = 1 and x(δE (w)) ≤ 1 for every w ∈ AS(Tv0 ), i.e., the
nodes in AS(Tv0 ) are already “saturated” by AM(Tv0 ). Thus, Lemma 8.5 applies to δ + (ê0 ),
and we have Φ(x, Tv0 ) ≥ min{ 21 , 12 δ + (ê0 )} ≥ 12 , which is a contradiction. Our claim follows:
AM(Tv0 ) covers Tv0 .
Additionally, we claim that AM(Tv0 ) has no links between v̄ and S ∩ V (Tv0 ). By way of
contradiction, assume that there exists a link ` = sq ∈ AM(Tv0 ) such that s ∈ S ∩ V (Tv0 )
and q ∈
/ V (Tv0 ). Suppose that q is an original non-leaf node. Then sq is a link between two
28

original non-leaf nodes with x(sq) = 1, hence, we have Φ(x, Tv0 ) ≥ 21 due to Fact 4.7 and the
following term in Φ(x, Tv0 ):
1
x(E((V −L) ∩ V (Tv0 ), (V −L) ∩ (V (T 0 )−V (Tv0 )))).
2
This is a contradiction. Otherwise, if q is a compound node or an original leaf, then we
claim that an (up-to-5) greedy contraction applies, and this too gives a contradiction. Note
that |S ∩ V (Tv0 )| ≤ 2 and |M (Tv0 )| = 1, hence, |AM(Tv0 )| ≤ 4. The credit assigned to the
leaves and matching links in Tv0 is 23 + |U (Tv0 )| = 32 + |S ∩ V (Tv0 )| + 1 = |AM(Tv0 )| + 21 . If
q is a compound node or an original M -exposed leaf, then q provides one additional credit,
and this suffices for an (up-to-5) greedy contraction of the links of AM(Tv0 ); otherwise, q is
an M -covered leaf, and the M -link `q incident to q provides additional 23 credit, and this
suffices for an (up-to-5) greedy contraction of `q together with the links of AM(Tv0 ). Our
claim follows: AM(Tv0 ) has no link of the form v̄s, s ∈ S ∩ V (Tv0 ).
Finally, we prove that twinlk(s) is in AM(Tv0 ) for each stem s ∈ S ∩ V (Tv0 ). Consider any
stem s ∈ S ∩ V (Tv0 ). By Lemma 8.2(1), Ts0 is contained in Tv0 and every node in Ts0 is original.
Let the leaves of Ts0 be a, b0 ; thus, twinlk(s) = ab0 .
Lemma 7.2(2) implies that one end of the twin link ab0 is M -covered. Since x|J is integral,
0
and J contains ab0 (each link incident to Lmatched (Tv0 ) is in
PJ), either ab0 ∈ AM(Tv ) or
x(ab0 ) = 0. We may assume that x(ab0 ) = 0. Suppose that b∈Lbud (s) x(buddylk(b)) = 0,
i.e., there does not exist a buddy link incident to Ts0 that has positive x-value. Consider the
link `s in AM(Tv0 ) incident with s; clearly, x(`s ) = 1. Thus, we have Φ(x, Tv0 ) ≥ slackx (s) ≥
1
1
2 x(`s ) = 2 . This is a contradiction.

q
s

b2
è

`s

a

b0

Figure 11. Illustration of è and `s in the proof of Lemma 8.6.

S
Now, we may assume that there exists a buddy link è ∈ b∈Lbud (s) {buddylk(b)} such that
x( è) > 0. W.l.o.g., let the original ends of è be a and b2 . Let q be the least common ancestor
of a and b2 w.r.t. T ; see Figure 11 and also see Figure 2 in Section 2. Observe that Tv0
contains q (either as an original node or within a compound node), because Tv0 has at least
3 leaves, whereas every proper subtree of Tq has ≤ 2 leaves. Thus, Tv0 contains both ends of
è. Note that b2 (the end of è not in T 0 ) may be an original leaf of T 0 or it may be contained
s
v
in a compound leaf of Tv0 (since C(Tv0 ) = ∅, b2 cannot be contained in a non-leaf compound
node of Tv0 ).
up (s), otherwise, ` , è form an overlapping pair (since x( è) > 0, x(` ) =
Observe that `s 6∈ δE
s
s
0 . Thus, ` = sb (` has an end
1). By similar arguments, `s cannot have both ends in Pa,s
s
0
s
dn (s) and ` ∈ AM(T 0 )). Let `¯ denote the link in
at an M -exposed leaf of Ts0 because `s ∈ δE
s
q
v
0
AM(Tv ) that covers the tree-edge between q and its parent (possibly, q = v, and in this case,
`¯q is the link incident with v̄ in AM(Tv0 )). Note that `¯q has an end at a leaf in Tq0 . Then,
29

`¯q forms an overlapping pair with either `s or è (since x(`¯q ) = 1, x(`s ) = 1, x( è) > 0). This
contradicts the overlapping constraints of (LP0 ). This completes the proof of the lemma.


The following theorem is the key result of this paper. It is used only once; see the last paragraph
of the proof of Theorem 8.8. Note that the last alternative in Theorem 8.7 (item (3)) is addressed
in the last paragraph of the proof of Theorem 8.8.
Theorem 8.7. Suppose that no (up-to-5) greedy contractions are applicable. Let Tv0 be a semiclosed
tree that is not good. Then one of the following holds for Tv0 .
(1) Tv0 is a deficient 3-leaf tree.
(2) Tv0 is a deficient 4-leaf tree.
(3) Tv0 has 4 leaves with |M (Tv0 )| = 1, and moreover Tv0 has no cover of size 3.
Proof. Since Tv0 is not good, Lemma 7.3 and Lemma 8.6(1) imply that Tv0 6= T 0 , C(Tv0 ) = ∅, and
|M (Tv0 )| = 1.
Observe that Tv0 has at least one M -exposed leaf. Otherwise, since |M (Tv0 )| = 1, Tv0 has exactly
two leaves and there exists an M -link between these two leaves; moreover, by Lemma 7.2(1), every
node on the path of T 0 between these two leaves is original; it follows that the link in M (Tv0 ) is a
twin link; this contradicts the definition of M . Thus, Tv0 has an M -exposed leaf and exactly two
M -covered leaves. Hence, Tv0 has at least three leaves.
Also, observe that |S ∩ V (Tv0 )| ≤ 2. Otherwise, suppose that |S ∩ V (Tv0 )| ≥ 3. Then, by
Lemma 8.2(1), for every stem s ∈ S ∩ V (Tv0 ), every node in Ts0 is original; hence, there exists a
stem s∗ ∈ S ∩ V (Tv0 ) such that both the leaves of Ts0∗ are M -exposed and there exists a twin link
between these two leaves; this contradicts Lemma 7.2(2).
Let ê denote the tree-edge between v and its parent. Let J denote {` ∈ δE (u) : u ∈ (S ∩ V (Tv0 )) ∪
Lmatched (Tv0 ) ∪ B(Tv0 )}, where B(Tv0 ) = B orig (Tv0 ) ∪ B comp (Tv0 ) (see the discussion before Lemma 8.4
for the definitions of B orig (Tv0 ) and B comp (Tv0 )).
P
By Lemma 8.4, y can be written as a convex combination i∈Z λi xi such that xi ∈ Las3 (LP0 )
and xi |J is integral. Since Tv0 is not good and |M (Tv0 )| = 1, Lemma 7.3 implies that Φ(y, Tv0 ) < 21 .
Thus, there exists an i0 ∈ Z such that Φ(xi0 , Tv0 ) < 12 .
We claim that |U (Tv0 )| ≤ |S ∩V (Tv0 )|+1. To see this, suppose that |U (Tv0 )| ≥ |S ∩V (Tv0 )|+1. Then,
all of the conditions of Lemma 8.6(2) apply, hence, the lemma implies that |U (Tv0 )| = |S ∩V (Tv0 )|+1.
Our claim follows.
Now, we analyze a few cases, depending on the number of leaves of Tv0 . By Lemma 8.2(1), for
every stem s ∈ S ∩ V (Tv0 ), every node in Ts0 is original; thus, each stem s ∈ S ∩ V (Tv0 ) contributes
two original leaves to Tv0 . Therefore, |S ∩ V (Tv0 )| ≤ |L(Tv0 )|/2.
Case 1: Tv0 has exactly three leaves. Let the three leaves be a, b1 , b2 , where a is M -exposed and
b1 , b2 are M -covered; thus, b1 b2 is the unique link in M (Tv0 ), and b1 , b2 are original nodes by
Lemma 7.2(1). Clearly, |S ∩ V (Tv0 )| ≤ 1. We have two subcases, depending on |S ∩ V (Tv0 )|.
Subcase 1.1: |S ∩ V (Tv0 )| = 1. Let s be the stem in Tv0 . The M -link b1 b2 cannot have both
ends in Ts0 (since M contains no twin links). Thus, the M -exposed leaf a is a leaf of Ts0 .
Then, it can be seen that a is a bud and buddylk(a) = b1 b2 (see the definition of bud
in Section 2). This is a contradiction, since M contains no buddy links.
Subcase 1.2: |S ∩ V (Tv0 )| = 0. Then we have |U (Tv0 )| = 1 = 1 + |S ∩ V (Tv0 )|. By
Lemma 8.6(2)(i–iv), there exist two links `v ∈ δE (ê) and `a ∈ δE (a) such that xi0 (`v ) =
xi0 (`a ) = 1, these two links cover Tv0 , and moreover, each of b1 , b2 is incident to exactly
one of these two links (since the auxiliary graph has a perfect matching formed by these
two links).
30

If there is only one non-leaf node with degree other than 2 in Tv0 (see Figure 6(a)),
then Tv0 is a deficient 3-leaf tree. We are done. Otherwise, we have exactly two non-leaf
nodes u, q in Tv0 with degree other than 2. In fact, both these nodes have degree 3 since
Tv0 has exactly 3 leaves. W.l.o.g., let u be a proper ancestor of q. Then, Tq0 has only two
leaves. By the argument at the beginning of the proof, the M -link in Tv0 cannot connect
both leaves in Tq0 . This implies that one leaf of Tq0 is M -exposed. Thus, a is a leaf of
Tq0 . W.l.o.g., let the other leaf of Tq0 be b2 . Then, b1 is the third leaf, which is not in Tq0 .
Suppose that `v is incident to b1 and `a is incident to b2 . Then, the tree-edge between q and its parent is not covered by these two links (see Figure 12(a)). This is a
contradiction. Hence, `v is incident to b2 and `a is incident to b1 (see Figure 12(b)).
Therefore, Tv0 satisfies all the conditions of a deficient 3-leaf tree.
(a)

v

`v

u

(b)

`v

u

q

b1

v

q

b1
b2

`a

a

b2

`a

a

Figure 12. The links `v and `a in Subcase 1.2 of the proof of Theorem 8.7. The
dashed lines indicate links and the thick dashed lines indicate M -links.
Case 2: Tv0 has exactly four leaves. Let the four leaves be a1 , a2 , b1 , b2 , where a1 , a2 are M -exposed
and b1 , b2 are M -covered; thus, b1 b2 is the unique link in M (Tv0 ), and b1 , b2 are original nodes
by Lemma 7.2(1). We have 1 = |U (Tv0 )| − 1 ≤ |S ∩ V (Tv0 )| ≤ 2. As above, we have two
subcases, depending on |S ∩ V (Tv0 )|.
Subcase 2.1: |S ∩ V (Tv0 )| = 1. Let s be the stem in Tv0 . By Lemma 7.2(2), it can be seen
that the twin link of s is incident to one M -exposed leaf, say a1 , and to one M -covered
leaf, say b1 (see Subcase 1.1).
Note that |U (Tv0 )| = 2 = 1 + |S ∩ V (Tv0 )|. By Lemma 8.6(2)(i–iv), there exist three
links a1 b1 (the twin link of s), `v ∈ δE (ê) and `a2 ∈ δE (a2 ) such that xi0 (a1 b1 ) =
xi0 (`v ) = xi0 (`a2 ) = 1, these three links cover Tv0 , and moreover, each of s, b2 is incident
to exactly one of the two links `v , `a2 (since the auxiliary graph has a perfect matching
formed by the three links); moreover, s cannot be incident to `v (by Lemma 8.6(2)(iv)).
Thus `v is incident to b2 , and `a2 is incident to s, i.e., `a2 = a2 s.
Let p be the least common ancestor of s and a2 (in Tv0 ). If Tp0 does not contain all
the leaves of Tv0 , then it can be seen that the tree-edge between p and its parent is not
covered by the three links a1 b1 , a2 s, `v (see Figure 13(a)). This is a contradiction (since
Tv0 is covered by {a1 b1 , a2 s, `v }). It follows that Tp0 contains all the leaves of Tv0 . Then,
it can be seen that Tv0 is a deficient 4-leaf tree (see Figure 13(b)).
Subcase 2.2: |S ∩ V (Tv0 )| = 2. If Tv0 has no cover of size 3, then item (3) in the statement
of the theorem holds. Thus, we may assume that Tv0 has a cover of size 3.
Let s1 , s2 be the two stems in Tv0 . Let a1 , b1 be the original leaves of Ts01 , and let
a2 , b2 be the original leaves of Ts02 . We may assume that a1 , a2 are M -exposed and b1 , b2
are M -covered, because each twin link is incident to one M -exposed leaf and to one
31

(a)

v

(b)

`v

v
p
a2

`v
p

b2

a2

`a2
`a2
b1

s

s

b2
a1

b1

a1

Figure 13. The links `v , `a2 and a1 b1 in subcase 2.1 of the proof of Theorem 8.7.
The dashed lines indicate links and the thick dashed lines indicate M -links. Another
case could occur, but it is not shown here (see Figure 7).

M -covered leaf by Lemma 7.2(2) (see Subcase 2.1). Thus, b1 b2 is the unique link in
M (Tv0 ).
By Lemma 8.2(1) and C(Tv0 ) = ∅, Tv0 has no compound nodes, i.e., all its nodes are
original.
Observe that Tv0 has at least 3 21 credits from the two M -exposed leaves and the
M -link.
Consider the possible leaf-to-leaf links of Tv0 . The link a1 a2 does not exist, by
Lemma 7.2(2), since a1 , a2 are both M -exposed. If both the links a1 b2 and a2 b1 exist, then an (up-to-5) greedy contraction applies (we contract these two links and we
have 3 21 credits). Thus, at most one of the links a1 b2 or a2 b1 is present.
If Tv has no leafy 3-cover w.r.t. T , then it satisfies all the conditions for a bad 2-stem
tree, hence, it would have been contracted in Preprocessing step 1 (Λ-contraction). This
is a contradiction.
Thus, we may assume that Tv has a leafy 3-cover Je = {`0 , `1 , `2 } w.r.t. T , where
`0 = uw is a link such that one end u is in Tv and the other end w is a leaf in L−L(Tv ).
Let `00 = uw0 be the link w.r.t. T 0 that corresponds to `0 , where w0 = w if w is still an
original node in T 0 , and otherwise, w0 is the compound node containing w. Note that
in either case, w0 is not in V (Tv0 ) since every node in Tv0 is original. If w0 is a compound
node or an M -exposed original leaf, then an (up-to-5) greedy contraction applies (we
contract the 3 links in Je and we have 4 21 credits). Otherwise, if w0 is an M -covered
original leaf, then again an (up-to-5) greedy contraction applies (we contract 4 links,
namely, the links in Je and the M -link incident to w, and we have 3 12 + 32 = 5 credits).
Thus, the existence of a leafy 3-cover gives a contradiction.
Case 3: Tv0 has at least five leaves. Then, Tv0 has at least three M -exposed leaves and two M -covered
leaves. Thus, we have 3 ≤ |U (Tv0 )| ≤ |S ∩ V (Tv0 )| + 1 ≤ 3, since |S ∩ V (Tv0 )| ≤ 2; it follows
that |U (Tv0 )| = 3, |S ∩ V (Tv0 )| = 2, and Tv0 has exactly 5 leaves.
Let s1 , s2 be the two stems in Tv0 . Let a1 , b1 be the original leaves of Ts01 , and let a2 , b2
be the original leaves of Ts02 . We may assume that a1 , a2 are M -exposed and b1 , b2 are M covered, because each twin link is incident to one M -exposed leaf and to one M -covered leaf
by Lemma 7.2(2) (see Subcase 2.1). Thus, b1 b2 is the unique link in M (Tv0 ). Let u be the
fifth leaf of Tv0 , where u is not in Ts01 nor in Ts02 .
Since |U (Tv0 )| = 3 = 1 + |S ∩ V (Tv0 )|, Lemma 8.6(2)(i–iv) implies that there exist four links
`v ∈ δE (ê), `u ∈ δE (u), a1 b1 , a2 b2 (the twin links of s1 , s2 ) such that each of s1 , s2 is incident
32

to exactly one of the two links `v , `u (since the auxiliary graph has a perfect matching formed
by these four links); moreover, `v cannot be incident to {s1 , s2 } (by Lemma 8.6(2)(iv)). This
is impossible. Thus, Tv0 cannot have more than four leaves.
The theorem follows from the above case analysis.

8.3. Addressing deficient trees. This section discusses the missing piece of the algorithm, namely,
the handling of deficient trees. Even, et al., see [5, Section 4.3], presented an elegant method for
addressing deficient 3-leaf trees. We use essentially the same method in Part I (Section 7.2). The
key point is to compute another (auxiliary) matching of the leaf-to-leaf links of T 0 , and then to find
a minimally semiclosed tree Tv0 w.r.t. this auxiliary matching; moreover, we prove (in Theorem 7.4
of Part I) that Tv0 is a good semiclosed tree w.r.t. the “original matching,” and Tv0 has a fitting cover
of appropriate size. In this section, we extend this method to address deficient 3-leaf trees as well as
deficient 4-leaf trees. The extension is straightforward (but non-trivial). We start by “transforming”
the current tree T 0 to another tree Te; this is achieved by applying “latch contractions” to the latches
of deficient 4-leaf trees in an appropriate way (the details are discussed below). Then, we apply the
method from Part I (Section 7.2) to Te. Thus, the main goal in this section is to find a semiclosed
tree Tv0 w.r.t. M of the current tree T 0 such that Tv0 is good (i.e., it has ≥ |Γ(M, Tv0 )| + 1 credits)
and Tv0 has a fitting cover of size |Γ(M, Tv0 )|.
For a deficient 3-leaf tree Tv0 , if Tv0 is not a proper subtree of another deficient 3-leaf tree, then
we call Tv0 a maximal deficient 3-leaf tree. Similarly, we define a maximal deficient 4-leaf tree. By
Property 2.1, any two different maximal deficient 3-leaf trees are disjoint; similarly, any two different
maximal deficient 4-leaf trees are disjoint.
Let E latch denote the set of latches of all maximal deficient 4-leaf trees of T 0 . Let Te = T 0 /E latch .
We mention that Te is an auxiliary graph that is used for achieving the main goal of this section
(find a semiclosed tree Tv0 with desired properties), and other than that, the algorithm does not
refer to Te at all; thus, the algorithm does not add any latch to F while constructing Te, nor does it
incur any credits while constructing Te. By a latched-node we mean a node of Te that results from
the contraction of a latch (note that these are not compound nodes of T 0 , and the algorithm does
not assign any credits to a latched-node).
Since two different maximal deficient 4-leaf trees are disjoint, each “latch contraction” results in
a distinct latched-node; thus, there is a bijection between the latches of T 0 and the latched-nodes of
Te. For a subtree Tew of Te, we use latch(Tew ) to denote the set consisting of latches that correspond
to latched-nodes of Tew .
For a node w of T 0 , let w
e denote the node of Te that corresponds to w. If there exists no latch cs of
0
0
T such that w is in Pc,s (the path of T 0 between c, s), then w
e = w, otherwise, w
e is the latched-node
0 (in this case, the latch cs is unique
formed by contracting the (unique) latch cs such that w is in Pc,s
because two different maximal deficient 4-leaf trees are disjoint).
Then, as in Part I (Section 7.2), we construct an auxiliary matching of the leaf-to-leaf links of
Te denoted by M new . For ease of exposition, we denote the image (in Te) of M (T 0 ) by M (Te), and
we refer to the image (in Te) of a link in M (T 0 ) as an M -link w.r.t. Te (this is justified because any
M -link w.r.t. T 0 has no ends in common with the nodes of T 0 that get contracted into latchednodes). To construct M new , we start with M new := M , then we examine each maximal deficient
3-leaf tree Tewe of Te and we replace the unique link of M (Tewe ) in M new by another leaf-to-leaf link.
In more detail, consider any maximal deficient 3-leaf tree Tewe , and let the three leaves be a, b, d,
where a is M -exposed, b is the ceiling leaf, and bd is the unique link in M (Tewe ); we remove the
M -link bd from M new and instead we add the link ad to M new (see Algorithm 2). Since any two
different maximal deficient 3-leaf trees are disjoint, this replacement takes place independently for
each maximal deficient 3-leaf tree. We mention that M new is an auxiliary matching that is used for
33

achieving the main goal of this section (find a semiclosed tree Tv0 with desired properties), and other
than that, the algorithm does not refer to M new at all; whereas, the matching M (and its image
M (T 0 )) are used throughout the algorithm and its analysis.
Theorem 8.8. Suppose that no (up-to-5) greedy contractions are applicable. Let Te = T 0 /E latch ,
and let Teve be a minimally semiclosed tree w.r.t. M new . Then, ve cannot be a latched-node of Te; thus,
ve = v, where v is a node of T 0 . Moreover, Tv0 is a good semiclosed tree w.r.t. M and Tv0 has a fitting
cover Γ(M new , Tev ) ∪ latch(Tev ) of size |Γ(M, Tv0 )|.

Proof. We start by addressing the first statement. By way of contradiction, suppose that ve is a
latched-node. Observe that every latched-node is contained in a deficient 3-leaf tree of Te (a latchednode is formed by a “latch contraction” that results in a deficient 3-leaf tree). Hence, Teve is a subtree
of a maximal deficient 3-leaf tree of Te. But, by our construction of M new , the ceiling leaf of every
maximal deficient 3-leaf tree is M new -exposed, hence, no subtree of a maximal deficient 3-leaf tree
is semiclosed w.r.t. M new . Thus, Teve is not semiclosed w.r.t. M new . This is a contradiction.
It follows that ve cannot be a latched-node. Thus, there exists a node v in T 0 such that v = ve;
moreover, Teve = Tev , and Tv0 is well defined.
Claim 8.9. (1) If Tv0 has a node in a maximal deficient 4-leaf tree of T 0 , then Tv0
properly contains this maximal deficient 4-leaf tree.
(2) If Tv0 has a node in a maximal deficient 3-leaf tree of T 0 , then Tv0 properly contains
this maximal deficient 3-leaf tree.

We address statement (1) of the claim. Suppose that Tv0 has a node in a maximal deficient 4-leaf
tree Tw0 . By “latch contraction,” Tw0 is transformed to a deficient 3-leaf tree Tewe of Te. Thus, Tev has
a node in a maximal deficient 3-leaf tree Teue , where u
e is an ancestor of w
e in Te. But, (as discussed
new
e
e
above) no subtree of Tue is semiclosed w.r.t. M . Hence, Tv cannot be a subtree of Teue . Then
Property 2.1 implies that Tev properly contains Teue . Hence, v is a proper ancestor of w in T 0 , and Tv0
properly contains Tw0 .
Next, we address statement (2) of the claim. Suppose that Tv0 has a node in a maximal deficient
3-leaf tree Tw0 . If this maximal deficient 3-leaf tree is contained in a maximal deficient 4-leaf tree,
then we are done by the previous discussion. Hence, by Property 2.1, we may assume that Tw0 has
no node in a maximal deficient 4-leaf tree. Then Tewe contains no latched-node, and Tewe = Tew = Tw0 is
a maximal deficient 3-leaf tree of Te. Since Tev has a node in Tew , and no subtree of Tew is semiclosed
w.r.t. M new , Property 2.1 implies that Tev properly contains Tew . It follows that Tv0 properly contains
Tw0 . This proves the claim.
Claim 8.9 implies that Tv0 is neither a deficient 3-leaf tree nor a deficient 4-leaf tree.
Next, we address the second statement in the theorem. To show that Tv0 is semiclosed w.r.t. M ,
we must show that every link incident to an M -exposed leaf of Tv0 has both ends in Tv0 , and every
M -link incident to Tv0 has both ends in Tv0 . Let u be an M -exposed leaf of Tv0 . Suppose that u is
contained in Tw0 , where Tw0 is either a deficient 3-leaf tree or a deficient 4-leaf tree (w.r.t. T 0 ). Then
Tv0 contains Tw0 , by Claim 8.9. Since Tw0 is a semiclosed tree w.r.t. M (by definition of deficient trees),
all links incident with u have both ends in Tw0 , hence, also in Tv0 . Next, suppose that u does not
belong to any deficient 3-leaf tree or any deficient 4-leaf tree (w.r.t. T 0 ). Such an M -exposed node
of Tv0 is an M new -exposed node of Te. Since Tev is semiclosed w.r.t. M new , it follows that Tev contains
both ends of each link incident with u
e = u; hence, Tv0 contains both ends of each link incident with
u. Next, consider an M -link uw incident to Tv0 , where u is a node of Tv0 . If u is contained in Tw0 ,
where Tw0 is a deficient 3-leaf tree or a deficient 4-leaf tree, then note that Tw0 is semiclosed, and
34

moreover, Tw0 is properly contained in Tv0 , hence, both ends of uw are in Tv0 . Otherwise, uw has no
end in a deficient 3-leaf tree or in a deficient 4-leaf tree; then, by our construction of M new , we have
uw ∈ M new (M and M new are the same, except “inside” some deficient tree). Since Tev is semiclosed
w.r.t. M new , it follows that uw has both ends in Tev , hence, uw has both ends in Tv0 . Thus, Tv0 is
semiclosed w.r.t. M .
By the construction of Te and M new , Claim 8.9, and the fact that Tev is semiclosed, we have
|M (Tv0 )| = |M new (Tev )|; moreover, the number of M -exposed nodes of Tv0 is equal to the sum of
the number of M new -exposed nodes of Tev and |latch(Tev )| (since each latched-node of Tev corresponds
to an M -exposed leaf of a maximal deficient 4-leaf tree of Tv0 ). Hence, we have |Γ(M, Tv0 )| =
|Γ(M new , Tev )| + |latch(Tev )|. Clearly, Γ(M new , Tev ) is a fitting cover of Tev , because Tev is a minimally
semiclosed tree w.r.t. M new (by Lemma 6.2). It follows that Γ(M new , Tev ) ∪ latch(Tev ) is a fitting
cover of Tv0 of size |Γ(M, Tv0 )|.
Finally, we apply Theorem 8.7 to prove that Tv0 is good. Suppose that Tv0 is not good. By
Claim 8.9, Tv0 is neither a deficient 3-leaf tree nor a deficient 4-leaf tree. Then, Theorem 8.7(3)
implies that Tv0 has 4 leaves, |M (Tv0 )| = 1, and Tv0 has no cover of size 3. Since |M (Tv0 )| = 1 and
|U (Tv0 )| = 2, we have |Γ(M, Tv0 )| = 3. The previous paragraph shows that Tv0 has a fitting cover of
size |Γ(M, Tv0 )| = 3. Thus, we have a contradiction. It follows that Tv0 is good. This completes the
proof.

The procedure described above to find a good semiclosed tree is summarized in the following
pseudocode.
let E latch denote the set of latches of all maximal deficient 4-leaf trees of T 0 ;
let Te := T 0 /E latch ;
start with M new := M ;
for each maximal deficient 3-leaf tree Tewe in Te do
let b be the ceiling leaf, a be the M -exposed leaf and db be the M -link in Tewe ;
update M new by replacing db by da (M new := M new −{db} ∪ {da});
end
find a minimally semiclosed tree Tev w.r.t. M new ;
Tv0 is a good semiclosed tree w.r.t. M with a fitting cover Γ(M new , Tev ) ∪ latch(Tev ) of size
|Γ(M, Tv0 )| (by Theorem 8.8);
return Tv0 and its fitting cover Γ(M new , Tev ) ∪ latch(Tev );
Algorithm 2: Find a good semiclosed tree by addressing deficient trees.

Algorithm 2 shows how to find a good semiclosed tree Tv0 together with a fitting cover of size
|Γ(M, Tv0 )| for the main loop in Algorithm 1 in Section 7. (The first step of Algorithm 2 applies
“latch contractions” to construct the auxiliary tree Te from T 0 ; “latch contractions” have no effect
on F or on the credits of the algorithm.)
In conclusion, Algorithm 1 runs in polynomial time and returns a solution for TAP of size ≤
3
( 2 + )y(E). This proves Theorem 6.1.
Although our integrality ratio (and approximation guarantee) is proved relative to a “weaker
lower bound” than the optimum value (since the feasible region of a relaxation is a superset of the
convex full of integer solutions), we loose an additive term of  in the approximation guarantee,
compared to the 23 approximation guarantee of [10]. But, we can show that our methods achieve an
approximation guarantee of 32 relative to the (integral) optimum value. Observe that the algorithm
is combinatorial and does not refer to the SDP relaxation at all (our analysis does rely on the SDP
relaxation and properties of its solutions). Thus, we can apply the algorithm and analysis for the
35

level t = |E| tightening of (LP0 ), and at this level, the set of (feasible) solutions of Last (LP0 )
corresponds to the convex hull of integer solutions. Consequently, for level t = |E|, Lemma 4.4 can
be restated as follows: if y ∈ Last (LP0 ), where t = |E|, then y|E(L) is in the matching polytope
of G(L) = (L, E(L)). Hence, for level t = |E|, the upperbound on the potential function stated in
Lemma 5.2 can be improved from ( 23 + )y(E) to 23 y(E). In other words, for y ∈ Last (LP0 ), where
t = |E|, the potential function is ≤ 23 y(E). Sections 6–8 show that Algorithm 1 returns a solution
for TAP whose size is ≤ the potential function. Thus, we have the following result.
Corollary 8.10. Let y denote an optimal (integral) solution of TAP. Algorithm 1 runs in polynomial
time, and returns a solution for TAP of size ≤ 32 y(E).

It can be seen that Algorithm 1 can be implemented to run in time O(|V |3 + |V |2 m50 ), where m0
denotes the number of (multi) links in the input and we assume that m0 = O(|V |2 ). This can be
achieved using simple data structures such as adjacency matrices and adjacency lists; the details are
not straightforward, but we skip them. To handle the (up-to-5) greedy contractions, every subset
of size ≤ 5 of the set of maximal links has to be examined (for each link uw in a subset, Pu,w has to
be examined), and there are O(|V |) such contractions, hence, these contractions contribute a total
of O(|V |2 m50 ) to the running time.
Theorem 8.11. Algorithm 1 can be implemented to run in time O(|V |3 + |V |2 m50 ).

Acknowledgments. We thank André Linhares for many discussions. We thank several other
colleagues who read preliminary drafts and gave us insightful comments.
References
[1] J. Cheriyan, H. J. Karloff, R. Khandekar, and J. Könemann. On the integrality ratio for tree augmentation. Oper.
Res. Lett., 36(4):399–401, 2008.
[2] R. Diestel. Graph Theory (4th ed.). Graduate Texts in Mathematics, Volume 173. Springer-Verlag, Heidelberg,
2010.
[3] G. Even, J. Feldman, G. Kortsarz, and Z. Nutov. A 3/2-approximation algorithm for augmenting the edgeconnectivity of a graph from 1 to 2 using a subset of a given edge set. In Approximation, Randomization and
Combinatorial Optimization: Algorithms and Techniques, APPROX-RANDOM 2001, Proceedings, volume 2129
of Lecture Notes in Computer Science, pages 90–101, 2001.
[4] G. N. Frederickson and J. Ja’Ja’. Approximation algorithms for several graph augmentation problems. SIAM J.
Comput., 10(2):270–283, 1981.
[5] G.Even, J.Feldman, G.Kortsarz, and Z.Nutov. A 1.8 approximation algorithm for augmenting edge-connectivity
of a graph from 1 to 2. ACM Transactions on Algorithms, 5:21:6–21:17, 2009.
[6] H.Nagamochi. An approximation for finding a smallest 2-edge connected subgraph containing a specified spanning
tree. Discrete Applied Mathematics, 126:83–113, 2003.
[7] K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1):39–
60, 2001.
[8] A. R. Karlin, C. Mathieu, and C. T. Nguyen. Integrality gaps of linear and semi-definite programming relaxations
for Knapsack. In Integer Programming and Combinatoral Optimization, volume 6655 of Lecture Notes in Computer
Science, pages 301–314. Springer Berlin / Heidelberg, 2011.
[9] G. Kortsarz, R. Krauthgamer, and J. R. Lee. Hardness of approximation for vertex-connectivity network design
problems. SIAM J. Comput., 33(3):704–720, 2004.
[10] G. Kortsarz and Z. Nutov. A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph
from 1 to 2. CoRR, abs/1507.02799, 2015.
[11] T. Rothvoß. Directed Steiner tree and the Lasserre hierarchy. CoRR, abs/1111.5473, 2011.
[12] T.Rothvoß. The Lasserre hierarchy in approximation algorithms. MAPSP Tutorial: Lecture notes http: // www.
math. washington. edu/ ~ rothvoss/ lecturenotes/ lasserresurvey. pdf , 2013.
Dept. of Comb. & Opt., University of Waterloo, Waterloo, Ontario N2L3G1, Canada.
E-mail address: jcheriyan@uwaterloo.ca
E-mail address: z9gao@uwaterloo.ca
36

