Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
Ran Duan Haoqing He Tianyi Zhang
cs.DS



1]Ran Duanduanran@mail.tsinghua.edu.cn
1]Haoqing Hehehq13@mails.tsinghua.edu.cn
1]Tianyi Zhangtianyi-z16@mails.tsinghua.edu.cn


[1]Institute for Interdisciplinary Information Sciences, Tsinghua University




Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees This work has been supported in part by the Zhongguancun Haihua Institute for Frontier Information Technology.
    [
    
=======================================================================================================================================================================================




Given a graph G = (V, E), we wish to compute a spanning tree whose maximum vertex degree, i.e. tree degree, is as small as possible. Computing the exact optimal solution is known to be NP-hard, since it generalizes the Hamiltonian path problem. For the approximation version of this problem, a Õ(mn) time algorithm that computes a spanning tree of degree at most +1 is previously known [Fürer & Raghavachari 1994]; here  denotes the minimum tree degree of all the spanning trees. In this paper we give the first near-linear time approximation algorithm for this problem. Specifically speaking, we propose an Õ(1/ϵ^7m) time algorithm that computes a spanning tree with tree degree (1+ϵ) + O(1/ϵ^2log n) for any constant ϵ∈ (0,1/6). Thus, when =ω(log n), we can achieve approximate solutions with constant approximate ratio arbitrarily close to 1 in near-linear time.







§ INTRODUCTION

Computing minimum degree spanning trees is a fundamental problem that has inspired a long time of research. Let G = (V, E) be an undirected graph, and we wish to compute a spanning tree of G whose tree degree, or maximum vertex degree in the tree, is the smallest. Clearly this problem is NP-hard as the Hamiltonian path problem can be reduced to it, and so we could only hope for a good approximation in polynomial time. The optimal approximation of this problem was achieved in <cit.> where the authors proposed a [Õ(·) hides poly-logarithmic factors.]Õ(mn) time algorithm that computes a spanning tree of tree degree ≤ + 1; conventionally n = |V|, m = |E| and  denotes the minimum tree degree of all the  spanning trees. For convenience, in this paper the degree of a vertex usually means its tree degree in the current spanning tree.



 §.§ Our results

The major result of this paper is a near-linear time algorithm for computing minimum degree spanning trees in undirected graphs. To the best of our knowledge, this is the first near-linear time algorithm for this problem. Formally we propose the following statement.



There is an [α(·) refers to the inverse Ackermann function.]O(mα(n)log^2 n + nlog^3 n) time algorithm that computes a spanning tree with tree degree O(log n).


The core argument for Theorem <ref> is that, starting from an arbitrary spanning tree, for a fixed threshold k≥ 3, we repeatedly search for an edge connecting two vertices of tree degree ≤ k-2 such that the tree path between its two endpoints contains a vertex of tree degree ≥ k. If such a search is successful, then we can modify the current spanning tree which immediate reduces the total number of high-degree vertices; otherwise, we argue a lower bound on  in terms of the current tree degree. The main technical difficulty of this approach is that the algorithm may generate a large number of (k-1)-degree vertices which undermines the lower bound on . To circumvent such difficulties, the crucial observation is that if a vertex which starts out as a low-degree vertex becomes (k-1)-degree, lots of high-degree vertices must have lost some tree neighbours.



For any constant ϵ∈ (0, 1/6), there is an algorithm that runs in  O(1/ϵ^7mlog^7 n) time which computes a spanning tree with tree degree at most (1+ϵ) + 576/ϵ^2log n.




The core argument of Theorem <ref> is that, starting from an arbitrary spanning tree, we repeatedly search for a sequence of distinct non-tree edges, named as augmenting sequence (The formal definition is given in Section <ref>), to modify the current spanning tree which immediately reduces the degree of some high-degree vertex.
The idea of augmenting sequence is similar to <cit.>, that is, given a fixed degree bound k, an augmenting sequence w.r.t. the current spanning tree and k is a sequence of vertex-disjoint non-tree edges (w_1, z_1), (w_2, z_2), ⋯, (w_h, z_h) such that w_1,w_2,⋯,w_h-1 have tree degree k-1 and w_h,z_1,z_2,⋯, z_h have tree degree <k-1. Also there is a vertex w_0 with tree degree ≥ k on the tree path between w_1 and z_1,  and w_i for 1≤ i<h is on the tree path between w_i+1 and z_i+1 but not on the tree path between w_j and z_j for j>i+1. Then we can add theses edges (w_1, z_1) ⋯, (w_h, z_h) to the spanning tree and delete the edges associated with w_0,⋯,w_h-1 on the cycles formed, so the total degree of vertices with degree ≥ k will decrease by 1 but more degree-(k-1) vertices may emerge. 

In our process of searching, similar to the blocking flow approach <cit.> for max-flow, we first construct a layering of the graph by the shortest length of augmenting sequences, then each time find a shortest augmenting sequence in the layering and do such tree modification by this augmenting sequence, thus after near-linear time the shortest length of augmenting sequences would increase. We repeat this until the length of the shortest augmenting sequence is longer than 1/ϵlog n. 
When this happens, the number of layers also exceeds 1/ϵlog n, so there are two adjacent layer whose ratio is at most 1+ϵ, then if the number of augmenting sequences we found are not too large (not too many new degree-(k-1) vertices emerge), we can argue a 1+O(ϵ) approximation for the optimal solution . In the whole procedure of our algorithm, we can let k=(1-O(ϵ))Δ for the degree Δ of the current spanning tree, and make k increase by one after each iteration until in some iteration the sum of degree of all the vertices with degree ≥ k is not significantly decreased. See Section <ref>.




 §.§ Related work

There is a line of works that are concerned with low-degree trees in weighted undirected graphs. In this scenario, the target low-degree that we wish to compute is constrained by two parameters: an upper bound B on tree degree, an upper bound C on the total weight summed over all tree edges. The problem was originally formulated in <cit.>. Two subsequent papers <cit.> proposed polynomial time algorithms that compute a tree with cost ≤ wC and degree ≤w/w-1bB + log_b n, ∀ b, w> 1. This result was substantially improved by <cit.>; using certain augmenting path technique, their algorithm is capable of finding a tree with cost ≤ C and degree B + O(log n / loglog n). Results and techniques from <cit.> might sound similar to ours, but in undirected graphs we are actually faced with different technical difficulties. <cit.>'s result was improved by <cit.> where for all k, a spanning tree of degree ≤ k+2 and of cost at most the cost of the optimum spanning tree of maximum degree at most k can be computed in polynomial time. The degree bound was later further improved from k+2 to the optimal k+1 in <cit.>.

Another variant is minimum degree Steiner trees which is related to network broadcasting <cit.>. For undirected graphs, authors of <cit.> showed that the same approximation guarantee and running time can be achieved as with minimum degree spanning trees in undirected graphs, i.e., a solution of tree degree + 1 and a running time of Õ(mn). For the directed case, <cit.> showed that directed minimum degree Steiner tree problem cannot be approximated within (1-ϵ)log|D|, ∀ϵ > 0 unless NP⊆DTIME(n^loglog n), where D is the set of terminals.

The minimum degree tree problem can also be formulated in directed graphs. This problem was first studied in <cit.> where the authors proposed a polynomial time algorithm that finds a directed spanning tree of degree at most O(log n). The approximation guarantee was improved to roughly O( + log n) in <cit.> while the time complexity became n^O(log n). The problem becomes much easier when G is acyclic, as shown in <cit.>, where a directed spanning tree of degree ≤ + 1 is computable in polynomial time. The approximation was greatly advanced to + 2 in <cit.> by an LP-based polynomial time algorithm, and this problem has become more-or-less closed since then.






§ PRELIMINARY

Let G=(V,E) be the graph we consider, and we assume G is a connected graph. Logarithms are taken at base 2. During the execution of our algorithm, a spanning tree  will be maintained. For every u∈ V, let (u) be the tree degree of u in , and the degree of the spanning tree  is defined as Δ = max_u∈ V(u). Our algorithm will repeatedly modify  to reduce its degree Δ. Let  denote the minimum degree of all the spanning trees. For each pair u, v∈ V, let ρ_u, v be the unique tree path that connects u and v in . For each 1≤ k≤ n, define S_k = {u|(u) ≥ k } to be the set of vertices of degree at least k, N_k = {u|(u) = k } to be the set of vertices of degree exactly k, and d_k = ∑_u∈ S_k(u) to be the sum of degrees of vertices in S_k.



 §.§ Boundary edge and boundary set

Boundary edge and boundary set are important concepts to get the lower bound of .
 
For a graph G = (V, E) and a sequence of disjoint vertex subsets V_1, V_2, ⋯, V_l ⊆ V, an edge (u,v)∈ E is called a boundary edge if u∈ V_i, v∈ V_j for 1≤ i≠ j≤ l, or u∈ V_i for some i but v∉ V_1∪⋯∪ V_l. A vertex set W is called a boundary set (with respect to V_1, V_2, ⋯, V_l), if for every boundary edge (u,v), at least one of u,v belongs to W.



Let V_1, V_2, ⋯, V_l⊆ V be a sequence of disjoint vertex subsets, W be a boundary set and  be the minimum degree of all the spanning tree in G. Then, ≥l-1/|W|.


By Definition <ref>, every set V_i can only be connected to other vertices by boundary edges, so for any spanning tree T of G, there are at least l-1 boundary edges connecting V_1, V_2, ⋯, V_l in T. Then for any boundary edge (u,v), at least one of u,v belongs to W. Thus by the pigeon-hole principle, there exists a u∈ W whose tree degree is ≥l-1/|W|.








§ A (1+Ε) + O(1/Ε^2LOG N) APPROXIMATION


Let ϵ∈ (0, 1/48) be a fixed parameter. This algorithm starts from an arbitrary spanning tree  and keeps modifying  to decrease its tree degree Δ. It consists of two phases: the large-step phase and the small-step phase. 


	
  * In the large-step phase, as long as Δ≥10log^2 n/ϵ^3, we repeatedly apply a near-linear time subroutine that, either Δ is reduced to ≤ (1-ϵ)·Δ or a spanning tree  is returned with the guarantee that Δ = (1+O(ϵ)). 
	
  * In the small-step phase, we need to deal with the situation where 9log n/ϵ^2≤Δ < 10log^2 n/ϵ^3. In this case we repeatedly run a weaker near-linear time subroutine that either Δ is reduced by 1 or a spanning tree  is returned with the guarantee that Δ≤ (1+O(ϵ)) + O(log n/ϵ^2).


Both phases rely on a degree reduction algorithm . The  efficiently reduces the total degree of vertices with degree ≥ k by 1 using an augmenting sequence technique.

For the rest of this section, we first propose and analyze the degree reduction algorithm  which underlies the core of our main algorithm. After that we specify how the large-step phase and the small-step phase work. Finally, we prove Theorem <ref>.



 §.§ Degree reduction via augmenting sequences


For a fixed threshold k≤Δ, a simple idea is that we repeatedly look for non-tree edges that connect two vertices of tree degree ≤ k-2 from different components of ∖ S_k and add these edges to , while at the same time we delete some edges incident on S_k to eliminate cycles, so the tree degrees of vertices become more balanced. In this algorithm, we continue to explore possibilities of improving the tree structure using the idea of augmenting sequence as in <cit.>. For a non-tree edge (u,v) that connects two different components C_u,C_v of ∖ S_k where deg(u) = k-1, we try to add (u,v) to  and delete some edge incident on S_k to eliminate cycles. At the same time, as deg(u) increases to k, we keep looking for a sequence of distinct non-tree edges inside C_u to add to  and delete a sequence of tree edges to eliminate cycles.

A difficulty is that when the degrees of some original (k-1)-degree vertices decrease, it is hard to make the layering of the graph stable. Therefore, we define marked vertices instead of the concept of the vertices with degree ≥ k-1. Given a degree threshold k≤Δ, a vertex gets marked whenever its tree degree becomes k-1, and it stays marked even if its tree degree becomes below k-2 afterwards. We only re-initialize the set of marked vertices when we change k in Section <ref>. Then we can define augmenting sequence formally.

An h-length augmenting sequence consists of a sequence of vertex-disjoint non-tree edges (w_1, z_1), (w_2, z_2), ⋯, (w_h, z_h)∈ E with the following properties.

	
  * ∃ w_0∈ρ_w_1, z_1∩ S_k, and for all 0≤ i < h,w_i∈ρ_w_i+1, z_i+1∖(⋃_j=i+2^hρ_w_j, z_j).
	
  * All z_i's are unmarked (∀ 1≤ i≤ h); w_i's are marked for all 1≤ i<h and w_h is unmarked.


Then the tree can be modified by the augmenting sequence (w_1, z_1), (w_2, z_2), ⋯, (w_h, z_h) by:

Given an augmenting sequence (w_1, z_1), (w_2, z_2), ⋯, (w_h, z_h)∈ E, one can modify  such that d_k decreases and no vertices are added to S_k. Also Δ cannot increase.


We modify  in an inductive way. For i=h-1, h-2, ⋯, 0, as w_i∈ρ_w_i+1, z_i+1, we can take an arbitrary tree edge (w_i, x)∈ρ_w_i+1, z_i+1, and then perform an update ←∪{(w_i+1, z_i+1)}∖{(w_i, x)} which guarantees that  is still a spanning tree. Because w_j∉ρ_w_i+1, z_i+1 for 0≤ j≤ i-1, tree update ←∪{(w_i+1, z_i+1)}∖{(w_i, x)} does not change the connected components of ∖{w_j}, so the property that w_j∈ρ_w_j+1, z_j+1∖(⋃_l=j+2^hρ_w_l, z_l), ∀ 0≤ j < i is preserved.

During the process, if for any z_i, (z_i) (1≤ i≤ h) becomes k-1 during the process, mark z_i. By definition, d_k decreases as w_0 loses a tree neighbour; plus, no vertices are newly added to S_k because all (w_i), 1≤ i<h are unchanged and (w_h)≤ k-2, (z_i)≤ k-2, ∀ 1≤ i≤ h. Also vertices in S_k can only lose tree neighbors so Δ cannot increase.


Now, back to the  algorithm. The core of this algorithm is that, if the currently shortest augmenting sequences have length h (h<1+log_1+ϵn), it searches for augmenting sequences of length h and applies Lemma <ref> to decrease d_k. When there is no augmenting sequence of length h, it repeats this process for some larger h. Finally this algorithm terminates when h ≥ 1 + log_1+ϵ n and we prove a lower bound on  based on the structure of .

First, we introduce the  algorithm which computes an auxiliary layering of the graph that will also help tree modification later. Initially set B_0← S_k. Inductively, suppose B_0, B_1, ⋯, B_h, h≥ 0 is already computed, then we compute the forest spanned by ∖ (⋃_i=0^hB_i); for each u∈ V∖ (⋃_i=0^hB_i), let C_u^h be the connected component of ∖ (⋃_i=0^hB_i) that contains u. If there exists an edge (u, v)∈ E such that both u, v are unmarked vertices, and that C_u^h≠ C_v^h, then the algorithm terminates and reports that the shortest length of augmenting sequences is equal to h+1; otherwise, we compute B_h+1 to be the set of all marked vertices u∈ V∖ (⋃_i=0^hB_i) such that there exists an unmarked adjacent vertex v with C_u^h≠ C_v^h, and then continue until h > 1+log_1+ϵ n. Note that whenever B_h=∅, B_h+1,⋯,B_⌈ 1+ log_1+ϵn⌉ are all empty. The pseudo code is shown in the  algorithm <ref>.



After we have invoked  and computed a sequence of vertex subsets B_0, B_1, ⋯, B_h which naturally divides the graph into h+2 layers (including a layer of other vertices), every time we will find a length-(h+1) augmenting sequence (w_1, z_1), (w_2, z_2), ⋯, (w_h+1, z_h+1) such that w_i∈ B_i for 1≤ i≤ h, then  apply tree modifications of Lemma <ref> by this augmenting sequence. Repeat this until there is no more length-(h+1) augmenting sequences any more. The difficulty in searching for the shortest augmenting sequences is that, for a search that starts from a pair of adjacent and unmarked vertices u, v satisfying C_u^h≠ C_v^h and goes up the layers B_h, B_h-1, ⋯, B_1, B_0, not every route can reach the top layer B_0 because some previous (h+1)-length augmenting sequences have already blocked the road. Therefore, a depth-first search needs to be performed. To save running time, some tricks are needed: if a certain vertex has been searched before by some previous (h+1)-length augmenting sequences and has failed to lead a way upwards to B_0, then we tag this vertex so that future depth-first searches may avoid this tagged vertex; if a certain edge has been searched before, then we tag this edge whatsoever. The  algorithm may be a better illustration of this algorithm. The recursive algorithm  takes the layer number i and an edge (u,v) as input and keeps searching for edges between a vertex w ∈ (u,v) ∩ B_i-1 and an unmarked vertex z. If such an edge is found, invoke  with the parameter (i-1, (w,z)) and return the result plus (u,v). The pseudo code is shown in the  algorithm <ref>. Later we will prove that  always returns an augmenting sequence if exists.



The upper-level  algorithm repeatedly applies  followed by several rounds of .
Each time  returns an augmenting sequence p, modify  by Lemma <ref> via p. The repeat-loop ends when h≥ 1+log_1+ϵ n. The pseudo code is shown in the  algorithm <ref>.



Before proving termination of , we first need to argue some properties of . The following lemma will serve as the basis for our future proof.


Throughout each iteration of the repeat-loop in , for any 1≤ i < h and  any two adjacent vertices u, v∈ V∖ (⋃_j=0^i B_j) such that u is  unmarked and C_u^i≠ C_v^i, then v∈ B_i+1. (Recall that C_u^h is the connected component of ∖ (⋃_i=0^hB_i) that contains u.)


By rules of , this blocking property holds right after  outputs them. This claim continuous to hold afterwards because tree modifications only merge components C_u^i's and never split any C_u^i's.


Here is an important corollary of this Lemma <ref>.

Throughout each iteration of the repeat-loop, for any w∈ B_i, 1≤ i≤ h, suppose w is adjacent to an unmarked z such that C_w^i-1≠ C_z^i-1. Then ρ_w, z only contains vertices from V∖ (⋃_j=0^i-2 B_j).


Suppose otherwise, then there would be a vertex x∈ρ_w, z∩ B_j, j≤ i-2, then in this case C_w^j ≠ C_z^j, and thus by Lemma <ref> w∈ B_j+1 which is a contradiction as j+1 < i.



Now we have the following lemmas:

If  returns a sequence of edges (w_1, z_1),⋯,(w_h+1,z_h+1), then w_i∈ B_i for 1≤ i≤ h, and w_h+1, z_1,⋯ z_h+1 are unmarked, also the edges are vertex-disjoint.


    The initial u,v are unmarked. From the algorithm, when calling , we find a w∈ρ_u,v∩ B_i-1 and z is unmarked , so the corresponding w_i∈ B_i for 1≤ i≤ h, and w_h+1, z_1,⋯ z_h+1 are unmarked, also the vertices {w_i|1≤ i≤ h} are distinct. To see that w_h+1, z_1,⋯ z_h+1 are distinct, we argue that in one execution of , w and z have C_z^i-2≠ C_w^i-2 but C_z^i-3= C_w^i-3, since if C_z^i-3≠ C_w^i-3, w would be in B_i-2 by the algorithm . Thus w_h+1, z_1,⋯ z_h+1 are in distinct components in ∖ (⋃_i=0^hB_i).



In the  algorithm,  returns either null or an augmenting sequence.


Assume a sequence of edges (w_1, z_1),⋯,(w_h+1,z_h+1) is returned by . Property (2) in Definition <ref> is proved by Lemma <ref>. Now let us focus on property (1). We can take an arbitrary w_0∈ρ_w_1, z_1∩ B_0 since C^0_w_1≠ C^0_z_1 by the algorithm. Also since w_i∈ B_i, ∀ 0≤ i≤ h, by Corollary <ref> we know ρ_w_i, z_i does not contain any w_j, 0≤ j≤ i-2, so property (2) holds.


The following statement concludes the  algorithm will terminate quickly.

In the  algorithm, h is increased by at least one during each repeat-loop, except the last one.


By the rules of , it is easy to see that at the beginning when  outputs B_0, B_1, ⋯, B_h, the shortest length of augmenting sequence is equal to h+1. So it suffices to prove that by the end of this iteration the shortest augmenting sequence has length >h+1.

First we need to characterize all augmenting sequences using B_0, B_1, ⋯, B_h. Let the sequence (w_1, z_1), (w_2, z_2), ⋯, (w_l, z_l) be an arbitrary augmenting sequence and let w_0 be the B_0-vertex on ρ_w_1, z_1. We argue that l≥ h+1, and more importantly, if l = h+1, it must be that w_i∈ B_i, ∀ 0≤ i≤ h. We inductively prove that w_i∈⋃_j=0^i B_j for i = 0, 1, ⋯, l-1. The basis is obvious as is required by property (1) in Definition <ref>. Now assume w_i∈ B_r for some r≤ i. Then, from algorithm , it would not be hard to see w_i+1∈⋃_j=0^r+1 B_j⊆⋃_j=0^i+1 B_j. Now, since components {C^r_u} for r≤ h-1 are not connected by edges whose both endpoints are unmarked by Lemma <ref>, so ρ_w_l, z_l∩⋃_j=0^h-1 B_j = ∅, and on the other hand w_l-1∈ρ_w_l, z_l∩⋃_j=0^l-1 B_j, so l≥ h+1. Plus, we can see from the induction that, when l = h+1 it must be that w_i∈ B_i, ∀ 0≤ i≤ h.

For any unmarked and adjacent vertices u, v such that C_u^h ≠ C_v^h, consider the instance of  with input (h+1,(u,v)). We make two claims.

	
  * If there is an (h+1)-length augmenting sequence ending with (u, v),  would succeed in finding one.
	
  * If it has returned null, then there would be no (h+1)-augmenting sequence ending with (u, v) throughout the entire repeat-loop iteration.
 

If (1), (2) can be proved, then by the end of this repeat-loop iteration, there would be no (h+1)-length augmenting sequences because such augmenting sequence should end with a pair of adjacent unmarked vertices. Next we come to prove (1), (2).


	
  * The depth-first search of  exactly coincides with the conditions that w_i∈ B_i, except that it skips all tagged vertices and edges. Now we prove that omitting tagged vertices and edges does not miss any (h+1)-length augmenting sequences. For an edge (w, z) to be tagged, either a further recursion  has succeeded or failed in finding an augmenting sequences; in the former case, C_w^i-2 and C_z^i-2 has been merged, and so the condition C_w^i-2≠ C_z^i-2 would be violated afterwards; in the latter case, we would not need to recur on (w, z) since the components w.r.t. B_0,⋯,B_i-2 also can only merge. For a vertex w to be tagged, we must have enumerated all of its untagged edges (w, z) but failed to find any augmenting sequences, and therefore any future depth-first searches on w would still end up in vain. 
	
	
  * If  has once failed to find any augmenting sequences starting with (u, v), then all vertices w∈ρ_u, v∩ B_h visited by this instance of  should be tagged and they would be omitted by all succeeding instances of . Therefore ρ_u, v∩ B_h would stay unchanged since then. 
	Hence, if we re-run  with h+1, (u, v), it will return null without any recursion because all vertices in ρ_u,v∩ B_h are tagged.



Suppose  has terminated with B_0, B_1, ⋯, B_⌈log_1+ϵn + 1⌉. We introduce the notion of a clean component, a sequence of disjoint vertex subsets, and apply Lemma <ref> to get the lower bound on .


After an instance of  has been executed, for any vertex u∈ V∖ (⋃_i=0^h B_i), an arbitrary component C_u^h, 0≤ h≤⌈log_1+ϵn + 1⌉ is called clean if all vertices in C_u^h are unmarked.



For any 0≤ h< ⌈log_1+ϵn + 1⌉, suppose ∖ (⋃_i=0^h B_i) has l clean components, then a lower bound holds that ≥l-1/∑_i=0^h+1|B_i|.


Since h<⌈log_1+ϵn + 1⌉, B_h is not the last one, so there is no edge connecting two unmarked vertices in different components of ∖ (⋃_i=0^h B_i). By Lemma <ref>, any edge that connects a clean components of ∖ (⋃_i=0^h B_i) outwards must be incident on a vertex in ⋃_i=0^h+1 B_i, so ⋃_i=0^h+1 B_i is a boundary set w.r.t. clean components. Therefore by Lemma <ref> we have ≥l-1/|⋃_i=0^h+1 B_i| = l-1/∑_i=0^h+1|B_i|





    There is an implementation of  that runs in O(1/ϵ^2mlog^2 n) time.



We discuss some implementation details of ,  and  separately, and analyse their contributions to the total running time in a single run of .


	
  * .
	
	For every instance of , computing the forest {C_u^h}_u∈ V∖ (⋃_i=0^hB_i) can be done in a single pass of breath-first search which takes O(m) time. Computing B_h+1, if necessary, is easily done by scanning the edge set E which also takes O(m) time. As the while-loop iterates for at most 1+log_1+ϵ n times, and due to Lemma <ref>  is invoked for at most 1+log_1+ϵ n times, the overall contribution of  is O(1/ϵ^2mlog^2 n).
	
	
  * .
	
	Excluding the contributions of  and , all  does is simply un-tagging all vertices and edges, scanning the edge set (u, v)∈ E and deciding if C_u^h ≠ C_v^h as well as modifying tree . As tree components only get merged and never split, we can use the union-find data structure <cit.> to support querying whether C_u^h ≠ C_v^h in O(α(n)) time. Every tree modification involves insertions and deletions of O(1/ϵlog n) edges, as well as merging O(1/ϵlog n) pairs of some tree components C_u^i. Using the link-cut tree, every edge insertion and deletion takes update time O(log n), and every component-merging takes time O(α(n)). Since every tree modification merges two components in ∖ S_k, there can be at most O(n) tree modifications throughout . Therefore, the overall contribution of tree modifications is O(1/ϵnlog^2 n). Hence, 's exclusive contributions to the total running time would be O(1/ϵmα(n)log n + 1/ϵnlog^2 n).
	
	
  * .
	
	Now we analyze the overall time complexity induced by  invoked on line-5 of . There are two technical issues to be resolved.
	
		
  * How to enumerate untagged vertices ∈ρ_u,v∩ B_i-1?
		
		For each u_i ∈ B_i, ∀ 0≤ i≤ h, assign u_i a weight of i; vertices that do not belong to any B_i have weight h+1. By Corollary <ref>, to enumerate vertices ∈ρ_u,v∩ B_i-1, it suffices to enumerate the lightest vertices on ρ_u,v, which can be done using a link-cut tree data structure <cit.> built on , each enumeration taking O(log n) amortized time. When a vertex gets tagged, we change its weight to h+1, and so future enumerations on ρ_u,v∩ B_i-1 may skip this tagged vertex.
		
		
  * How to enumerate unmarked z connected by an untagged edge (w, z) such that C_z^i-2≠ C_w^i-2?
		
		Each w decrementally maintains a list of all its neighbours. While we scan the list, if the next edge (w, z) satisfies both conditions that C_z^i-2≠ C_w^i-2 and z is unmarked, then the algorithm starts a new iteration and recur; either way we cross the edge (w, z) off the list. In this way, every edge appears for at most once. Thus the total time of this part is O(mα(n)); the additional α(n) factor comes from the union-find data structure that helps deciding if C_z^i-2≠ C_w^i-2.	
	
	
	Note that (a)'s running time is always dominated by (b)'s, then the overall complexity of  is O(mα(n) + 1/ϵnlog^2 n).


Summing up (1)(2)(3), the total running time is dominated by the time complexity of  which is O(1/ϵ^2mlog^2 n).






 §.§ Large-step phase and small-step phase


The large-step phase and small-step phase are described in the  algorithm <ref>. In the large-step phase, we deal with the case Δ≥10log^2 n/ϵ^3. It works by invoking  with an incremental parameters k from (1-2ϵ)Δ + 1 if d_k-1≤ 2d_k. Within each iteration, if  fails to reduce d_k by a factor of (1 - ϵ^2/2log n), then the algorithm reports a lower bound on  and returns  immediately. Otherwise, increase k by 1 and continue until d_k becomes 0. Since d_k+1≤ d_k, d_k will become 0 in at most O(log^2 n/ϵ^2) iterations. Once d_k = 0, Δ must have decreased and repeat the while-loop. (Note that by Lemma <ref>, Δ cannot increase during the whole algorithm.)

In the small-step phase, we only deal with 9log n/ϵ^2≤Δ < 10log^2 n/ϵ^3. Set c = 2(log_1+ϵn+2) and define a potential:

    ϕ() = ∑_i = Δ +1 - log n^Δ c^i· |N_i|

The small-step phase works by repeatedly selecting a degree k that maximizes c^k· |N_k| and then run  until Δ decreases. Similar with the large-step phase, if  fails to reduce d_k significantly, then the algorithm reports a lower bound on  and returns  immediately. Clearly k must be larger than Δ - log n.





 §.§ Running time

In the large-step phase, every iteration d_k shrinks by a factor of ≤ (1 - ϵ^2/2log n), so d_k will become zero in O(log^2 n/ϵ^2) iterations. We have:

	The running time of the large-step phase is bounded by O(1/ϵ^5mlog^5 n).


	From the previous subsection we already know that  runs in O(1/ϵ^2mlog^2 n) time, so here we only need to upper bound the total number of times  gets invoked before Δ < 10log^2 n/ϵ^3 or a spanning tree  is returned within a while-loop. Next we only focus on the previous cases because it takes a longer running time. In this case, at the end of each iteration, d_k ≤ (1-ϵ^2/2log n)· d. The inside while-loop would break when k > (1-2ϵ)Δ + 2log^2 n/ϵ^2 because by the time 
    d_k ≤(1-ϵ^2/2log n)^2log^2 n/ϵ^2· d_(1-2ϵ)Δ≤d_(1-2ϵ)Δ/n < 1
 
	As (1-2ϵ)Δ + 2log^2 n/ϵ^2≤ (1-ϵ)Δ when Δ≥10log^2 n/ϵ^3, which means Δ has been reduced by a factor of at most 1-ϵ in the end of each while-loop and there are at most O(1/ϵlog n) while-loops within the large-step phase. In summary, the total running time of the large-step phase is O(log^2 n/ϵ^2m ×log^2 n/ϵ^2×log n/ϵ) = O(m·log^5 n/ϵ^5).


In the small-step phase, every iteration ϕ() shrinks by a factor of ≤ 1 - ϵ^2/5log^2 n, after O(log^3 n/ϵ^2) rounds, ϕ() will be smaller than c^Δ.


	The running time of the small-step phase is bounded by O(1/ϵ^7mlog^7 n).



	We already know that  runs in O(1/ϵ^2mlog^2 n) time. Now we study how many rounds of  could be invoked before Δ changes or this algorithm returns  within a while-loop. We only focus on the previous cases because it takes a longer running time. For one execution of , let N^'_k, d^'_k, ^' (k∈ [Δ + 1-log n, Δ]) be snapshots of N_k,d_k, right before we execute , and here we consider the case when Δ is not changed and d_k ≤ (1-ϵ^2/2log n)· d^'_k.

	Next we analyse how ϕ() has decreased. The potential before the change is ϕ(^') = ∑_i=Δ+1-log n^Δ c^i· |N_k^'|. Every time  modified , at least one vertex in S_k lost a tree edge and at most 2+log_1+ϵ n vertices with degree <k-1 gained a tree edge, and then the total loss of ϕ() would be at least

    (c^k - c^k-1) - (2+log_1+ϵn)· (c^k-1 - c^k-2)≥ (c^k-1 - c^k-2)(c - 2-log_1+ϵn)
       = c^k·(1 - 1/c)·(1 - 2+log_1+ϵ n/c) ≥ c^k·(1 - 1/c)·1/2 > 0.4· c^k


	After executing , d_k has decreased by d_k^' - d_k≥ϵ^2/2log nd_k^'≥ϵ^2/2log n· k|N_k^'|. For each tree modification via Lemma <ref>, at most two vertices in S_k lost one degree (only removing the edge connected to w_0 affects S_k), which makes d_k decreased by at most 2k. So there are at least (d_k^' - d_k) / (2k) ≥ϵ^2/4log n· |N_k^'| tree modifications via Lemma <ref> to . Therefore, 
    ϕ()≤ϕ(^') - (0.4· c^k)·(ϵ^2/4log n· |N_k^'|)≤(1-0.1ϵ^2/log^2 n)ϕ(^')
 The second inequality holds by maximality of c^k· |N_k^'| which implies c^k· |N_k^'|≥1/log n·ϕ(^').

	In a nutshell, ϕ() has decreased by a factor of at most 1 - 0.1ϵ^2/log^2 n. As long as Δ has not changed, ϕ() belongs to the interval (c^Δ, n· c^Δ), and consequently, ϕ() could suffer at most -log_1 - 0.1ϵ^2/log^2 nn = O(log^3 n/ϵ^2) rounds of  before Δ decreases. There are at most O(log^2 n/ϵ^3) while-loops in the small-step phase because each while-loop reduces Δ by at least 1.

	In summary, the total running time of the small-step phase is O(log^2 n/ϵ^2m ×log^3 n/ϵ^2×log^2 n/ϵ^3) = O(m·log^7 n/ϵ^7)




 §.§ Approximation guarantee


When a spanning tree  is returned within the large-step phase or the small-step phase, the vertex subsets B_0,B_1,⋯,B_⌈ 1+log_1+ϵ n⌉ created by  satisfies the blocking property (see Lemma <ref>). By Lemma <ref>, there is a lower bound on  for each vertex set B_h, 0≤ h< ⌈ 1+log_1+ϵ n⌉ as long as we get the lower bound on the number of clean components in ∖ (⋃_i=0^h B_i). The following two statements show the lower bound on .


For any vertex subset B and any spanning tree , the number of connected components in ∖ B is at least ∑_u∈ B(u) - 2|B| + 2.


Note that there are at least ∑_u∈ B(u) - |B| + 1 tree edges incident on B, and so removing all of these edges would break  into ≥∑_u∈ B(u) - |B| + 2 components. Therefore, excluding singleton components formed by B, there are ≥∑_u∈ B(u) - 2|B| + 2 components from ∖ B. 



If a spanning tree  is returned within the large-step phase or the small-step phase and k is the parameter of the last invoked , for any 0≤ h < ⌈ 1+log_1+ϵ n⌉, the number of clean components in ∖ (⋃_i=0^h B_i) is at least k·(1 - 4ϵ)∑_i=0^h |B_i| + 1 for ϵ∈ (0, 1/48). Furthermore,

    ≥ k(1-4ϵ)·∑_i=0^h |B_i|/∑_i=0^h+1 |B_i|



	By Lemma <ref>, the number of tree components in ∖ (⋃_i=0^h B_i) is at least 
    ∑_u∈⋃_i=0^h B_i(u) - 2|⋃_i=0^h B_i| + 2

	Let d_k^', d_k-1^', S_k-1^' and S_k^' be snapshots of d_k, d_k-1, S_k-1 and S_k right before the last instance of  started and let M be the set of all marked vertices ∉ S_k-1^' (i.e., vertices that are initially unmarked) by the end of . Then, the number of clean components in ∖ (⋃_i=0^h B_i) is at least
	
    ∑_u∈⋃_i=0^h B_i(u) - 2∑_i=0^h |B_i| + 2 - |M∪ S_k-1^'|

	
	The argument consists of a lower bound on ∑_u∈⋃_i=0^h B_i(u) and an upper bound on |M∪ S_k-1^'|. 
	
	
		
  * Lower bound on ∑_u∈⋃_i=0^h B_i(u).
		
		By the  algorithm B_0 = S_k, then we have ∑_u∈ B_0(u) = d_k.
	
		For any vertex u∈⋃_i=1^h B_i, deg(u) = k-1 by the time u was first added to some B_i. After that, (u) could only decrease when we modify  by an augmenting sequence (w_1,z_1),⋯,(w_t,z_t) where u=w_j for some 1≤ j≤ t. Since t ≤⌈ 1+log_1+ϵ n⌉, during a tree modification, at least one vertex in S_k loses one degree and at most ⌈ 1+log_1+ϵ n⌉ vertices in ⋃_i=1^h B_i lose one degree separately. As the total number of the degree loss in S_k is (d_k^' - d_k), we have
	
		
    ∑_u∈⋃_i=1^h B_i(u)≥ (k-1)∑_i=1^h |B_i| - (d_k^' - d_k)⌈ 1 + log_1+ϵ n ⌉

	
		Since d_k > (1 - ϵ^2/2log n)· d_k^', we get a lower bound on ∑_u∈⋃_i=0^h B_i(u),
	
		
    ∑_u∈⋃_i=0^h B_i(u)    ≥ d_k + (k-1)∑_i=1^h |B_i| - (d_k^' - d_k)⌈ 1 + log_1+ϵ n ⌉
       ≥ (k-1)∑_i=1^h |B_i| + (1 - ϵ^2/2log n)d_k^' - ϵ^2/2log n(2+ log_1+ϵ n) d_k^'
       ≥ (k-1)∑_i=1^h |B_i| + (1 - 3ϵ^2/2log n- ϵ/2)d_k^'

		
		
  * Upper bound on |M|.
		
		The argument is similar to (1). An unmarked vertex u is marked only when we modify  by an augmenting sequence (w_1,z_1),⋯,(w_t,z_t) where u=z_j for some 1≤ j≤ t or u=w_t. Since t ≤ 1+log_1+ϵ n, during a tree modification, at least one vertex in S_k loses one degree and at most 2+log_1+ϵ n unmarked vertices are marked. Then we get a upper bound on |M|.
		
		
    |M| ≤ (d_k^' - d_k)(2 + log_1+ϵ n) ≤ϵ· d_k^'

		
		
  * Upper bound on |S_k-1^'|.

		First we claim d_k^'/d_k-1^'≥1/ϵ(k-1) when k≥9log n/ϵ^2 - log n ≥8log n/ϵ^2 and n > 2^ϵ. In the large-step phase, the inequality holds since d_k^'≥1/2 d_k-1^'. In the small-step phase, by maximality of c^k· |N_k|, we have |N_k|≥1/c· |N_k-1|. Then, 
    d_k^'/d_k-1^' = ∑_i=k^Δ i|N_i|/∑_i=k-1^Δ i|N_i| > k|N_k|/k|N_k| + (k-1)|N_k-1|≥1/1 + c(k-1)/k > 1/c+1≥1/ϵ(k-1)

		The last inequality holds by c = 2log_1+ϵ n + 4 ≤2ln 2/ϵlog n + 4, k·ϵ≥8log n/ϵ and ϵ<log n≤log n/ϵ. Then we have the upper bound on |S_k-1^'|:
		
    |S_k-1^'| ≤d_k-1^'/k-1≤ϵ· d_k^'

	
	
	Summing up (1), (2), (3), for n > 2 and ϵ∈ (0,1/48), k≥9log n/ϵ^2 - log n, we have
	
    ∑_u∈⋃_i=0^h B_i(u) - 2∑_i=0^h |B_i| + 2 - |M∪ S_k-1^'|
       ≥(1-3ϵ^2/2log n -2.5ϵ)· d_k^'  + (k-1)∑_i=1^h |B_i| - 2∑_i=0^h |B_i| + 2
       ≥(1-2.6ϵ)· k|B_0|  - 2|B_0| + (k-3)∑_i=1^h |B_i| + 2
       ≥ k(1-4ϵ)·∑_i=0^h |B_i| +2

	We apply Lemma <ref>, and conclude the proof
	
    ≥k(1-4ϵ)·∑_i=0^h |B_i| + 1/∑_i=0^h+1 |B_i|≥ k(1-4ϵ)·∑_i=0^h |B_i|/∑_i=0^h+1 |B_i|



In the following two statements, we combine all the inequalities for each B_h and get the upper bound on Δ with  in both the large-step phase and the small-step phase.


	When a spanning tree  is returned within the large-step phase, it must be that Δ≤ (1+8ϵ)· for ϵ∈ (0, 1/48).


	Consider the most recent execution of  before returning. By the previous subsection, this instance of  has created a sequence of disjoint vertex subsets B_0, B_1, ⋯, B_1+log_1+ϵ n that satisfy the blocking property. By the pigeon-hole principle, there exists an h such that ∑_i=0^h |B_i|/∑_i=0^h+1 |B_i|≥1/1+ϵ. Then by Lemma <ref>, (recall that in the large-step phase k>(1-2ϵ)Δ)
	
    ≥ k(1-4ϵ)·1/1+ϵ > 1-6ϵ + 8ϵ^2/1+ϵΔ

	or equivalently, Δ≤1+ϵ/1-6ϵ + 8ϵ^2 < (1+8ϵ) when ϵ∈ (0, 1/48).



	When a spanning tree  is returned within the small-step phase, it must be that Δ≤ (1+6ϵ) + log n for ϵ∈ (0, 1/48).


	Consider the most recent execution of  before returning. By the previous subsection, this instance of  has created a sequence of disjoint vertex subsets B_0, B_1, ⋯, B_1+log_1+ϵ n that satisfies the blocking property. By the pigeon-hole principle, there exists an h such that ∑_i=0^h |B_i|/∑_i=0^h+1 |B_i|≥1/1+ϵ. Then by Lemma <ref>, (recall that in the small-step phase, k>Δ-log n))
	 
    ≥ k(1-4ϵ)·1/1+ϵ > 1-4ϵ/1+ϵ(Δ - log n)
 or equivalently, Δ≤1+ϵ/1-4ϵ + log n < (1+6ϵ) + log n for ϵ∈ (0, 1/48).


Now we can finish the proof of Theorem <ref>


	We claim that, for any constant ϵ∈ (0, 1/6), the  algorithm computes a spanning tree with tree degree at most (1+ϵ) + 576/ϵ^2log n in O(1/ϵ^7mlog^7 n) time (by resetting ϵ→ 8ϵ' where ϵ' is the ϵ in previous analysis).

	By Lemma <ref> and Lemma <ref>, we know the total running time of the  algorithm is bounded by O(1/ϵ^7mlog^7 n). The degree analysis is divided into three cases:
	
		
  * If  is returned after the small-step phase, then Δ < 576/ϵ^2log n for ϵ∈ (0, 1/6).

		
  * If  is returned during the large-step phase, by Lemma <ref>, Δ≤ (1 + ϵ)· for ϵ∈ (0, 1/6).

		
  * If  is returned during the small-step phase, by Lemma <ref>, Δ≤ (1+ 3ϵ/4) + log n for ϵ∈ (0, 1/6).
	

	In summary, the  algorithm computes a spanning tree with tree degree (1+ϵ) + 576/ϵ^2log n in O(1/ϵ^7mlog^7 n) time.










