Better approximability results for min–max tree/cycle/path cover problems

Abstract

We study the problem of covering the vertices of an undirected weighted graph with a given number of trees (cycles, paths) to minimize the weight of the maximum weight tree (cycle, path). Improved inapproximability lower bounds are proved and better approximation algorithms are designed for several variants of this problem.

1 Introduction

Given an undirected graph with nonnegative edge weights and a positive integer k, the objective is to find k trees (cycles, paths) to cover all the vertices such that the weight of the maximum weight tree (cycle, path) is minimized. This fundamental optimization problem, known as Min–Max Tree/Cycle/Path Cover Problem, and its variants have attracted considerable research attention in recent decades. This is mainly due to its wide range of application in both operations research and computer science, such as mail and newspaper delivery (Frederickson et al. 1978), nurse station location (Even et al. 2004), disaster relief efforts routing (Campbell et al. 2008), data gathering and wireless recharging in wireless sensor networks (Xu et al. 2015), multi-vehicle scheduling problem (Karuno and Nagamochi 2003; Bhattacharya and Hu 2010), political districting (Karakawa et al. 2011), and so on. For more practical examples that can be modeled by min–max tree/cycle/path cover problems, we refer to Arkin et al. (2006), Xu et al. (2010), Nagarajan and Ravi (2012), Xu et al. (2012).

Given the NP-hardness of the min–max tree/cycle/path cover problem (Even et al. 2004), most researchers have concentrated on designing approximation algorithms that generate near-optimal solutions in polynomial time as well as on deducing inapproximability lower bounds.

1.1 Previous results

For the Min–Max Tree Cover Problem (MMTCP), Even et al. (2004) and Arkin et al. (2006) devised independently 4-approximation algorithms, which was improved to a 3-approximation algorithm by Khani and Salavatipour (2014). The above-mentioned 4-approximation algorithm by Arkin et al. (2006) is actually developed for the Min–Max Path Cover Problem (MMPCP), which is still the best available algorithm. For the Min–Max Cycle Cover Problem (MMCCP), Xu et al. (2012) gave a 6-approximation algorithm, which can also be achieved by a combination of the 3-approximation algorithm for MMTCP with standard edge-doubling strategy. Xu et al. (2015) and Jorati (2013) proposed independently 16/3-approximation algorithms. Recently, Yu and Liu (2016) developed a $\min \{4\rho ,5\}$-approximation algorithm provided an algorithm for TSP with approximation ratio $\rho$ is available. By the result in Christofides (1976), we have $\rho \le 3/2$.

In Rooted MMTCP/MMCCP/MMPCP, which is an important variant treated in the literature, a depot set D is prescribed and the aim is to cover all the vertices not in D with at most k trees/cycles/paths each of which contains at least one vertex from D. If each vertex in D has a unit-capacity, i.e., each tree/cycle/path has to contain a distinct vertex in D, we obtain a capacitated rooted problem. Otherwise, if each tree/cycle/path is allowed to contain an arbitrary vertex in D, we have an uncapacitated rooted problem. As shown in Xu et al. (2010, 2015), Yu and Liu (2016), an ($\alpha +1$)-approximation algorithm for the uncapacitated rooted problem can be derived from an $\alpha$-approximation algorithm for the corresponding unrooted problem. For Single-Depot Rooted MMTCP/MMCCP/MMPCP, i.e., $|D|=1$, better algorithms with approximation ratios 3, $\rho +1$, 3 were obtained by Nagamochi (2005), Frederickson et al. (1978), Xu et al. (2010), respectively ($\rho$ defined as before).

For Capacitated Rooted MMCCP, Xu et al. (2012) developed the first approximation algorithm with ratio 13 and obtained a 7-approximation algorithm for the case $|D|=k$. The latter result was shown independently by Jorati (2013). Subsequently, Xu et al. (2015) improved the ratio to 7 for the general problem. For Capacitated Rooted MMTCP with $|D|=k$, Even et al. (2004) provided a 4-approximation algorithm.

In addition, the above results can be further improved if either the graph has a special structure [e.g., a tree (Nagamochi and Okada 2003), embedded into a Euclidean space (Karakawa et al. 2011)] or k is fixed (Farbstein and Levin 2015).

As for the approximation hardness, Xu and Wen (2010) proved an inapproximability lower bound of 3/2 for both MMTCP and MMPCP, which applies to the capacitated rooted problems even with the restriction $|D|=k$. Xu et al. (2010) obtained the same result for Uncapacitated Rooted MMPCP. Xu et al. (2012) gave a lower bound of 4/3 for both MMCCP and its rooted version. Xu and Wen (2010) also showed a lower bound of 10/9 (20/17) for Single-Depot Rooted MMTCP (MMCCP), complemented by a lower bound of 4/3 for Single-Depot Rooted MMPCP in Xu et al. (2010).

1.2 Our results

We obtain both improved approximation algorithms and better inapproximability lower bounds for several variants of the min–max tree/cycle/path cover problem. Firstly, we devise a 6-approximation algorithm for Capacitated Rooted MMCCP, improving on the algorithm in Xu et al. (2015) with an approximation ratio of 7. Second, we propose the first approximation algorithms for Capacitated Rooted MMTCP and Capacitated Rooted MMPCP, both of which have a constant ratio of 7. Third, we provide further improvement on the approximation algorithms for some interesting special cases, i.e., planar problem, graphic problem (see Sect. 2 for definitions). Last, we prove better inapproximability lower bounds for (Rooted) MMCCP, Single-Depot Rooted MMCCP, Single-Depot Rooted MMTCP, as illustrated in Table 1, and show that the reductions used to prove the lower bounds are essentially best possible.

The remainder of the paper is organized as follows. We explain some notations and formally describe the problems in Sect. 2. The inapproximablility lower bounds are proved in Sect. 3. This is followed by approximation algorithms for the capacitated rooted min–max tree/cycle/path cover problem in Sect. 4.

2 Preliminaries

We denote by $G=(V,E)$ an undirected weighted complete graph with the vertex set V and the edge set E. Let w(e) denote the weight or length of edge e. If $e=(u,v)$, we also use w(u, v) to denote the weight of e. The weights are metric, i.e., nonnegative, symmetric and satisfy the triangle inequality. For $B>0, G[B]$ denotes the subgraph of G obtained by removing all the edges in E with weights greater than B. For $u\in V$ and $V'\subseteq V$, let $d(u,V')=\min _{v\in V'}w(u,v)$ be the distance from u to $V'$. For a subgraph H (e.g., tree, cycle, path) of G, let V(H), E(H) denote the vertex set and edge set of H, respectively. The weight of H is defined as $w(H)=\sum _{e\in E(H)}w(e)$. For $u\in V, d(u,H)=d(u,V(H))$ denotes the distance from u to H. The weight of a path or cycle is also called its length. A tree (cycle, path) containing only one vertex and no edges is a trivial tree (cycle, path) and its weight is defined as zero.

For a subset $V'$ of V, a set $\{T_1,T_2,\ldots ,T_k\}$ of trees (some of them may be trivial trees) is called a tree cover of $V'$ if $V' \subseteq \cup _{i=1}^k V(T_i)$. And the cost of this tree cover is defined as $\max _{1\le i\le k}w(T_i)$, i.e., the maximum weight of the trees. Particularly, a tree cover of V is simply called a tree cover. By replacing trees with cycles (paths) we can define cycle cover (path cover) and its cost similarly. Note that a cycle containing exactly two vertices u, v consists of two copies of edge (u, v) and has a length of 2w(u, v).

Now we can formally state the following problems.

Definition 1

In the Min–Max Tree Cover Problem (MMTCP), we are given an undirected complete graph $G=(V,E)$ with a metric weight function w on E and a positive integer k, the goal is to find a minimum cost tree cover with at most k trees.

Definition 2

In the Rooted Min–Max Tree Cover Problem (RMMTCP), we are given an undirected complete graph $G=(V,E)$ with a metric weight function w on E, a depot set $D\subseteq V$ (the vertices in D are called depots or roots) and a positive integer k, the objective is to find a minimum cost tree cover of $V\setminus D$ with at most k trees such that each tree contains at least one root in D.

Definition 3

In the Capacitated Rooted Min–Max Tree Cover Problem (CRMMTCP), we are given the same input as in RMMTCP, the objective is to find a minimum cost tree cover of $V\setminus D$ with at most k trees such that each tree contains a distinct root in D.

The first problem is called unrooted problem as before, since no depot set is given. The second problem is referred to as uncapacitated rooted problem while the last problem is called capacitated rooted problem.

By replacing trees with cycles or paths in the above definitions we have another six problems, which are denoted by similar acronyms. For example, CRMMPCP stands for the Capacitated Rooted Min–Max Path Cover Problem while RMMCCP refers to the Rooted Min–Max Cycle Cover Problem. Note that in a rooted path cover problem, not only each path has to contain one root in D but also this root has to be an end vertex of the path. This is natural if one interprets the paths as the routing of a fleet of vehicles that start from given depots and service the customers located at the vertices.

In our problem definitions we assume that the graphs are complete. This involves no loss of generality since we can take the metric closure of a connected graph if it is not complete but connected. For a disconnected graph, we first add some edges of sufficiently large length to obtain a connected graph, and then consider the problems defined on the metric closure of this connected graph. Moreover, we suppose w.l.o.g. that the weights of the edges are integers.

In MMTCP, by restricting the graph to be the metric closure of a connected (weighted) planar graph we obtain (Weighted) Planar MMTCP. In Graphic MMTCP, the graph is required to be the metric closure of a connected unweighted graph. The same special case of the min–max cycle/path cover problems is defined similarly.

Given an instance of some min–max tree/cycle/path cover problem, OPT indicates its optimal value as well as the corresponding optimal solution. Each tree (cycle, path) in OPT is called an optimum tree (cycle, path). By the triangle inequality, except for the uncapacitated rooted problem, we can assume w.l.o.g that any two optimum cycles (paths) are vertex-disjoint, since one can eliminate the repeated vertices without increasing the cost. However, the optimum trees are not necessarily vertex-disjoint since there may exist vertices of degree greater than 2 and eliminating these vertices may increase the cost.

3 Inapproximability lower bounds

In this section we show that even Planar Min–Max Tree/Cycle/Path Cover Problems are hard to approximate and give improved lower bounds for some single-depot, i.e., $|D|=1$, rooted problems. However, Weighted Planar TSP, the special case of Weighted Planar MMCCP with $k=1$, admits PTAS (see Arora et al. 1998; Klein 2008).

Our results are based on reductions from a restriction of the following well-known NP-Complete problem (see Garey and Johnson 1979).

3-Dimensional matching problem (3DM) Given disjoint sets X, Y, Z that have the same number q of elements and a set $\mathcal {M}\subseteq X\times Y \times Z$ of triples with $|\mathcal {M}|=m$, is there an exact matching $\mathcal {M'}\subseteq \mathcal {M}$ such that $|\mathcal {M'}|=q$ and any two triples in $\mathcal {M'}$ do not have any common coordinate?

Associated with an instance of 3DM there is a bipartite graph $B=(W\cup (X\cup Y \cup Z),E)$, where each element of W represents a triple of $\mathcal {M}$. There is an edge connecting $w\in W$ to $v\in X\cup Y \cup Z$ if and only if v is a coordinate of the triple represented by w. By restricting the associated bipartite graph to be planar we obtain Planar 3-Dimensional Matching Problem (Planar 3DM), which is still NP-Complete (see Dyer and Frieze 1986).

Table 1 Previous and new lower bounds on min–max tree/cycle/path cover problems

Xu and Wen (2010), Xu et al. (2010, 2012) derived the lower bounds for min–max tree/cycle/path cover problems summarized in Table 1. All these bounds are deduced by gap-reductions from 3DM. In what follows, we show that the lower bound of 3/2 holds even for the planar version of all the problems in Table 1 except for the single-depot rooted problems. First, we observe that restricting the planar bipartite graph to be connected in Planar 3DM preserves NP-Completeness. This special case is called Connected Planar 3DM.

Fig. 1

The constructions in the proof of Lemma 1

Lemma 1

Connected Planar 3DM is NP-Complete.

Proof

Given an instance I of Planar 3DM consisting of $\mathcal {M}\subseteq X\times Y \times Z$ with $|X|=|Y|=|Z|=q$ and $|\mathcal {M}|=m$, the associated planar bipartite graph is $B=(W\cup (X\cup Y \cup Z),E')$. We assume w.l.o.g that each element in $X\cup Y \cup Z$ is a coordinate of some triple, since otherwise I cannot have a solution. We next deduce an instance $\hat{I}$ of Connected Planar 3DM. If B is connected, we have done by taking $\hat{I}=I$. Otherwise, B has at least two components. Since B is planar, we fix a planar embedding of B in the following discussion. Therefore, each component is also embedded into the plane and we can choose two components $C_1,C_2$ such that $C_1$ is contained in some face F of $C_2$.

Since $C_1$ corresponds to at least one triple, the boundary of its outer face contains some vertex in $X\cup Y \cup Z$. If the boundary of F does not include a cycle, then this boundary contains three vertices each of which is from a distinct set of X, Y, Z, since $C_2$ corresponds to at least one triple. If the boundary of F includes a cycle C, then C has to be a even cycle with at least four vertices since B is bipartite. By the definition of B, the only two vertices adjacent to any $w\in W\cap V(C)$ are from two distinct sets of X, Y, Z. Therefore, we can always choose one vertex from the boundary of the outer face of $C_1$ and one vertex from the boundary of F such that these two vertices are from two distinct sets of X, Y, Z. Without loss of generality, we assume that these two vertices are $x_0\in X\cap V(C_1)$ and $y_0\in Y\cap V(C_2)$.

Let $x',y',z'$ be three new elements not in $X\cup Y \cup Z$. As shown in Fig. 1, we derive an new instance $I'$ of 3DM by adding two triples $(x_0,y_0,z'), (x',y',z')$ to $\mathcal {M}$ and extending X, Y, Z to $X\cup \{x'\}, Y\cup \{y'\}, Z\cup \{z'\}$ respectively. It follows from the choice of $x_0,y_0$ that the bipartite graph associated with $I'$, denoted by $B'$, is also planar, which implies $I'$ is an instance of Planar 3DM. Since $C_1$ and $C_2$ are connected together in $B'$, the number of connected components of $B'$ is one less than B. Moreover, since $(x',y',z')$ is the only triple contains $x',y'$ as coordinates in $I'$, we conclude that $\mathcal {M'}$ is an exact matching of I if and only if $\mathcal {M'}\cup \{(x',y',z')\}$ is an exact matching of $I'$. By repeating the process at most $m=|\mathcal {M}|$ times we derive an instance $\hat{I}$ with connected planar bipartite graph. This completes a polynomial transformation from Planar 3DM to Connected Planar 3DM and proves the lemma. $\square$

Now we are ready to show the inapproximablity lower bounds.

Theorem 1

It is NP-hard to approximate the planar version of the min–max tree/cycle/path cover problem and its rooted version within a performance ratio less than 3/2.

Proof

First we concentrate on the unrooted problems. Given an instance I of Connected Planar 3DM consisting of $\mathcal {M}\subseteq X\times Y \times Z$ with $|X|=|Y|=|Z|=q$ and $|\mathcal {M}|=m$, the associated planar bipartite graph is $B=(W\cup (X\cup Y \cup Z),E')$. We derive an instance $I'$ of MMTCP/MMCCP/MMPCP consisting of the metric closure of a connected unweighted planar graph G and the positive integer $k=q+3m$. G is obtained by subdividing the edges of B and attaching some vertices of degree one, so G remains a connected planar graph. For each vertex in B, there is a corresponding vertex in G. For each triple $w=(x,y,z)\in \mathcal {M}$, there is a subgraph $K_{1,3}$ in B, and we construct a corresponding subgraph in G by adding eight new vertices, called internal vertices, and three new edges, as shown in Fig. 2 (the roles of circled vertices will be explained later). Therefore, G has $3q+9m$ vertices and 11m edges.$\square$

Fig. 2

The construction in proof of Theorem 1

We note that this reduction is similar to that used by Xu and Wen (2010), but they make no difference between w and the internal vertices, which is important to obtain the planarity and connectivity of G, and define the length of edges not in G to be 2 instead of the length of shortest path between the end vertices. However, the following claim proved by Xu and Wen (2010) is still valid since it is independent of the length of edges not in G.

Claim

There is an exact matching for I if and only if G can be partitioned into k paths of length 2.

Since G can be partitioned into k paths of length 2 is equivalent to the metric closure of G has a tree/path cover of cost at most 2, we have obtained a lower bound of 3/2 for Planar MMTCP/MMPCP by the integrality of edge length in G.

As for the cycle cover problem, we first note a crucial property that the length of shortest simple cycle in G is at least 8. Suppose that C is a simple cycle in G, let $V_1=V(C)\cap (W\cup (X\cup Y \cup Z))$. Clearly, $|V_1|\ge 3$. By eliminating the vertices in $V(C)\setminus V_1$ from C we can obtain a simple cycle $C'$ in B. Since B is bipartite and $|V_1|\ge 3$, the length of $C'$ is at least 4. By the construction of G, along the simple C there is at least one vertex in $V(C)\setminus V_1$ lies between any two adjacent vertices of $C'$. So C has a length of $|V(C)|\ge 2|V(C')|\ge 8$.

As a consequence of the property, it holds that (i) each cycle of length 4 in the metric closure of G consists of two copies of a path of length 2; (ii) there is no cycle of length 5 of the metric closure of G (because such a cycle contains either a simple cycle of length 3 or a simple cycle of length 5). Therefore, the above Claim is equivalent to

Claim

There is an exact matching for I if and only if $I'$ has a cycle cover of cost at most 4. Moreover, there is no exact matching for I if and only if the cost of any cycle cover of $I'$ is at least 6.

This implies the lower bound 3/2 also holds for Planar MMCCP.

Next we turn to the rooted version. The transformation is the same as the unrooted problem. In addition, we choose the depot set D consisting of all the circled vertices as shown in Fig. 2. So we have $|D|=q+3m=k$. One can verify that in any tree/path cover of cost at most 2 (cycle cover of cost at most 4) each tree/path (cycle) contains exactly one vertex from D. This implies the above two claims still hold for rooted problems. Consequently, the lower bound 3/2 is also valid for the rooted tree/path/cycle cover problems, even if we add the restriction $|D|=k$.

Remark 1

Replacing 3DM with Planar 3DM in the reductions of Xu and Wen (2010) and redefining the edge length as the shortest path length are not sufficient to obtain our results. In this case we may derive a disconnected planar graph. To make it connected we have to add some long edges. As a result, we have a connected weighted planar graph, instead of a connected unweighted planar graph.

In Single-Depot RMMTCP/RMMCCP/RMMPCP, the depot set D contains a single vertex. Xu et al. (2010) derived a lower bound of 4/3 for Graphic Single-Depot RMMPCP using the following reduction. Given an instance I of 3DM, each triple $w=(x,y,z)\in \mathcal {M}$ corresponds to a subgraph of G as illustrated in Fig. 3. They proved that I has an exact matching if and only if the metric closure of G has a path cover with $k=q+2m$ paths of cost at most 3. We note that the same reduction also implies a lower bound of 4/3 for Graphic Single-Depot RMMTCP. A tree cover of the metric closure of G with $k=q+2m$ trees of cost at most 3 has to be a path cover with $q+2m$ paths of cost at most 3.

Theorem 2

It is NP-hard to approximate Graphic Single-Depot RMMTCP within a performance ratio less than 4/3.

Fig. 3

The constructions in proof of Theorem 2 (The circled vertex is the only depot.)

For the single-depot cycle cover problem we have the following result.

Theorem 3

It is NP-hard to approximate Graphic Single-Depot RMMCCP within a performance ratio less than 5/4.

Proof

Given an instance I of 3DM, we use the same reduction as in Theorem 1 to obtain an instance $I'$ of MMCCP consisting of the metric closure of $G=(V,E)$ and $k>0$. Then, we add a new vertex r to V and connect r to each vertex of V to derive a graph $G'$. So we have an instance $I''$ of Graphic Single-Depot RMMCCP consisting of the metric closure $G'$ with depot vertex r and $k>0$.

Clearly, each path of length 2 in G can be transformed into a simple cycle of length 4 in $G'$ by connecting both end vertices to r. On the other hand, if the metric closure of $G'$ has a cycle cover of cost at most 4, each cycle has to contain exactly 3 vertices other than r since the total number of vertices is $3k+1$ and r has to be included in each cycle. Therefore, each cycle in the cycle cover is a simple cycle of length 4 (instead of two copies of a path of length 2), which can be turned into a path of length 2 in G by discarding the two edges incident to r. So we have shown that G can be partitioned into k paths of length 2 if and only if the metric closure of $G'$ has a cycle cover of cost at most 4. Combining this with the first claim in the proof of Theorem 1 completes the proof. $\square$

We end this section by showing that the results in Theorems 1, 2, 3 are the best possible if we are confined to give a gap-reduction from an NP-Complete problem to derive inapproximability lower bounds for graphic tree/cycle/path cover problems.

Lemma 2

There is a polynomial time algorithm to decide if (i) the optimal value of an instance of Graphic (Rooted) MMTCP/MMPCP equals 1; (ii) the optimum value of an instance of Graphic (Rooted) MMCCP equals 2.

Proof

Let OPT be the optimal value of an instance of Graphic MMTCP/MMPCP consisting of $k>0$ and an unweighted graph $G=(V,E)$ with n vertices. Since a tree/path of length 1 is simply an edge, $OPT=1$ if and only if the maximum matching of G contains at least $n-k$ edges.

For the uncapacitated rooted problem, it is straightforward that $OPT=1$ if and only if $|V\setminus D|\le k$ and each vertex in $V\setminus D$ is adjacent to some vertex in D.

For the capacitated rooted problem, it can be seen that $OPT=1$ if and only if $|V\setminus D|\le k$ and the maximum matching of B contains exactly $|V\setminus D|$ edges, where $B=(D\cup (V\setminus D),E')$ is a bipartite graph obtained by removing from G all the edges with both end vertices contained in either D or $V\setminus D$. The case for cycle cover problem can be proved similarly. $\square$

Lemma 3

There is a polynomial time algorithm to decide if (i) the optimal value of an instance of Graphic Single-Depot RMMTCP/RMMPCP is not greater than 2; (ii) the optimal value of an instance of Graphic Single-Depot RMMCCP is not greater than 3.

Proof

Given an instance of Graphic Single-Depot RMMTCP/RMMCCP/RMMPCP consisting of $k>0$ and an unweighted graph $G=(V,E)$ with n vertices and r the depot, let OPT be the optimal value. Let l(v) be the length of the shortest path from r to v.

(i) For the tree cover problem, if there is a vertex v with $l(v)\ge 3$, then we have $OPT\ge 3$ since some optimum tree has to contain both r and v. If there are some edge (u, w) with $l(u)=l(w)=2$ present in some optimum tree T, then we deduce that $OPT\ge w(T)\ge \max \{l(u),l(w)\}+1=3$. Therefore, we next assume that V can be partitioned into $\{r\},V_1,V_2$, where $l(v)=i$ for each $v\in V_i\ (i=1,2)$, and there is no edge connecting two vertices in $V_2$. Let R be the set of vertices in $V_1$ that are adjacent to some vertex in $V_2$. $\square$

Claim

$OPT \le 2$ if and only if $\lceil \frac{|V_1|-|R|}{2}\rceil + |V_2| \le k$.

If $OPT \le 2$, the optimum trees can be partitioned into two types. Each tree of the first type, which is actually a path, consists of r, one vertex in R and one vertex in $V_2$. There are exactly $|V_2|$ such trees. Each tree of the other type contains r and at most two vertices in $V_1\setminus R$. Since r is connected to each vertex of $V_1$, we can assume w.l.o.g that this type of trees consists of one or two edges of (r, u), (r, v), where $u,v \in V_1\setminus R$(if the edge (u, v) is present in the tree, we can replace it with either (r, u) or (r, v)). Note that it is most advantageous to have $\lceil \frac{|V_1|-|R|}{2} \rceil$ such trees. Since OPT is feasible, the total number of trees, i.e., $\lceil \frac{|V_1|-|R|}{2}\rceil + |V_2|$ in OPT is at most k.

Conversely, if $\lceil \frac{|V_1|-|R|}{2}\rceil + |V_2|$, it is easy to derive a feasible solution with objective value at most 2. Hence the claim follows.

For the path cover problem, if $OPT\le 2$, we can still assume the same partition $\{r\},V_1,V_2$ of the vertex set and no edge has two end vertices in $V_2$. However, the paths in OPT contains some edges connecting two vertices of $V_1$ and these edges cannot be replaced by edges linking r and vertices in $V_1$ since this operation may change a path to a tree. Therefore, we obtain a subgraph $G'$ of G induced by $V_1\setminus R$. It can be observed that there is a bijection between the matchings of $G'$ and the path covers of $V_1\setminus R$(it is possible that two paths, say (r, u), (u, v) and (r, u), (u, w), contain a common vertex, but we can replace the second path by (r, w) which preserves feasibility). Hence the following claim holds.

Claim

$OPT \le 2$ if and only if $|V_1\setminus R| + |V_2| - |M| \le k$, where M is a maximum matching of $G'$.

This completes the proof of (i).

(ii) For the cycle cover problem, if there is a vertex v with $l(v)\ge 2$, then we have $OPT\ge 2l(v)\ge 4$. So we only need to treat the case where V contains only the depot vertex r and its $n-1$ neighbors. And in this case each pair of neighbors of r connected by an edge corresponds a cycle of length 3. Therefore, $OPT\le 3$ if and only if the maximum matching of the subgraph induced by $V\setminus \{r\}$ contains at least $n-k-1$ edges.$\square$

4 Approximation algorithms

In this section we show how to obtain approximation algorithms for Capacitated Rooted Min–Max Tree/Cycle/Path Cover Problem by using the approximation algorithm for the unrooted problem.

To design an approximation algorithm for CRMMTCP, we adopt a two-stage process. The first is to obtain an $\alpha$-subroutine defined as below.

Definition 4

A polynomial time algorithm is called an $\alpha$-subroutine for CRMMTCP, if for any instance consisting of $G=(V,E)$ and $k>0$, and any nonnegative integer $\lambda \le \sum _{e\in E}w(e)$, the algorithm returns either failure or a feasible tree cover of cost at most $\alpha \lambda$ and it always returns the latter output as long as $OPT\le \lambda$.

Given an instance of CRMMTCP consisting of $G=(V,E)$ and $k>0$, clearly $0\le OPT \le \sum _{e\in E}w(e)$. We guess an objective value $\lambda \in [0,\sum _{e\in E}w(e)]$ and run the $\alpha$-subroutine. If no feasible tree cover is returned, we have $OPT>\lambda$ by the above definition. So we increase the value of $\lambda$ and run the subroutine again. If the subroutine does return a feasible tree cover of cost at most $\alpha \lambda$, we decrease the value of $\lambda$ and run the subroutine again. Finally, we find the minimum value $\lambda ^*$ such that a feasible tree cover of cost no more than $\alpha \lambda ^*$ is returned by the subroutine. It follows that $OPT \ge \lambda ^*$ since the subroutine does not return a feasible tree cover for $\lambda ^*-1$. Therefore, the tree cover returned by the $\alpha$-subroutine for $\lambda ^*$ is an $\alpha$-approximate solution. By a binary search for $\lambda ^*$, this procedure uses the $\alpha$-subroutine at most $\log \sum _{e\in E}w(e)$ times and hence runs in polynomial time.

One can see that the above procedure applies to other min–max tree/cycle/path cover problems.

Lemma 4

A T(n) time $\alpha$-subroutine for MMTCP (MMCCP, MMPCP) or its rooted version implies an $\alpha$-approximation algorithm for the same problem that runs in $O(T(n)\log \sum _{e\in E}w(e))$ time.

4.1 Cycle cover

Suppose there is a $\rho _c$-subroutine for MMCCP. We give the following algorithm for CRMMCCP. The input is an instance of CRMMCCP consisting of $G=(V,E)$ and $k>0$ and a value $\lambda \in [0,\sum _{e\in E}w(e)]$.

Algorithm $CRMMCCP(\rho _c)$

Step 1.:

If $\max _{v\in V \setminus D}d(v,D) > \frac{\lambda }{2}$, stop and return failure. Otherwise, i.e., $\max _{v\in V \setminus D}d(v,D) \le \frac{\lambda }{2}$, delete all the edges with weight greater than $\frac{\lambda }{2}$ in G to obtain $G[\frac{\lambda }{2}]$. Remove the connected components of $G[\frac{\lambda }{2}]$ that contain no vertices in $V\setminus D$ and let the remaining p connected components be $F_1,F_2,\,\ldots ,F_p$.

Step 2.:

For each $i=1,2,\ldots ,p$,

Step 2.1.:

Let $D_i=D\cap V(F_i)=\{r_1,r_2,\ldots ,r_{|D_i|}\}$. Find the minimum integer $k_i$ with $1\le k_i\le |D_i|$ such that the $\rho _c$-subroutine for MMCCP outputs a cycle cover $\mathcal {C}_i=\{C_{i,1},C_{i,2},\ldots ,C_{i,k_i}\}$ of $V(F_i)\setminus D_i$ of cost at most $\rho _c\lambda$, while using $\lambda$, the complete subgraph $G_i$ of G induced by $V(F_i)\setminus D_i$ and $k_i>0$ as inputs. If no such $k_i$ exists, stop and return failure.

Step 2.2.:

Construct a bipartite graph $H_i=(U\cup D_i, E'_i)$, where $U=\{t_1,\ldots ,t_{k_i}\}$ represents the $k_i$ cycles in $\mathcal {C}_i (t_j$ corresponds to $C_{i,j})$ and $(t_j,r_l)\in E'_i$ if and only if $d(r_l,C_{i,j})\le \frac{\lambda }{2}$. Find a maximum matching $M_i$ on $H_i$.

Step 2.3.:

If $M_i$ matches all the vertices in U, i.e., $|M_i|=k_i$, then we can obtain a feasible cycle cover of $V(F_i)\setminus D_i$ as follows. For each $(t_j,r_l)\in M_i$ we add two copies of the edge in the original graph G that corresponds to $d(r_l,C_{i,j})$ and make a shortcut to derive a cycle $C'_{i,j}$ on $V(C_{i,j})\cup \{r_l\}$.

Step 2.4.:

If $M_i$ does not match all the vertices in U, i.e., $|M_i|<k_i$, choose any unmatched vertex $u\in U$ and determine the set S of vertices in $V(H_i)$ that can be reached by an alternating path starting from u. Let $U'=S\cap U$ and $D'=S\cap D_i$. Run the $\rho _c$-subroutine for $\lambda$ and the instance consisting of the complete subgraph induced by $\bigcup _{t_j\in U'}V(C_{i,j})$ and $|D'|>0$ to obtain a cycle cover of $\bigcup _{t_j\in U'}V(C_{i,j})$ of cost at most $\rho _c\lambda$. Update $\mathcal {C}_i$ by replacing the cycles corresponding to the vertices in $U'$ with the newly generated cycles. For simplicity the cycles in $\mathcal {C}_i$ are still denoted by $C_{i,1},C_{i,2},\ldots ,C_{i,k_i-1}$. Set $k_i:=k_i-1$ and go to Step 2.2.

Step 3.:

If $\sum _{i=1}^p k_i\le k$, return the cycle cover $C'_{1,1},\cdots ,C'_{1,k_1},\cdots \cdots ,C'_{p,1},\cdots ,$$C'_{p,k_p}$ of $V\setminus D$; otherwise, return failure.

Let $C^*_1,\,C^*_2,\,\ldots ,\,C^*_k$ be all the vertex-disjoint optimum cycles. By the triangle inequality, it is easy to verify that

Observation 1

If $OPT \le \lambda$, then $w(e)\le \frac{OPT}{2}\le \frac{\lambda }{2}$ for each $e\in \cup _{i=1}^k E(C^*_i)$.

By this observation the vertex set of each optimum cycle is contained entirely in exactly one of $V(F_1),V(F_2),\ldots ,V(F_p)$ when $OPT \le \lambda$. As a consequence, the optimum cycles whose vertex sets are contained in $V(F_i)$ constitute a cycle cover of $V(F_i)\setminus D_i$. Moreover, the cost of this cycle cover of $V(F_i)\setminus D_i$ is at most $OPT\le \lambda$ since the length of each optimum cycle is no more than OPT. Therefore, we have

Observation 2

If $OPT \le \lambda$, the optimum cycles can be partitioned into p groups such that the $i\mathrm{th}\ (i=1,2,\ldots ,p)$ group consisting of $k^*_i\ge 1$ optimum cycles is a cycle cover of $V(F_i)\setminus D_i$ with cost at most $\lambda$.

The performance of Algorithm $CRMMCCP(\rho _c)$ can be derived by the following lemma.

Lemma 5

If $OPT \le \lambda$, then

• (i) For any $v\in V\setminus D$, $d(v,D)\le \frac{OPT}{2}\le \frac{\lambda }{2}$;

• (ii) For each $i=1,2,\ldots ,p$, Step 2.1. returns a cycle cover of $V(F_i)\setminus D_i$ of cost at most $\rho _c\lambda$ and $k_i\le k^*_i$;

• (iii) For each $i=1,2,\ldots ,p$, whenever Step 2.4. is executed for $|M_i|<k_i$ it holds that $|D'|=|U'|-1\ge 1$ and the $\rho _c$-subroutine returns a cycle cover of $\bigcup _{t_j\in U'}V(C_{i,j})$ of cost at most $\rho _c\lambda$;

• (iv) Algorithm $CRMMCCP(\rho _c)$ returns a feasible cycle cover of cost at most $(\rho _c+1)\lambda$.

Proof

• (i) In the optimal solution, each vertex $v\in V\setminus D$ has to be contained in some optimum cycle, say $C^*_i$, of length at most OPT. $C^*_i$ must contain some vertex $d\in D$ and hence can be decomposed into two paths $P_1,P_2$ from v to d. By the triangle inequality, we have $d(v,D)\le \min \{w(P_1),w(P_2)\}\le \frac{OPT}{2}\le \frac{\lambda }{2}$.

• (ii) By Observation 2, there is a group of $k^*_i$ optimum cycles which is a cycle cover of $V(F_i)\setminus D_i$ of cost at most $OPT\le \lambda$. By shortcutting these cycles to eliminate vertices in $D_i$ we obtain a feasible cycle cover $\mathcal {C}$ for the instance I of MMCCP consisting of $G_i$ and $k^*_i$. Since the cost of $\mathcal {C}$ can not exceed $OPT\le \lambda$, the optimal value of I is also no more than $\lambda$. Therefore, by definition the $\rho _c$-subroutine with inputs $\lambda$ and I will return a cycle cover of $V(F_i)\setminus D_i$ of cost at most $\rho _c\lambda$. Using the fact that $k^*_i\le |D_i|$ and the minimality of $k_i$ we have proved this property.

• (iii) By the optimality of $M_i$ we have $D'=\varGamma _{H_i}(U')$ which is the set of vertices adjacent to some vertex of $U'$ in $H_i$ and $|U'|=|D'|+1$. Since $OPT\le \lambda$, we have $d(u,D)\le \frac{\lambda }{2}$ by (i) and hence u has at least one vertex in $D'$ adjacent to it, which implies $|D'|=|U'|-1\ge 1$. Given $D'=\varGamma _{H_i}(U')$, all the vertices in $\bigcup _{t_j\in U'}V(C_{i,j})$ can be covered by at most $|D'|$ optimum cycles. By shortcutting these optimum cycle to eliminate the vertices in $D'$ we obtain a cycle cover of $\bigcup _{t_j\in U'}V(C_{i,j})$ with at most $|D'|$ cycles and its cost does not exceed $\lambda$. This implies that the MMCCP instance consisting of the complete subgraph induced by $\bigcup _{t_j\in U'}V(C_{i,j})$ and $|D'|$ has an optimal value no more than $\lambda$. Therefore, the $\rho _c$-subroutine returns a desired cycle cover of $\bigcup _{t_j\in U'}V(C_{i,j})$ of cost at most $\rho _c \lambda$.

• (iv) By (i), (ii) the algorithm does not terminate in Step 1 and work correctly in Step 2.1. By (iii) the executions of Step 2.4. are correct. It can be observed that the number $k_i$ is strictly decreasing during the running of the algorithm. Once $k_i=1$ in Step 2.3. $M_i$ can match all the vertices in $U'$ and Step 2.4. is skipped. So the algorithm runs through to Step 3. Since $\sum _{i=1}^p k^*_i\le k$ and $k_i\le k^*_i$ by (ii) a feasible cycle cover will be returned. As for the cost of this cycle cover, it is sufficient to note that all the edges added to the unrooted cycles in Step 2.3. are of length no more than $\frac{\lambda }{2}$. $\square$

This lemma shows that Algorithm $CRMMCCP(\rho _c)$ is a $(\rho _c+1)$-subroutine for CRMMCCP. Combining this with Lemma 4, we have the following result.

Theorem 4

Given a $\rho _c$-subroutine for MMCCP, there is a $(\rho _c+1)$-approximation algorithm for CRMMCCP.

In Yu and Liu (2016), we have obtained a 5-subroutine for MMCCP running in $O(n^3)$ time for instances with n-vertex graphs. Plugging in this subroutine and using the $O(n^{2.5})$ time matching algorithm of Hopcroft and Karp (1973) for n-vertex bipartite graphs we deduce that the Algorithm $CRMMCCP(\rho _c)$ has a time complexity of $O(n^3 k)$ since the possible running of k subroutines dominates the complexity. Therefore we conclude that

Theorem 5

There is an $O(n^3 k \log \sum _{e\in E}w(e))$ time 6-approximation algorithm for CRMMCCP.

Given a $\rho$-approximation algorithm for TSP, we also devised a $4\rho$-subroutine for MMCCP in Yu and Liu (2016) that runs in polynomial time. Since Weighted Planar TSP admits a PTAS (Arora et al. 1998; Klein 2008), we have a $(4+\epsilon )$-subroutine for Weighted Planar MMCCP. For Graphic MMCCP, using the fact that a set of k connected subgraphs can be turned into a single connected subgraphs by adding $k-1$ unit-length edge one can show that the same subroutine in Yu and Liu (2016) always returns a cycle cover of cost at most $2\rho (\lambda +2)$ whenever $OPT\le \lambda$. By Lemma 2, we can assume $\lambda \ge 3$. This implies $2\rho (\lambda +2)\le \frac{10}{3}\rho \lambda$ and we have a $\frac{10}{3}\rho$-subroutine for Graphic MMCCP. By the results of Sebo and Vygen (2014), we can take $\rho =7/5$ for Graphic TSP. Using Theorem 4, we have improved the results for weighted planar or graphic cycle cover problem.

Corollary 1

For any $\epsilon >0$, there is a $(5+\epsilon )$-approximation algorithm for Weighted Planar CRMMCCP and a $(\frac{13}{3}+\epsilon )$-approximation algorithm for Planar CRMMCCP. For Graphic CRMMCCP, there exists a $\frac{17}{3}$-approximation algorithm.

4.2 Path cover

The framework to design approximation algorithms for CRMMPCP is similar to Algorithm $CRMMCCP(\rho _c)$ in the last section. However, in Step 1., we delete edges of length greater than $\lambda$ instead of $\frac{\lambda }{2}$. And in other steps, we construct a path (cover) instead of a cycle (cover). Given a $\rho _p$-subroutine for MMPCP, the algorithm accepts an instance of CRMMPCP consisting of the graph $G=(V,E)$ and $k>0$ and a value $\lambda \in [0,\sum _{e\in E}w(e)]$ as inputs.

Algorithm $CRMMPCP(\rho _p)$

Step 1.:

If $\max _{v\in V \setminus D}d(v,D) > \lambda$, stop and return failure. Otherwise, i.e., $\max _{v\in V \setminus D}d(v,D) \le \lambda$, delete all the edges with weight greater than $\lambda$ in G to obtain $G[\lambda ]$. Remove the connected components of $G[\lambda ]$ that contain no vertices in $V\setminus D$ and let the remaining p connected components be $F_1,F_2,\,\ldots ,F_p$.

Step 2.:

For each $i=1,2,\ldots ,p$,

Step 2.1.:

Let $D_i=V\cap V(F_i)=\{r_1,r_2,\ldots ,r_{|D_i|}\}$. Find the minimum integer $k_i$ with $1\le k_i\le |D_i|$ such that the $\rho _p$-subroutine for MMPCP outputs a path cover $\mathcal {P}_i=\{P_{i,1},P_{i,2},\ldots ,P_{i,k_i}\}$ of $V(F_i)\setminus D_i$ of cost at most $\rho _p\lambda$ using $\lambda$, the complete subgraph $G_i$ of G induced by $V(F_i)\setminus D_i$ and $k_i>0$ as inputs.

Step 2.2.:

Construct a bipartite graph $H_i=(U\cup D_i, E'_i)$, where $U=\{t_1,\ldots ,t_{k_i}\}$ represents the $k_i$ paths in $\mathcal {P}_i$ ($t_j$ corresponds to $P_{i,j}$) and $(t_j,r_l)\in E'_i$ if and only if $d(r_l,P_{i,j})\le \lambda$. Find a maximum matching $M_i$ on $H_i$.

Step 2.3.:

If $M_i$ matches all the vertices in U, i.e., $|M_i|=k_i$, then we can obtain a feasible path cover of $V(F_i)\setminus D_i$ as follows. For each $(t_j,r_l)\in M_i$, let $(u_j,r_l)$ be the edge in the original graph that corresponds to $d(r_l,P_{i,j})$. Denote by $v_j,w_j$ the two end vertices of $P_{i,j}$ such that $w(u_j,v_j)\le w(u_j,w_j)$. After adding edge $(u_j,r_l)$ to connect $r_l$ with $P_{i,j}$ and edge $(u_j,v_j)$, we can derive an Eulerian path from $r_l$ to $w_j$ that goes through $\{r_l\}\cup V(P_{i,j})$. By shortcutting this path, we obtain a path $P'_{i,j}$ with one end vertex $r_l\in D$ covering all the vertices in $V(P_{i,j})$.

Step 2.4.:

If $M_i$ does not match all the vertices in U, i.e., $|M_i|<k_i$, choose any unmatched vertex $u\in U$ and determine the set S of vertices in $V(H_i)$ that can be reached by an alternating path starting from u. Let $U'=S\cap U$ and $D'=S\cap D_i$. Run the $\rho _p$-subroutine for $\lambda$ and the instance consisting of the complete subgraph induced by $\bigcup _{t_j\in U'}V(P_{i,j})$ and $|D'|>0$ to obtain a path cover of $\bigcup _{t_j\in U'}V(P_{i,j})$ of cost at most $\rho _p\lambda$. Update $\mathcal {P}_i$ by replacing the paths corresponding to the vertices in $U'$ with the newly generated paths. For simplicity the paths in $\mathcal {P}_i$ are still denoted by $P_{i,1},P_{i,2},\ldots ,P_{i,k_i-1}$. Set $k_i:=k_i-1$ and go to Step 2.2.

Step 3.:

If $\sum _{i=1}^p k_i\le k$, return the path cover $P'_{1,1},\cdots ,P'_{1,k_1},\cdots \cdots ,P'_{p,1},\cdots ,$$P'_{p,k_p}$ of $V\setminus D$; otherwise, return failure.

Let $P^*_1,\,P^*_2,\,\ldots ,\,P^*_k$ be all the vertex-disjoint optimum paths. We have two observations similar to the cycle cover problem.

Observation 3

If $OPT \le \lambda$, then $w(e)\le OPT\le \lambda$ for each $e\in \cup _{i=1}^k E(P^*_i)$.

Observation 4

If $OPT \le \lambda$, the optimum paths can be partitioned into p groups such that the $i { th}\ (i=1,2,\ldots ,p)$ group consisting of $k^{*}_{i}{\ge } 1$ optimum paths is a path cover of $V(F_i){\setminus }D_i$ with cost at most $\lambda$.

Based on these facts and an analogous proof to Lemma 5 we have

Lemma 6

If $OPT \le \lambda$, then Algorithm $CRMMCCP(\rho _p)$ returns a feasible path cover of cost at most $(\frac{3}{2}\rho _p+1)\lambda$.

By the results of Arkin et al. (2006), there is an $O(n^2)$ time $\rho _p$-subroutine with $\rho _p=4$. This implies

Theorem 6

There is an $O(n^{2.5}k\log \sum _{e\in E}w(e))$ time 7-approximation algorithm for CRMMPCP.

Again one can show that for graphic instances, the subroutine in Arkin et al. (2006) returns a path cover of cost at most $2(\lambda +1)$ whenever $OPT\le \lambda$. By Lemma 2, we may assume that $\lambda \ge 2$ and hence $2(\lambda +1)\le 3\lambda$. So we have a 3-subroutine for Graphic MMPCP, which implies by Lemma 6 that

Corollary 2

There is an $\frac{11}{2}$-approximation algorithm for Graphic CRMMPCP.

4.3 Tree cover

For any $V'\subseteq V$, a cycle (path) cover of cost at most $\lambda$ can be transformed into a cycle (path) cover of $V'$ of cost at most $\lambda$ by shortcuting the vertices of $V\setminus V'$, since the vertices in a cycle (path) are of degree no more than 2. This transformation cannot be conducted directly for a tree cover since the degree of the vertices of a tree can be greater than 2. However, by doubling the edges of a tree cover of cost at most $\lambda$ we first obtain a cycle cover of cost at most $2\lambda$. After that we can shortcut the vertices of $V\setminus V'$ and delete one edge from each cycle to obtain a path cover of $V'$ (and hence a tree cover of $V'$) of cost no greater than $2\lambda$.

Due to this subtle difference, we obtain an algorithm for CRMMTCP as follows. First, we replace paths with trees in Algorithm $CRMMPCP(\rho _p)$ and change $\rho _p$-subroutine for MMPCP to $\rho _t$-subroutine for MMTCP. In Step 2.1. and Step 2.4. whenever running the subroutine for MMTCP, we also replace the value $\lambda$ with $2\lambda$. As a consequence, we obtain a tree cover of cost at most $2\rho _t\lambda$. In addition, in Step 2.3. the construction of a tree cover is simplified to connect each matched root to the corresponding tree by the edge in $M_i$. One can verify that this procedure is a $(2\rho _t+1)$-subroutine for CRMMTCP. Since Khani and Salavatipour (2014) derived an $O(n^5)$ time 3-subroutine for MMTCP, we have the following result.

Theorem 7

There is an $O(n^5 k \log \sum _{e\in E}w(e))$ time 7-approximation algorithm for CRMMTCP.