Approximation algorithms for the maximum weight internal
spanning tree problem∗

arXiv:1608.03299v2 [cs.DS] 26 May 2017

Zhi-Zhong Chen†

Guohui Lin‡§

Lusheng Wang¶

Yong Chenk‡

Dan Wang¶

May 30, 2017

Abstract
Given a vertex-weighted connected graph G = (V, E), the maximum weight internal spanning
tree (MwIST for short) problem asks for a spanning tree T of G such that the total weight of
the internal vertices in T is maximized. The unweighted variant, denoted as MIST, is NPhard and APX-hard, and the currently best approximation algorithm has a proven performance
ratio 13/17. The currently best approximation algorithm for MwIST only has a performance
ratio 1/3 − ǫ, for any ǫ > 0. In this paper, we present a simple algorithm based on a novel
relationship between MwIST and the maximum weight matching, and show that it achieves a
better approximation ratio of 1/2. When restricted to claw-free graphs, a special case been
previously studied, we design a 7/12-approximation algorithm.

Keywords: Maximum weight internal spanning tree; maximum weight matching; approximation algorithm; performance analysis

∗

An extended abstract appears in the Proceedings of COCOON 2017.
Division of Information System Design, Tokyo Denki University. Hatoyama, Saitama 350-0394, Japan. Email:
zzchen@mail.dendai.ac.jp
‡
Department of Computing Science, University of Alberta. Edmonton, Alberta T6G 2E8, Canada. Email:
guohui@ualberta.ca
§
Correspondence author.
¶
Department of Computer Science, City University of Hong Kong. Tat Chee Avenue, Kowloon, Hong Kong,
China. Email: cswangl@cityu.edu.hk
k
Institute of Operational Research and Cybernetics, Hangzhou Dianzi University. Hangzhou, Zhejiang 310018,
China. Email: chenyong@hdu.edu.cn
†

1

2

1

Chen et al. /v:May 30, 2017

Introduction

In the maximum weight internal spanning tree (MwIST for short) problem, we are given a vertexweighted connected graph G = (V, E), where each vertex v of V has a nonnegative weight w(v),
with the objective to compute a spanning tree T of G such that the total weight of the internal
vertices in T , denoted as w(T ), is maximized. MwIST has applications in the network design for
cost-efficient communication [18] and water supply [1].
When the vertex weights are uniform, or simply vertex-unweighted, the problem is referred to as
the maximum internal spanning tree (MIST for short) problem. MIST is clearly NP-hard because it
includes the NP-hard Hamiltonian-path [6] problem as a special case. Furthermore, MIST has been
proven APX-hard [12], suggesting that it does not admit a polynomial-time approximation scheme
(PTAS). In the literature, much research is done on designing (polynomial-time, if not specified)
approximation algorithms for MIST to achieve the worst-case performance ratio as close to 1 as
possible.
The probably first approximation for MIST is a local search algorithm, which achieves a ratio
of 1/2 and is due to Prieto and Sliper [14]. Salamon and Wiener [18] later modified slightly
Prieto and Sliper’s algorithm to make it run faster (in linear-time) while achieving the same ratio
of 1/2. Besides, two special cases of MIST were considered by Salamon and Wiener [18]: when
restricted to claw-free graphs, they designed a 2/3-approximation algorithm; when restricted to
cubic graphs, they designed a 5/6-approximation algorithm. Later, Salamon [17] proved that the
1/2-approximation algorithm in [18] actually achieves a performance ratio of 3/(r + 1) for the
MIST problem on r-regular graphs (r ≥ 3). Based on local optimization, Salamon [16] presented
an O(n4 )-time 4/7-approximation algorithm for MIST restricted to graphs without leaves. The
algorithm was subsequently simplified and re-analyzed by Knauer and Spoerhase [7] to run faster
(in cubic time), and it becomes the first improved 3/5-approximation for the general MIST. Via a
deeper local search strategy than those in [7] and [16], Li et al. [8] presented a further improved
approximation algorithm for MIST with ratio 2/3. At the same time, Li and Zhu [12] presented
another 2/3-approximation algorithm for MIST.
Unlike the other previously known approximation algorithms for MIST, the 2/3-approximation
by Li and Zhu [12] is based on a simple but crucial observation that the maximum number of
internal vertices in a spanning tree of a graph G can be upper bounded by the maximum number
of edges in a triangle-free 2-matching (a.k.a. path-cycle cover) of G. The time complexity of
this approximation algorithm is dominated by computing the maximum triangle-free 2-matching,
O(nm1.5 log n), where n and m are the numbers of vertices and edges in G, respectively. Li and
Zhu [11] claimed that they are able to further improve their design to achieve a 3/4-approximation
algorithm for MIST, of the same time complexity. Recently, Chen et al. [2] gave another 3/4approximation algorithm for MIST, which is simpler than the one in [11]; and they showed that by
applying three more new ideas, the algorithm can be refined into a 13/17-approximation algorithm
for MIST of the same time complexity. This is currently the best approximation algorithm for
MIST.
The parameterized MIST by the number of internal vertices k, and its special cases and variants,
have also been extensively studied in the literature [14, 13, 15, 3, 5, 1, 4, 9, 10]. The best known
kernel for the general problem has a size 2k, which leads to the fastest known algorithm with
running time O(4k nO(1) ) [9].
For the vertex-weighted version, MwIST, Salamon [16] designed the first O(n4 )-time 1/(2∆−3)approximation algorithm, based on local search, where ∆ is the maximum degree of a vertex in
the input graph. For MwIST on claw-free graphs without leaves, Salamon [16] also designed an
O(n4 )-time 1/2-approximation algorithm. Subsequently, Knauer and Spoerhase [7] proposed the

Approximating the maximum weight internal spanning tree

3

first constant-ratio 1/(3 + ǫ)-approximation algorithm for the general MwIST, for any constant
ǫ > 0. The algorithm is based on a new pseudo-polynomial time local search algorithm, that
starts with a depth-first-search tree and applies six rules to reach a local optimum. It yields a
1/3-approximation for MwIST and then is extended to a polynomial time 1/(3 + ǫ)-approximation
scheme. The authors also showed that the ratio of 1/3 is asymptotically tight.
In this paper, we deal with the MwIST problem. We first prove a novel relationship between the
total weight of the internal vertices in a spanning tree of the given vertex-weighted graph and the
maximum weight matching of an edge-weighted graph, that is constructed out of the given vertexweighted graph. Based on this relationship, we present a simple 1/2-approximation algorithm for
MwIST; this ratio 1/2 significantly improves upon the previous known ratio of 1/3. When restricted
to claw-free graphs, a special case previously studied in [18, 16], we design a 7/12-approximation
algorithm, improving the previous best ratio of 1/2.

2

The 1/2-approximation algorithm

Recall that in the MwIST problem, we are given a connected graph G = (V, E), where each vertex
v of V has a nonnegative weight w(v), with the objective to compute a spanning tree T of G such
that the total weight of the internal vertices in T , denoted as w(T ), is maximized. We note that for
such an objective function, we may assume without loss of generality that every leaf in the given
graph G has weight 0.
We construct an edge-weighted graph based on G = (V, E). In fact, the structure of the new
graph is identical to that of G: the vertex set is still V , but instead the vertices have no weights;
the edge set is still E, where the weight of each edge e = {u, v} is w(e) = w(u) + w(v), i.e., the
weight of an edge is the total weight of its two ending vertices in the original graph. Since there is
no ambiguity when we discuss the edge weights or the vertex weights, the new edge-weighted graph
is still referred to as G. The weight of an edge subset refers to the total weight of the edges therein;
while the weight of an acyclic subgraph refers to the total weight of the internal (and those surely
will become internal) vertices therein.
Let M ∗ denote the maximum weight matching of (the edge-weighted graph) G, which can be
computed in O(n min{m log n, n2 })-time, where n = |V | and m = |E|.
Lemma 1 Given a spanning tree T of G, we can construct a matching M of G such that w(T ) ≤
w(M ).
Proof. We construct M iteratively. Firstly, we root the tree T at an internal vertex r, and all the
edges of T are unmarked; then in every iteration we include into M an unmarked edge e = {u, v}
of T such that 1) both u and v are internal and 2) e is the closest to the root r measured by the
number of edges on the path from r to e, followed by marking all the edges incident at u or v.
This way, the total weight of the two internal vertices u and v in the tree T is transferred to M
by adding the edge e to M . At the time this iterative procedure stops, there is no unmarked edge
of T connecting two internal vertices, and thus every internal vertex whose weight has not been
transferred to M must be adjacent to at least a leaf each via an unmarked edge.
Next, we iteratively include into M a remaining unmarked edge e = {u, v} of T , followed by
marking all the edges incident at u or v. This way, the total weight of u and v, which is greater
than or equal to the weight of the internal vertex between u and v, is transferred to M by adding
the edge e to M . At the end of this procedure, T contains no more unmarked edges. Since leaves in
the tree T count nothing towards w(T ), we conclude that w(T ) ≤ w(M ). This proves the lemma.
✷

4

Chen et al. /v:May 30, 2017

The following corollary directly follows from Lemma 1, stating an upper bound on the total
weight of an optimal solution to the MwIST problem.
Corollary 1 Let T ∗ denote an optimal (maximum weight internal) spanning tree of G. Then,
w(T ∗ ) ≤ w(M ∗ ).
We next start with M ∗ to construct a spanning tree T . Let the edges of M ∗ be e1 , e2 , . . . , ek ;
let ej = {aj , bj }, such that w(aj ) ≥ w(bj ), for all j = 1, 2, . . . , k. Note that there could be vertices
of degree 0 in the spanning subgraph G[V, M ∗ ] with the edge set M ∗ , and there could be edges of
weight 0 in M ∗ ; let X denote the set of such degree-0 vertices and the end-vertices of such weight-0
edges. Essentially we do not worry about the degree of any vertex of X in our final tree T , since their
weights (if any) are not counted towards w(M ∗ ). This way, we assume without loss of generality
that w(aj ) > 0 for each edge ej of M ∗ , and consequently the degree of aj is dG (aj ) ≥ 2, that is, aj
is adjacent to at least one other vertex than bj in the graph G. Let A = {aj | j = 1, 2, . . . , k}, and
B = {bj | j = 1, 2, . . . , k}; note that V = A ∪ B ∪ X.
Let E aa = E(A, A ∪ X), i.e., the set of edges each connecting a vertex of A and a vertex of
A ∪ X, and E ab = E(A, B), i.e., the set of edges each connecting a vertex of A and a vertex of
B. Our construction algorithm first computes a maximal acyclic subgraph of G, denoted as H0 ,
by adding a subset of edges of E aa to M ∗ . This subset of edges is a maximum weight spanning
forest on A ∪ X, and it can be computed in O(|E aa | log n)-time via a linear scan. In the achieved
subgraph H0 , if one connected component C contains more than one edge, then the vertex aj of
each edge ej = {aj , bj } in C has degree at least 2, i.e. is internal. Therefore, the total weight of
the internal vertices in the component C is at least half of w(C ∩ M ∗ ), and C is called settled and
left alone by the algorithm.
Our algorithm next considers an arbitrary edge of M ∗ that is not yet in any settled component,
say ej = {aj , bj }. In other words, the edge ej is an isolated component in the subgraph H0 . This
implies that the vertex aj is not incident to any edge of E aa , and thus it has to be adjacent to
some vertex in B − {bj }. If aj is adjacent to some vertex bi in a settled component, then this edge
(aj , bi ) is added to the subgraph H0 (the edge ej is said merged into a settled component) and the
iteration ends. The updated component remains settled, as w(aj ) ≥ w(ej )/2 is saved towards the
weight of the final tree T .
In the other case, the vertex aj is adjacent to a vertex bi , such that the edge ei = {ai , bi } is also
an isolated component in the current subgraph. After adding the edge (aj , bi ) to the subgraph, the
algorithm works with the vertex ai exactly the same as with aj at the beginning. That is, if ai is
adjacent to some vertex bℓ in a settled component, then this edge (ai , bℓ ) is added to the subgraph
(the component that ai belongs to is merged into a settled component) and the iteration ends; if
ai is adjacent to a vertex bℓ , such that the edge eℓ = {aℓ , bℓ } is also an isolated component in the
current subgraph, then the edge (ai , bℓ ) is added to the subgraph, the algorithm works with the
vertex aℓ exactly the same as with aj at the beginning; in the last case, ai is adjacent to a vertex
bℓ inside the current component that ai belongs to, then the edge (ai , bℓ ) is added to the current
component to create a cycle, subsequently the lightest edge of M ∗ in the cycle is removed, the
iteration ends, and the current component becomes settled. We note that in the above last case,
the formed cycle in the current component contains at least 2 edges of M ∗ ; breaking the cycle by
removing the lightest edge ensures that at least half of the total weight of the edges of M ∗ in this
cycle (and thus in this component) is saved towards the weight of the final tree T . Therefore, when
the iteration ends, the resulting component is settled.
When the second step of the algorithm terminates, there is no isolated edge of M ∗ in the current
subgraph, denoted as H1 , and each component is acyclic and settled. In the last step, the algorithm

Approximating the maximum weight internal spanning tree

5

connects the components of H1 into a spanning tree using any possible edges of E. We denote the
entire algorithm as Approx.
Lemma 2 At the end of the second step of the algorithm Approx, every component C of the
achieved subgraph H1 is acyclic and settled (i.e., w(C) ≥ w(C ∩ M ∗ )/2).
Proof. Let C denote a component; C ∩ M ∗ is the subset of M ∗ , each edge of which has both
end-vertices in C.
If C is obtained at the end of the first step, then C is acyclic and for every edge ej ∈ C ∩ M ∗ ,
the vertex aj has degree at least 2, and thus w(C) ≥ w(C ∩ M ∗ )/2.
If a subgraph of C is obtained at the end of the first step but C is finalized in the second step,
then C is also acyclic and for every edge ej ∈ C ∩ M ∗ , the vertex aj has degree at least 2, and thus
w(C) ≥ w(C ∩ M ∗ )/2.
If C is newly formed and finalized in the second step, then at the time C was formed, there
was a cycle containing at least 2 edges of M ∗ of which the lightest one is removed to ensure the
acyclicity, and thus the total weight of the internal vertices on this path is at least half of the total
weight of the edges of M ∗ on this cycle. Also, the vertex aj of every edge ej not on the cycle has
degree at least 2. Thus, w(C) ≥ w(C ∩ M ∗ )/2.
✷
Theorem 1 The algorithm Approx is a 1/2-approximation for the MwIST problem.
Proof. One clearly sees that Approx runs in polynomial time, and in fact the running time is
dominated by computing the maximum weight matching M ∗ .
From Lemma 2, at the end of the second step of the algorithm Approx, every component C of
the achieved subgraph H1 is acyclic and satisfies w(C) ≥ w(C ∩ M ∗ )/2. Since there is no edge of
M ∗ connecting different components of the subgraph H1 , the total weight of the internal vertices
in H1 is already at least w(M ∗ )/2, i.e. w(H1 ) ≥ w(M ∗ )/2. The last step of the algorithm may
only increase the total weight. This proves that the total weight of the internal vertices of the tree
T produced by Approx is
w(T ) ≥ w(H1 ) ≥ w(M ∗ )/2 ≥ w(T ∗ )/2,
where the last inequality is by Corollary 1, which states that w(M ∗ ) is an upper bound on the
optimum. Thus, Approx is a 1/2-approximation for the MwIST problem.
✷

3

A 7/12-approximation algorithm for claw-free graphs

We present a better approximation algorithm for the MwIST problem on claw-free graphs. A graph
G = (V, E) is called claw-free if, for every vertex, at least two of its arbitrary three neighbors are
adjacent. We again assume without loss of generality that every leaf in the graph G has weight 0.
Besides, we also assume that |V | ≥ 5.
We first present a reduction rule, which is a subcase of Operation 4 in [2], that excludes certain
induced subgraphs of the given graph G from consideration.
Operation 1 If G has a cut-vertex v such that one connected component C of G − v has two, three
or four vertices, then obtain G1 from G − V (C) by adding a new vertex u of weight 0 and a new
edge {v, u}.

6

Chen et al. /v:May 30, 2017

Let tw(C) denote the maximum total weight of the internal vertices in a spanning tree of the
subgraph induced on V (C) ∪ v, in which w(v) is revised to 0. Then there is an optimal spanning
tree T1 of G1 of weight w(T1 ) if and only if there is an optimal spanning tree T of G of weight
w(T ) = w(T1 ) + tw(C).
Proof. Let Gc denote the subgraph induced on V (C) ∪ v, that is, Gc = G[V (C) ∪ v]; and let Tc
denote the spanning tree of Gc achieving the maximum total weight of the internal vertices, that
is, w(Tc ) = tw(C) (Tc can be computed in O(1)-time).
Note that in T1 , the leaf u must be adjacent to v and thus w(v) is counted towards w(T1 ). We
can remove the edge {v, u} and u from T1 while attach the tree Tc to T1 by collapsing the two
copies of v. This way, we obtain a spanning tree T of G, of weight w(T ) = w(T1 ) + w(Tc ) since
w(v) is not counted towards w(Tc ).
Conversely, for any spanning tree T of G, the vertex v is internal due to the existence of C.
We may duplicate v and separate out a subtree Tc on the set of vertices V (C) ∪ v, in which the
weight of v is revised to 0. This subtree Tc is thus a spanning tree of Gc , and every vertex of V (C)
is internal in T if and only if it is internal in Tc . We attach the 0-weight vertex u to the vertex v
in the remainder tree via the edge {v, u}, which is denoted as T1 and becomes a spanning tree of
G1 ; note that the vertex v is internal in T1 . It follows that w(T ) = w(Tc ) + w(T1 ).
✷
See Figure 1 for an illustration of the local configurations specified in Operation 1. When
|V (C)| = 2 and Gc is a triangle, we refer the configuration as a hanging triangle; when |V (C)| = 3
and Gc contains a length-4 cycle, we refer the configuration as a hanging diamond; when |V (C)| = 4
and Gc contains a length-5 cycle, we refer the configuration as a hanging pentagon. Applying
Operation 1, we assume in the sequel that there is no hanging triangle, or hanging diamond, or
hanging pentagon in the given graph G.

v

v
v

(a) A hanging triangle.

(b) A hanging diamond.

(c) A hanging pentagon.

Figure 1: Local configurations of a hanging triangle, a hanging diamond, and a hanging pentagon,
specified in Operation 1, where the dotted edges could be in or not in the graph.
Let M ∗ denote a maximum weight matching of G, which is computed in O(n min{m log n, n2 })time, where n = |V | and m = |E|. Let the edges of M ∗ be e1 , e2 , . . . , ek ; let ej = {aj , bj }, such that
w(aj ) ≥ w(bj ), for all j = 1, 2, . . . , k. For convenience, aj and bj are referred to as the head and the
tail vertices of the edge ej , respectively. The same as in the last section, we assume without loss
of generality that w(aj ) > 0 for each j, and consequently the degree of aj is dG (aj ) ≥ 2, that is,
aj is adjacent to at least one vertex other than bj in the graph G. Let A = {aj | j = 1, 2, . . . , k},
B = {bj | j = 1, 2, . . . , k}, and X = V − (A ∪ B).
Let E aa = E(A, A), i.e., the set of edges each connecting two vertices of A, E ax = E(A, X),
i.e., the set of edges each connecting a vertex of A and a vertex of X, and E ab = E(A, B), i.e., the
set of edges each connecting a vertex of A and a vertex of B, respectively.

Approximating the maximum weight internal spanning tree

7

Let M aa ⊆ E aa be a maximum cardinality matching within the edge set E aa . We next prove a
structure property of the spanning subgraph G[V, M ∗ ∪ M aa ], which has the edge set M ∗ ∪ M aa .
For an edge ej = {aj , bj } of M ∗ , if aj is not incident to any edge of M aa , then ej is called isolated
in G[V, M ∗ ∪ M aa ].
Lemma 3 Assume that two edges ej1 = {aj1 , bj1 } and ej2 = {aj2 , bj2 } of M ∗ are connected by the
edge {aj1 , aj2 } ∈ M aa in G[V, M ∗ ∪ M aa ]. Then there is at most one isolated edge ej3 = {aj3 , bj3 }
whose head aj3 can be adjacent to aj1 or aj2 .
Proof. By contradiction, assume that there are two isolated edges ej3 = {aj3 , bj3 } and ej4 =
{aj4 , bj4 } such that both the vertices aj3 and aj4 are adjacent to aj1 or aj2 . Then from the maximum
cardinality of M aa , aj3 and aj4 must be both adjacent to aj1 or both adjacent to aj2 . Suppose they
are both adjacent to aj1 ; from the claw-free property, at least two of aj2 , aj3 and aj4 are adjacent,
which contradicts the maximum cardinality of M aa . This proves the lemma.
✷
For an isolated edge ej3 = {aj3 , bj3 } whose head is adjacent to an edge {aj1 , aj2 } ∈ M aa (i.e.,
satisfying Lemma 3), and assuming that {aj2 , aj3 } ∈ E aa , we add the edge {aj2 , aj3 } to G[V, M ∗ ∪
M aa ]; consequently the edge ej3 is no longer isolated. Let N aa denote the set of such added edges
associated with M aa . At the end, the achieved subgraph is denoted as H0 = G[V, M ∗ ∪ M aa ∪ N aa ].
Lemma 4 In the subgraph H0 = G[V, M ∗ ∪ M aa ∪ N aa ],
• every connected component containing more than one edge has either two or three edges from
M ∗ , with their head vertices connected (by the edges of M aa ∪ N aa ) into a path; it is called a
type-I component (see Figure 2a) and a type-II component (see Figure 2b), respectively;
• for every isolated edge ej = {aj , bj }, the head vertex is incident with at least one edge of
E ax ∪ E ab , but with no edge of E aa .
Proof. The proof directly follows the definition of the subgraph H0 and Lemma 3.

aj2

aj1

aj3

bj2

bj1

bj3

(a) A type-I component.

aj2

bj2

✷

aj1

bj1

(b) A type-II component.

Figure 2: The configurations of a type-I component and a type-II component.
The following lemma is analogous to Lemma 3.
Lemma 5 Any vertex of X can be adjacent to the head vertices of at most two isolated edges in
the subgraph H0 = G[V, M ∗ ∪ M aa ∪ N aa ].

8

Chen et al. /v:May 30, 2017

Proof. By contradiction, assume that x ∈ X and there are three isolated edges ejk = {ajk , bjk },
k = 1, 2, 3, in the subgraph H0 = G[V, M ∗ ∪ M aa ∪ N aa ], such that the edge {ajk , x} ∈ E ax . From
the claw-free property, at least two of aj1 , aj2 and aj3 are adjacent, which contradicts Lemma 4.
This proves the lemma.
✷
For an isolated edge ej = {aj , bj } in the subgraph H0 = G[V, M ∗ ∪ M aa ∪ N aa ] whose head is
adjacent to a vertex x ∈ X (i.e., satisfying Lemma 5), we add the edge {aj , x} to H0 ; consequently
the edge ej is no longer isolated. Let N ax denote the set of such added edges associated with X.
At the end, the achieved subgraph is denoted as H1 = G[V, M ∗ ∪ M aa ∪ N aa ∪ N ax ].
Lemma 6 In the subgraph H1 = G[V, M ∗ ∪ M aa ∪ N aa ∪ N ax ],
• every connected component of H0 containing more than one edge remains unchanged in H1 ;
• every connected component containing a vertex x of X and some other vertex has either one
or two edges from M ∗ , with their head vertices connected (by the edges of N ax ) to the vertex
x; it is called a type-III component (see Figure 3a) and a type-IV component (see Figure 3b),
respectively;
• for every isolated edge ej = {aj , bj }, the head vertex is incident with at least one edge of E ab ,
but with no edge of E aa ∪ E ax .
Proof. The proof directly follows the definition of the subgraph H1 and Lemmas 4 and 5.

aj1

aj1

aj2

x

✷

x
bj1

(a) A type-III component.

bj2

bj1

(b) A type-IV component.

Figure 3: The configurations of a type-III component and a type-IV component.
Let E0ab denote the subset of E ab , to include all the edges {aj , bℓ } where both the edges ej =
{aj , bj } and eℓ = {aℓ , bℓ } are isolated in the subgraph H1 = G[V, M ∗ ∪ M aa ∪ N aa ∪ N ax ]. Let
M ab ⊆ E0ab be a maximum cardinality matching within the edge set E0ab . Let H2 = G[V, M ∗ ∪
M aa ∪ N aa ∪ N ax ∪ M ab ] be the subgraph obtained from H1 by adding all the edges of M ab . One
clearly sees that all the isolated edges in the subgraph H1 are connected by the edges of M ab into
disjoint paths and cycles; while a path may contain any number of isolated edges, a cycle contains
at least two isolated edges. Such a path and a cycle component are called a type-V component (see
Figure 4a) and a type-VI component (see Figure 4b), respectively.
Note that in a type-V component, there is exactly one head vertex of degree 1 and there is
exactly one tail vertex of degree 1. We assume that for the tail vertex in a type-V component, it is
not adjacent to the head of any other edge (via an edge of E ab ) in the same component; otherwise,
through an edge exchange, the component is decomposed into a smaller type-V component and a
new type-VI component.

Approximating the maximum weight internal spanning tree

......

......

(a) A type-V component.

9

(b) A type-VI component.

Figure 4: The configurations of a type-V component and a type-VI component.
Lemma 7 In the subgraph H2 = G[V, M ∗ ∪ M aa ∪ N aa ∪ N ax ∪ M ab ], for every type-V component,
the degree-1 head vertex is adjacent (via an edge of E ab ) to the tail vertex of an edge in a type-I,
-II, -III, or -IV component; on the other hand, the tail vertex of every edge in a type-I, -II, -III, or
-IV component is adjacent to at most one such head vertex.
Proof. We first show that the degree-1 head vertex in a type-V component C, denoted as aj ,
cannot be adjacent to the tail of any edge in another type-V or a type-VI component C ′ . By
contradiction, assume {aj , bℓ } ∈ E ab and eℓ is in C ′ . If the tail bℓ is already incident to some
edge of M ab , say {ai , bℓ }, then by the claw-free property at least two of ai , aj , aℓ must be adjacent,
contradicting the fact that they are all isolated in the subgraph H1 . In the other case, the tail bℓ is
the tail vertex of C ′ (which is a type-V component too), then it violates the maximum cardinality
of M ab since {aj , bℓ } ∈ E ab can be added to increase the size of M ab . This proves the first half of
the lemma.
The second half can be proven by a simple contradiction using the claw-free property of the
graph.
✷
Subsequently, every type-V component C is connected to a type-I, -II, -III, or -IV component
C ′ , via the edge between the degree-1 head vertex of C and the tail vertex of an edge in C ′ ∩ M ∗ .
This way, the degree-1 tail vertex of C takes up the role of “the tail vertex” of the edge in C ′ ∩ M ∗ ,
to become a tail vertex in the newly formed bigger component. For simplicity, the type of the
component C ′ is passed to the newly formed bigger component. Denote this set of newly added
edges as N ab , which is a subset of E ab − M ab . The achieved subgraph is denoted as H3 = G[V, M ∗ ∪
M aa ∪ N aa ∪ N ax ∪ M ab ∪ N ab ].
Lemma 8 In the subgraph H3 = G[V, M ∗ ∪ M aa ∪ N aa ∪ N ax ∪ M ab ∪ N ab ],
• there is no isolated type-V component;
• the head vertex of every edge of M ∗ has degree at least 2.
Proof. The first half of the lemma follows from Lemma 7; the second half holds since there is no
more isolated type-V component, which is the only type of component containing a degree-1 head
vertex.
✷
We next create a set F of edges that are used to interconnect the components in the subgraph
H3 . F is initialized to be empty. By Lemma 8, for every type-I, -II, -III, or -IV component C in the
subgraph H3 , of weight w(C ∩M ∗ ), it is a tree and the total weight of the internal vertices therein is
at least 12 w(C ∩ M ∗ ); for every type-VI component C, which is a cycle, by deleting the lightest edge

10

Chen et al. /v:May 30, 2017

of C ∩ M ∗ from C we obtain a path and the total weight of the internal vertices in this path is also
at least 12 w(C ∩ M ∗ ). In the next five lemmas, we show that every component C in the subgraph
H3 can be converted into a tree on the same set of vertices, possibly with one edge specified for
connecting a leaf of this tree outwards, such that the total weight of the internal vertices (and the
leaf, if specified) in the tree is at least 32 w(C ∩ M ∗ ). The specified edge for the interconnection
purpose, is added to F . At the end of the process, the component C is called settled. A settled
component C can be expressed in multiple equivalent ways, for example, that the total weight of
the internal vertices (and the leaf, if specified) in the resulting tree is at least 32 w(C ∩ M ∗ ), or that
the total weight of the internal (and the leaf, if specified) vertices in the resulting tree is at least
twice the total weight of the leaves (excluding the specified leaf, if any).
In the sequel, we abuse the vertex notation to also denote its weight in math formulae; this
simplifies the presentation and the meaning of the notation is easily distinguishable. For estimating
the total weight of the internal vertices in a tree in the sequel, we frequently use the following
inequality:
∀w1 , w2 , w3 ∈ R, w1 + w2 + w3 − min{w1 , w2 , w3 } ≥ 2 min{w1 , w2 , w3 }.
Lemma 9 A type-I component in the subgraph H3 can be settled.
Proof. Consider a type-I component C in the subgraph H3 . Recall from Lemma 8 and the
paragraph right above it, that a general type-I component is an original type-I component (shown
in Figure 2a) augmented with zero to two type-V components.
Let the two original edges of M ∗ in C be ej1 and ej2 and the two tail vertices be b1 and b2 (which
replace bj1 and bj2 to be the tail vertices, respectively) with w(b1 ) ≥ w(b2 ). The corresponding two
head vertices to the tails b1 and b2 are denoted as a1 and a2 , respectively. See Figure 5 for the
general configuration of such a component. We assume that w(b1 ) > 0, since otherwise C is settled
automatically.

a2

b2

aj2

bj2

aj1

a1

bj1

b1

Figure 5: The general configuration of a type-I component, with a type-V component adjacent to
each of the two tail vertices.

Case 1. If b1 is adjacent to a vertex v outside C, then we add the edge {b1 , v} to F ; this settles
C, since the total weight of the internal vertices in C is at least a1 + b1 + a2 ≥ 3b2 (recall that a
vertex notation here represents the weight of the vertex).
We next consider the case where b1 is not adjacent to any vertex outside C, and thus it has to
be adjacent to some vertex inside C. Note that C is a path with b1 and b2 being its two ending
vertices. Let v denote the vertex adjacent to b1 that is the farthest to b1 on C. We distinguish this
distance dC (b1 , v) ≥ 2 and where v locates.

Approximating the maximum weight internal spanning tree

11

Case 2. If b1 6= bj1 and v is in the type-V component containing b1 , then by the construction of
a type-V component we know that v must be a tail of an edge of M ∗ (Figures 6a and 6b), and thus
dC (b1 , v) is even. Denote this edge as ej3 = {aj3 , bj3 }, that is v = bj3 .

a2

b2

aj2

bj2

aj1

a1

a2

bj1 v

b1

b2

(a) dC (b1 , v) ≥ 4.

aj2

bj2

a1

aj1

bj1

v

b1

(b) dC (b1 , v) = 2.

Figure 6: Local configurations corresponding to Case 2, where v is inside the type-V component
adjacent to bj1 .
Case 2.1. If dC (b1 , v) ≥ 4, then denote the head vertex other than aj3 that bj3 is adjacent to
as aj4 (see Figure 6a). We conclude from the claw-free property that there must be at least an
edge among aj3 , aj4 , b1 , which contradicts the identity of the type-V component. Therefore, it is
impossible to have dC (b1 , v) ≥ 4.
Case 2.2. If dC (b1 , v) = 2, then we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1 (see Figure 6b), i.e. there is at least another edge incident at a1 besides {a1 , bj3 } and
{a1 , b1 }. Denote this neighbor of a1 as u. If u is inside C, then u = b2 ; in this case, add the
edges {b1 , bj3 } and {a1 , b2 } to C while delete the edge {a1 , bj3 } and the lightest among the edges
of C ∩ M ∗ from C. This way, the component becomes a tree and thus C is settled. If u is outside
C, then we add the edge {b1 , bj3 } to C while delete the edge {a1 , bj3 } from C, and add the edge
{a1 , u} to F ; this way, the component becomes a tree and thus C is settled.
Case 3. If b1 6= bj1 and v = bj1 , we consider the size of the type-V component containing b1 (see
Figure 7).

a2

b2

aj2

bj2

aj1

a1

bj1

b1

Figure 7: Local configurations corresponding to Case 3, where v = bj1 .
Case 3.1. If this type-V component contains more than one edge of M ∗ , then by the claw-free
property aj1 must be adjacent to b1 , which violates the definition of v being the farthest and thus
it is impossible.
Case 3.2. If the type-V component containing b1 has only one edge of M ∗ , which is {a1 , b1 },
then we have dG (b1 ) = 2, and thus dG (a1 ) ≥ 3 by Operation 1, i.e. there is at least another edge
incident at a1 besides {a1 , bj1 } and {a1 , b1 }. (The following is the same as in Case 2.2.) Denote
this neighbor of a1 as u. If u is inside C, then u = b2 ; in this case, add the edges {b1 , bj1 } and

12

Chen et al. /v:May 30, 2017

{a1 , b2 } to C while delete the edge {a1 , bj1 } and the lightest among the edges of C ∩ M ∗ from C.
This way, the component becomes a tree and thus C is settled. If u is outside C, then we add the
edge {b1 , bj1 } to C while delete the edge {a1 , bj1 } from C, and add the edge {a1 , u} to F ; this way,
the component becomes a tree and thus C is settled.
Case 4. If b1 6= bj1 and v = aj1 (see Figure 8), then we leave C as it is when w(b1 ) ≤ w(bj1 ),
or we add the edge {aj1 , b1 } to C while delete the edge {aj1 , bj1 } from C. The total weight of the
internal vertices in the resulting path is at least a2 + aj1 + a1 + max{b1 , bj1 } ≥ 2(b2 + min{b1 , bj1 }),
and thus C is settled.

a2

b2

aj2

bj2

aj1

a1

bj1

b1

Figure 8: Local configurations corresponding to Case 4, where v = aj1 .

Case 5. If b1 6= bj1 and v = aj2 (see Figure 9), then by the claw-free property there is at least
an edge among bj2 , aj1 , b1 . Note that bj2 and b1 cannot be adjacent due to the definition of the
vertex v (being the farthest). If aj1 and b1 are adjacent, then it has been proven in Case 4 that
C can be settled. If bj2 and aj1 are adjacent, then similarly as in Case 4 we either leave C as
it is when w(b1 ) ≤ w(bj1 ), or add the edges {aj2 , b1 } and {aj1 , bj2 } to C while delete the edges
{aj1 , bj1 } and {aj2 , bj2 } from C; the total weight of the internal vertices in the resulting path is at
least a2 + aj1 + a1 + max{b1 , bj1 } ≥ 2(b2 + min{b1 , bj1 }), and thus C is settled.

a2

b2

aj2

bj2

aj1

a1

bj1

b1

Figure 9: Local configurations corresponding to Case 5, where v = aj2 .

Case 6. If b1 6= bj1 and v = bj2 (see Figure 10), then by the claw-free property aj2 and b1 must
be adjacent.
Case 6.1. If b2 6= bj2 , then we have three ways to convert C into a path ending at b2 : 1) doing
nothing to leave b1 as a leaf; 2) adding the edge {aj2 , b1 } to C while deleting the edge {aj2 , aj1 } to
leave aj1 as a leaf; 3) adding the edge {bj2 , b1 } to C while deleting the edge {aj2 , bj2 } to leave aj2
as a leaf. Then, the maximum total weight of the internal vertices among these three paths is at
least a2 + a1 + aj1 + aj2 + b1 − min{b1 , aj1 , aj2 } ≥ 2(b2 + min{b1 , aj1 , aj2 }). Thus, C is settled.

Approximating the maximum weight internal spanning tree

a2

aj2

b2

bj2

aj1

a1

bj1

b1

13

Figure 10: Local configurations corresponding to Case 6, where v = bj2 .
Case 6.2. If b2 = bj2 , that is, there is no type-V component adjacent to bj2 , then we add the
edge {bj2 , b1 } to C while delete the lightest edge of C ∩ M ∗ from C to settle C, because C ∩ M ∗
contains at least three edges.
Case 7. If b1 6= bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail (see Figure 11).
a2
2

a

v

aj2

aj1

b

bj2

bj1

(a) v is a head.

aj1

a1

a2

bj1

b1

b2

aj2

aj1

a1

bj1

b1

a

b2
2

aj2

1

b

bj2

v

bj2

1

(b) v = b2 .

(c) v is a tail.

Figure 11: Local configurations corresponding to Case 7, where v is inside the type-V component
adjacent to bj2 .
Case 7.1. If v is a head, say aj3 of the edge ej3 (see Figure 11a), and assume that aj3 is also
adjacent to bj4 , then we do nothing to C to leave b1 as a leaf when w(b1 ) ≤ w(bj4 ), or add the edge
{aj3 , b1 } to C while delete the edge {aj3 , bj4 } from C to leave bj4 as a leaf. Then, the total weight of
the internal vertices in the resulting path is at least a2 +a1 +aj4 +max{b1 , bj4 } ≥ 2(b2 +min{b1 , bj4 }).
Thus, C is settled.
Case 7.2. If v is a tail, say bj3 of the edge ej3 (see Figures 11b and 11c). If b2 = bj3 (see
Figure 11b), then we add the edge {b1 , b2 } to C makes it a cycle while delete the lightest edge of
C ∩ M ∗ to settle C since there are at least four edges in C ∩ M ∗ ; if b2 6= bj3 (see Figure 11c), then
by the claw-free property and the definition of v we conclude that b1 is adjacent to aj3 too, and
thus the argument in Case 7.1 applies to settle C.
In summary, Cases 2-7 together prove that when b1 6= bj1 , the component C can be settled. We
next consider the situation where b1 = bj1 , that is, there is no type-V component adjacent to bj1
(see Figure 12).
Case 8. If b1 = bj1 and v = aj2 , then we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1 (see Figure 13).
Case 8.1. If there is a vertex u outside C that is adjacent to a1 , then we add the edge {a1 , u}
to F , add the edge {aj2 , b1 } to C while delete the edge {a1 , aj2 } from C; this way, C is settled.
Case 8.2. Otherwise by the claw-free property a1 must be adjacent either to b2 or to bj2 .

14

Chen et al. /v:May 30, 2017

a2

a1

aj2

b2

b1

bj2

Figure 12: A special configuration without a type-V component adjacent to bj1 , i.e. bj1 = b1 .

a2

a1

aj2

b2

b1

bj2

Figure 13: Local configurations corresponding to Case 8, where v = aj2 .
Case 8.2.1. Assuming b2 6= bj2 , in the former case, we add the edges {aj2 , b1 } and {a1 , b2 } to
C while delete the edge {a1 , aj2 } and the lightest edge of C ∩ M ∗ from C; this way, C is settled
since there were at least three edges in C ∩ M ∗ . In the latter case, we conclude that dG (aj2 ) ≥ 4 by
Operation 1. Recursively, if there is a vertex u outside C that is adjacent to aj2 , then we add the
edge {aj2 , u} to F , add the edges {aj2 , b1 } and {a1 , bj2 } to C while delete the edges {a1 , aj2 } and
{aj2 , bj2 } from C; this way, C is settled. Otherwise by the claw-free property aj2 must be adjacent
to b2 ; we add three edges {aj2 , b1 }, {a1 , bj2 } and {aj2 , b2 } to C while delete the edges {a1 , aj2 } and
{aj2 , bj2 }, and the lightest edge of C ∩ M ∗ from C; this way, C is settled.
Case 8.2.2. Assuming b2 = bj2 , that is, there is no type-V component adjacent to bj2 . We
conclude that dG (a2 ) ≥ 4 and there is a vertex u outside C that is adjacent to a2 by Operation 1.
Thus, we add the edge {a2 , u} to F , add the edges {a2 , b1 } and {a1 , b2 } to C while delete the edges
{a1 , a2 } and {a2 , b2 } from C; this way, C is settled.

Case 9.

If b1 = bj1 and v = bj2 (see Figure 14), we consider two possible scenarios.

a2

aj2

a1

a2

a1

b2

bj2

b1

b2

b1

(a) b2 6= bj2 .

(b) b2 = bj2 .

Figure 14: Local configurations corresponding to Case 9, where v = bj2 .

Approximating the maximum weight internal spanning tree

15

Case 9.1. If b2 6= bj2 (see Figure 14a), then we conclude from the claw-free property and the
definition of v that b1 is also adjacent to aj2 . By Operation 1, at least one of a1 and aj2 must be
adjacent to another vertex u.
Case 9.1.1. If there is a vertex u outside C that is adjacent to a1 (aj2 , respectively) then we
add the edge {a1 , u} ({aj2 , u}, respectively) to F , add the edges {bj2 , b1 } and {aj2 , b1 } ({bj2 , b1 },
respectively) to C while delete the edges {a1 , b1 } and {aj2 , bj2 } ({aj2 , bj2 }, respectively) from C;
this way, C is settled.
Case 9.1.2. Otherwise by the claw-free property u ∈ {b2 , bj2 }. If u = b2 , then we can settle C
by converting C into a cycle on the same set of vertices, followed by deleting the lightest edge of
C ∩ M ∗ from C. In the other case, u = bj2 and thus a1 is adjacent to bj2 , which by Operation 1 is
impossible.
Case 9.2. If b2 = bj2 , that is, there is no type-V component adjacent to bj2 (see Figure 14b).
We conclude that either there is a vertex u outside C that is adjacent to a2 , or a2 is adjacent to b1
and there is a vertex u outside C that is adjacent to a1 . In either case, we add the edge {·, u} to
F , and convert C into a path with b2 and · as two ending vertices; this way, C is settled.
Case 10. If b1 = bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail (see Figure 15).

a2
a2

b2

v

aj2

a1

bj2

b1

(a) v is a head.

b2

aj2

bj2

a1

a2

b1

b2

(b) v = b2 .

aj2

v

bj2

a1

b1

(c) v is a tail.

Figure 15: Local configurations corresponding to Case 10, where v is inside the type-V component
adjacent to bj2 .
Case 10.1. If v is a head, say aj3 of the edge ej3 (see Figure 15a), and assume that aj3 is also
adjacent to bj4 , then we do nothing to C to leave b1 as a leaf when w(b1 ) ≤ w(bj4 ), or add the edge
{aj3 , b1 } to C while delete the edge {aj3 , bj4 } from C to leave bj4 as a leaf. Then, the total weight of
the internal vertices in the resulting path is at least a2 +a1 +aj4 +max{b1 , bj4 } ≥ 2(b2 +min{b1 , bj4 }).
Thus, C is settled.
Case 10.2. If v is a tail, say bj3 of the edge ej3 (see Figures 15b and 15c). If b2 = bj3 (see
Figure 15b), then we add the edge {b1 , b2 } to C makes it a cycle while delete the lightest edge of
C ∩ M ∗ to settle C since there are at least three edges in C ∩ M ∗ ; if b2 6= bj3 (see Figure 15c), then
by the claw-free property and the definition of v we conclude that b1 is adjacent to aj3 too, and
thus the argument in Case 10.1 applies to settle C.
All possible cases have be discussed in the above. The lemma is proven.
✷
Lemma 10 A type-II component in the subgraph H3 can be settled.
Proof. Consider a type-II component C in the subgraph H3 . Recall from Lemma 8 and the
paragraph right above it, that a general type-II component is an original type-II component (shown

16

Chen et al. /v:May 30, 2017

in Figure 2b) augmented with zero to three type-V components.
Let the three original edges of M ∗ in C be ej1 , ej2 , ej3 , with ej2 in the middle (see Figure 2b),
and the three tail vertices be b1 , b2 , b3 (which replace bj1 , bj2 , bj3 , respectively). We consider the
situation where b1 is the heaviest among the three tail vertices (the other situation is where b2 is
the heaviest, and can be similarly discussed). In the following, discussion for most cases is similar
to the cases in the proof of Lemma 9, and thus not all details are presented (neither the illustration
figures).
Case 1. If b1 is adjacent to a vertex v outside C, then we add the edge {b1 , v} to F , which settles
C, since the total weight of the internal vertices in C is at least a1 + b1 + a2 + a3 ≥ 2(b2 + b3 ) (recall
that a vertex notation here represents the weight of the vertex).
In the sequel we assume b1 is not adjacent to any vertex outside C, and thus it has to be
adjacent to some vertex inside C. Let v denote the vertex adjacent to b1 that is the farthest to b1
on C (tie breaks arbitrarily). We distinguish this distance dC (b1 , v) ≥ 2 and where v locates.
Case 2. If b1 6= bj1 and v is in the type-V component containing b1 , then v must be the tail of
an edge of M ∗ and thus dC (b1 , v) is even. Denote this edge as ej4 = {aj4 , bj4 }, that is v = bj4 .
Case 2.1. If dC (b1 , v) ≥ 4, then denote the head vertex other than aj4 that bj4 is also adjacent
to as aj5 . We conclude from the claw-free property that there must be at least an edge among
aj4 , aj5 , b1 , which contradicts the identity of the type-V component. Thus it is impossible to have
dC (b1 , v) ≥ 4.
Case 2.2. If dC (b1 , v) = 2, then we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1, i.e. there is at least another edge incident at a1 besides {a1 , bj4 } and {a1 , b1 }. Denote
this neighbor of a1 as u. If u is inside C, then u ∈ {b2 , b3 }; in the case of u = b2 (the argument
for u = b3 is identical), we know that the branch incident at aj1 contains at least three edges of
M ∗ (ej1 , ej4 , e1 ), and thus we may add the edges {bj4 , b1 } and {a1 , b2 } to C while delete the edge
{a1 , bj4 } and the lightest among the three edges ej1 , ej4 , e2 (which are on the created cycle), denoted
as ex = {ax , bx }, from C. This way, the component becomes a tree with leaves b3 , ax , bx . The total
weight of the internal vertices in the tree is at least a3 + (a1 + b1 ) + 2(ax + bx ) ≥ 2(b3 + ax + bx );
that is, C is settled.
If u is outside C, then we add the edge {bj4 , b1 } to C while delete the edge {a1 , bj4 } from C,
and add the edge {a1 , u} to F ; this way, the component becomes a tree and thus C is settled.
Case 3. If b1 6= bj1 and v = bj1 , we consider the size of the type-V component containing b1 .
Case 3.1. If this type-V component contains more than one edge of M ∗ , then by the claw-free
property aj1 must be adjacent to b1 , which violates the definition of v being the farthest and thus
it is impossible.
Case 3.2. If the type-V component containing b1 has only one edge of M ∗ , which is {a1 , b1 };
in this case, we have dG (b1 ) = 2, and thus dG (a1 ) ≥ 3 by Operation 1, i.e. there is at least another
edge incident at a1 besides {a1 , bj1 } and {a1 , b1 }. Denote this neighbor of a1 as u. If u is inside
C, then u ∈ {b2 , b3 }. In the case of u = b2 (the argument for u = b3 is identical), we may add the
edges {b1 , bj1 } and {a1 , b2 } to C while delete the edge {a1 , bj1 } to form a cycle. When bj2 = b2 ,
we either delete the edge {aj2 , bj2 } to leave bj2 as a leaf, or delete the edge {aj2 , aj1 } to leave aj1
as a leaf. The maximum total weight of the internal vertices between the two trees is at least
a3 + a1 + b1 + a2 + max{b2 , aj1 } ≥ 2(b3 + min{b2 , aj1 }), and thus C is settled. When bj2 6= b2 , we
delete the lightest among the three edges ej1 , ej2 , e2 (which are on the created cycle), denoted as
ex = {ax , bx }, from C. This way, the component becomes a tree with leaves b3 , ax , bx . The total

Approximating the maximum weight internal spanning tree

17

weight of the internal vertices in the tree is at least a3 + (a1 + b1 ) + 2(ax + bx ) ≥ 2(b3 + ax + bx );
that is, C is settled.
If u is outside C, then we add the edge {b1 , bj1 } to C while delete the edge {a1 , bj1 } from C,
and add the edge {a1 , u} to F ; this way, the component becomes a tree and thus C is settled.
Case 4. If b1 6= bj1 and v = aj1 , we consider the size of the type-V component containing b1 .
Case 4.1. If this type-V component contains more than one edge of M ∗ , then denote one edge
other than {a1 , b1 } as ej4 = {aj4 , bj4 }. We add the edge {aj1 , b1 } to C while either delete the edge
{aj1 , bj1 } to have a tree with leaves bj1 , b2 , b3 , or delete the edge {aj4 , bj4 } to have a tree with leaves
aj4 , bj4 , b2 , b3 . It follows that the maximum total weight of the internal vertices between the two
trees is at least a2 + a3 + a1 + b1 + aj1 + max{bj1 , aj4 + bj4 } ≥ 2(b2 + b3 + min{bj1 , aj4 + bj4 });
therefore, C is settled.
Case 4.2. If this type-V component contains only one edge of M ∗ , which is {a1 , b1 }, then from
the claw-free property and the definition of v being the farthest we conclude that bj1 is adjacent to
at least one of aj2 and b1 .
Case 4.2.1. Assume bj1 and aj2 are adjacent. By treating aj2 as the cut-vertex in Operation 1,
we conclude that at least one of the three vertices aj1 , bj1 , a1 is adjacent to a vertex u outside of
the set {aj2 , aj1 , bj1 , a1 , b1 }.
Case 4.2.1.1. If aj1 is adjacent to a vertex u outside the component C, then we add the edges
{aj2 , bj1 } and {aj1 , b1 } to C while delete the edges {aj2 , aj1 } and {aj1 , bj1 } from C to obtain a tree
with leaves b3 , b2 , aj1 ; thus, adding the edge {aj1 , u} to F settles C.
If bj1 is adjacent to a vertex u outside the component C, then we add the edge {aj1 , b1 } to C
while delete the edge {aj1 , bj1 } from C to obtain a tree with leaves b3 , b2 , bj1 ; thus, adding the edge
{bj1 , u} to F settles C.
If a1 is adjacent to a vertex u outside the component C, then we add the edges {aj2 , bj1 } and
{aj1 , b1 } to C while delete the edges {aj2 , aj1 } and {bj1 , a1 } from C to obtain a tree with leaves
b3 , b2 , a1 ; thus, adding the edge {a1 , u} to F settles C.
Case 4.2.1.2. If aj1 is not adjacent to any vertex outside the component C, but to some
vertices inside C, then let u denote the farthest neighbor on C (tie breaks arbitrarily). There are
only four possibilities.
When u = aj3 (u = bj3 and bj3 6= b3 implying that aj3 and aj1 are adjacent), we can add
the edges {aj3 , aj1 }, {aj2 , bj1 } and {aj1 , b1 } to C while delete the edges {aj3 , aj2 }, {aj2 , aj1 } and
{aj1 , bj1 } from C to obtain a path with leaves b3 , b2 ; thus, C is settled.
When u = bj2 , we can add the edges {bj2 , aj1 }, {aj2 , bj1 } and {aj1 , b1 } to C while delete the
edges {aj2 , aj1 }, {aj2 , bj2 } and {aj1 , bj1 } from C to obtain a path with leaves b3 , b2 ; thus, C is
settled.
When u = b3 (whether b3 = bj3 or not), we can add the edge {b3 , aj1 } to C while delete the
edge {aj2 , aj1 } from C to obtain a path with leaves b2 , b1 ; we also can add the edges {b3 , aj1 } and
{aj1 , b1 } to C while delete the edges {aj2 , aj1 } and {aj1 , bj1 } from C to obtain a path with leaves
b2 , bj1 . It follows that the maximum total weight of the internal vertices between the two paths is
at least a2 + aj1 + a1 + max{bj1 , b1 } ≥ 2(b2 + min{bj1 , b1 }); therefore, C is settled.
When u = b2 , it can be shown the same as in the last paragraph by replacing b3 with b2 , that
C can be settled.
Case 4.2.1.3. If a1 is not adjacent to any vertex outside the component C, but to some vertices
inside C, then let u denote the farthest neighbor on C (tie breaks arbitrarily). Note that u cannot
be any head vertex, as otherwise it violates the algorithm; u cannot be any tail vertex either, unless
it is b2 or b3 . Therefore there are only two possibilities.

18

Chen et al. /v:May 30, 2017

When u = b3 (whether b3 = bj3 or not), we can add the edges {b3 , a1 } and {aj1 , b1 } to C while
delete the edge {aj2 , aj1 }. Then, we either delete {a1 , b1 } to obtain a path with leaves b2 , b1 , or
delete {a1 , bj1 } to obtain a path with leaves b2 , bj1 . It follows that the maximum total weight of the
internal vertices between the two paths is at least a2 + aj1 + a1 + max{bj1 , b1 } ≥ 2(b2 + min{bj1 , b1 });
therefore, C is settled.
When u = b2 , it can be shown the same as in the last paragraph by replacing b3 with b2 , that
C can be settled.
Case 4.2.1.4. If bj1 is not adjacent to any vertex outside the component C, but to some
vertices inside C, then let u denote the farthest neighbor on C (tie breaks arbitrarily).
When u ∈ {aj3 , bj3 , bj2 } (u = bj3 and bj3 6= b3 implying that aj3 and bj1 are adjacent), similarly
as in Case 4.2.1.2, we can convert C into a path with leaves b3 , b2 to settle C. In the remaining
case, u is inside one of the attached type-V components.
When u is a head, say aj4 of the edge ej4 in the type-V component attached to bj2 (or bj3 ), and
assume that aj4 is adjacent to bj5 besides bj4 , then we can do nothing to have a tree with leaves
b3 , b2 , b1 ; or we can add the edge {aj1 , b1 } to C while delete the edge {aj1 , bj1 } to obtain a tree with
leaves b3 , b2 , bj1 ; or we can add the edges {aj4 , bj1 } and {aj1 , b1 } to C while delete the edges {aj4 , bj5 }
and {aj1 , bj1 } to obtain a tree with leaves b3 , b2 , bj5 . The maximum total weight of the internal
vertices among the three trees is at least a3 + a2 + aj1 + bj1 + aj5 + bj5 + a1 + b1 − min{b1 , bj1 , bj5 } ≥
2(b3 + b2 + min{b1 , bj1 , bj5 }), which settles C.
When u is a tail, say bj4 of the edge ej4 in the type-V component attached to bj2 (or bj3 ), but
bj 4 ∈
/ {b2 , b3 }, then from the claw-free property and the definition of u we conclude that bj1 is also
adjacent to aj4 . Thus the argument in the last paragraph applies to settle C.
Lastly, when u = b2 (or b3 , which can be shown in the same way), we conclude that b2 is
adjacent either to aj1 , which is settled in Case 4.2.1.2, or to a1 , which is settled in Case 4.2.1.3.
Case 4.2.2. Assume bj1 is not adjacent to aj2 but to b1 . By treating aj1 as the cut-vertex
in Operation 1, we conclude that at least one of the two vertices bj1 , a1 is adjacent to a vertex u
outside the set {aj1 , bj1 , a1 , b1 }.
Case 4.2.2.1. If bj1 is adjacent to a vertex u outside the component C, then we add the edge
{aj1 , b1 } to C while delete the edge {aj1 , bj1 } from C to obtain a tree with leaves b3 , b2 , bj1 ; thus,
adding the edge {bj1 , u} to F settles C.
If a1 is adjacent to a vertex u outside the component C, then we add the edges {bj1 , b1 } and
{aj1 , b1 } to C while delete the edges {aj1 , bj1 } and {a1 , b1 } from C to obtain a tree with leaves
b3 , b2 , a1 ; thus, adding the edge {a1 , u} to F settles C.
Case 4.2.2.2. If a1 is not adjacent to any vertex outside the component C, but to some vertices
inside C, then let u denote the farthest neighbor on C (tie breaks arbitrarily). Note that u cannot
be any head vertex, as otherwise it violates the algorithm; u cannot be any tail vertex either, unless
it is b2 or b3 . Therefore there are only two possibilities. (This is very similar to Case 4.2.1.3.)
When u = b3 (whether b3 = bj3 or not), we can add the edges {b3 , a1 } and {aj1 , b1 } to C while
delete the edge {aj2 , aj1 }. Then, we can delete {a1 , b1 } to obtain a path with leaves b2 , b1 , or we can
delete {a1 , bj1 } to obtain a path with leaves b2 , bj1 . It follows that the maximum total weight of the
internal vertices between the two paths is at least a2 + aj1 + a1 + max{bj1 , b1 } ≥ 2(b2 + min{bj1 , b1 });
therefore, C is settled.
When u = b2 , it can be shown the same as in the last paragraph by replacing b3 with b2 , that
C can be settled.
Case 4.2.2.3. If bj1 is not adjacent to any vertex outside the component C, but to some
vertices inside C, then let u denote the farthest neighbor on C (tie breaks arbitrarily). Note that
u 6= aj2 , which is Case 4.2.1. When u ∈ {aj3 , bj3 , bj2 }, similarly as in Case 4.2.1.2, we can convert

Approximating the maximum weight internal spanning tree

19

C into a path with leaves b3 , b2 to settle C. In the remaining case, u is inside one of the attached
type-V components. (This is very similar to Case 4.2.1.4.)
When u is a head, say aj4 of the edge ej4 in the type-V component attached to bj2 (or bj3 ), and
assume that aj4 is adjacent to bj5 besides bj4 , then we can do nothing to have a tree with leaves
b3 , b2 , b1 ; or we can add the edge {aj1 , b1 } to C while delete the edge {aj1 , bj1 } to obtain a tree with
leaves b3 , b2 , bj1 ; or we can add the edges {aj4 , bj1 } and {aj1 , b1 } to C while delete the edges {aj4 , bj5 }
and {aj1 , bj1 } to obtain a tree with leaves b3 , b2 , bj5 . The maximum total weight of the internal
vertices among the three trees is at least a3 + a2 + aj1 + bj1 + aj5 + bj5 + a1 + b1 − min{b1 , bj1 , bj5 } ≥
2(b3 + b2 + min{b1 , bj1 , bj5 }), which settles C.
When u is a tail, say bj4 of the edge ej4 in the type-V component attached to bj2 (or bj3 ), but
bj 4 ∈
/ {b2 , b3 }, then from the claw-free property and the definition of u we conclude that bj1 is also
adjacent to aj4 . Thus the argument in the last paragraph applies to settle C.
Lastly, when u = b2 (or b3 , which can be shown in the same way), we conclude that b2 is
adjacent either to aj1 or to a1 , the latter of which is settled in Case 4.2.2.3. In the remaining case
where b2 is adjacent to aj1 , we can add the edge {b2 , aj1 } to C while delete the edge {aj1 , aj2 } to
obtain a path with leaves b3 , b1 ; or we can add the edges {b2 , aj1 } and {b1 , aj1 } to C while delete the
edges {aj1 , aj2 } and {aj1 , bj1 } to obtain a path with leaves b3 , bj1 . The maximum total weight of the
internal vertices between the two trees is at least a3 + a1 + aj1 + max{b1 , bj1 } ≥ 2(b3 + min{b1 , bj1 }),
which settles C.
Case 5. If b1 6= bj1 and v = aj2 , then by the claw-free property there is at least an edge among
bj2 , aj1 , b1 . Note that bj2 and b1 cannot be adjacent due to the definition of the vertex v being the
farthest. If aj1 and b1 are adjacent, then it has been proven in the above Case 4 that C can be
settled. If bj2 and aj1 are adjacent, then we add the edges {aj2 , b1 } and {aj1 , bj2 } to C while delete
the edges {aj2 , aj1 } and {aj2 , bj2 } from C; this way we obtain a path with two leaves b2 and b3 , and
thus it settles C.
Case 6. If b1 6= bj1 and v = bj2 , then we add the edge {bj2 , b1 } to C while delete the edge {aj2 , bj2 }
from C; this way we obtain a path with two leaves b2 and b3 , and thus it settles C.
If b1 6= bj1 and v = aj3 , then we add the edge {aj3 , b1 } to C while delete the edge {aj3 , aj2 }
from C; this way we obtain a path with two leaves b2 and b3 , and thus it settles C.
If b1 6= bj1 and v = bj3 , then there are two possible scenarios. When b3 6= bj3 , by the clawfree property and the definition of v we conclude that aj3 and b1 must be adjacent, and the last
paragraph shows that C is settled. When b3 = bj3 , we add the edge {b3 , b1 } to C while either delete
the edge {a3 , aj2 } from C to achieve a path with two leaves a3 , b2 , or delete the edge {aj2 , aj1 } from
C to achieve a path with leaves aj1 , b2 ; we may also do nothing to C which is a tree with leaves
b1 , b2 , b3 . Among these three trees, the maximum total weight of the internal vertices is at least
a3 + b3 + a2 + aj1 + a1 + b1 − min{a3 , aj1 , b1 + b3 } ≥ 2(b2 + min{a3 , aj1 , b1 + b3 }); thus, C is settled.
Case 7. If b1 6= bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail. (Note that the same argument applies to b3 6= bj3 and v is in the
type-V component containing b3 .)
Case 7.1. If v is a head, say aj4 of the edge ej4 , and assume that aj4 is adjacent to bj5 besides
bj4 , then we consider two distinct scenarios.
Case 7.1.1. When bj5 6= bj2 , besides two leaves b2 and b3 , we either do nothing to C to leave
1
b as a leaf, or add the edge {aj4 , b1 } to C while delete the edge {aj4 , bj5 } from C to leave bj5
as a leaf, or add the edge {aj4 , b1 } to C while delete the edge {aj2 , bj2 } from C to leave bj2 as

20

Chen et al. /v:May 30, 2017

a leaf. Among these three trees, the maximum total weight of the internal vertices is at least
a3 + a2 + a1 + b1 + aj2 + bj2 + aj5 + bj5 − min{b1 , bj2 , bj5 } ≥ 2(b3 + b2 + min{b1 , bj2 , bj5 }); thus, C is
settled.
Case 7.1.2. When bj5 = bj2 , by the claw-free property and the definition of the vertex v we
conclude that bj2 is adjacent to at least one of bj4 and b1 . If bj2 and bj4 are adjacent, then we
add the edges {aj4 , b1 } and {bj2 , bj4 } to C while delete the edges {aj2 , bj2 } and {aj4 , bj4 } from C to
obtain a path with leaves b2 and b3 ; if bj2 and b1 are adjacent, then we add the edge {bj2 , b1 } to C
while delete the edge {aj2 , bj2 } from C to obtain a path with leaves b2 and b3 . Thus, C is settled.
Case 7.2. In the other case v is a tail, say bj4 of the edge ej4 .
Case 7.2.1. If b2 = bj4 , then besides the leaf b3 , we either do nothing to C to leave b1 , b2 as
leaves, or add the edge {b1 , b2 } to C and delete the edge {aj2 , aj1 } to leave aj1 as a leaf, or add the
edge {b1 , b2 } to C and delete the edge {aj2 , bj2 } to leave bj2 as a leaf. Among these three trees, the
maximum total weight of the internal vertices is at least a3 + a1 + aj1 + bj2 + b1 + b2 − min{b1 +
b2 , aj1 , bj2 } ≥ 2(b3 + min{b1 + b2 , aj1 , bj2 }); thus, C is settled.
(In this paragraph, we deal with the case where b3 takes the role of b2 and prove our claim at the
beginning of Case 7 “that the same argument applies to b3 6= bj3 and v is in the type-V component
containing b3 ”. The complete assumption of Case 7.2.1 is thus b3 6= bj3 and v = b3 . Then, besides
the leaf b2 , we either do nothing to C to leave b1 , b3 as leaves, or add the edge {b1 , b3 } to C and
delete the edge {aj2 , aj1 } to leave aj1 as a leaf, or add the edge {b1 , b3 } to C and delete the edge
{aj2 , aj3 } to leave aj3 as a leaf. Among these three trees, the maximum total weight of the internal
vertices is at least a2 + a1 + aj1 + aj3 + b1 + b3 − min{b1 + b3 , aj1 , aj3 } ≥ 2(b2 + min{b1 + b3 , aj1 , aj3 });
thus, C is settled. In summary, here the vertex aj3 takes up the role of bj2 correspondingly.)
Case 7.2.2. If b2 6= bj4 , then by the claw-free property and the definition of v we conclude
that b1 is adjacent to aj4 too. Assume that aj4 is adjacent to bj5 besides bj4 . When bj5 6= bj2 , the
argument in Case 7.1.1 can be applied to settle C; when bj5 = bj2 (the argument in Case 7.1.2
does not applied to settle C due to the deferent v), besides the leaves b2 and b3 , we either do
nothing to C to leave b1 as a leaf, or add the edge {b1 , aj4 } to C and delete the edge {aj2 , bj2 }
to leave bj2 as a leaf, or add the edge {b1 , aj4 } to C and delete the edge {aj2 , aj1 } to leave aj1
as a leaf. Among these three trees, the maximum total weight of the internal vertices is at least
a3 + a2 + aj1 + aj2 + bj2 + a1 + b1 − min{b1 , aj1 , bj2 } ≥ 2(b3 + b2 + min{b1 , aj1 , bj2 }); thus, C is settled.
This finishes the discussion on Case 7.
In summary, Cases 2-7 together prove that when b1 6= bj1 , the component C can be settled. We
next consider the situation where b1 = bj1 , that is, there is no type-V component attached to bj1 .
Case 8. If b1 = bj1 and v = aj2 , then dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by Operation 1.
Case 8.1. If there is a vertex u outside C that is adjacent to a1 , then we add the edge {a1 , u}
to F , add the edge {aj2 , b1 } to C while delete the edge {aj2 , a1 } from C; this way, C is settled.
Case 8.2. Note that if a1 and bj3 (6= b3 ) are adjacent, then a1 and aj3 are adjacent too. By
the claw-free property, we conclude that a1 must be adjacent to a vertex u ∈ {aj3 , b3 , bj2 , b2 }.
Case 8.2.1. When u = aj3 (or u = bj2 ), we add the edges {a1 , u} and {b1 , aj2 } to C while
delete the edges {u, aj2 } and {aj2 , a1 } from C; this way, we obtain a path with two leaves b3 and
b2 , and thus settle C.
Case 8.2.2. Otherwise, aj3 and bj2 are adjacent. When u = b2 (6= bj2 ), we add the edge {a1 , b2 }
to C while delete the edge {aj2 , a1 } from C, to obtain a path with two leaves b3 and b1 ; we may
also add the edges {a1 , b2 } and {aj2 , b1 } to C while delete the edges {aj2 , a1 } and {aj2 , bj2 } from C
to obtain a path with two leaves b3 and bj2 . Between these two paths, the maximum total weight
of the internal vertices is at least a3 + aj2 + bj2 + a1 + b1 − min{b1 , bj2 } ≥ 2(b3 + min{b1 , bj2 }); thus,

Approximating the maximum weight internal spanning tree

21

C is settled. When u = b3 (6= bj3 ), the same argument applies to settle C.
Case 9. If b1 = bj1 and v = bj2 , we add the edge {b1 , bj2 } to C while delete the edge {aj2 , bj2 }
from C; this way, we obtain a path with two leaves b3 and b2 , and thus C is settled.
If b1 = bj1 and v = aj3 , we add the edge {b1 , aj3 } to C while delete the edge {aj3 , aj2 } from C;
this way, we obtain a path with two leaves b3 and b2 , and thus C is settled.
If b1 = bj1 and v = bj3 , then we distinguish whether bj3 = b3 or not. When bj3 6= b3 , then b1
and aj3 must be adjacent in G and thus C can be settled as in the last paragraph. When bj3 = b3 ,
if aj3 is adjacent to one of a1 and bj2 , then we can obtain a path with two leaves b3 and b2 to settle
C; if a1 and bj2 are adjacent and bj2 6= b2 , then we can obtain a path with two leaves being b2 and
the lightest among a3 , aj2 , a1 , and thus the total weight of the internal vertices of this path is at
least a2 + a3 + aj2 + a1 + b1 − min{a3 , aj2 , a1 } ≥ 2(b2 + min{a3 , aj2 , a1 }), which settles C; otherwise
bj2 = b2 , and then we add the edge {a1 , b2 } to C while delete the edge {a2 , a1 } from C to obtain a
cycle, followed by deleting the lightest edge of C ∩ M ∗ = {{a1 , b1 }, {a2 , b2 }, {a3 , b3 }} to settle C.
Case 10. If b1 = bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail. Note that the case where b3 6= bj3 and v is in the type-V component
containing b3 can be argued in exactly the same way.
Case 10.1. If v is a head, say aj4 of the edge ej4 , assume that aj4 is adjacent to bj5 besides
bj4 . Exactly the same argument as in Case 7.1 applies to settle C, since it does not matter whether
b1 = bj1 or not.
Case 10.2. If v is a tail, say bj4 of the edge ej4 . Note that bj4 6= bj2 , which has been dealt in
Case 9.
Case 10.2.1. If b2 = bj4 , then besides the leaf b3 , we either do nothing to C to leave b1 , b2 as
leaves, or add the edge {b1 , b2 } to C and delete the edge {aj2 , a1 } to leave a1 as a leaf, or add the
edge {b1 , b2 } to C and delete the edge {aj2 , bj2 } to leave bj2 as a leaf. Among these three trees, the
maximum total weight of the internal vertices is at least a3 + a1 + aj2 + bj2 + b1 + b2 − min{b1 +
b2 , a1 , bj2 } ≥ 2(b3 + min{b1 + b2 , a1 , bj2 }); thus, C is settled.
Case 10.2.2. If b2 6= bj4 , then by the claw-free property and the definition of v we conclude
that b1 is adjacent to aj4 too. Assume that aj4 is adjacent to bj5 besides bj4 . When bj5 6= bj2 ,
the argument in Case 7.1.1 can be applied to settle C; when bj5 = bj2 , if aj3 and bj2 are adjacent,
then we add the edges {aj3 , bj2 } and {b1 , aj4 } to C and delete the edges {aj3 , aj2 } and {bj2 , aj4 } to
achieve a path with leaves b3 and b2 ; if aj3 and a1 are adjacent, then we add the edges {aj3 , a1 },
{b1 , aj4 } and {b1 , bj4 } to C and delete the edges {aj3 , aj2 }, {a1 , b1 } and {aj4 , bj4 } to achieve a path
with leaves b3 and b2 ; if bj2 and a1 are adjacent, then we add the edges {bj2 , a1 }, {b1 , aj4 } and
{b1 , bj4 } to C and delete the edges {aj2 , bj2 }, {a1 , b1 } and {aj4 , bj4 } to achieve a path with leaves
b3 and b2 . Thus, C is settled.
All possible cases have be discussed in the above. The lemma is proven.
✷

Lemma 11 A type-III component in the subgraph H3 can be settled.
Proof. Recall that a type-III component C in its original form contains only one edge ej1 =
{aj1 , bj1 } of M ∗ , with another edge {aj1 , x} where x ∈ X (see Figure 3a); there could be a type-V
component attached to bj1 , with its tail b1 replacing the role of bj1 .

22

Chen et al. /v:May 30, 2017

Case 1. If b1 is adjacent to a vertex v outside C, then we add the edge {b1 , v} to F , which settles
C, since the total weight of the internal vertices in C is w(C ∩ M ∗ ).
We next consider the case where b1 is not adjacent to any vertex outside C, and thus it has to
be adjacent to some vertex inside C. Note that C is a path with b1 and x being its two ending
vertices. Let v denote the vertex adjacent to b1 that is the farthest to b1 on C. We distinguish this
distance dC (b1 , v) ≥ 2 and where v locates.
Case 2. If b1 6= bj1 and v is in the type-V component containing b1 , then v must be a tail of an
edge of M ∗ and thus dC (b1 , v) is even. Denote this edge as ej2 = {aj2 , bj2 }, that is v = bj2 .
Case 2.1. If dC (b1 , v) ≥ 4, then denote the head vertex bj2 is adjacent to in the type-V
component as aj3 , besides aj2 . We conclude from the claw-free property that there must be at least
an edge among aj2 , aj3 , b1 , which contradicts the identity of the type-V component. Therefore, it
is impossible to have dC (b1 , v) ≥ 4.
Case 2.2. If dC (b1 , v) = 2, then we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1, i.e. there is at least another edge incident at a1 besides {a1 , bj2 } and {a1 , b1 }. Denote
this neighbor of a1 as u, which is impossible to be inside C by our construction algorithm. Thus,
we add the edge {b1 , bj2 } to C while delete the edge {a1 , bj2 } from C, and add the edge {a1 , u} to
F ; this way, the component becomes a path and thus C is settled.
Case 3. If b1 6= bj1 and v = bj1 , we consider the size of the type-V component containing b1 .
Case 3.1. If this type-V component contains more than one edge of M ∗ , then by the claw-free
property aj1 must be adjacent to b1 , which violates the definition of v being the farthest and thus
it is impossible.
Case 3.2. If the type-V component containing b1 has only one edge of M ∗ , that is {a1 , b1 },
then exactly the same argument in Case 2.2 settles C.
Case 4. If b1 6= bj1 and v = aj1 , then we leave C as it is if w(b1 ) ≤ w(bj1 ), or we add the edge
{aj1 , b1 } to C while delete the edge {aj1 , bj1 } from C. In either case, the total weight of the internal
vertices in the resulting path is at least aj1 + a1 + max{bj1 , b1 } ≥ 3 min{bj1 , b1 }, and thus it settles
C.
Case 5. If b1 6= bj1 and v = x, then we leave C as it is if w(b1 ) ≤ w(aj1 ), or we add the edge
{x, b1 } to C while delete the edge {aj1 , x} from C. In either case, the total weight of the internal
vertices in the resulting path is at least a1 + max{aj1 , b1 } ≥ 2 min{aj1 , b1 }, and thus it settles C.
In summary, Cases 2-5 together prove that when b1 6= bj1 , the component C can be settled. We
next consider the situation where b1 = bj1 , that is, there is no type-V component adjacent to bj1 .
Case 6. If b1 = bj1 , then v = x, and we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1, that is, there is a vertex u outside C that is adjacent to a1 . Thus we add the edge
{a1 , u} to F , add the edge {x, b1 } to C while delete the edge {a1 , x} from C; this way, C is settled.
All possible cases have be discussed in the above. The lemma is proven.
✷

Lemma 12 A type-IV component in the subgraph H3 can be settled.
Proof. Denote the two edges of M ∗ in the type-IV component C in its original form as ej1 and
ej2 . Note that both aj1 and aj2 are adjacent to a vertex x ∈ X (see Figure 3b), and there could be

Approximating the maximum weight internal spanning tree

23

a type-V component attached to bj1 and bj2 , respectively, with the tails b1 , b2 replacing the roles of
bj1 , bj2 . We assume w.l.o.g. that w(b1 ) ≥ w(b2 ).
Case 1. If b1 is adjacent to a vertex v outside C, then we add the edge {b1 , v} to F , which settles
C, since the total weight of the internal vertices in C is at least a1 + b1 + a2 ≥ 3b2 .
We next consider the case where b1 is not adjacent to any vertex outside C, and thus it has to
be adjacent to some vertex inside C. Note that C is a path with b1 and b2 being its two ending
vertices. Let v denote the vertex adjacent to b1 that is the farthest to b1 on C. We distinguish this
distance dC (b1 , v) ≥ 2 and where v locates.
Case 2. If b1 6= bj1 and v is in the type-V component containing b1 , then v must be a tail of an
edge of M ∗ and thus dC (b1 , v) is even. Denote this edge as ej3 = {aj3 , bj3 }, that is v = bj3 .
Case 2.1. If dC (b1 , v) ≥ 4, then denote the head vertex bj3 is adjacent to in the type-V
component as aj4 , besides aj3 . We conclude from the claw-free property that there must be at least
an edge among aj3 , aj4 , b1 , which contradicts the identity of the type-V component. Therefore, it
is impossible to have dC (b1 , v) ≥ 4.
Case 2.2. If dC (b1 , v) = 2, then we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1, i.e. there is at least another edge incident at a1 besides {a1 , bj3 } and {a1 , b1 }. Denote
this neighbor of a1 as u. If u is inside C, then u = b2 by our construction algorithm and the
claw-free property. We add the edges {a1 , b2 } and {bj3 , b1 } to C while delete the edge {bj3 , a1 }
from C to obtain a cycle, followed by deleting the lightest edge of C ∩ M ∗ ; this settles C since
C ∩ M ∗ has at least three edges. If u is outside C, then we add the edge {b1 , bj3 } to C while delete
the edge {a1 , bj3 } from C, and add the edge {a1 , u} to F ; this way, the component becomes a path
and thus C is settled.
Case 3. If b1 6= bj1 and v = bj1 , we consider the size of the type-V component containing b1 .
Case 3.1. If this type-V component contains more than one edge of M ∗ , then by the claw-free
property aj1 must be adjacent to b1 , which violates the definition of v being the farthest and thus
it is impossible.
Case 3.2. If the type-V component containing b1 has only one edge of M ∗ , that is {a1 , b1 },
then from the definition of v we have dG (b1 ) = 2, and thus dG (a1 ) ≥ 3 by Operation 1, i.e. there is
at least another edge incident at a1 besides {a1 , bj1 } and {a1 , b1 }. The same argument as in Case
2.2, with j3 replaced by j1 , applies to settle C.
Case 4. If b1 6= bj1 and v = aj1 , then we leave C as it is when w(b1 ) ≤ w(bj1 ), or we add the
edge {aj1 , b1 } to C while delete the edge {aj1 , bj1 } from C. In either case, the total weight of the
internal vertices in the resulting path is at least a2 + aj1 + a1 + max{bj1 , b1 } ≥ 2(b2 + min{bj1 , b1 }),
and thus it settles C.
Case 5. If b1 6= bj1 and v = x, then by the definition of v and the claw-free property aj1 and b1
are adjacent. We thus settle C as in Case 4. We note that this is simpler than Case 5 in the proof
of Lemma 10 because here aj1 and aj2 cannot be adjacent.
Case 6. If b1 6= bj1 and v = aj2 , then we add the edge {aj2 , b1 } to C while delete the edge {aj2 , x}
from C. This gives a path with leaves b2 and x, and thus it settles C.
If b1 6= bj1 and v = bj2 , then we conclude that aj2 and b1 are adjacent when b2 6= bj2 , and thus
we settle C as in the last paragraph; when b2 = bj2 , we add the edge {b2 , b1 } to C to obtain a cycle,

24

Chen et al. /v:May 30, 2017

followed by deleting the lightest edge of C ∩ M ∗ from C. Since C ∩ M ∗ has at least three edges,
this settles C.
Case 7. If b1 6= bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail.
Case 7.1. If v is a head, say aj3 of the edge ej3 , and assume that aj3 is adjacent to bj4 besides bj3 ,
then we do nothing to C to leave b1 as a leaf when w(b1 ) ≤ w(bj4 ), or otherwise add the edge {aj3 , b1 }
to C while delete the edge {aj3 , bj4 } from C to leave bj4 as a leaf. In either way, the total weight of
the internal vertices of the resulting path is at least a2 +aj4 +a1 +max{bj4 , b1 } ≥ 2(b2 +min{bj4 , b1 }).
Therefore, in either case C can be settled.
Case 7.2. If v is a tail, say bj3 of the edge ej3 . If b2 = bj3 , then we add the edge {b1 , b2 } to C
to obtain a cycle, followed by deleting the lightest edge of C ∩ M ∗ from C. Since C ∩ M ∗ has at
least three edges, this settles C. If b2 6= bj3 , then by the claw-free property and the definition of v
we conclude that b1 is adjacent to aj3 too, and thus the argument in Case 7.1 applies to settle C.
This finishes the discussion on Case 7.
In summary, Cases 2-7 together prove that when b1 6= bj1 , the component C can be settled. We
next consider the situation where b1 = bj1 , that is, there is no type-V component adjacent to bj1 .
Case 8. If b1 = bj1 and v = x, and we conclude that dG (b1 ) = 2 and thus dG (a1 ) ≥ 3 by
Operation 1, that is there is a vertex u adjacent to a1 other than x and b1 .
Case 8.1. If u is inside C, then u = b2 by our construction algorithm and the claw-free property.
2
If b 6= bj2 , then we add the edges {a1 , b2 } and {x, b1 } to C while delete the edge {x, a1 } from C
to obtain a cycle, followed by deleting the lightest edge of C ∩ M ∗ ; this settles C since C ∩ M ∗
has at least three edges. If b2 = bj2 , then we add the edges {a1 , b2 } and {x, b1 } to C while delete
the edges {x, a1 } and {x, a2 } from C to obtain a path with leaves x and a2 when w(a2 ) ≤ w(b1 ),
or otherwise we add the edge {a1 , b2 } to C while delete the edge {x, a1 } from C to obtain a path
with leaves x and b1 . In either way, the total weight of the internal vertices of the resulting path
is at least a1 + max{a2 , b1 } ≥ 2 min{a2 , b1 }. Therefore, C can be settled.
Case 8.2. If u is outside C, then we add the edge {b1 , x} to C while delete the edge {a1 , x}
from C, and add the edge {a1 , u} to F ; this way, the component becomes a path and thus C is
settled.
Case 9. If b1 = bj1 and v = aj2 , then we add the edge {aj2 , b1 } to C while delete the edge {aj2 , x}
from C to obtain a path with leaves x and b2 . Therefore, C can be settled.
If b1 = bj1 and v = bj2 , when b2 6= bj2 then we conclude from the claw-free property and
the definition of v that aj2 and b1 are also adjacent, and thus C can be settled as in the last
paragraph; when b2 = bj2 , we can either do nothing to C to leave b1 and b2 as leaves, or add the
edge {b2 , b1 } to C to obtain a cycle, followed by either deleting the edge {a2 , x} to obtain a path
with leaves a2 and x, or deleting the edge {a1 , x} to obtain a path with leaves a1 and x. This
way, the maximum total weight of the internal vertices among the three resulting paths is at least
a1 + a2 + b1 + b2 − min{a1 , a2 , b1 + b2 } ≥ 2 min{a1 , a2 , b1 + b2 }. Thus, C can be settled.
Case 10. If b1 = bj1 , b2 6= bj2 , and v is in the type-V component containing b2 , we distinguish
whether v is a head or a tail.
Case 10.1. If v is a head, say aj3 of the edge ej3 , and assume that aj3 is adjacent to bj4 besides
bj3 , then we do nothing to C to leave b1 as a leaf if w(b1 ) ≤ w(bj4 ), or otherwise add the edge {aj3 , b1 }
to C while delete the edge {aj3 , bj4 } from C to leave bj4 as a leaf. This way, the total weight of the

Approximating the maximum weight internal spanning tree

25

internal vertices of the resulting path is at least a1 + a2 + aj4 + max{b1 , bj4 } ≥ 2(b2 + min{b1 , bj4 }).
Thus, C can be settled.
Case 10.2. If v is a tail, say bj3 of the edge ej3 . If b2 = bj3 , then we add the edge {b1 , b2 } to C
to make it a cycle followed by deleting the lightest edge of C ∩ M ∗ ; this settles C since there are
at least three edges in C ∩ M ∗ . If b2 6= bj3 , then from the claw-free property and the definition of
v, we conclude that aj3 must be adjacent to b1 too. Therefore, the same as in Case 10.1, C can be
settled.
All possible cases have be discussed in the above. The lemma is proven.
✷

Lemma 13 A type-VI component in the subgraph H3 can be settled.
Proof. Recall that a type-VI component C is a cycle containing two or more edges of M ∗ , where
the head of one edge of M ∗ is adjacent to the tail of another edge of M ∗ (see Figure 4b). Clearly,
if there are three or more edges of M ∗ in C, we simply delete the lightest one to settle C. In the
sequel we deal with the case where C is a length-4 cycle. Denote the two edges of C ∩M ∗ as {a1 , b1 }
and {a2 , b2 }, and assume that w(b1 ) ≥ w(b2 ).
If a1 (a2 , respectively) is adjacent to a vertex v outside C, then we add the edge {a1 , v} ({a2 , v},
respectively) to F and delete the edge {a1 , b2 } ({a2 , b2 }, respectively) from C; this way, the total
weight of the internal vertices is at least a1 + a2 + b1 ≥ 3b2 , and thus C is settled.
If neither a1 nor a2 is adjacent to any vertex v outside C, then we conclude from the construction
algorithm that dG (a1 ) = dG (a2 ) = 2 since a1 and a2 are not adjacent to each other. It follows from
the claw-free property that neither b1 nor b2 can be adjacent to any vertex u outside C. This
implies |V | = 4, a contradiction to our assumption that |V | ≥ 5. The lemma is proved.
✷

Theorem 2 The MwIST problem on claw-free graphs admits a 12/7-approximation algorithm.
Proof. The above Lemmas 9–13 state that every component of the subgraph H3 = G[V, M ∗ ∪
M aa ∪ N aa ∪ N ax ∪ M ab ∪ N ab ] can be settled, without affecting any other components. Also, such a
settling process for a component takes only linear time, by scanning once the edges in the subgraph
induced on the set of vertices of the component. By settling, essentially the component is converted
into a tree, possibly with one edge of F specified for connecting a leaf of the tree outwards.
In the next step of the algorithm, it iteratively processes the heaviest component C, i.e. with
the largest w(C ∩ M ∗ ). If the component C has been associated with an edge e of F , and using
the edge e to connect a leaf of the resulting tree for C outwards does not create a cycle, then the
algorithm does this and C is processed. This guarantees the total weight of the internal vertices
in V (C) is at least 2w(C ∩ M ∗ )/3. If using the edge e to connect a leaf of the resulting tree for
C outwards would create a cycle, the algorithm processes C by replacing C with another tree that
guarantees the total weight of the internal vertices in V (C) at least 21 w(C ∩ M ∗ ). Notice that
the latter case happens only because of (at least) one edge of F in an earlier iteration where a
distinct component C ′ was processed, which connects a vertex of C ′ into a vertex of C. Therefore,
every such C is associated with a distinct component C ′ processed by the algorithm in an earlier
iteration, and thus w(C ′ ) ≥ w(C). On the other hand, every such component C ′ is associated to
one C only, due to its edge in F connecting a leaf outwards into a vertex of C. It follows that for
this pair of components C and C ′ , the total weight of the internal vertices in V (C) ∪ V (C ′ ) is at
least
w(C)/2 + 2w(C ′ )/3 ≥ 7(w(C) + w(C ′ ))/12.

26

Chen et al. /v:May 30, 2017

After all components of H3 are processed, we obtain a forest for which the total weight of the
internal vertices therein is at least 7w(M ∗ )/12. The algorithm lastly uses any other available edges
of E to interconnect the forest into a final tree, denoted as T ; clearly w(T ) ≥ 7w(M ∗ )/12.
The time for the interconnecting purpose is at most O(m log n). Therefore, by Corollary 1 we
have a 7/12-approximation algorithm for the MwIST problem on claw-free graphs.
✷

4

Concluding remarks

We have presented an improved approximation algorithm for the vertex weighted MIST problem,
denoted MwIST, which achieves the worst-case performance ratio 1/2, beating the previous best
ratio of 1/(3 + ǫ), designed by Knauer and Spoerhase in 2009 [7]. The key ingredient in the design
and analysis of our algorithm is a novel relationship between MwIST and the maximum weight
matching, which we uncovered and it is inspired by the work [12, 11, 2]. A step further, for the
problem restricted to claw-free graphs, we presented a 7/12-approximation algorithm, improving
the previous best ratio of 1/2 designed by Salamon in 2009 for claw-free graphs without leaves.
It would be interesting to see whether this newly uncovered relationship, possibly combined with
other new ideas, can be explored further to design better approximation algorithms for MwIST, or
special cases of MwIST including claw-free graphs and cubic graphs.

Acknowledgement
The authors are grateful to two reviewers for their insightful comments on the COCOON 2017
submission and for their suggested changes that improve the presentation greatly.
ZZC was supported in part by the Grant-in-Aid for Scientific Research of the Ministry of
Education, Culture, Sports, Science and Technology of Japan, under Grant No. 24500023. GL was
supported by the NSERC Canada and the NSFC Grant No. 61672323; most of his work was done
while visiting ZZC at the Tokyo Denki University at Hatoyama. LW was supported by the Hong
Kong GRF Grants CityU 114012 and CityU 123013. YC was supported in part by the NSERC
Canada, the NSFC Grants No. 11401149, 11571252 and 11571087, and the China Scholarship
Council Grant No. 201508330054.

References
[1] D. Binkele-Raible, H. Fernau, S. Gaspers, and M. Liedloff. Exact and parameterized algorithms
for max internal spanning tree. Algorithmica, 65:95–128, 2013.
[2] Z.-Z. Chen, Y. Harada, and L. Wang. An approximation algorithm for maximum internal
spanning tree. CoRR, abs/1608.00196, 2016.
[3] N. Coben, F. V. Fomin, G. Gutin, E. J. Kim, S. Saurabh, and A. Yeo. Algorithm for finding kvertex out-trees and its application to k-internal out-branching problem. Journal of Computer
and Systems Science, 76:650–662, 2010.
[4] F. V. Fomin, S. Gaspers, S. Saurabh, and S. Thomasse. A linear vertex kernel for maximum
internal spanning tree. Journal of Computer and Systems Science, 79:1–6, 2013.

Approximating the maximum weight internal spanning tree

27

[5] F. V. Fomin, D. Lokshtanov, F. Grandoni, and S. Saurabh. Sharp separation and applications
to exact and parameterized algorithms. Algorithmica, 63:692–706, 2012.
[6] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-completeness. W. H. Freeman and Company, San Francisco, 1979.
[7] M. Knauer and J. Spoerhase. Better approximation algorithms for the maximum internal
spanning tree problem. In Proceedings of WADS 2009, LNCS 5664, pages 489–470, 2009.
[8] W. Li, J. Chen, and J. Wang. Deeper local search for better approximation on maximum
internal spanning tree. In Proceedings of ESA 2014, LNCS 8737, pages 642–653, 2014.
[9] W. Li, J. Wang, J. Chen, and Y. Cao. A 2k-vertex kernel for maximum internal spanning tree.
In Proceedings of WADS 2015, LNCS 9214, pages 495–505, 2015.
[10] X. Li, H. Jiang, and H. Feng. Polynomial time for finding a spanning tree with maximum
number of internal vertices on interval graphs. In Proceedings of FAW 2016, LNCS 9711,
pages 92–101, 2016.
[11] X. Li and D. Zhu. A 4/3-approximation algorithm for the maximum internal spanning tree
problem. CoRR, abs/1409.3700, 2014.
[12] X. Li and D. Zhu. Approximating the maximum internal spanning tree problem via a maximum
path-cycle cover. In Proceedings of ISAAC 2014, LNCS 8889, pages 467–478, 2014.
[13] E. Prieto. Systematic kernelization in FPT algorithm design. PhD thesis, The University of
Newcastle, Australia, 2005.
[14] E. Prieto and C. Sliper. Either/or: Using vertex cover structure in designing fpt-algorithms
– the case of k-internal spanning tree. In Proceedings of WADS 2003, LNCS 2748, pages
474–483, 2003.
[15] E. Prieto and C. Sloper. Reducing to independent set structure – the case of k-internal spanning
tree. Nordic Journal of Computing, 12:308–318, 2005.
[16] G. Salamon. Approximating the maximum internal spanning tree problem. Theoretical Computer Science, 410:5273–5284, 2009.
[17] G. Salamon. Degree-Based Spanning Tree Optimization. PhD thesis, Budapest University of
Technology and Economics, Hungary, 2009.
[18] G. Salamon and G. Wiener. On finding spanning trees with few leaves. Information Processing
Letters, 105:164–169, 2008.

