Polynomial-Time Constant-Approximation for Fair Sum-Of-Radii Clustering

In our work, we prove two theorems resolving Questions 1 and 2 in the affirmative. First, we prove the following theorem.

Our result complements the FPT approximation result of Carta et al. [15] by achieving the first $O(1)$-approximation for the problem in polynomial time. The result also implies a poly-time $O(1)$-approximation for Euclidean $(t,k)$-fair sum-of-radii, for which only an FPT $(1+ϵ)$-approximation was known [24]. We note that our result should also be compared with that of $(t,k)$-fair $k$-median for which only $O(t)$-approximation is known in polynomial time. In particular, our result places sum-of-radii in the same group of objectives as $k$-center that admits polynomial-time $O(1)$-approximations. Moreover, our result shows that $(t,k)$-fair sum-of-radii is in contrast to most of the constrained versions of sum-of-radii, including capacitated clustering, for which only FPT $O(1)$-approximations are known.

Next, we give an overview of our approach. Our approximation algorithm is motivated by the algorithms for $(t,k)$-fair center and $(t,k)$-fair median [20]. These algorithms have two major steps. In the first step, a fairlet decomposition of the points in $X=P_1\cup P_2$ is computed, i.e., a partition $𝒴=\{Y_1,\mathrm{\dots },Y_m\}$ such that for each fairlet $Y_i$, it either has 1 red point and at most $t$ blue points or 1 blue point and at most $t$ red points. Let $\beta :P_1\cup P_2\to [m]$ be the function that maps each point $x$ to the index of the fairlet that contains $x$. From each $Y_i$, an arbitrary point $y_i$ is designated as its representative. In the second step, a clustering of these $m$ representatives is computed with the respective cost function. Also, for each $Y_i$, all of its points are assigned to the cluster that contains $y_i$. The new clustering is obviously $(t,k)$-fair, as each cluster is a merger of fairlets. For the analysis of the cost of the computed clustering, they define a fairlet decomposition cost, which is used to bound the assignment cost of the points in the second step. For $k$-center, this cost is ${\max }_{x\in X}d(x,y_{\beta (x)})$, and for $k$-median, it is ${\sum }_{x\in X}d(x,y_{\beta (x)})$. Indeed, both of these costs when optimal are comparable to the optimal $(t,k)$-fair clustering cost. For $k$-center, it is within a constant factor, and for $k$-median it is within an $O(t)$ factor. Then, it is sufficient to compute a fairlet decomposition in the first step whose cost is within a small constant-factor of the optimal fairlet decomposition cost.

Coming back to $(t,k)$-fair sum-of-radii, it is not clear how to define a suitable fairlet decomposition cost that can be compared to the optimal $(t,k)$-fair sum-of-radii cost. In particular, such a cost needs to be defined independent of the number of clusters $k$. However, for sum-of-radii, the objective is the sum of radii of $k$ clusters. For example, a natural candidate, the cost for $k$-median, i.e., ${\sum }_{x\in X}d(x,y_{\beta (x)})$, is likely to be much larger than the optimal sum-of-radii cost. In the absence of such a suitable fairlet decomposition cost, it is difficult to argue the increase in the assignment cost, when actual points of $Y_i$ are assigned instead of just the representative $y_i$.

In the following, we are going to prove Lemma 6. Consider the min-cost DCS $H=(V,E^{\prime })$ computed in Step 1. Also, consider the optimal clusters in ${𝒞}^{\ast }$. We construct a new clustering $\widehat{𝒞}=\{{\widehat{C}}_1,{\widehat{C}}_2,\mathrm{\dots },{\widehat{C}}_{\kappa }\}$ by merging clusters in ${𝒞}^{\ast }$ in the following way, where $1\le \kappa \le k$. Initially, we set $\widehat{𝒞}$ to ${𝒞}^{\ast }$. For each edge $\{p,q\}$ of $E^{\prime }$ such that $p\in {\widehat{C}}_i,q\in {\widehat{C}}_j$ and $i\ne j$, replace ${\widehat{C}}_i,{\widehat{C}}_j$ in $\widehat{𝒞}$ by their union and denote it by ${\widehat{C}}_i$ as well.

When the above merging procedure ends, by renaming the indexes, let $\widehat{𝒞}=\{{\widehat{C}}_1,{\widehat{C}}_2,\mathrm{\dots },{\widehat{C}}_{\kappa }\}$ be the new clustering. Then, we have the following observation.

Consider the clustering ${𝒞}^{\prime }=\{C_1^{\prime },\mathrm{\dots },C_{\kappa }^{\prime }\}$ of ${\mathrm{\Omega }}^{\prime }$ defined in the following way. For each star $S$ in $H$, identify the cluster ${\widehat{C}}_i$ in $\widehat{𝒞}$ that contains all the points in $S$. By Observation 8, such an index $i$ exists. Assign the point $p$ in ${\mathrm{\Omega }}^{\prime }$ corresponding to $S$ to $C_i^{\prime }$.

We will prove the following lemma.

Lemma 6 follows by Lemma 9 and 10 noting that the Algorithm of Buchem et al. [14] yields a $(3+ϵ)$-factor approximation to the optimal clustering (along with an appropriate scaling of $ϵ$). In the rest of this section, we prove Lemma 10.

For simplicity of notation, we drop $(\mathrm{\Omega },d)$ from $r_{(\mathrm{\Omega },d)}(.)$, as henceforth centers are always assumed to be in $\mathrm{\Omega }$ and the metric to be $d$. Let us consider any fixed ${\widehat{C}}_i$, and suppose it is constructed by merging the clusters $C_{i_1}^{\ast },C_{i_2}^{\ast },\mathrm{\dots },C_{i_{\tau }}^{\ast }$. It is sufficient to prove that $r({\widehat{C}}_i)\le 8\cdot {\sum }_{j=1}^{\tau }r(C_{i_j}^{\ast })$. For simplicity of notation, we rename ${\widehat{C}}_i$ by $\widehat{C}$, and $C_{i_1}^{\ast },C_{i_2}^{\ast },\mathrm{\dots },C_{i_{\tau }}^{\ast }$ by $C_1^{\ast },C_2^{\ast },\mathrm{\dots },C_{\tau }^{\ast }$.

Let $H_1=(V_1,E_1)$ be the induced subgraph of $H$ such that the vertices of $V_1$ are in $\widehat{C}$. We refer to a point of $P_1$ (resp. $P_2$) as a red (resp. blue) point. Note that the edges of $H$ are across red and blue points. In the following, we construct an edge-weighted, directed multi-graph $G^{\ast }=(V^{\ast },E^{\ast })$ in the following manner. $G^{\ast }$ has a vertex $v_j$ corresponding to each cluster $C_j^{\ast }$, where $1\le j\le \tau$. There is an edge $e=(v_i,v_j)$ from $v_i$ to $v_j$ for each $p\in P_1\cap C_i^{\ast }$ and $q\in P_2\cap C_j^{\ast }$ such that $\{p,q\}$ is in $E_1$. We refer to such an edge as a $0$-edge, i.e., its parity is 0. The weight ${\omega }_e$ of the edge $e$ is $d(p,q)$. Similarly, there is a $1$-edge (or parity 1 edge) $e=(v_i,v_j)$ from $v_i$ to $v_j$ for each $p\in P_2\cap C_i^{\ast }$ and $q\in P_1\cap C_j^{\ast }$ such that $\{p,q\}$ is in $E_1$. The weight ${\omega }_e$ of the edge $e$ is $d(p,q)$. For each edge $e_i\in E^{\ast }$, we denote the corresponding edge in $E_1$ by $\{r_i,b_i\}$, where $r_i$ is the red point and $b_i$ is the blue point. For simplicity of exposition, we are going to make heavy use of this correspondence.

A directed path (or simply a path) $\pi =\{u_1,\mathrm{\dots },u_l\}$ from $u_1$ to $u_l$ in $G^{\ast }$ is a sequence of distinct vertices such that $(u_i,u_{i+1})$ is in $G^{\ast }$ for all $1\le i\le l-1$. We say that $\pi$ contains the edges $(u_i,u_{i+1})$. If $\pi$ contains all 0-edges (resp. 1-edges), it is called a 0-path (resp. 1-path). Two consecutive edges $e_1=(u_i,u_{i+1}),e_2=(u_{i+1},u_{i+2})$ on $\pi$ are said to form a switch if they have different parity. We say that the switch happens at $u_{i+1}$ and it is the corresponding switching vertex. The switch is called a $b$-switch if the parity of $e_1$ is $b$ for $b\in \{0,1\}$. A directed cycle is formed from $\pi$ by adding the edge $(u_l,u_1)$ (if any) with it. The reverse path of $\pi$ is the path $\{u_l,\mathrm{\dots },u_1\}$ that contains the edges $(u_{i+1},u_i)$ for all $1\le i\le l-1$. Such edges exist according to Observation 11. A 0-path (resp. 1-path) in a subgraph of $G^{\ast }$ starting at $v_i$ and ending at $v_j$ is called maximal if $v_j$ does not have any outgoing 0-edges (resp. 1-edges) in the subgraph.

Consider any two vertices $v_{\alpha }$ and $v_{\beta }$ of $G^{\ast }$. Let ${\pi }^{\ast }=\{v_{\alpha }=u_1,\mathrm{\dots },u_l=v_{\beta }\}$ be a directed path from $v_{\alpha }$ to $v_{\beta }$ having the minimum number of switches, i.e., a minimum-switch path from $v_{\alpha }$ to $v_{\beta }$.

We prove the following lemma.

Before proving this lemma, we show how to prove Lemma 10. Consider any point $p$ in ${\widehat{C}}_j$. Let $p\in C_g^{\ast }$. Now, consider any point $q$ in ${\widehat{C}}_j$ that is the farthest point from $p$. Let $q\in C_h^{\ast }$. By Lemma 13 it follows that, there is a path, say ${\pi }^{\prime }$, from $v_g$ to $v_h$ whose sum of the edge weights is at most $6\cdot {\sum }_{i=1}^{\tau }r(C_i^{\ast })$. Then, $r({\widehat{C}}_j)\le d(p,q)\le {\sum }_{e\in {\pi }^{\prime }}{\omega }_e+{\sum }_{\text{vertex }{v}_i\in {\pi }^{\prime }}2\cdot r(C_i^{\ast })\le 8\cdot {\sum }_{i=1}^{\tau }r(C_i^{\ast }).$

Summing over all clusters ${\widehat{C}}_j$ in $\widehat{𝒞}$, we obtain Lemma 10.

The overall idea is to show the existence of a subset of edges $E_2^{\prime }\subset E$, such that the set of edges $(E^{\prime }\setminus {\pi }^{\ast })\cup E_2^{\prime }$ form a valid degree-constrained subgraph of $G$ on the set of vertices $P_1\cup P_2$. Additionally, we need that the total weight of the edges of $E_2^{\prime }$ is small. Then we can show that the weight of ${\pi }^{\ast }$ is also small, as $H=(V,E^{\prime })$ is a min-cost DCS of $G$. However, it might not be possible to remove only the edges of ${\pi }^{\ast }$ from $E^{\prime }$ to show the existence of such a set $E_2^{\prime }$. We show that there is a subset $E_1^{\prime }\subseteq E^{\prime }$ that contains the edges of ${\pi }^{\ast }$ and can be removed to obtain such a valid degree-constrained subgraph. In the following, we prove that obtaining two such sets $E_1^{\prime }$ and $E_2^{\prime }$ is sufficient to prove Lemma 13. For a set of edges $S\subseteq E$, let $w(S)={\sum }_{e\in S}w(e)$.

Two subgraphs $G_1$ and $G_2$ of $G^{\ast }$ are called 0-1-edge-disjoint if for any edge $e_{{\eta }^1}$ of $G_1$ and $e_{{\eta }^2}$ of $G_2$, the corresponding edges in $E^{\prime }$ are distinct. Thus, if $G_1$ contains a 0-edge $(v_i,v_j)$, and $G_1$ and $G_2$ are 0-1-edge-disjoint, then $G_2$ cannot contain the 0-edge $(v_i,v_j)$ and the 1-edge $(v_j,v_i)$. Similarly, if $G_1$ contains a 1-edge $(v_i,v_j)$, and $G_1$ and $G_2$ are 0-1-edge-disjoint, then $G_2$ cannot contain the 1-edge $(v_i,v_j)$ and the 0-edge $(v_j,v_i)$. Let be the indexes of the vertices on ${\pi }^{\ast }=\{u_1,\mathrm{\dots },u_l\}$ where the switches occur. Note that . Denote the switch that occurs at $u_{j^h}$ by $b^h$ for all $1\le h\le \lambda$ (i.e., $b^h$ is the parity of $(u_{j^h-1},u_{j^h})$). Let $b^0$ be the parity of $(u_1,u_2)$ and $b^{\lambda +1}$ be the parity of $(u_{l-1},u_l)$.

First, we consider the simple case when the parity of $\mathbf{(}{u}_{l\mathbf{-}\mathrm{𝟏}}\mathbf{,}{u}_l\mathbf{)}$ is 0 (resp. 1) and there is a 0-path (resp. 1-path) from $u_l$ to $u_{\mathrm{𝟏}}$ in $G^{\mathbf{\ast }}$ that is 0-1-edge-disjoint from ${\pi }^{\mathbf{\ast }}$. Let us denote the latter path by $\pi (l)$. Note that ${\pi }^{\ast }$ is a path having the minimum number of switches and the existence of $\pi (l)$ ensures that ${\pi }^{\ast }$ does not have a switch. Let $U_0\subseteq E^{\ast }$ be the subset of edges that lie on the paths in $\{{\pi }^{\ast }\}\cup \{\pi (l)\}$. Next, we define a subset $E_1^{\prime }\subseteq E_1$ that has a one-to-one mapping with $U_0$. In particular, consider any edge $(v_i,v_j)$ in $U_0$. Note that if it is a $0$-edge, it was added due to an edge $\{p,q\}$ in $E_1$ such that $p\in P_1\cap C_i^{\ast }$ and $q\in P_2\cap C_j^{\ast }$. We add the edge $\{p,q\}$ to $E_1^{\prime }$. Otherwise, if $(v_i,v_j)$ is a $1$-edge, it was added due to an edge $\{p,q\}$ in $E_1$ such that $p\in P_2\cap C_i^{\ast }$ and $q\in P_1\cap C_j^{\ast }$. In this case, we add the edge $\{p,q\}$ to $E_1^{\prime }$.

Next, we show the construction of $E_2^{\prime }$. Wlog, let us assume that ${\pi }^{\ast }$ is a 0-path. The other case is symmetric. Note that then $\pi (l)$ is also a 0-path as per our assumption. First, we describe the process of adding the replacement edges for the path ${\pi }^{\ast }$. Consider any intermediate vertex (if any) $v_{j^{\prime }}$ on this path. Then, there are exactly two points in $C_{j^{\prime }}^{\ast }$ corresponding to the edges on ${\pi }^{\ast }$, which are of opposite colors. We add an edge between these two points in $E_2^{\prime }$ (see Figure 1). Removal of the edges of $E_1^{\prime }$ corresponding to ${\pi }^{\ast }$ and the addition of this edge do not change the degree of the two points in $C_{j^{\prime }}^{\ast }$. Similarly, we add edges to $E_2^{\prime }$ corresponding to the intermediate vertices of $\pi (l)$. Next, consider the vertex $u_l=v_i$. There is an incoming 0-edge on ${\pi }^{\ast }$ and an outgoing 0-edge on $\pi (l)$ that are incident on $v_i$. Thus, there are exactly two points in $C_i^{\ast }$ of opposite colors corresponding to these two edges. We add an edge between these two points in $E_2^{\prime }$. Removal of the edges of $E_1^{\prime }$ corresponding to those two edges, and the addition of this edge does not change the degree of the two points in $C_i^{\ast }$. Similarly, consider the vertex $u_1=v_i^{\prime }$. There is an outgoing 0-edge on ${\pi }^{\ast }$ and an incoming 0-edge on $\pi (l)$ that are incident on $v_i^{\prime }$. Thus, there are exactly two points in $C_{i^{\prime }}^{\ast }$ of opposite colors corresponding to these two edges. We add an edge between these two points in $E_2^{\prime }$. Again, the removal of the edges of $E_1^{\prime }$ corresponding to those two edges, and the addition of this edge does not change the degree of the two points in $C_{i^{\prime }}^{\ast }$. See Figure 1 for an illustration.

By our construction, the set of edges $(E^{\prime }\setminus E_1^{\prime })\cup E_2^{\prime }$ form a valid degree-constrained subgraph of $G$ on the set of vertices $P_1\cup P_2$. The way we add the edges to $E_2^{\prime }$, both endpoints of each edge lie in a cluster $C_j^{\ast }$ such that the vertex $v_j$ corresponding to the cluster lies on a path in $\{{\pi }^{\ast }\}\cup \{\pi (l)\}$. Now, $v_j$ can lie either on one such path or on two paths. Thus, we add at most two edges to $E_2^{\prime }$ corresponding to $v_j$. The sum of the weights of these two edges is at most 2 times the diameter of $C_j^{\ast }$. Hence, by Lemma 14, we obtain ${\sum }_{e\in {\pi }^{\ast }}{\omega }_e\le 4\cdot {\sum }_{i=1}^{\tau }r(C_i^{\ast }).$

Next, we consider the remaining case when the parity of $\mathbf{(}{u}_{l\mathbf{-}\mathrm{𝟏}}\mathbf{,}{u}_l\mathbf{)}$ is 0 (resp. 1) and there is no 0-path (resp. 1-path) from $u_l$ to $u_{\mathrm{𝟏}}$ in $G^{\mathbf{\ast }}$ that is 0-1-edge-disjoint from ${\pi }^{\mathbf{\ast }}$. Thus, there is no $b^{\lambda +1}$-path from $u_l$ to $u_1$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$.

Consider a path $\pi$ and let $v_i$ denote its start vertex. Also, consider a cycle $O$ such that $\pi$ and $O$ have exactly one vertex $v_j$ in common. Note that $\pi$ might not have an edge, in which case $v_j=v_i$. Let $D$ be the graph formed by the union of $\pi$ and $O$, i.e., by gluing them together at $v_j$. We refer to such a graph $D$ as a hanging cycle for $v_i$ with $v_j$ being the join vertex. $D$ is called a $b$-hanging cycle if all the edges of $\pi$ and $O$ are $b$-edges. Let $p$ be the point in the cluster $C_j^{\ast }$ corresponding to the edge of the cycle $O$ incoming to $v_j$. Additionally, $D$ is called special if the degree of $p$ in $H_1$ is at least 2, and $p$ is called the special point of $D$ (see Figure 2).

In the current case, we need the following lemmas.

Next, we apply the above lemmas to show the construction of $E_1^{\prime }$ and $E_2^{\prime }$. Recall that in this case there is no $b^{\lambda \mathbf{+}\mathrm{𝟏}}$-path from $u_l$ to $u_{\mathrm{𝟏}}$ in $G^{\mathbf{\ast }}$ that is 0-1-edge-disjoint from ${\pi }^{\mathbf{\ast }}$. If ${\pi }^{\ast }$ has a switch, then there is no 0-path or 1-path from $u_l$ to $u_1$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$. Otherwise, it must be that $b^0=b^{\lambda +1}$, and hence by our assumption, there is no $b^0$-path from $u_l$ to $u_1$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$. We conclude that in this case ($b^0=b^{\lambda +1}$), there is no $b^0$-path from $u_l$ to $u_1$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$. Then, by Lemma 16 it follows that, either there is a $(1-b^0)$-hanging cycle for $u_1$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$, or a $(1-b^0)$-path starting from $u_1$ in $G^{\ast }$ with special properties. This is true, as the parity of $(u_1,u_2)$ is $b^0$. We denote this structure by $\pi (0)$. Additionally, if $\pi (0)$ is a path, we call $b_{\eta }$ (resp. $r_{\eta }$) an anchor point if its degree in $H_1$ is at least 2. Similarly, by Lemma 15 it follows that, either there is a $b^{\lambda +1}$-hanging cycle for $u_l$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$, or a $b^{\lambda +1}$-path starting from $u_l$ in $G^{\ast }$ with special properties. This is true, as $(u_{l-1},u_l)$ is a $b^{\lambda +1}$-edge. We denote this structure by $\pi (\lambda +1)$. Additionally, if $\pi (\lambda +1)$ is a path, we call $b_{\eta }$ (resp. $r_{\eta }$) an anchor point if its degree in $H_1$ is at least 2.

Now, if $\mathrm{𝟏}-{𝐛}^{\mathrm{𝟎}}\ne {𝐛}^{\lambda +\mathrm{𝟏}}$, then $\pi (0)$ and $\pi (\lambda +1)$ must be vertex-disjoint. If they are not vertex-disjoint, there exists a $b^{\lambda +1}$-path from $u_l$ to $u_1$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$: take the edges on $\pi (\lambda +1)$ from $u_l$ to a common vertex and the reverse of $\pi (0)$, from the common vertex to $u_1$. These reverse edges have parity opposite of $1-b^0$, i.e., the same as $b^{\lambda +1}$. But, by our assumption, such a $b^{\lambda +1}$-path does not exist. Hence, $\pi (0)$ and $\pi (\lambda +1)$ are vertex-disjoint.

In the other case, $\mathrm{𝟏}-{𝐛}^{\mathrm{𝟎}}={𝐛}^{\lambda +\mathrm{𝟏}}$. We note that if ${\pi }^{\ast }$ has no switch, $b^0=b^{\lambda +1}$. Thus, if $1-b^0=b^{\lambda +1}$, then we can safely assume that ${\pi }^{\ast }$ has at least one switch. In this case, suppose there are a $(1-b^0)$-hanging cycle for $u_1$ and a $b^{\lambda +1}$-hanging cycle for $u_l$ in $G^{\ast }$, such that both are 0-1-edge-disjoint, each of the hanging cycles is 0-1-edge-disjoint from ${\pi }^{\ast }$, and either the special vertices of both are distinct or the special points are the same and the degree of that point in $H_1$ is at least 3. Then, we take the hanging cycle for $u_1$ as $\pi (0)$ and the one for $u_l$ as $\pi (\lambda +1)$. Otherwise, if there is a $(1-b^0)$-hanging cycle for $u_1$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$ or a $b^{\lambda +1}$-hanging cycle for $u_l$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$, we consider one of those. Assume that the former holds. The other case is symmetric. We take such a hanging cycle for $u_1$ as $\pi (0)$. Then, one can prove that there is a $b^{\lambda +1}$-path from $u_l$ in $G^{\ast }$ with special properties (Lemma 8 in the full version). We take this $b^{\lambda +1}$-path as $\pi (\lambda +1)$. Otherwise, there is neither a $(1-b^0)$-hanging cycle for $u_1$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$ nor a $b^{\lambda +1}$-hanging cycle for $u_l$ in $G^{\ast }$ 0-1-edge-disjoint from ${\pi }^{\ast }$. Then, one can prove that there are two 0-1-edge-disjoint paths with parity $1-b^0=b^{\lambda +1}$, from $u_1$ and $u_l$, respectively, such that both are also 0-1-edge-disjoint from ${\pi }^{\ast }$ (Lemma 9 in the full version). In this case, we take the path from $u_1$ as $\pi (0)$ and the path from $u_l$ as $\pi (\lambda +1)$.

For all $1\le h\le \lambda$, if there are two 0-1-edge-disjoint $b^h$-hanging cycles for $u_{j^h}$ in $G^{\ast }$ that are 0-1-edge-disjoint from ${\pi }^{\ast }$ and have distinct special points or the same special point of degree at least 3 in $H_1$, denote them by ${\pi }_1(h)$ and ${\pi }_2(h)$. Otherwise, if there is one $b^h$-hanging cycle for $u_{j^h}$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$, denote it by ${\pi }_1(h)$. Now, $(u_{j^h-1},u_{j^h})$ is a $b^h$-edge and $(u_{j^h},u_{j^h+1})$ is a $(1-b^h)$-edge. Then, one can prove that there is a $b^h$-path starting from $u_{j^h}$ in $G^{\ast }$ with special properties (Lemma 8 in the full version). Denote this path by ${\pi }_2(h)$. Otherwise, there is no $b^h$-hanging cycle for $u_{j^h}$ in $G^{\ast }$ that is 0-1-edge-disjoint from ${\pi }^{\ast }$. In this case, one can prove that there are two $b^h$-paths starting from $u_{j^h}$ in $G^{\ast }$ with special properties. Denote them by ${\pi }_1(h)$ and ${\pi }_2(h)$. Note that in all the cases, $\pi ()$, ${\pi }_1()$ or ${\pi }_2()$ can either be a path or a hanging cycle.