The Heterogeneous Rooted Tree Cover Problem

Abstract

We consider the heterogeneous rooted tree cover (HRTC) problem. Concretely, given an undirected complete graph $G=(V,E)$ with a root $r\in V$, an edge-weight function $w:E\rightarrow R^{+}$ satisfying the triangle inequality, a vertex-weight function $f:V{\setminus }\{r\}\rightarrow R^{+}_{0}$, and k construction teams having nonuniform construction speeds $\lambda _{1}$, $\lambda _{2}$, $\ldots$, $\lambda _{k}$, we are asked to find k trees for these k construction teams to cover all vertices in V, each tree starting at the same root r, i.e., k trees having a sole common vertex called root r, the objective is to minimize the maximum completion time, where the completion time of each team is the total construction weight of its related tree divided by its construction speed.

    In this paper, we first design a $58.3286(1+\delta )$-approximation algorithm to solve the HRTC problem in time $O(n^{3}(1+\frac{1}{\delta })+\log (w(E)+f(V\backslash \{r\})))$ for any $\delta >0$. In addition, we present a $\max \{2\rho , 2+\rho -\frac{2}{k}\}$-approximation algorithm for resolving the HRTC problem in time $O(n^{2})$, where $\rho$ is the ratio between the maximum and minimum speed of these k teams.

This paper is supported by the National Natural Science Foundation of China [Nos. 12361066, 12101593]. Junran Lichen is also supported by Fundamental Research Funds for the Central Universities [No.buctrc202219], and Jianping Li is also supported by Project of Yunling Scholars Training of Yunnan Province [No. K264202011820].

1 Introduction

The subgraph cover problems, including the cycle cover problem and the tree cover problem, form a much-studied family of combinatorial optimization problems. These problems have wide range of practical applications, such as routings of multi-vehicles [2, 7, 12], nurse station location [4] and data gathering in wireless sensor networks [13, 15]. In some applications, the minimization of the latest service completion time at the service locations is more relevant. As a result, there is a growing body of literature on cover problems under the min-max objective.

Considering the vehicles to have nonuniform speeds in routing planning, Gørtz et al. [8] in 2016 proposed the heterogeneous traveling salesman problem, which we refer to as the heterogeneous rooted cycle cover (HRCC) problem. In the HRCC problem, given a complete graph $G=(V, E)$ equipped with an edge-weight function $w:E\rightarrow R^{+}$ that satisfies the triangle inequality, a root $r\in V$ and k vehicles with nonuniform speeds $\lambda _{1}$, $\lambda _{2}$, $\ldots$, $\lambda _{k}$, we are asked to find k cycles for these k vehicles to cover all vertices in V, each vehicle starting at r, i.e., these k cycles having a sole common vertex r, the objective is to minimize the maximum completion time, where the completion time of a vehicle is the total weight of its related cycle divided by its speed. For the HRCC problem, Gørtz et al. [8] in 2016 presented a constant factor approximation algorithm.

The rooted cycle cover (RCC) problem [6], also called the k-traveling salesman problem, which is an important special version of the HRCC problem, where $\lambda _{i}=1$ for each $i\in \{1,2,\ldots ,k\}$. Employing a splitting strategy, Frederickson et al. [6] in 1978 gave a ($\frac{5}{2}-\frac{1}{k}$)-approximation algorithm to solve the RCC problem. For the version $k=1$ of the RCC problem, i.e., the metric traveling salesman problem, Christofides [3] provided a famous 3/2-approximation algorithm by using an algorithm for solving the Euler tour problem.

In addition, many researches focus on the tree cover problems of graphs, in which vertices are all covered by a set of k trees. Taking the service handling times of vertices into consideration, Nagamochi [10] proposed the rooted tree cover (RTC) problem, which is modelled as follows. Given a complete graph $G=(V, E)$ equipped with an edge-weight function $w:E\rightarrow R^{+}$ satisfying the triangle inequality, a vertex-weight function $f:V{\setminus }\{r\}\rightarrow R^{+}_{0}$, a root $r\in V$ and k construction teams, it is asked to find k trees for these k teams to cover all vertices in V, each tree starting at the same root r, the objective is to minimize the maximum total weight among these k trees, where the total weight of a tree is the summation of edge weights and vertex weights in that tree, equivalently, the objective is to minimize the maximum completion time, where the completion time of a construction team is the total construction weight of that tree divided by its speed for the case that speeds of these k teams are all same one.

The RTC problem is NP-hard [1] even for the case $k=2$ and $f(\cdot )\equiv 0$. Many research papers have been focused on the development of constant factor approximation algorithms to resolve the RTC problem. Using a tree partition technique, Nagamochi [10] in 2005 presented a $(3-\frac{2}{k+1})$-approximation algorithm to resolve the RTC problem. Xu and Wen [14] in 2010 gave a lower bound of 10/9 for the RTC problem. Moreover, the other relevant results can be found in [5, 9, 11, 16].

In practice, the construction efficiencies or construction speeds of multiple construction teams are often different similar to the vehicle speeds of the HRCC problem. Motivated by the observation and the RTC problem, we address the heterogeneous rooted tree cover (HRTC) problem. Concretely, given an undirected complete graph $G=(V,E;w,f)$ with a root $r\in V$, an edge-weight function $w:E\rightarrow R^{+}$ satisfying the triangle inequality, a vertex-weight function $f:V{\setminus }\{r\}\rightarrow R^{+}_{0}$, and k construction teams having nonuniform construction speeds $\lambda _{1}$, $\lambda _{2}$, $\ldots$, $\lambda _{k}$, we are asked to find k trees $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ for these k construction teams to cover all vertices in V, each starting at the same root r, i.e., k trees having a sole common vertex called root r, the objective is to minimize the maximum completion time, where the completion time of each team is the total construction weight of its related tree divided by its construction speed. In a formulaic way, the min-max objective is written as $\min _\mathcal{T}\max \{\frac{w(T_{i})+f(T_{i})}{\lambda _{i}}~|~i=1,2,\ldots ,k\}$.

As far as what we have known, the HRTC problem has not been considered in the literature. The aforementioned HRCC problem (without vertex weights) has been studied in [8], but we cannot directly use the algorithms for the HRCC problem to solve the HRTC problem, because the HRTC problem includes the vertex weights. However, modifying the technique in [8], we intend to design first approximation algorithm with constant approximation ratio to solve the HRTC problem. In addition, we shall present second approximation algorithm with lower time complexity to resolve the HRTC problem.

The remainder of this paper is organized as follows. In Sect. 2, we present some terminologies and fundamental lemmas to state descriptions of approximation algorithms; In Sect. 3, we design first constant factor approximation algorithm to solve the HRTC problem; In Sect. 4, we design second approximation algorithm with lower time complexity to resolve the HRTC problem; In Sect. 5, we provide our conclusion and further research.

2 Terminologies and Fundamental Lemmas

All graphs considered in the paper are assumed to be finite, undirected and loopless. Given a graph $G=(V,E)$, to contract a vertex subset $V'\subseteq V$ is to replace these vertices by a single vertex incident to all the edges which were incident in G to any vertex in $V'$. The resulting graph is denoted by $G/V'$ with vertex set $V\cup \{v'\}\backslash V'$ and edge set $E\cup \{uv'~|~uv\in E, u\in V{\setminus } V', v\in V'\}\backslash E(G[V'])$, where $v'$ is viewed as a new vertex obtained by contracting the vertex subset $V'$. For a vertex set V and a set $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ of trees (or cycles), if $V\subseteq \bigcup _{i=1}^{k}V(T_{i})$, we say that $\mathcal{T}$ covers V.

For any two sets $X_{1}$ and $X_{2}$, $X_{1}+ X_{2}$ is a multiset obtained by adding all elements in $X_{1}\cap X_{2}$ to $X_{1}\cup X_{2}$. Especially, for any two graphs $G=(V, E)$ and $G'=(V', E')$, denote $G\cup G'=(V\cup V', E\cup E')$ and $G+ G'=(V\cup V', E+ E')$, respectively.

In designing a constant factor approximation algorithm for the HRTC problem, we need the following definition, which is obtained by slightly modifying the definition in [8].

Definition 1

Given an undirected graph $G=(V,E;w,f)$ with two constants $M>0$ and $\varepsilon >0$, where $w:E\rightarrow R^{+}$ is an edge-weight function and $f:V{\setminus }\{r\}\rightarrow R^{+}_{0}$ is a vertex-weight function, let $\mathcal{F}_{i}$ be a set of trees in G starting at the same vertex r for each integer $i\ge 0$. Then the collection $\{\mathcal{F}_{i}\}_{i\ge 0}=\bigcup _{i\ge 0}\mathcal{F}_{i}$ is referred to as $(\alpha ,\beta )_{M,\varepsilon }$-assignable, if it has the following properties

• (1)  $w(F)+f(F)\le \alpha \cdot (1+\varepsilon )^{i}M$, for each tree $F\in \mathcal{F}_{i}$, $i\ge 0$;

• (2)  $\sum _{j\ge i}(w(\mathcal{F}_{i})+f(\mathcal{F}_{i}))\le \beta M\cdot \varLambda ((1+\varepsilon )^{i-1})$ for each $i\ge 0$, where $\varLambda ((1+\varepsilon )^{i-1})$ is the sum of speeds that at least $(1+\varepsilon )^{i-1}$.

For Definition 1, we can regard the sum of edge weights and vertex weights of each tree as a whole weight, and using the ASSIGN algorithm in Gørtz et al. [8], we can obtain the following important result.

Lemma 1

[8] Given an $(\alpha ,\beta )_{M,\varepsilon }$-assignable collection $\{\mathcal{F}_{i}\}_{i\ge 0}$ of trees starting at r, we can use the ASSIGN algorithm to assign all trees in $\{\mathcal{F}_{i}\}_{i\ge 0}$ to k construction teams in time $O(n^{3}+\log (w(E)+f(V\backslash \{r\})))$, satisfying that the completion time of each construction team is at most $((1+\varepsilon )\alpha +\beta )M$, where the completion time of each team is the total construction weight divided by its construction speed, n is the number of vertices.

3 An Approximation Algorithm with Constant Approximation Ratio

In this section, we consider the heterogeneous rooted tree cover (HRTC) problem. Without loss of generality, we may assume that the considered graph are all connected and $2\le k\le n-1$.

By Lemma 1, we design the following strategies to solve the HRTC problem.

• (1) Find an $(\alpha ,\beta )_{M,\varepsilon }$-assignable collection of subtrees to cover all vertices;

• (2) Assign subtrees in the above collection to k construction teams to minimize the completion time of any team.

Given an undirected graph $G=(V, E;w,f)$ with two current values M and $\varepsilon$ (the precise value to be chosen later), we first give a partition of V that is $\{V_{0},V_{1},\cdots \}$, where $V_{0}=\{v\in V~|~ w(rv)+f(v)\le M\}$, and $V_{i}=\{v\in V~|~ (1+\varepsilon )^{i-1}M< w(rv)+f(v)\le (1+\varepsilon )^{i}M\}$ for each $i\ge 1$. For each $i\ge 0$, let $V_{\le i}=\bigcup _{j\le i}V_{j}$ and $V_{\ge i}=\bigcup _{j\ge i}V_{j}$. Similarly, we give a partition of E that is $\{E_{0}, E_{1},\cdots \}$, where $E_{i}=\{uv\in E~|~ u\in V_{\le i}, v\in V_{i}\}$ for each $i\ge 0$. For each $i\ge 0$, let $E_{\le i}=\bigcup _{j\le i}E_{j}$ and $E_{\ge i}=\bigcup _{j\ge i}E_{j}$.

Now, analyzing the lower bound of the HRTC problem, we obtain the following lemma.

Lemma 2

Given a complete graph $G=(V,E;w,f)$ as an instance of the HRTC problem, for any constant $M\ge OPT$, we have $w(T^{MS}_{G/V_{<l}})+f(V_{\ge l})\le M\cdot \varLambda ((1+\varepsilon )^{l-1})$ for each integer $l\ge 0$, where OPT is the optimal value to the given instance, $T^{MS}_{G/V_{<l}}$ is a minimum edge-weight spanning tree of $G/V_{<l}$, i.e., a new graph obtained by contracting a vertex set $V_{<l}$, and $\varLambda ((1+\varepsilon )^{l-1})$ is the total of speeds that exceed $(1+\varepsilon )^{l-1}$.

Proof. Consider that in an optimal solution to G for the HRTC problem, if any vertex $v\in V_{\ge l}$ can be constructed by a construction team with speed $\lambda '$, then we have $\lambda '> (1+\varepsilon )^{l-1}$. This is because $w(rv)+f(v)> (1+\varepsilon )^{l-1}M$ holds for each $v\in V_{\ge l}$, and the construction weight of a construction team with speed $\lambda '$ is at most $\lambda '\cdot OPT\le \lambda '\cdot M$, implying $\lambda '\cdot M \ge \lambda '\cdot OPT> (1+\varepsilon )^{l-1}M$. Since $\max \{w(rv)+f(v), w(rv')+f(v')\}> (1+\varepsilon )^{l-1}M$ holds for each edge $e=vv'\in E_{\ge l}$, we deduce that any edge in $E_{\ge l}$ must be constructed by some team with speed exceed $(1+\varepsilon )^{l-1}$.

Let $E^{*}$ denote the set of edges constructed by teams in the optimal solution. By the above arguments, we have $w(E^{*}\cap E_{\ge l})+f(V_{\ge l})\le OPT\cdot \varLambda ((1+\varepsilon )^{l-1})\le M\cdot \varLambda ((1+\varepsilon )^{l-1})$, meaning $w(E^{*}\cap E_{\ge l})+f(V_{\ge l})\le M\cdot \varLambda ((1+\varepsilon )^{l-1})$. Clearly, $G[E^{*}]$ is a spanning tree of G, and $E^{*}\cap E_{\ge l}$ corresponds to a spanning tree of $G/V_{<l}$. Since $T^{MS}_{G/V_{<l}}$ is a minimum edge-weight spanning tree of $G/V_{<l}$, we obtain $w(T^{MS}_{G/V_{<l}})+f(V_{\ge l})\le w(E^{*}\cap E_{\ge l})+f(V_{\ge l})$, implying $w(T^{MS}_{G/V_{<l}})+f(V_{\ge l})\le M\cdot \varLambda ((1+\varepsilon )^{l-1})$.    $\square$

For each $i\ge 0$, let $H_{i}$ denote the edge subset of G corresponding to a minimum spanning tree of $G[V_{\le i}]/V_{< i}$. Obviously, $G[\mathcal{H}]$ with $\mathcal{H}=\bigcup _{i\ge 0}H_{i}$ is a spanning tree of G. Using the similar arguments in [8] to analyze the relation between $\mathcal{H}$ and a minimum edge-weight spanning tree of G, we obtain a result as follows.

Lemma 3

[8] Given a complete graph $G=(V,E;w,f)$ and a constant $\varepsilon >0$, a spanning tree $G[\mathcal{H}]$ with $\mathcal{H}=\bigcup _{i\ge 0}H_{i}$ of G can be constructed to satisfy:

• The vertex levels along every root-leaf path are nondecreasing.

• For each $i\ge 0$, we have $\sum _{j\ge i}w(H_{j})\le (6+\frac{6}{\varepsilon })\cdot w(T^{MS}_{G/V_{<i}})$, where $T^{MS}_{G/V_{<i}}$ is a minimum edge-weight spanning tree of $G/V_{< i}$.

In Lemma 3, for each $i\ge 0$, it is clear that $\sum _{j\ge i}w(H_{j})\le (6+\frac{6}{\varepsilon })\cdot w(T^{MS}_{G/V_{<i}})$ means $\sum _{j\ge i}(w(H_{j})+f(V_{j}))\le (6+\frac{6}{\varepsilon })\cdot w(T^{MS}_{G/V_{<i}})+f(V_{\ge i})\le (6+\frac{6}{\varepsilon })\cdot (w(T^{MS}_{G/V_{<i}})+f(V_{\ge i}))$. By Lemma 2, we obtain at once that $\sum _{j\ge i}(w(H_{j})+f(V_{j}))\le (6+\frac{6}{\varepsilon })\cdot (w(T^{MS}_{G/V_{<i}})+f(V_{\ge i}))\le (6+\frac{6}{\varepsilon })\cdot M\cdot \varLambda ((1+\varepsilon )^{i-1})$, which is stated in the following

Lemma 4

Given a complete graph $G=(V,E;w,f)$ with two constants $\varepsilon >0$ and $M\ge OPT$, where OPT is the optimal value to the instance G for the HRTC problem, then the spanning tree $G[\mathcal{H}]$ with $\mathcal{H}=\bigcup _{i\ge 0}H_{i}$ of G mentioned-above satisfies:

• The vertex levels along every root-leaf path are nondecreasing.

• For each $i\ge 0$, we have $\sum _{j\ge i}(w(H_{j})+f(V_{j}))\le (6+\frac{6}{\varepsilon })\cdot M\cdot \varLambda ((1+\varepsilon )^{i-1})$.

To shorten notation, given each edge $e=uv$ in $\mathcal{H}$, denote $x_{e}\in \{u,v\}$ to be a vertex farther away from r in $G[\mathcal{H}]$, and $y_{e}\in \{u,v\}$ to be a vertex closer to r in $G[\mathcal{H}]$. For each subtree $G'=(V',E')$ of $G[\mathcal{H}]$ mentioned above, we define a new function $f_{1}(\cdot )$ to be $f_{1}(G')=\sum _{e\in E'}f_{1}(x_{e})$, implying $f_{1}(G')=f(G')-f(y_{G'})$, where $y_{G'}$ is a vertex in $G[\mathcal{H}]$ closest to r.

Basing from Lemma 1 to Lemma 4, we design a following algorithm, denoted by the algorithm HRTC$_{1}$, to solve the HRTC problem.

• Algorithm: HRTC$_{1}$

• Input: An undirected complete graph $G=(V, E;w, f)$ with a root $r\in V$, an edge-weight function $w: E\rightarrow R^{+}$, a vertex-weight function $f:V{\setminus } \{r\}\rightarrow R^{+}_{0}$, k construction teams having speeds $\lambda _{1},\ldots ,\lambda _{k}$ respectively, a small fixed constant $\delta >0$, and two constants $\zeta =2$ and $\varepsilon =1.3146$ (to be chosen in Theorem 1);

• Output: A set $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ of k trees.

• Begin

• Step 1 Set $M=\max _{v\in V}\{\frac{w(r,v)+f(v)}{\lambda _{\max }}\}$, where $\lambda _{\max }=\max \{\lambda _{i}~|~i=1,2,\ldots ,k\}$;

• Step 2 Using M and $\varepsilon$, we can partition the set V into subsets $V_{0},V_{1},\ldots$, and the set E into subsets $E_{0},E_{1},\ldots$ as mentioned-above; For convenience, we may actually assume that the number of subsets partitioned is t, i.e., $(1+\varepsilon )^{t-1}M< \max \{w(rv)+f(v)~|~v\in V\}\le (1+\varepsilon )^{t}M$;

• Step 3 If ($w(T^{MS}_{G/V_{<l}})+f(V_{\ge l})> M\cdot \varLambda ((1+\varepsilon )^{l-1})$ holds for some $l\in \{1,2,\ldots ,t\}$) then      set $M:=(1+\delta )M$, and go to Step 2;

• Step 4 Construct a spanning tree $G[\mathcal{H}]$ with $\mathcal{H}=\bigcup _{i\ge 0}H_{i}$ of G, where $H_{i}$ is the edge subset of G corresponding to a minimum edge-weight spanning tree of $G[V_{\le i}]/V_{< i}$; Set $\mathcal{S}_{0}:=\{H_{0}\}$;

• Step 5 For each $i\in \{1,2,\ldots ,t\}$, partition $H_{i}$ into a set $\mathcal{S}_{i}$ of subtrees such that each subtree $\eta \in \mathcal{S}_{i}$ contains exactly one edge $h(\eta )$ from $V_{<i}$ to $V_{i}$; Let $\gamma =\frac{\varepsilon }{(2+\varepsilon )(1+\varepsilon )}$ and $\mathcal{S}_{0}^{m}=\mathcal{S}_{0}$; For each $i\in \{1,2,\ldots ,t\}$, set $\mathcal{S}_{i}^{m}=\emptyset$ and $\mathcal{S}_{i}^{u}=\emptyset$;

• Step 6 For all $i\in \{1,2,\ldots ,t\}, \eta \in \mathcal{S}_{i}$ do:      If ($w(\eta )+f_{1}(\eta )\ge \gamma \cdot (1+\varepsilon )^{i}M$) then        Set $\mathcal{S}_{i}^{m}:=\mathcal{S}_{i}^{m}\cup \{\eta \}$;      Else        Set $\mathcal{S}_{i}^{u}:=\mathcal{S}_{i}^{u}\cup \{\eta \}$;

• Step 7 For all $i\in \{1,2,\ldots ,t\}, \sigma \in \mathcal{S}_{i}^{u}$ do:      Determine a subtree $\pi (\sigma )$ in $\bigcup _{j<i}\mathcal{S}_{j}$, having $\pi (\sigma )\cap \sigma \ne \emptyset$;

• Step 8 For all $i\in \{0,1,2,\ldots ,t\}, \tau \in \mathcal{S}_{i}^{m}$ do:      (8.1) Set $\textrm{Dangle}(\tau )=\{\sigma \in \mathcal{S}_{i+1}^{u}: \pi (\sigma )=\tau \}$;      (8.2) If the total weight of $(\tau {\setminus } h(\tau ))\cup \textrm{Dangle}(\tau )$ is at most $\zeta (1+\varepsilon )^{i+1}M$, then set $q=1$ and $F'_{1}= (\tau {\setminus } h(\tau ))\cup \textrm{Dangle}(\tau )$, and go to Step (8.5);      (8.3) Find an Euler tour in the multigraph $((\tau {\setminus } h(\tau ))\cup \textrm{Dangle}(\tau ))+((\tau {\setminus } h(\tau ))\cup \textrm{Dangle}(\tau ))$, and transform the tour to a cycle by “short-cutting” previously visited vertices;      (8.4) Split the resulting cycle into maximal paths of total weight, including edge weights and vertex weights, at most $\zeta (1+\varepsilon )^{i+1}M$ each, denoted by $F'_{1},F'_{2},\ldots ,F'_{q}$;      (8.5) For each $j\in \{1,\ldots ,q\}$, augment $F'_{j}$ by adding an edge from r to the vertex in $F'_{j}$ closest to r, to obtain a set of subtrees starting at r, denoted by $\mathcal{F}_{i}(\tau )=\{F_{1}, F_{2}, \ldots , F_{q}\}$;

• Step 9 For each $i\in \{0,1,\ldots ,t\}$, set $\mathcal{F}_{i}=\bigcup _{\tau \in \mathcal{S}_{i}^{m}}\mathcal{F}_{i}(\tau )$; Using the ASSIGN algorithm, combine the set $\{\mathcal{F}_{i}\}_{i\ge 0}=\bigcup _{i\ge 0}\mathcal{F}_{i}$ into k trees $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ corresponding to k construction teams;

• Step 10 Output k trees $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ corresponding to k teams.

• End

Using Step 4, we obtain that each connected component of the subgraph in G corresponding to $H_{i}$ ($i\ge 1$) is a subtree. Note that such a subtree contains at least one edge from $V_{<i}$ to $V_{i}$, it follows that the partition at Step 5 is indeed executed.

Using Steps 6–7 in the algorithm HRTC$_{1}$, we can obtain the following

Lemma 5

For any $i\ge 1$ and $\sigma \in \mathcal {S}_{i}^{u}$, there exists $\pi (\sigma )\in \mathcal{S}_{i-1}$. Moreover, $\pi (\sigma )\in \mathcal{S}_{i-1}^{m}$.

Proof. For an $\sigma \in \mathcal {S}_{i}^{u}$, it is clear that $w(h(\sigma ))+f_{1}(h(\sigma ))\le w(\sigma )+f_{1}(\sigma )< \gamma \cdot (1+\varepsilon )^{i}M$. By the definition of $\mathcal{S}_{i}^{u}$, we have $v\in V_{\le i}$ for every $v\in V(\sigma )$. Let $h(\sigma )=yx$, where $y\in \pi (\sigma )$ and $x\in V_{i}$. Moreover, we deduce that $y\in V_{i-1}$. Otherwise, we assume $x\in V_{i}$ and $y\in V_{<i-1}$, it follows that $w(\sigma )+f_{1}(\sigma )\ge w(yx)+f(x)\ge w(rx)+f(x)-(w(ry)+f(y))> (1+\varepsilon )^{i-1}M-(1+\varepsilon )^{i-2}M> \gamma \cdot (1+\varepsilon )^{i}M$, which contradicts $\sigma \in \mathcal{S}_{i}^{u}$. Thus, we obtain $y\in V_{i-1}$, implying $\pi (\sigma )\in \mathcal{S}_{i-1}$.

For the second part of the lemma, if $i=1$, then clearly $\pi (\sigma )=\mathcal{S}_{0}$ and $\pi (\sigma )\in \mathcal{S}_{0}^{m}$. When $i\ge 2$, from the above arguments, we have $\pi (\sigma )\in \mathcal{S}_{i-1}$. Similar to the above arguments, since G is connected, we conclude that there is a vertex $z\in \pi (\sigma )$ satisfying $z\in V_{<i-1}$. Using the triangle inequality twice, we have the following

$$w(zy)+f(y)+w(yx)+f(x)\ge w(zx)+f(x)\ge w(rx)+f(x)-(w(rz)+f(z)).$$

Since $x\in V_{i}$ and $z\in V_{<i-1}$, we obtain $w(rx)+f(x)-(w(rz)+f(z))> (1+\varepsilon )^{i-1}M-(1+\varepsilon )^{i-2}M= \varepsilon (1+\varepsilon )^{i-2}M$, meaning $w(rx)+f(x)-(w(rz)+f(z))> \varepsilon (1+\varepsilon )^{i-2}M$. Since $\sigma \in \mathcal {S}_{i}^{u}$, we have $w(yx)+f(x)\le w(\sigma )+f_{1}(\sigma )< \gamma \cdot (1+\varepsilon )^{i}M$. Hence, we have the following

$$w(\pi (\sigma ))+f_{1}(\pi (\sigma ))\ge w(zy)+f(y)> \varepsilon (1+\varepsilon )^{i-2}M- \gamma \cdot (1+\varepsilon )^{i}M= \gamma \cdot (1+\varepsilon )^{i-1}M.$$

This shows that the subtree $\pi (\sigma )\in \mathcal{S}_{i-1}^{m}$.    $\square$

Employing the similar argument as in [8], we obtain the following two lemmas by executing Step 8.

Lemma 6

For any $F\in \mathcal{F}_{i}(\tau )$, we have $w(F)+f(F)\le (\zeta +1+(\zeta +1)\varepsilon )(1+\varepsilon )^{i}M$.

Proof. For each $F\in \mathcal{F}_{i}(\tau )$, note that F consists of some subtree $F'_{j}$ $(1\le j\le q)$ and an edge $rv'_{j}$ connecting r to $v'_{j}$, where $v'_{j}$ is a vertex in $F'_{j}$ closest to r. Based on the construction of $F'_{j}$, we obtain $w(F'_{j})+f(F'_{j})\le \zeta (1+\varepsilon )^{i+1}M$. Since $F'_{j}$ only contains vertices in $V_{\le i+1}$, we have $w(rv'_{j})\le w(rv'_{j})+f(v'_{j})\le (1+\varepsilon )^{i+1}M$. Hence, it follows that $w(F)+f(F)= w(F'_{j})+f(F'_{j})+w(rv'_{j})\le (\zeta +1+(\zeta +1)\varepsilon )(1+\varepsilon )^{i}M$.    $\square$

Lemma 7

$\sum _{F\in \mathcal{F}_{i}(\tau )}(w(F)+f(F))\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))$.

Proof. We break the analysis into two cases depending on q.

Case 1: $q=1$, i.e., $\mathcal{F}_{i}(\tau )$ only contains a subtree F.

If $i=0$, then $\tau$ includes r and $w(F)+f(F)\le w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau ))$. If $i>0$, it is clear that there exists $u\in \tau$ having $u\in V_{<i}$. Based on the construction of subtree, we obtain $w(F)+f(F)\le w(rx_{h(\tau )})+w(F')+f_{1}(\tau \cup \textrm{Dangle}(\tau ))\le w(ry_{h(\tau )})+w(y_{h(\tau )}x_{h(\tau )})+w(F')+f_{1}(\tau \cup \textrm{Dangle}(\tau ))\le (1+\varepsilon )^{i-1}M+ w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau ))$. Since $\tau \in \mathcal{S}_{i}^{m}$, implying $w(\tau )+f_{1}(\tau )\ge \gamma \cdot (1+\varepsilon )^{i}M$, we have $(1+\varepsilon )^{i-1}M\le \frac{2+\varepsilon }{\varepsilon }\cdot (w(\tau )+f_{1}(\tau ))$. Thus, we obtain $w(F)+f(F)\le (1+\varepsilon )^{i-1}M+ w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau ))\le (\frac{2+\varepsilon }{\varepsilon }+1)\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))= (2+\frac{2}{\varepsilon })\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))$, which implies $\sum _{F\in \mathcal{F}_{i}(\tau )}(w(F)+f(F))=w(F)+f(F)\le (2+\frac{2}{\varepsilon })\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))$.

Case 2: $q\ge 2$.

By Step 8, we obtain that $4(w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))> (q-1)\cdot \zeta (1+\varepsilon )^{i+1}M$, that is $(1+\varepsilon )^{i+1}M< \frac{4(w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))}{\zeta (q-1)}$. Since $V(\tau \cup \textrm{Dangle}(\tau ))\subseteq V_{\le i+1}$, each edge added from r to subtree $F'_{j}$ $(1\le j\le q)$ has weight at most $(1+\varepsilon )^{i+1}M$. Therefore, we conclude that $\sum _{F\in \mathcal{F}_{i}(\tau )}(w(F)+f(F))\le q\cdot (1+\varepsilon )^{i+1}M+ 2w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau ))\le (\frac{4 q}{\zeta (q-1)}+2)\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))\le (\frac{4}{\zeta }+2)\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))$.

Combining the two preceding arguments in Cases 1–2, we obtain $\sum _{F\in \mathcal{F}_{i}(\tau )}($ $w(F)+f(F))\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau ))).$    $\square$

Applying Lemmas 5–7, we obtain the following

Lemma 8

If $w(T^{MS}_{G/V_{<i}})+f(V_{\ge i})\le M\cdot \varLambda ((1+\varepsilon )^{i-1})$ holds for each integer $i\ge 0$, then the collection $\{\mathcal{F}_{i}\}_{i\ge 0}$ obtained at Step 8 is $(\alpha ,\beta )_{M,\varepsilon }$-assignable, where $\alpha =\zeta +1+(\zeta +1)\varepsilon$, $\beta =(6+\frac{6}{\varepsilon })\max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}$ and $\mathcal{F}_{i}= \bigcup _{\tau \in \mathcal{S}_{i}^{m}}\mathcal{F}_{i}(\tau )$.

Proof. We shall prove that the collection $\{\mathcal{F}_{i}\}_{i\ge 0}$ satisfies the two properties in Definition 1. By Lemma 6, it is clear that the property (1) in Definition 1 holds. Recall that in Lemma 4, $\sum _{j\ge i}(w(H_{j})+f(V_{j}))\le (6+\frac{6}{\varepsilon })\cdot M\cdot \varLambda ((1+\varepsilon )^{i-1})$ holds for each $i\ge 0$. Now, the proof is completed by showing that $\sum _{j\ge i}(w(\mathcal{F}_{j})+f(\mathcal{F}_{j}))\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot \sum _{j\ge i}(w(H_{j})+f(V_{j}))$.

In the algorithm HRTC$_{1}$, we observe that

$$\sum _{j\ge i}(w(\mathcal{S}_{j}^{m})+w(\mathcal{S}_{j+1}^{u}))\le \sum _{j\ge i}w(\mathcal{S}_{j})= \sum _{j\ge i}w(H_{j}). $$

By Lemma 5, $\{\textrm{Dangle}(\tau )~|~ \tau \in \mathcal{S}_{j}^{m}\}$ is a partition of $\mathcal{S}_{j+1}^{u}$, which means $\sum _{\tau \in \mathcal{S}_{j}^{m}} (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))= w(\mathcal{S}_{j}^{m})+w(\mathcal{S}_{j+1}^{u})+f_{1}(\mathcal{S}_{j}^{m}\cup \mathcal{S}_{j+1}^{u})$. By Lemma 7, we have $w(\mathcal{F}_{j})+f(\mathcal{F}_{j})= \sum _{\tau \in \mathcal{S}_{j}^{m}}(w(\mathcal{F}_{j}(\tau ))+f(\mathcal{F}_{j}(\tau )))= \sum _{\tau \in \mathcal{S}_{j}^{m}} \sum _{F\in \mathcal{F}_{j}(\tau )} (w(F)+f(F))\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot \sum _{\tau \in \mathcal{S}_{j}^{m}} (w(\tau \cup \textrm{Dangle}(\tau ))+f_{1}(\tau \cup \textrm{Dangle}(\tau )))$, implying $w(\mathcal{F}_{j})+f(\mathcal{F}_{j})\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot (w(\mathcal{S}_{j}^{m})+w(\mathcal{S}_{j+1}^{u})+f_{1}(\mathcal{S}_{j}^{m}\cup \mathcal{S}_{j+1}^{u}))$. By Steps 6–8, for each edge $e\in \mathcal{S}_{i}^{m}$ $(i\ge 0)$, we see that $x_{e}\in V_{\ge i}$, and any two subtrees in $\{\mathcal{F}_{i}\}_{i\ge 0}$ are disjoint except for root r. Thus, we obtain $\sum _{j\ge i} (w(\mathcal{F}_{j})+f(\mathcal{F}_{j}))\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot \sum _{j\ge i} (w(\mathcal{S}_{j}^{m})+w(\mathcal{S}_{j+1}^{u})+$ $f_{1}(\mathcal{S}_{j}^{m}\cup \mathcal{S}_{j+1}^{u})\le \max \{2+\frac{2}{\varepsilon }, \frac{4}{\zeta }+2\}\cdot \sum _{j\ge i}(w(H_{j})+f(V_{j})).$    $\square$

Using the above lemmas, we obtain the following result.

Theorem 1

The algorithm HRTC$_{1}$ is a $58.3286(1+\delta )$-approximation algorithm to solve the HRTC problem, and it runs in time $O(n^{3}(1+\frac{1}{\delta })+\log (w(E)+f(V\backslash \{r\})))$, where $w(E)=\sum _{e\in E} w(e)$ and $f(V\backslash \{r\})=\sum _{v\in V\backslash \{r\}} f(v)$, respectively.

Proof. By Lemma 2, the decision condition in Step 3 does not hold whenever $M\ge OPT$. Based on the update rule for M, we deduce that Steps 4–9 is executed with $M\le (1+\delta )\cdot OPT$. When fixing $\zeta =2$ and $\varepsilon =1.3146$, using Lemma 8, we obtain a $(6.9438,42.2565)_{M,1.3146}$-assignable collection $\{\mathcal{F}_{i}\}_{i\ge 0}$. Using Lemma 1 at Step 9, we can assign $\{\mathcal{F}_{i}\}_{i\ge 0}$ into k construction teams in time $O(n^{3}+\log (w(E)+f(V\backslash \{r\})))$, such that the completion time of any construction team is at most $58.3286\cdot M$, which implies $OUT\le 58.3286\cdot M\le 58.3286(1+\delta )\cdot OPT$.

Notice that every step in the algorithm HRTC$_{1}$ can be executed in polynomial time. We shall bound the number of iterations. As mentioned above, the algorithm HRTC$_{1}$ halts before $M> (1+\delta )OPT$, where $(1+\delta )OPT\le (1+\delta )\cdot \frac{\sum _{v\in V}(w(rv)+f(v))}{\lambda _{\max }}\le (1+\delta )\cdot |V|\cdot \frac{\max _{v\in V}\{w(rv)+f(v)\}}{\lambda _{\max }}$. Since M is initialized at $\frac{\max _{v\in V}\{w(r,v)+f(v)\}}{\lambda _{\max }}$, and increased by an $(1+\delta )$-factor for each iteration, we deduce that the number of iterations is at most $O(\frac{1}{\delta }\log |V|)$. This implies that Steps 1–3 run in at most time $O(\frac{n^{3}}{\delta })$. By Lemma 1, it is easy to check that Steps 4–10 execute in time $O(n^{3}+\log (w(E)+f(V\backslash \{r\})))$. Hence, the algorithm HRTC$_{1}$ can be implemented in time $O(n^{3}(1+\frac{1}{\delta })+\log (w(E)+f(V\backslash \{r\})))$.    $\square$

4 An Approximation Algorithm with Lower Time Complexity

In practice, we observe a fact that $\frac{\lambda _{\max }}{\lambda _{\min }}$ is generally small, where $\lambda _{\max }=\max \{\lambda _{i}~|~i=1,2,\ldots ,k\}$ and $\lambda _{\min }=\min \{\lambda _{i}~|~i=1,2,\ldots ,k\}$. Thus, we intend to design a better approximation algorithm to resolve the HRTC problem under the above fact.

Different from the method in [10] for solving the RTC problem, we modify a splitting technique in [6] to design an approximation algorithm to resolve the HRTC problem, which is described as follows.

• Algorithm: HRTC$_{2}$

• Input: An undirected complete graph $G=(V, E;w, f)$ with a root $r\in V$, an edge-weight function $w: E\rightarrow R^{+}$, a vertex-weight function $f:V{\setminus } \{r\}\rightarrow R^{+}_{0}$ and k construction teams having speeds $\lambda _{1},\ldots ,\lambda _{k}$, respectively;

• Output: A set $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ of trees.

• Begin

• Step 1 Find a minimum edge-weight spanning tree $T^{MS}$ in G; Determine an Euler tour in $(V, E_{T^{MS}}+E_{T^{MS}})$ traversing each edge exactly once, and use “short-cutting” to transform such tour to a cycle $C=rv_{i_{1}}v_{i_{2}}\cdots r$ traversing each vertex $v\in V$ exactly once;

• Step 2 Set $w_{0}=\max \{w(rv)~|~v\in V\}$; For each edge $uv\in E$, set $w'(uv)=w(uv)+f(u)+f(v)$; For each $i\in \{1,2,\ldots ,k\}$, set $\lambda _{1,i}=\sum _{j=1}^{i}\lambda _{j}$;

• Step 3 For $j=1$ to $k-1$ do: Set $L_{j}=\frac{\lambda _{1,j}}{\lambda _{1,k}}(w'(C)-2w_{0})+w_{0}$, find the last vertex $v_{i_{p(j)}}$ such that $w'(C[r,v_{i_{p(j)}}])\le L_{j}$, where $C[r,v_{i_{p(j)}}]=r v_{i_{1}} v_{i_{2}} \cdots v_{i_{p(j)}}$;

• Step 4 Set $T'_{1}=C[r,v_{i_{p(1)}}]=r v_{i_{1}}\cdots v_{i_{p(1)}}$, $T'_{2}=C[v_{i_{p(1)+1}},v_{i_{p(2)}}]$, $\ldots$ , $T'_{k}=C[v_{i_{p(k-1)+1}},r]$; For each $j\in \{1,2,\ldots , k\}$, augment $T'_{j}$ by connecting r to a vertex in $T'_{j}$ closest to r with edge, where the resulting tree is denoted by $T_{j}$;

• Step 5 Output k trees $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$ corresponding to k teams.

• End

Analyzing the lower bound of the optimal value for the HRTC problem, we obtain the following result.

Lemma 9

Given a complete graph $G=(V,E;w,f)$ as an instance of the HRTC problem, we have $OPT\ge \max \{\frac{f_{0}}{\lambda _{\max }}, \frac{w_{0}}{\lambda _{\max }}, \frac{w'(C)}{2\lambda _{1,k}}\}$, where OPT is the optimal value to the given instance, $f_{0}=\max \{f(v)~|~v\in V\}$, $w_{0}=\max \{w(rv)~|~v\in V\}$ and C is produced at Step 1 of the algorithm HRTC$_{2}$.

Proof. Note that any feasible solution for the instance G cover all vertices in V, it is clear that $OPT\ge \frac{f_{0}}{\lambda _{\max }}$ and $OPT\ge \frac{w_{0}}{\lambda _{\max }}$. We shall prove $OPT\ge \frac{w'(C)}{2\lambda _{1,k}}$.

Consider any optimal solution $\mathcal{T}^{*}=\{T^{*}_{i}~|~i=1,2,\ldots ,k\}$ for the instance G. By the construction of C at Step 1, we have $w(T^{MS})+f(T^{MS})\ge \frac{w(C)}{2}+f(C)$, where $T^{MS}$ is a minimum edge-weight spanning tree of G. Since all subtrees in $\mathcal{T}^{*}$ can be merged into a spanning tree, we obtain $\sum _{i=1}^{k}(w(T^{*}_{i})+f(T^{*}_{i}))\ge w(T^{MS})+f(T^{MS})$, implying $\sum _{i=1}^{k}(w(T^{*}_{i})+f(T^{*}_{i}))\ge \frac{w(C)}{2}+f(C)$. Since $OPT=\max \{\frac{w(T^{*}_{i})+f(T^{*}_{i})}{\lambda _{i}}|i=1,2,\ldots ,k\}$, it follows that $OPT\cdot \sum _{i=1}^{k}\lambda _{i}\ge \sum _{i=1}^{k}(w(T^{*}_{i})+f(T^{*}_{i}))\ge \frac{w(C)}{2}+f(C)$, meaning $OPT\ge \frac{w(C)+2f(C)}{2\sum _{i=1}^{k}\lambda _{i}}= \frac{w(C)+2f(C)}{2\lambda _{1,k}}$. This implies $OPT\ge \frac{w(C)+2f(C)}{2\lambda _{1,k}}= \frac{w'(C)}{2\lambda _{1,k}}$.    $\square$

By the algorithm HRTC$_{2}$, we obtain the following result.

Theorem 2

The algorithm HRTC$_{2}$ is a $\max \{\frac{2\lambda _{\max }}{\lambda _{\min }}, 2+\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k}\}$-approximation algorithm for resolving the HRTC problem, and it runs in time $O(n^{2})$, where n is the number of vertices.

Proof. Given an instance $G=(V,E;w, f)$ of the HRTC problem, we may assume that $\mathcal{T}^{*}=\{T^{*}_{i}~|~i=1,2,\ldots ,k\}$ is an optimal solution with the optimal value $OPT=\max \{\frac{w(T^{*}_{i})+f(T^{*}_{i})}{\lambda _{i}}~|~i=1,\ldots ,k\}$, and $\mathcal{T}$ is trees outputted by the algorithm HRTC$_{2}$ with the output value $OUT=\max \{\frac{w(T_{i})+f(T_{i})}{\lambda _{i}}~|~i=1,\ldots ,k\}$.

Now, we consider the $j^{th}$ tree $T_{j}$ ($1\le j\le k$) in $\mathcal{T}$. Using the algorithm HRTC$_{2}$, we obtain the following

$$\begin{aligned} \frac{w(T_{j})+f(T_{j})}{\lambda _{j}} & \le & \frac{w(T'_{j})+f(T'_{j})+w_{0}}{\lambda _{j}} \\ & \le & \max \{\frac{f_{0}}{\lambda _{j}}, \frac{w'(T'_{j})}{\lambda _{j}}\}+\frac{w_{0}}{\lambda _{j}} \\ & = & \max \{\frac{f_{0}+w_{0}}{\lambda _{j}}, \frac{w'(T'_{j})+w_{0}}{\lambda _{j}}\}. \end{aligned}$$

From Lemma 9, it may be concluded that $\frac{f_{0}+w_{0}}{\lambda _{j}}=\frac{f_{0}}{\lambda _{j}}+\frac{w_{0}}{\lambda _{j}}\le \frac{f_{0}}{\lambda _{\min }}+\frac{w_{0}}{\lambda _{\min }}\le \frac{2\lambda _{\max }}{\lambda _{\min }}OPT$. On account of the construction of $\mathcal{T}$ in algorithm, we have the following

$$\begin{aligned} \frac{w'(T'_{j})+w_{0}}{\lambda _{j}} & \le & \frac{\frac{\lambda _{j}}{\lambda _{1,k}}\cdot (w'(C)-2w_{0})+w_{0}}{\lambda _{j}} \\ & = & \frac{w_{0}}{\lambda _{j}}+\frac{w'(C)-2w_{0}}{\lambda _{1,k}}\\ & \le & \frac{w_{0}}{\lambda _{\min }}+\frac{w'(C)}{\lambda _{1,k}}-\frac{2w_{0}}{\lambda _{1,k}}\\ & = & \frac{\lambda _{\max }\cdot w_{0}}{\lambda _{\min }\cdot \lambda _{\max }}+\frac{w'(C)}{\lambda _{1,k}}-\frac{2w_{0}}{\lambda _{1,k}}\\ & \le & \frac{\lambda _{\max }\cdot w_{0}}{\lambda _{\min }\cdot \lambda _{\max }}+\frac{w'(C)}{\lambda _{1,k}}-\frac{2w_{0}}{k\cdot \lambda _{\max }}\\ & = & \frac{w'(C)}{\lambda _{1,k}}+(\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k})\cdot \frac{w_{0}}{\lambda _{\max }}\\ & \le & 2OPT+(\frac{\lambda _{\max }}{\lambda _{\min }}- \frac{2}{k})\cdot OPT\\ & = & (2+\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k})\cdot OPT, \end{aligned}$$

implying $\frac{w(T_{j})+f(T_{j})}{\lambda _{j}}\le \max \{\frac{2\lambda _{\max }}{\lambda _{\min }}, 2+\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k}\}\cdot OPT$.

Thus, for each $j\in \{1,\ldots ,k\}$, we have $\frac{w(T_{j})+f(T_{j})}{\lambda _{j}}\le \max \{\frac{2\lambda _{\max }}{\lambda _{\min }}, 2+\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k}\}\cdot OPT$ by using the above arguments. This shows that

$$OUT\le \max \{\frac{2\lambda _{\max }}{\lambda _{\min }}, 2+\frac{\lambda _{\max }}{\lambda _{\min }}-\frac{2}{k}\}\cdot OPT.$$

The time complexity of the algorithm HRTC$_{2}$ can be determined as follows. (1) Using Prim algorithm for solving the minimum spanning tree problem, Step 1 execute in time $O(n^{2})$; (2) Step 2 needs O(m) time to compute $w_{0}$ and define $w'(\cdot )$, where $m=|E|$; (3) Step 3 needs time $O(n^{2})$ to split a cycle; (4) Step 4 needs time O(m) to construct the trees $\mathcal{T}=\{T_{i}~|~i=1,2,\ldots ,k\}$. Therefore, the running time of the algorithm HRTC$_{2}$ is $O(n^{2})$.    $\square$

5 Conclusion and Further Work

In this paper, we consider the heterogeneous rooted tree cover problem (the HRTC problem), and design two approximation algorithms for solving the HRTC problem.

In further work, it is a challenge for us to design some approximation algorithms with constant approximation ratios to solve the HRTC problem in strongly polynomial time, and we shall study other versions of the cover problems with nonuniform speeds.