Proof of 1. Reduction. Let \({\mathcal{I}}= (\mathcal{U},\mathcal{F},k,D)\) be an instance of wpSC. Let \(\mathcal{U}\) consist of the items \(u_1,\dots,u_s\) and let \(\mathcal{F}\) contain the sets \(F_1,\dots,F_t\). We may assume that for each \(u_i\) there is a set \(F_j\) which contains \(u_i\). We define an instance \({\mathcal{I}}' = ({\mathcal{N}},k,D')\) of MapPD as follows. Let \(k' = k\) and define \(D' := D\cdot Q + 1\) for \(Q := t(s+1)\). We define a network \(\mathcal{N}\) with leaves \(x_1,\dots,x_t\), and additional vertices \(\rho,v_1,\dots,v_s,w_1,\dots,w_t\).

Let the set of edges in \(\mathcal{N}\) consist of the edges \((\rho,v_{i})\) for \(i\in [s]\), \((w_j,x_j)\) for \(j\in [t]\), and let \((v_i,w_j)\) be an edge if and only if \(u_i \in F_j\). We define the weight of \((\rho,v_i)\) to be \({\omega}(u_i) \cdot Q\) for each \(i\in [s]\) and 1 for each other edge. 1 depicts an example of this reduction.

This completes the construction of instance \({\mathcal{I}}'\) in Case [it:P-62Mweighted] of the theorem. We now describe how to construct an instance \({\mathcal{I}}_2'\) from \({\mathcal{I}}'\) in which the weight of each edge is 1, completing the construction for Case [it:P-62Munweighted]. For each edge \(e=(\rho,v_i)\) with \(w(e) > 1\), make \({\omega}(e)-1\) subdivisions and attach a new leaf as the child of each subdividing vertex. We call these newly-added leaves false leaves, and we call the other leaves of \(\mathcal{N}\)true leaves.

Correctness. The instance \({\mathcal{I}}'\) is computed in time polynomial in \(|\mathcal{U}|+|\mathcal{F}|\) and the instance \({\mathcal{I}}_2'\) is computed in time polynomial in \(|\mathcal{U}|+|\mathcal{F}|+\max_{\omega}\). Clearly, in \({\mathcal{I}}'\) we observe \(k'=k\) and \(|X|={\mathop{\mathrm{{ret}}}_{{\mathcal{N}}}}=|\mathcal{F}|\) and in \({\mathcal{I}}_2'\) we observe \(k'=k\) and \(\max_{\omega'}=1\). It remains to show the equivalence of the instances.

Without loss of generality, let \(S:=\{F_{1},\dots,F_{\ell}\}\) with \(\ell\le k\) be a solution for wpSC on the instance \(\mathcal{I}\) that covers the items \(u_1,\dots,u_p\). That is, we assume \(S\) consists of the first \(\ell\) sets in \(\mathcal{F}\) and they cover the first \(p\) elements in \(\mathcal{U}\). We show that \(Y:=\{x_{1},\dots,x_{\ell}\}\) is a solution for MapPD on the instances \({\mathcal{I}}'\) and \({\mathcal{I}}_2'\). Clearly, the size of \(Y\) is at most \(k'\). Now consider the phylogenetic diversity of \(Y\) in the network of \({\mathcal{I}}'\). Let \(\hat{E}\) be the edges in \(\mathcal{N}\) between two vertices of \(v_1,\dots,v_p,w_1,\dots,w_\ell\). Then \[\begin{align} {PD_{{\mathcal{N}}}}(Y) &=& \sum_{i=1}^\ell {\omega}'((w_i,x_i)) + \sum_{e\in \hat{E}} {\omega}'(e) + \sum_{i=1}^p {\omega}'((\rho,v_i)) \ge {\omega}'((w_1,x_1)) + \sum_{i=1}^p {\omega}'((\rho,v_i))\\ &=& 1 + \sum_{i=1}^p {\omega}(u_i)\cdot Q = 1 + Q \cdot \sum_{i=1}^p {\omega}(u_i) \ge 1 + QD = D'. \end{align}\] Here, the first equality holds because the sets in \(S\) cover the items \(u_1,\dots,u_p\) and the last inequality holds because \(S\) is a solution. It is easy to see that the phylogenetic diversity of the set \(Y\) in the network of \({\mathcal{I}}_2'\) is identical. Hence, \(Y\) is a solution for MapPD on \({\mathcal{I}}'\) and \({\mathcal{I}}_2'\).

We now show that the existence of a solution for MapPD on \({\mathcal{I}}'\) or \({\mathcal{I}}_2'\) implies the existence of a solution for wpSC on \({\mathcal{I}}\). Without loss of generality, let \(Y:=\{x_1,\dots,x_\ell\}\) with \(\ell\le k\) be a solution for MapPD on instance \({\mathcal{I}}'\). We show that \(S:=\{F_1,\dots,F_\ell\}\) is a solution for wpSC on instance \(\mathcal{I}\). Clearly, the size of \(S\) is at most \(k\). Without loss of generality, let \(v_1,\dots,v_p\) be the ancestors of \(Y\) that are children of \(\rho\). Thus, there is a path from \(v_i\) to a taxon \(x_j\in Y\), for each \(i\in [p]\). By the construction of \({\mathcal{I}}'\), we conclude \(u_i \in F_j\). Again, let \(\hat{E}\) be the edges between two vertices of \(v_1,\dots,v_p,w_1,\dots,w_\ell\). We have \(D' \le {PD_{{\mathcal{N}}}}(Y) = \sum_{i=1}^\ell {\omega}'((w_i,x_i)) + \sum_{e\in \hat{E}} {\omega}'(e) + \sum_{i=1}^p {\omega}'((\rho,v_i)) \le t + st + \sum_{i=1}^p {\omega}'((\rho,v_i))\). Consequently, \(\sum_{i=1}^p Q\cdot {\omega}(u_i) = \sum_{i=1}^p {\omega}'((\rho,v_i)) \ge D' - Q = Q(D-1) + 1\). We conclude that \(\sum_{i=1}^p {\omega}(u_i) \ge D-1 + 1/Q\). Since the weights of \(u_i\) are integers, it follows that \(\sum_{i=1}^p {\omega}(u_i) \ge D\).

It remains to show that for each solution \(Y\) for MapPD on instance \({\mathcal{I}}_2'\), an equivalent solution for MapPD on instance \({\mathcal{I}}'\) exists. If \(Y\) does not contain false leaves, then as previously observed, the phylogenetic diversity of \(Y\) is the same in \({\mathcal{I}}'\) as in \({\mathcal{I}}_2'\). Assume now otherwise and let \(z\) be a false leaf in \(Y\) and let \(p_z\) be the parent of \(z\). We consider two different cases, \(p_z\) has an offspring in \(Y\setminus\{z\}\), or not. In the former case, we observe \({PD_{{\mathcal{N}}}}(Y) = {PD_{{\mathcal{N}}}}(Y\setminus\{z\}) + {\omega}((p_z,z)) = {PD_{{\mathcal{N}}}}(Y\setminus\{z\}) + 1\). Consequently, we can replace \(z\) with any true leaf that is not yet in \(Y\) to receive another solution for MapPD on \({\mathcal{I}}_2'\). In the second case, let the true leaf \(x_i\) be an offspring of \(p_z\). Because of the assumption, \(x_i\not\in Y\). Then, \({PD_{{\mathcal{N}}}}(Y) - {\omega}((p_z,z)) \le {PD_{{\mathcal{N}}}}((Y\setminus \{z\}) \cup \{x_i\}) - {\omega}((w_i,x_i))\). Consequently, \(Y\setminus \{z\} \cup \{x_i\}\) is also a solution. Therefore, we can replace all false leaves and we are done. ◻

Proof. Reduction. Let \({\mathcal{I}}= ({\mathcal{N}},k,D)\) be an instance of MapPD. We define an instance \({\mathcal{I}}' = (\mathcal{U},\mathcal{F},{\omega}',k',D')\) of wpSC as follows. Let \(k' := k\) and \(D':= D\). For each edge \(e\) of \(\mathcal{N}\), define an item \(u_e\) with weight \({\omega}'(u_e)={\omega}(e)\) and let \(\mathcal{U}\) be the set of these \(u_e\). For each taxon \(x\), define a set \(F_x\) which contains item \(u_e\) if and only if \(e\) is affected by \(\{x\}\). Let \(\mathcal{F}\) be the family of these \(F_x\).

Correctness. Clearly, the reduction is computed in polynomial time. We show the equivalence of the two instances.

Let \(Y\) be a solution for MapPD on instance \(\mathcal{I}\). Without loss of generality, assume \(Y=\{x_1,\dots,x_\ell\}\) with \(\ell\le k\). We show that \(F_1,\dots,F_\ell\) is a solution for wpSC on \({\mathcal{I}}'\). By definition, \(\ell\le k'\). Let \(E_Y\) be the edges affected by \(Y\). Observe that \(e\) is in \(E_Y\) if and only if \(u_e\) is in \(F^+ := \bigcup_{i=1}^\ell F_i\). Then, \(D \le {PD_{{\mathcal{N}}}}(Y) = \sum_{e\in E_Y} {\omega}(e) = \sum_{u_e\in F^+} {\omega}'(u_e)\). Hence, \(F_1,\dots,F_\ell\) is a solution for wpSC on \({\mathcal{I}}'\).

Now, without loss of generality, let \(F_1,\dots,F_\ell\) be a solution for wpSC on \({\mathcal{I}}'\). Let \(u_{e_1},\dots,u_{e_p}\) be the items in the union of \(F_1,\dots,F_\ell\). By the construction, the edges \(e_1,\dots,e_p\) are affected by \(Y=\{x_1,\dots,x_\ell\}\). Then, \({PD_{{\mathcal{N}}}}(Y)\ge \sum_{i=1}^p {\omega}(e_i) = \sum_{i=1}^p {\omega}'(u_{e_i}) \ge D\). Because the size of \(Y\) is at most \(k'\), \(Y\) is a solution for MapPD on \({\mathcal{I}}\). ◻

Proof. Algorithm. Let \({\mathcal{I}}:= ({\mathcal{N}}:=(V,E,{\omega}),k,D,c)\) be an instance of colored-MapPD. Delete all edges \((u,v)\) for which \(v\) has a green offspring, and then delete any isolated vertices. For any vertex \(u\) of in-degree \(0\) with children \(v_1,\dots, v_q\), replace \(u\) with \(q\) vertices \(u_1,\dots, u_q\) and add and edge \((u_i,v_i)\) of weight \({\omega}((u,v_i))\) for each \(i \in [q]\), so that each in-degree-\(0\) vertex now has one child. Let \(G'\) be the resulting graph. An example of this transformation is depicted in 2.

Compute the set of weakly connected components of \(G'\). For every weakly connected components \(C = (V_C,E_C)\) of \(G'\), proceed as follows. Define an item \(I_C\) with weight \({\omega}(E_C)\) and value \(|Y_C|\), where \(Y_C\) is the set of taxa in \(V_C\).

Let \(M\) be the set of these items. Now, return yes if there is a subset of items in \(M\) whose total weight is at most \({\overline{D}}\) and whose total value is at least \({\overline{k}}=|X|-k\), and no otherwise. Here, \(\overline{k}\) and \(\overline{D}\) are from the original network \({\mathcal{N}}\). Observe that this can be determined by solving an instance of Knapsack with set of items \(M\), budget \({\overline{D}}\), and target value \({\overline{k}}\), which can be done in \(\mathcal{O}({\overline{D}}\cdot |N| \cdot \log({\overline{k}})) \in \mathcal{O}({\overline{D}}\cdot |X| \cdot \log({\overline{k}}))\) time [35], [36].²

Correctness. We show first that if \({\mathcal{I}}\) is a yes-instance of colored-MapPD, then the algorithm return yes and secondly we show the converse.

Assume that \(\mathcal{I}\) is a yes-instance of colored-MapPD. Thus, there is a set \(S \subseteq X\) of size at most \(k\) with \({PD_{{\mathcal{N}}}}(S) \ge D\) and \(X\setminus S\) is color-fitting. We claim that \(X\setminus S\) is also color-fitting in \(G'\). Indeed, suppose for a contradiction that this is not the case. Then, there exists some vertex \(v\) in \(G'\) for which \(v\) has an offspring in \(X\setminus S\) and an offspring in \(S\). Let \(v\) be a lowest such vertex. Then, \(v\) does not have in-degree \(0\) in \(G'\), as in this case \(v\) has a unique child with the same offspring. Furthermore, \(v\) does not have any green offspring in \({\mathcal{N}}\), as the incoming edges of \(v\) were not deleted in the construction of \(G'\). Then, in fact \(v\) has the same offspring in \({\mathcal{N}}\) as in \(G'\), implying that \(X\setminus S\) is not color-fitting. This is a contradiction and we conclude that \(X\setminus S\) is color-fitting in \(G'\).

Since \(X \setminus S\) is color-fitting in \(G'\), and \(G'\) has no green taxa, every vertex \(v\) in \(G\) satisfies \(\mathop{\mathrm{off}}(v) \subseteq X\setminus S\) or \(\mathop{\mathrm{off}}(v) \subseteq S\). Each edge \(e\) in \({\mathcal{N}}\) that is not affected by \(S\) is strictly affected by \(X\setminus S\). Because \(X\setminus S\) is color-fitting, each taxon in \(X\setminus S\) is red and so \(e\) is still an edge in \(G'\). Let \(C_e\) be the connected component of \(G'\) that contains \(e\). Observe that every edge in \(C_e\) is also strictly affected by \(X \setminus S\)—indeed, for any edge \(uv\) in \(C\), \(u\) has all its offspring in \(X\setminus S\) if and only if \(v\) has all its offspring in \(X\setminus S\). Thus, \(C_e\) satisfies the conditions to be in \(M\) for each edge \(e\) that is not affected by \(S\). Let \(C_1,\dots,C_t\) be the unique connected components that contain the edges that are not affected by \(S\). We conclude that \({\omega}(C_1 \cup \dots \cup C_t) \le {\overline{D}}\) and \(C_1 \cup \dots \cup C_t\) is the set of taxa \(X\setminus S\), which has size at least \({\overline{k}}\). Hence, \(I_{C_1},\dots,I_{C_t}\) is a solution for Knapsack on \((M, {\overline{D}}, {\overline{k}})\) and the algorithm returns yes.

For the converse, assume that the algorithm returns yes and let \(I_{C_1},\dots,I_{C_t}\) be a solution for Knapsack on \((M, {\overline{D}}, {\overline{k}})\). Let \(Y_i\) be the set of taxa of \(C_i\) and define \(Y := \bigcup_{i=1}^t Y_i\). We prove that \(S := X \setminus Y\) is a solution for colored-MapPD on instance \(\mathcal{I}\). By the construction, we conclude that all taxa in \(Y_i\) are colored red and that \(Y_i\) and \(Y_j\) are disjoint for any \(i\neq j\). Each vertex \(v \in {\mathcal{N}}\) that has some but not all offspring in \(Y_i\) has at least one green offspring. Consequently, \(Y\) is color-fitting. Further, for any edge \(e = (u,v)\) that is strictly affected by \(Y\) in \({\mathcal{N}}\), we have that \(v\) has no green offspring, and therefore \(e\) is not deleted in the construction of \(G'\). Moreover, as \(v\) has offspring in \(Y_i\) for some \(i \in [t]\), we conclude that \(e\) is in \(C_i\). Because \(\sum_{i=1}^t {\omega}(E_{C_i}) \le {\overline{D}}\) the phylogenetic diversity of \(S\) is \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}}}(X) - \sum_{i=1}^t {\omega}(E_{C_i}) \ge {PD_{{\mathcal{N}}}}(X) - {\overline{D}}= D\). Likewise, as \(\sum_{i=1}^t |Y_i| \ge {\overline{k}}\), we conclude \(|S| = |X| - \sum_{i=1}^t |Y_i| \le |X| - {\overline{k}}= k\).

Running Time. The graph \(G'\) can be computed from \({\mathcal{N}}\) in \(\mathcal{O}(m)\) time. The weakly connected components of \(G'\) can be computed in \(\mathcal{O}(m)\) time as well. For each connected component \(C = (V_C,E_C)\) the item \(I_C\) of \(M\) is computed in \(\mathcal{O}(|E_C| \cdot \log({\overline{D}}))\) time. Consequently, we can compute \(M\) in \(\mathcal{O}(m \cdot \log({\overline{D}}))\) time. As the instance of Knapsack can be solved in \(\mathcal{O}({\overline{D}}\cdot |X| \cdot \log({\overline{k}}))\) time [35], [36], we have an overall running time of \(\mathcal{O}(m \cdot \log({\overline{D}}) + {\overline{D}}\cdot |X| \cdot \log({\overline{k}})) \in \mathcal{O}({\overline{D}}\cdot m \cdot \log({\overline{D}}))\). ◻

Proof of 4. Algorithm. Let \({\mathcal{I}}:= ({\mathcal{N}}:=(V,E,{\omega}),k,D)\) be an instance of MapPD. Arbitrarily order the taxa \(x_1,\dots, x_n\). Construct an \((n,{\overline{D}}+ {\overline{k}})\)-universal

Now for each \(A \in \mathcal{U}\), construct a \(2\)-coloring \(c_A: X\to \{\text{red},\text{green}\}\) where \(x_i\) is colored green if and only if \(i \in A\), and solve colored-MapPD on \(({\mathcal{N}}, k, D, c_A)\). Return yes, if \(({\mathcal{N}}, k, D, c_A)\) is a yes-instance for some \(A \in \mathcal{U}\). Otherwise return no.

Correctness. First observe that if \(({\mathcal{N}}, k, D, c)\) is a yes-instance of colored-MapPD for any coloring \(c: X\to \{\text{red},\text{green}\}\), then \(({\mathcal{N}},k,D)\) is also a yes-instance of MapPD.

Now suppose \(({\mathcal{N}},k,D)\) is a yes-instance for MapPD. Let \(S\subseteq X\) be a subset of taxa of size at most \(k\) and with \({PD_{{\mathcal{N}}}}(S)\ge D\). If necessary, add taxa to \(S\) until \(|S| = k\). Consequently, \(X\setminus S\) has size \({\overline{k}}\). Let \(V_Y\) be the set of vertices \(u\) of \(\mathcal{N}\) which have an offspring \(x_u\) in \(S\) and have a child \(v\) with \(\mathop{\mathrm{off}}(v) \subseteq X\setminus S\). Define \(Y := \{ x_u \mid u\in V_Y \}\). Observe that if we could define a coloring which colors the taxa in \(X\setminus S\) in red and the taxa in \(Y\) in green, then \(X\setminus S\) would be color-fitting.

Define an operation \(\texttt{ind}: 2^X \to [n]\) by \(\texttt{ind}(X') := \{ i \mid x_i \in X' \}\) for any set \(X' \subseteq X\).

For each \(u\in V_Y\) and child \(v\) of \(u\) with \(\mathop{\mathrm{off}}(v) \subseteq X\setminus S\), the edge \(uv\) is strictly affected by \(X\setminus S\). Consequently, \(|Y| \le |V_Y| \le {\omega}(uv) \le {\overline{D}}\). Therefore, \(Z := Y \cup (X\setminus S) \subseteq X\) is a set of size at most \({\overline{k}}+ {\overline{D}}\). If necessary, add taxa until \(Z\) has size \({\overline{D}}+{\overline{k}}\). Consequently, there is a set \(A\in \mathcal{U}\) with \(A \cap \texttt{ind}(Z) = \texttt{ind}(Y)\). Then, the associated \(2\)-coloring \(c_A\) colors every taxa in \(Y\) green and every taxa in \(X \setminus S\) red. So \(X\setminus S\) is color-fitting with respect to \(c_A\), and \(S\) is a solution for colored-MapPD on instance \(({\mathcal{N}}, k, D, c_A)\).

Running Time. The construction of \(\mathcal{U}\) takes \(2^{{\overline{D}}+ {\overline{k}}+ \mathcal{O}(\log^2 ({\overline{D}}))} n\log n\) time, and for each of the \(2^{{\overline{D}}+ {\overline{k}}+ \mathcal{O}(\log^2 ({\overline{D}}))}\log n\) sets in \(\mathcal{U}\) we solve an instance of colored-MapPD, which can be done in \(\mathcal{O}({\overline{D}}\cdot m \cdot \log({\overline{D}}))\) time by 3. The overall running time is \(\mathcal{O}(2^{{\overline{D}}+ {\overline{k}}+ o({\overline{D}})} \cdot m\log n)\). ◻

Proof. Algorithm. We define two operations, called take and leave, that take as input an instance \({\mathcal{I}}= ({\mathcal{N}},k,D)\) and a reticulation \(v\) of \(\mathcal{N}\) and return another instance of MapPD. Every subset of taxa \(Y\) that contains an offspring of \(v\) should be a solution for MapPD on \(\mathcal{I}\) if and only if \(Y\) is a solution forMapPD on \(\texttt{take}({\mathcal{I}},v)\). Similarly every subset of \(Y\) that does not contain an offspring of \(v\) should be a solution for MapPD on \(\mathcal{I}\) if and only if \(Y\) is a solution forMapPD on \(\texttt{leave}({\mathcal{I}},v)\).

Recall that \(\mathop{\mathrm{off}}(e)\subseteq X\) is the set of offspring of \(w\) for an edge \(e=(v,w)\) and the strictly affected edges \(T_Y\) for a set of taxa \(Y\subseteq X\) is the set of edges \(e\) with \(\mathop{\mathrm{off}}(e)\subseteq Y\). We define \(\texttt{leave}({\mathcal{I}},v)\) to be the instance \({\mathcal{I}}'=({\mathcal{N}}',k,D)\) of MapPD, in which \(k\) and \(D\) are unchanged and \({\mathcal{N}}'\) is the network that results from deleting the edges \(T_{\mathop{\mathrm{off}}(v)}\) and the resulting isolated vertices from \(\mathcal{N}\).

For a reticulation \(v\) in a network \(\mathcal{N}\) with child \(u\), let \(E^{(\uparrow vu)}\) be the set of edges of \(\mathcal{N}\) that are between two vertices of \(\mathop{\mathrm{anc}}(v) \cup \{u\}\). Recall that \({\overline{D}}=\sum_{e\in E} {\omega}(e)-D\). We define \(\texttt{take}({\mathcal{I}},v)\) to be the instance \({\mathcal{I}}'=({\mathcal{N}}',k,D')\) of MapPD with \(D'=D+{\overline{D}}\) and \(k\) is unchanged. \({\mathcal{N}}'\) is the network that results from \(\mathcal{N}\) by deleting the edges \(E^{(\uparrow vu)}\), merging all the ancestors of \(v\) to a single vertex \(\rho\), adding an edge \((\rho,u)\), and setting the weight \({\omega}'((\rho,u))\) to \({\omega}(E^{(\uparrow vu)})+{\overline{D}}\). For each vertex \(w\ne u\) that, in \(\mathcal{N}\), has \(t\ge 1\) parents \(u_1,\dots,u_t\) in \(\mathop{\mathrm{anc}}(v)\), we replace the edges \((u_1,w),\dots, (u_t,w)\) with a single edge \((\rho,w)\) that has weight \(\sum_{i=1}^t {\omega}((u_i,w))\). Observe that \(PD_{{\mathcal{N}}'}(X) = {PD_{{\mathcal{N}}}}(X) + {\overline{D}}\). 3 depicts an example of the operations take and leave.

Now, we are at the position to define the branching algorithm. Let \({\mathcal{I}}=({\mathcal{N}},k,D)\) be an instance of MapPD. If \({\mathcal{N}}\) is a phylogenetic tree, solve the instance \(\mathcal{I}\) with Faith’s Algorithm [2], [11], [12]. Otherwise, let \(v\) be a reticulation of \({\mathcal{N}}\).

Then, recursively, solve MapPD on \(\texttt{take}({\mathcal{I}},v)\) and \(\texttt{leave}({\mathcal{I}},v)\). If either of these is a yes-instance of MapPD, return yes. Otherwise, return no.

Correctness. The correctness of the base case is given by the correctness of Faith’s Algorithm. We show that if \(\mathcal{N}\) contains a reticulation \(v\), then \(\mathcal{I}\) is a yes-instance of MapPD if and only if \(\texttt{take}({\mathcal{I}},v)\) or \(\texttt{leave}({\mathcal{I}},v)\) is a yes-instance of MapPD.

Consider any set of taxa \(Y \subseteq X\). Firstly, we claim that if \(Y \cap \mathop{\mathrm{off}}(v) = \emptyset\), then \(PD_{{\mathcal{N}}'}(Y) = {PD_{{\mathcal{N}}}}(Y)\), where \({\mathcal{N}}'\) is the network in \(\texttt{leave}({\mathcal{I}},v)\). Indeed, \({\mathcal{N}}'\) contains all the vertices and edges of \(\mathcal{N}\) that have an offspring outside of \(\mathop{\mathrm{off}}(v)\). Therefore, the set of edges affected by \(Y\) is the same in both networks, and \(PD_{{\mathcal{N}}'}(Y) = {PD_{{\mathcal{N}}}}(Y)\). Secondly, we claim that if \(Y \cap \mathop{\mathrm{off}}(v) \neq \emptyset\), then \(PD_{{\mathcal{N}}'}(Y) = {PD_{{\mathcal{N}}}}(Y) + {\overline{D}}\), where \({\mathcal{N}}'\) is the network in \(\texttt{take}({\mathcal{I}},v)\). Recall that each edge \(e=(u_1,u_2)\) with \(u_1\ne \rho\) of \(E({\mathcal{N}}')\) is also an edge of \({\mathcal{N}}\) and \({\omega}'(e)={\omega}(e)\). Further, for each edge \(e=(\rho,u_2)\in E({\mathcal{N}}')\) with \(u_2\ne u\), there are edges \(e_1=(u_{i_1},u_2),\dots,e_t=(u_{i_t},u_2)\) of \(E({\mathcal{N}})\) with \({\omega}'(e)=\sum_{i=1}^t {\omega}(e_i)\). Now, let \(Q = Q_1 \cup Q_2 \cup \{(\rho,u)\}\) be the edges of \({\mathcal{N}}'\) that have at least one offspring in \(Y\), of which edges in \(Q_1\) have both endpoints in \(V({\mathcal{N}}')\setminus\{\rho\}\), and \(Q_2\) are outgoing edges of \(\rho\). Further, let \(P = P_1 \cup P_2 \cup E^{(\uparrow vu)}\) be the edges of \({\mathcal{N}}\) that have at least one offspring in \(Y\), of which edges in \(P_1\) have both endpoints in \(V({\mathcal{N}}')\setminus \{\rho\}\), and \(P_2\) are edges with one endpoint in \(\mathop{\mathrm{anc}}(v)\setminus \{v\}\) and one endpoint in \(V({\mathcal{N}}')\setminus\{\rho\}\). Observe that, \(Q_1 = P_1\) and \({\omega}'(Q_1) = {\omega}(P_1)\) since any vertex in \(V({\mathcal{N}}')\setminus \{\rho\}\) has the same offspring in \({\mathcal{N}}\) as in \({\mathcal{N}}'\). Further, \({\omega}'(Q_2) = {\omega}(P_2)\) as for each \(u_2 \in V({\mathcal{N}}')\setminus\{\rho\}\), the total weight of edges \((u_1,u_2)\) with \(u_1 \in \mathop{\mathrm{anc}}(v)\setminus \{v\}\) in \({\mathcal{N}}\) is equal to the weight of the edge \((\rho,u_2)\) in \({\mathcal{N}}'\). It follows that \(PD_{{\mathcal{N}}'}(Y) = {\omega}'(Q_1) + {\omega}'(Q_2) + {\omega}'((\rho,u)) = {\omega}(P_1) + {\omega}(P_2) + {\omega}(E^{(\uparrow vu)}) + {\overline{D}}= {PD_{{\mathcal{N}}}}(Y) + {\overline{D}}\).

It follows from the above that if \(Y\) is a solution for MapPD on \(\mathcal{I}\)(that is, \(|Y|\le k\) and \({PD_{{\mathcal{N}}}}(Y)\ge D\)), then either \(Y\) is a solution for MapPD on \(\texttt{leave}({\mathcal{I}},v)\) or \(Y\) is a solution for MapPD on \(\texttt{take}({\mathcal{I}},v)\). Conversely, if \(Y\) is a solution for MapPD on \(\texttt{leave}({\mathcal{I}},v)\) then \(Y \cap \mathop{\mathrm{off}}(e) = \emptyset\) and thus \({PD_{{\mathcal{N}}}}(Y) = PD_{{\mathcal{N}}'}(Y) \geq D\), so \(Y\) is also a solution for MapPD on \(\mathcal{I}\). Finally, if \(Y\) is a solution for MapPD on \(\texttt{take}({\mathcal{I}},v)\) then \(Y \cap \mathop{\mathrm{off}}(e) \neq \emptyset\), as otherwise \(PD_{{\mathcal{N}}'}(Y) \le PD_{{\mathcal{N}}'}(X) - {\omega}'((\rho,v)) = D + 2{\overline{D}}- ({\omega}(E^{(\uparrow vu)}) + {\overline{D}}) \le D + {\overline{D}}- 1 < D'\). Then \(PD_{{\mathcal{N}}'}(Y) = {PD_{{\mathcal{N}}}}(Y) + {\overline{D}}\), from which it follows that \({PD_{{\mathcal{N}}}}(Y) \geq D' - {\overline{D}}= D\) and \(Y\) is also a solution for MapPD on \(\mathcal{I}\).

Running Time. Let \(\mathcal{I}\) be an instance of MapPD that contains a reticulation \(v\). The number of reticulations in \(\mathcal{I}\) is greater than the number of reticulations in \(\texttt{take}({\mathcal{I}},v)\) and \(\texttt{leave}({\mathcal{I}},v)\), because at least the reticulation, \(v\), is removed and no new reticulations are added. Therefore, the search tree contains \(\mathcal{O}(2^{{\mathop{\mathrm{{ret}}}_{{\mathcal{N}}}}})\) nodes. It can be checked in \(\mathcal{O}(m)\) time, if \({\mathcal{N}}\) contains a reticulation. Faith’s Algorithm takes \(\mathcal{O}(k \cdot m\cdot \log(\max_{\omega}))\) time [11], [12].

The sets \(\mathop{\mathrm{off}}(v)\) and \(\mathop{\mathrm{anc}}(v)\) for a vertex \(v\), and \(T_Y\) for a set \(Y\) can be computed in \(\mathcal{O}(m)\) time. Once \(\mathop{\mathrm{anc}}(v)\) is computed, we can iterate over \(E\) to find the edges that are outgoing from \(\mathop{\mathrm{anc}}(v)\) and compute the total weight for an edge \((\rho,w)\) in \({\mathcal{N}}'\) in \(\mathcal{O}(m\cdot \log(\max_{\omega}))\) time, which is also the time needed to compute \({\omega}((\rho,u))\) which needs \(\overline{D}\) and the weight of \(E^{(\uparrow vu)}\). Therefore, the instances \(\texttt{take}({\mathcal{I}},v)\) and \(\texttt{leave}({\mathcal{I}},v)\) can be computed in \(\mathcal{O}(m\cdot \log(\max_{\omega}))\) time.

Thus, a solution for MapPD can be computed in \(\mathcal{O}(2^{{\mathop{\mathrm{{ret}}}_{{\mathcal{N}}}}} \cdot k \cdot m\cdot \log(\max_{\omega}))\) time. ◻

Proof of 7. We define a dynamic programming instance over a nice tree-decomposition \(T\) of the \(X\)-network \({\mathcal{N}}=(V,E,{\omega})\) in which vertices are introduced without incident edges and all edges are induced exactly once.

Definition of the Table. Let \({\mathcal{I}}=({\mathcal{N}},k,D)\) be an instance of MapPD and let \(T\) be a nice tree decomposition of \({\mathcal{N}}\). We index solutions by a node \(t \in T\), a partition \(R\cup G\cup B\) of \(Q_t\), and a non-negative integer \(s\in [k]_0\). For a set of edges \(F \subseteq E_t\), we call a vertex \(u \in V_t\) green with respect to \(F\) if \(u\) is a leaf or has an outgoing edge in \(F\). We call \(u\) red* with respect to \(F\)* if \(u\) is not a leaf and has an incoming but no outgoing edge in \(F\). Finally, we call \(u\) **black* with respect to \(F\)* if \(u\) is not a leaf and has no incident edges in \(F\). For a node \(t\in T\), a partition \(R\cup G\cup B\) of \(Q_t\) and an integer \(s\), we call a set of edges \(F \subseteq E_t\) feasible for \(t,R,G,B,s\), if all the following conditions hold:

1. If \((u,v)\) is an edge in \(F\) and \(v\notin Q_t\), then \(v\) is a leaf of \({\mathcal{N}}\) or \(v\) has an outgoing edge in \(F\).

2. The vertices \(R\subseteq Q_t\) are red with respect to \(F\).

3. The vertices \(G\subseteq Q_t\) are green with respect to \(F\).

4. The vertices \(B\subseteq Q_t\) are black with respect to \(F\).

5. The number of leaves in \({\mathcal{N}}\) with an incoming edge in \(F\) is \(s\).

Further, we define \(\mathcal{S}^*_{t,R,G,B,s}\) to be the set of all sets \(F\) that are feasible for \(t,R,G,B,s\).

We define a dynamic programming algorithm over a nice tree decomposition \(T\). In a table entry of \(\mathop{\mathrm{DP}}[t,A,R,G,B,s]\), we store the greatest weight \({\omega}(F)\) of a set \(F \subseteq E_t\) that is feasible for \(t,R,G,B,s\). If there is no feasible \(F\), then we store a large negative value. For our purposes a value of \(-m\cdot \max_{\omega}-1\) will suffice, as even if every edge would be chosen, the entry at the root of the tree decomposition is still negative. Let \(r\) be the root of the nice tree-decomposition \(T\). We claim that \(\mathop{\mathrm{DP}}[r,\emptyset,\emptyset,\emptyset,k]\) stores the greatest phylogenetic diversity that can be preserved with a budget of \(k\). Indeed, for any set \(Y\) of \(k\) taxa, the set of affected edges \(E_Y\) is feasible for \(r,\emptyset,\emptyset,\emptyset,k\) and has weight \({PD_{{\mathcal{N}}}}(Y)\). Conversely if \(F\) is feasible for \(r,\emptyset,\emptyset,\emptyset,k\), then letting \(Y\) be the set of leaves in \({\mathcal{N}}\) with an incoming edge in \(F\), we have that \(E_Y \supseteq F\) and so \({PD_{{\mathcal{N}}}}(Y)\geq {\omega}(F)\). Hence, we can return yes if \(\mathop{\mathrm{DP}}[r,\emptyset,\emptyset,\emptyset,k]\ge D\) and no otherwise.

Now we have everything we need to define the dynamic programming algorithm. In the calculations that follow, any time a value \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) is called for which \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) is not defined (in particular, if \(s < 0\)), we take \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) to be \(-m\cdot \max_{\omega}-1\).

Leaf Node. For a leaf \(t\) of \(T\) the sets \(Q_t\) and \(E_t\) are empty. So if \(s = 0\), we trivially store \[\begin{align} \label{tw:leaf} \mathop{\mathrm{DP}}[t,\emptyset,\emptyset,\emptyset,s] &=& 0. \end{align}\tag{1}\] Otherwise, we store \(\mathop{\mathrm{DP}}[t,R,G,B,s] = -m\cdot \max_{\omega}-1\).

Introduce Vertex Node. Suppose now that \(t\) is an introduce vertex node, i.e., \(t\) has a single child \(t'\), \(Q_t = Q_{t'} \cup \{v\}\), and \(v\) is an isolated vertex in \({\mathcal{N}}_t\). If either \(v\in B\), or \(v\in G\) and \(v\) is a leaf, we store \[\begin{align} \label{tw:insertvertex} \mathop{\mathrm{DP}}[t,R,G,B,s] &=& \mathop{\mathrm{DP}}[t',R,G\setminus\{v\},B\setminus\{v\},s]. \end{align}\tag{2}\] Otherwise, we store \(\mathop{\mathrm{DP}}[t,R,G,B,s] = -m\cdot \max_{\omega}-1\).

Introduce Edge Node. Suppose now that \(t\) is an introduce edge node, i.e., \(t\) has a single child \(t'\), \(Q_t = Q_{t'}\), and \(e=(v,w)\) is introduced at \(t'\). The algorithm must decide whether \(e\) is an affected edge, or not. If \(v\notin G\) or \(w\in B\), \(e\) can not be an affected edge and so we store \(\mathop{\mathrm{DP}}[t,R,G,B,s] = \mathop{\mathrm{DP}}[t',R,G,B,s]\). Otherwise, we store \[\begin{align} \label{tw:insertedge} \mathop{\mathrm{DP}}[t,R,G,B,s] &=& \max\{ \mathop{\mathrm{DP}}[t',R,G,B,s]; \max_{R',G',B'}\mathop{\mathrm{DP}}[t',R',G',B',s'] + {\omega}(e) \}, \end{align}\tag{3}\] where the second maximum is over all possible partitions \(R'\cup G'\cup B'\) of \(Q_t\), such that \(S\setminus\{v,w\} = S'\setminus\{v,w\}\) for all \(S \in \{R,G,B\}\) (i.e. the two partitions agree on \(Q_T\setminus\{v,w\}\)), and such that if \(w \in G'\) then \(w \in G\), and \(w \in R\) otherwise. Here \(s' = s-1\) if \(w\) is a leaf and \(s' = s\) if not.

Forget Node. Suppose now that \(t\) is an forget node, i.e., \(t\) has a single child \(t'\) and \(Q_t = Q_{t'} \setminus \{v\}\). We store \[\begin{align} \label{tw:forget} \mathop{\mathrm{DP}}[t,R,G,B,s] = \max \{ \mathop{\mathrm{DP}}[t',R,G,B\cup\{v\},s]; \mathop{\mathrm{DP}}[t',R,G\cup\{v\},B,s]\}. \end{align}\tag{4}\]

Join Node. Suppose now that \(t\in T\) is an join node, i.e., \(t\) in \(T\) has two children \(t_1\) and \(t_2\) with \(Q_t = Q_{t_1} = Q_{t_2}\). We call two partitions \(R_1\cup G_1\cup B_1\) and \(R_2\cup G_2 \cup B_2\) of \(Q_t\) qualified for \(R\cup G\cup B\) if \(R=(R_1\cup R_2) \setminus (G_1 \cup G_2)\) and \(G = G_1\cup G_2\) (and consequently \(B = B_1 \cap B_2\)). See 4. We store \[\begin{align} \label{tw:join} \mathop{\mathrm{DP}}[t,R,G,B,s] &=& \max_{(\pi_1, \pi_2) \in{\cal Q},s'} ~ \mathop{\mathrm{DP}}[t_1,R_1,G_1,B_1,s'] + \mathop{\mathrm{DP}}[t_2,R_2,G_2,B_2,s-s'], \end{align}\tag{5}\] where \({\cal Q}\) is the set of pairs of partitions \(\pi_1 = R_1\cup G_1\cup B_1\) and \(\pi_2 = R_2\cup G_2 \cup B_2\) that are qualified for \(R,G,B\) and \(s' \in [s]_0\).

Correctness. Let \(t\) be a node of the nice tree-decomposition \(T\), \(s\) an integer, and \(R\cup G\cup B\) a partition of \(Q_t\). We show that the value of \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) is correct, for each type of node individually. As we have already argued that \(\mathop{\mathrm{DP}}[r,\emptyset,\emptyset,\emptyset,k]\) stores the greatest phylogenetic diversity that can be preserved with a budget of \(k\), this is sufficient to prove the correctness of the algorithm.

If \(t\) is a leaf node, then \(Q_t\) and \(E_t\) are empty. Consequently, \(R=G=B=\emptyset\) and any feasible set \(F\) is also empty. Therefore, we also conclude with (F5) that \(s=0\) and \({\omega}(F)=0\) for any \(F \in \mathcal{S}^*_{t,R,G,B,s}\). Hence, the stored value by Equation (1 ) is correct.

Let \(t\) be an introduce vertex node with child \(t'\) and \(Q_t=Q_{t'}\cup\{v\}\). Then, the graph \({\mathcal{N}}_t\) is the graph \({\mathcal{N}}_{t'}\) with an additional isolated vertex \(v\). Thus, \(v\) is black with respect to any \(F \subseteq E_t\), unless \(v\) is a leaf in which case \(v\) is green. Thus, there is no feasible set \(F\) for \(\mathcal{S}^*_{t,R,G,B,s}\) unless either \(v \in B\) or \(v \in G\) and \(v\) is a leaf. Assuming this is the case, any set \(F \subseteq E_t\) is feasible for \(t,R,G,B,s\) if and only if it is feasible for \(t',R,G\setminus\{v\},B\setminus\{v\},s\). Hence, we store the right value.

Let \(t\) be a introduce edge node with child \(t'\) and \(Q_t=Q_{t'}\) and \({\mathcal{N}}_t-e={\mathcal{N}}_{t'}\). Define \(e:=(v,w)\). Clearly, every set \(F\subseteq E_t\setminus\{e\}\) is feasible for \(t,R,G,B,s\) if and only if \(F\) is also feasible for \(t',R,G,B,s\), because then \({\mathcal{N}}_t[F]\) is isomorphic to \({\mathcal{N}}_{t'}[F]\). Now consider a set \(F\subseteq E_t\) with \((v,w) \in F\). Note that \(v\) is green, and \(w\) cannot be black, with respect to any such set \(F\). Therefore such an \(F\) only exists if \(v \in G\) and \(w \notin B\). Now let \(F' = F\setminus\{(v,w)\}\). The colors of vertices \(u\) that are not \(v\) or \(w\) are the same with respect to \(F\) as with respect to \(F'\). Observe that if \(w\) is green with respect to \(F\) if and only if it is green with respect to \(F'\) (as it has the same outgoing edges in \(F\) and \(F'\)). If \(w\) is red or black with respect to \(F'\), then it is red with respect to \(F\) (as it has an incoming edge and no outgoing edge). On the other hand, \(v\) could be any color with respect to \(F'\), but is necessarily green with resepct to \(F\). Likewise, we can show the correctness of \(s'\). Thus, the correct value is stored.

Let \(t\) be a forget node with child \(t'\) and \(Q_t=Q_{t'}\setminus\{v\}\). We show that a set \(F\) is feasible for \(t,R,G,B,s\) if and only if \(F\) is also feasible for \(t',R,G,B\cup\{v\},s\) or for \(t',R,G \cup \{v\},B,s\). It then follows that \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) stores the correct value.

To this end, let \(F\) be a set of edges that is feasible for \(t,R,G,B,s\). Since \(v \notin Q_t\) and condition (F1) holds, \(v\) either has an outgoing edge in \(F\) or is a leaf or does not have any incoming edge in \(F\). It follows that \(v\) is green or black with respect to \(F\). From this it is straightforward to confirm that \(F\) is feasible for \(t',R,G,B\cup\{v\},s\) or for \(t',R,G \cup \{v\},B,s\). Conversely, if \(F\) is feasible for \(t',R,G,B\cup\{v\},s\) or for \(t',R,G \cup \{v\},B,s\), then \(F\) also satisfies condition (F1) for \(t,R,G,B,s\) (in particular, the condition is satisfied for \(v\) as \(v\) is green or black with respect to \(F\)). It is straightforward to confirm that \(F\) satisfies the remaining conditions to be feasible with respect to \(t,R,G,B,s\).

Finally, let \(t\) be a join node with children \(t_1\) and \(t_2\). We show that there is an \(F\in \mathcal{S}^*_{t,R,G,B,s}\) if and only if there are partitions \(R_1 \cup G_1 \cup B_1\) and \(R_2 \cup G_2 \cup B_2\), qualified for \(R,G,B\) and \(s'\le s\) such that there are \(F_1\in \mathcal{S}^*_{t_1,R_1,G_1,B_1,s'}\) and \(F_2\in \mathcal{S}^*_{t_2,R_2,G_2,B_2,s-s'}\) with \(F_1\cup F_2 = F\).

First, let \(F\) be feasible for \(t,R,G,B,s\). Let \(F_i\) be the subset of edges of \(F\) that occur in \({\mathcal{N}}_{t_i}\) for \(i\in\{1,2\}\). Because every edge is introduced exactly once, the sets \(F_1\) and \(F_2\) are disjoint. We define \(s'\) to be the number of edges of \(F_1\) that are incident with a leaf. Further, we define \(R_i\) to be the set of vertices in \(Q_t\) that are not leaves in \(\mathcal{N}\) and have an incoming but no outgoing edge in \(F_i\) for \(i\in \{1,2\}\). Similarly, we define \(G_i\) to be the set of vertices in \(Q_t\) that are leaves or have an outgoing edge in \(F_i\), and we define \(B_i\) to be the set of vertices in \(Q_t\) that are not leaves and have no incident vertices in \(F_i\), for \(i\in \{1,2\}\).

We show that \(F_1\in \mathcal{S}^*_{t_1,R_1,G_1,B_1,s'}\) and \(F_2\in \mathcal{S}^*_{t_2,R_2,G_2,B_2,s-s'}\). Let \(e=(u,v)\) be an edge in \(F_i\) such that \(v\) is not a leaf and \(v\not\in Q_{t_i}\) for \(i\in \{1,2\}\). Because \(Q_t=Q_{t_i}\), we conclude that \(v\not\in Q_{t}\). Thus, with (F1) we conclude that \(v\) has an outgoing edge \(e^*\) in \(F\). Because \(v\) is not in \(Q_t\) and \(v\) is in \(V_{t_i}\), the vertex \(v\) is not in \(V_{t_{3-i}}\). Thus, the edge \(e^*\) is also in \(F_i\) and so \(F_i\) satisfies (F1). By construction, \(F_i\) satisfies (F2) to (F4). Also, \(F_1\) satisfies (F5), by definition of \(s'\). As \(F_2\) contains the edges of \(F\) that are not in \(F_1\), there are \(s-s'\) edges in \(F_2\) that are incident with a leaf. Hence, \(F_2\) holds (F5) and so, \(F_1\in \mathcal{S}^*_{t_1,R_1,G_1,B_1,s'}\) and \(F_2\in \mathcal{S}^*_{t_2,R_2,G_2,B_2,s-s'}\).

It remains to show that \(R_1\cup G_1 \cup B_1\) and \(R_2\cup G_2 \cup B_2\) are qualified for \(R,G,B\). If \(v\) is a leaf, we conclude that \(v\) is in \(G_1,G_2\) and \(G\). Further, \(v\) has an outgoing edge in \(F\) if and only if \(v\) has an outgoing edge in \(F_1\) or \(F_2\). We conclude that \(G=G_1\cup G_2\). For each \(v\in R\) there is an incoming edge \(e\) but no outgoing edge in \(F\). Consequently, if \(v\in R\) then \(v\not\in G_1\cup G_2\). Further, \(e \in F_i\) for some \(i \in \{1,2\}\) but there is no outgoing edge for \(v\) in \(F_i\). Thus, \(v\in R_i\) and so \(R\subseteq (R_1\cup R_2) \setminus (G_1 \cup G_2)\). If \(v\in (R_1\cup R_2) \setminus (G_1 \cup G_2)\) then there is an incoming edge for \(v\) in \(F_1\) or \(F_2\) and therefore in \(F\), but no outgoing, and so \(v\in R\). We conclude that \(R=(R_1\cup R_2) \setminus (G_1 \cup G_2)\). From \(G=G_1\cup G_2\) and \(R=(R_1\cup R_2) \setminus (G_1 \cup G_2)\) we have that \(B = B_1 \cap B_2\), and so \(R_1\cup G_1 \cup B_1\) and \(R_2\cup G_2 \cup B_2\) are qualified for \(R,G,B\), as required.

For the converse, assume that there are partitions \(R_1\cup G_1 \cup B_1\) and \(R_2\cup G_2 \cup B_2\) qualified for \(R\) and \(G\), and \(s'\le s\) such that there are \(F_1\in \mathcal{S}^*_{t_1,R_1,G_1,B_1,s'}\) and \(F_2\in \mathcal{S}^*_{t_2,R_2,G_2,B_2,s-s'}\). We show that \(F:=F_1\cup F_2\) is feasible for \(t,R,G,B,s\). Let \(e=(u,v)\) be an edge in \(F\) such that \(v\) is not a leaf and \(v\not\in Q_t\). Without loss of generality, \(e\in F_1\). Because \(Q_t=Q_{t_1}\), we conclude that \(v\not\in Q_{t_1}\). Thus, \(v\) has an outgoing edge in \(F_1\) and therefore in \(F\) and \(F\) holds (F1). Let \(v\) be a vertex of \(Q_t\). If \(v\in R=(R_1\cup R_2) \setminus (G_1 \cup G_2)\), then there is an incoming edge \(e\) for \(v\) in \(F_1\) or \(F_2\) but \(F_1\) and \(F_2\) do not contain an outgoing edge for \(v\). Consequently, \(v\) has an incoming edge in \(F\) but no outgoing edge. Analogously, we can see that if \(v\in G=G_1\cup G_2\) then \(v\) has an outgoing edge in \(F\) and if \(v\in B=B_1\cap B_2\), then \(v\) is not incident with any edge in \(F\). Because that covers all options, \(F\) holds (F2) to (F4). Let \(\hat{E}_1\) and \(\hat{E}_2\) be the edges of \(F_1\) and \(F_2\), respectively, that are incident with a leaf. Thus, \(|\hat{E}_1|=s'\) and \(|\hat{E}_2|=s-s'\). Because every edge is introduced exactly once, the sets \(F_1\) and \(F_2\) and therefore \(\hat{E}_1\) and \(\hat{E}_2\) are disjoint. Consequently, \(\hat{E}_1\cup \hat{E}_2\) contains \(s\) edges that are incoming at leaves. Thus, \(F\) holds (F5). Hence, the value that is stored with Equation (5 ) is correct.

Running Time. The tree decomposition \(T\) has \(\mathcal{O}(m)\) nodes. Note that comparing and adding numbers takes \(\mathcal{O}(\log D)\) time, as we may assume we do not deal with numbers larger than \(\mathcal{O}(D)\).

For a leaf node, an introduce vertex nodes and a forget node, the value of each entry \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) can clearly be computed in linear time in \({\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot \log D\). Checking the conditions in an introduce edge node requires checking the colors of \(v\) and \(w\). Further, the partition \(R'\cup G'\cup B'\) agrees on all vertices but \(v\) and \(w\). Therefore, we can also compute the values of entries in time linear in \({\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot \log D\) for an introduce edge node. Altogether, we can compute the value of all entries of nodes that are not join nodes in \(\mathcal{O}(3^{\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot {\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot k \cdot m \cdot \log D)\) time.

For the computation of a join node \(t\), we first store \(-m\cdot \max_{\omega}-1\) in each entry \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) for partitions \(R\cup G\cup B\) of \(Q_t\) and an integer \(s\in [k]_0\). Then, iterate over partitions \(R_1\cup G_1\cup B_1\) and \(R_2\cup G_2\cup B_2\) of \(Q_t\). From the partitions \(R_1\cup G_1\cup B_1\) and \(R_2\cup G_2\cup B_2\), compute the implicitly defined partition \(R\cup G\cup B\) of \(Q_t\) in \(\mathcal{O}({\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}})\) time. (See 4). Iterate over \(s\in [k]_0\) and \(s'\in [s]_0\). If \(\mathop{\mathrm{DP}}[t_1,R_1,G_1,B_1,s'] + \mathop{\mathrm{DP}}[t_2,R_2,G_2,B_2,s-s']\) exceeds the value of \(\mathop{\mathrm{DP}}[t,R,G,B,s]\), then replace it. Otherwise let \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) stay unchanged. After the iterations, we have computed the values of \(\mathop{\mathrm{DP}}[t,R,G,B,s]\) for all partitions \(R\cup G\cup B\) of \(Q_t\) and integer \(s\in [k]_0\). Therefore, \(\mathcal{O}(9^{{\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}} \cdot {\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot k^2 \cdot \log D)\) time is required to compute all values of entries for each join node \(t\).

Hence, a solution for MapPD can be computed in \(\mathcal{O}(9^{\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot {\mathop{\mathrm{{tw}}}_{{\mathcal{N}}}}\cdot k^2 \cdot m \cdot \log D)\) time. ◻

Proof. Correctness. We show first that if \(\mathcal{I}\) is a yes-instance of MapPD then \({\mathcal{I}}' := ({\mathcal{N}}',k,D)\) is a yes-instance of MapPD. Let \(S\subseteq X\) be a solution for MapPD on \(\mathcal{I}\). If \(y\in S\) but \(x\not\in S\), then set \(S' := {(S\cup \{x\})} \setminus \{y\}\). Then, because \({PD_{{\mathcal{N}}}}(S') = {PD_{{\mathcal{N}}}}(S) + {\omega}((v,x)) - {\omega}((v,y)) \ge {PD_{{\mathcal{N}}}}(S)\), also \(S'\) is a solution. Therefore, we may assume without loss of generality that \(x \in S\) or \(y \notin S\). If \(x \notin S\) and \(y \notin S\), then observe that \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\) since all edges affected by \(S\) appear in both networks with the same weight. Similarly, if \(x \in S\) and \(y \notin S\), then \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\). Finally, if \(x \in S\) and \(y \in S\), then any edge \(e \in E({\mathcal{N}})\setminus \{(v,y)\}\) is affected by \(S\) in \({\mathcal{N}}\) if and only if \(e\) is affected by \(S\) in \({\mathcal{N}}'\) (in particular, if \(y\) is an offspring of \(e\) in \({\mathcal{N}}\) then \(x\) is an offspring of \(e\) in \({\mathcal{N}}'\)). It follows that \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S) - {\omega}'((\rho,y)) + {\omega}((v,y)) = {PD_{{\mathcal{N}}'}}(S)\). Thus, \(S\) is a solution for MapPD on \({\mathcal{I}}'\) in all cases.

Conversely, observe that for any edge \(e \in E({\mathcal{N}}')\setminus \{\rho y\}\) and any \(S \subseteq X\), if \(e\) is affected by \(S\) in \({\mathcal{N}}'\) then it is also affected by \(S\) in \({\mathcal{N}}\). Thus, \({PD_{{\mathcal{N}}'}}(S) \le {PD_{{\mathcal{N}}}}(S)\), and so each solution for MapPD on \({\mathcal{I}}'\) is also a solution for MapPD on \(\mathcal{I}\). Thus, if \({\mathcal{I}}'\) is a yes-instance of MapPD, then so is \(\mathcal{I}\).

Running Time. In \(\mathcal{O}(|X|)\) time, we can determine whether there exists a vertex \(v\) which has two children in \(X\), by iterating over \(X\) and marking each taxon’s parent. If such a vertex \(v\) exists, we only need to compare \({\omega}((v,x))\) and \({\omega}((v,y))\) in \(\mathcal{O}(\log\max_{{\omega}})\) time. ◻

Proof. Correctness. The correctness follows from the observation that \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\) for any \(S \subseteq X\).

Running Time. In \(\mathcal{O}(n)\) time, we can find out whether there exists a vertex of degree 2. If such a vertex \(v\) exists, it takes \(\mathcal{O}(\log\max_{{\omega}})\) time to remove \(v\) and its incident edges and create the new edge \(uw\) with the appropriate weight. ◻

Proof. Observe that \(|R| = {\mathop{\mathrm{{ret}}}_{{\mathcal{N}}}}\leq {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}\).

To show the other two claims, we give a bound on the number of side-paths from above and below. As every side-path in \({\mathcal{N}}\) ends at a core vertex or reticulation, we have that the number of side-paths is at most \[\sum_{v \in Q\cup R} \deg^-(v) = \sum_{r \in R} (\deg^-(r) - 1) + |Q| + |R| = {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}+ |Q| + |R| \leq 2\cdot {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}+ |Q|.\] To give a bound from below, consider that each core-vertex has at least two side-paths leaving it, from which it follows that the number of side-paths is at least \(2|Q|\). It follows that \(2|Q| \leq 2\cdot {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}+ |Q|\) and so \(|Q| \leq 2{\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}\). This in turn implies that the number of side-paths is at most \(4\cdot {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}\). ◻

Proof. Correctness. The proof follows similar lines as the proof of 4. Let \(S\subseteq X\) be a solution for MapPD on \({\mathcal{I}}\). Assume that \(x_v \in S\) but \(S \cap \mathop{\mathrm{off}}(w) = \emptyset\). Then, define \(S' := {(S\cup \{x_w\})} \setminus \{x_v\}\). Observe that \((w,x_w)\) and \((v,w)\) are affected by \(S'\) but not by \(S\), while the only edge affected by \(S\) and not by \(S'\) is \((v,x_v)\). Thus \({PD_{{\mathcal{N}}}}(S') = {PD_{{\mathcal{N}}}}(S) - {\omega}((v,x_v)) + {\omega}((w,x_w)) + {\omega}((v,w))\), which, by the condition of the reduction rule, is at least \({PD_{{\mathcal{N}}}}(S)\). Therefore, also \(S'\) is a solution for MapPD on \(\mathcal{I}\) with \(x_v\not\in S'\). Thus, we may now assume that \(S\) contains a taxon from \(\mathop{\mathrm{off}}(w)\) or \(x_v\not\in S\). In either case we can observe that \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\).

Conversely, observe that any edge \(e \in E({\mathcal{N}}')\setminus\{(\rho,x_v)\}\) affected by \(S\) in \({\mathcal{N}}'\) is also affected by \(S\) in \({\mathcal{N}}\). Thus, \({PD_{{\mathcal{N}}'}}(S) \le {PD_{{\mathcal{N}}}}(S)\) for any \(S \subseteq X\), and so each solution for MapPD on \({\mathcal{I}}'\) is also a solution for MapPD on \(\mathcal{I}\).

Running Time. In \(\mathcal{O}(n \cdot \log\max_{{\omega}})\) time, we can find out whether there exists a vertex satisfying the conditions of \(v\) in 3, and if so edit the network accordingly. ◻

Proof. Correctness. Observe that any edge \(e \in E({\mathcal{N}}')\setminus\{(\rho,v_2), (v_1,w)\}\) that is affected by \(S \subseteq X\) in \({\mathcal{N}}'\) is also affected by \(S\) in \({\mathcal{N}}\). Furthermore, \((\rho,v_2)\) is affected by \(S\) in \({\mathcal{N}}'\) if and only if \((v_1,v_2)\) is affected by \(S\) in \({\mathcal{N}}\). Therefore, \({PD_{{\mathcal{N}}'}}(S) \le {PD_{{\mathcal{N}}}}(S) + {\omega}'((v_1,w)) = {PD_{{\mathcal{N}}}}(S)\) for every set \(S \subseteq X\), and each solution for MapPD on \({\mathcal{I}}'\) is also a solution for MapPD on \(\mathcal{I}\).

It remains to show that if \({\mathcal{I}}\) is a yes-instance of MapPD, then so is \({\mathcal{I}}'\). We first observe some facts. Let \(x_i\) denote the leaf child of \(v_i\) for each \(i \in [\ell]\). Note that due to 3 we may assume that \({\omega}((v_i,x_i)) \ge {\omega}((v_i,v_{i+1})) + {\omega}((v_{i+1},x_{i+1}))\) for each \(i \in [\ell - 1]\). Consequently, \[\begin{align} {\omega}((v_1,x_1)) &\geq& {\omega}((v_2,x_2)) + {\omega}((v_1,v_2))\\ &\geq& {\omega}((v_3,x_3)) + {\omega}((v_2,v_3)) + {\omega}((v_1,v_2))\\ &\geq& {\omega}((v_i,x_i)) + \sum_{j = 1}^{i-1}{\omega}((v_j,v_{j+1})) \end{align}\] for each \(i \in [\ell - 1]\).

Let \(S\) be a solution for MapPD on \(\mathcal{I}\). Observe that if \(S\) contains \(x_1\) or an offspring of \(w\), then \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\). Similarly, if \(S\) does not contain a taxon in \(x_1, \dots, x_\ell\) then \({PD_{{\mathcal{N}}}}(S) = {PD_{{\mathcal{N}}'}}(S)\). So assume \(S\) does not contain \(x_1\) nor an offspring of \(w\) but \(x_i \in S\) for some \(i\in [\ell]\) with \(i>1\). Define \(S':= (S \cup \{x_1\}) \setminus \{x_i\}\). Then, \({PD_{{\mathcal{N}}}}(S') \ge {PD_{{\mathcal{N}}}}(S) + {\omega}((v_1,x_1)) - {\omega}((v_i,x_i)) - \sum_{j = 1}^{i-1}{\omega}((v_j,v_{j+1}))\), which by the observation above is at least \({PD_{{\mathcal{N}}}}(S)\). As \(x_1 \in S'\) we have \({PD_{{\mathcal{N}}'}}(S') = {PD_{{\mathcal{N}}}}(S')\), and so \(S'\) is a solution for MapPD on \({\mathcal{I}}'\).

Running Time. To find the vertices \(u\) and \(w\) we iterate over the vertices in \(Q\) as vertex \(u\) and consider each outgoing edge as a path to \(u\). Therefore, all possible combinations of \(u\) and \(w\) are found in \(\mathcal{O}(m)\) time. Each operation can be executed in \(\mathcal{O}( \log\max_{\omega})\) time. ◻

Proof. To see the first claim, let \({\mathcal{N}}'\) be the network after saving \(x\) and let \(S \subseteq X\) contain \(x\). Any edge in \({\mathcal{N}}'\) affected by \(S\setminus\{x\}\) has a corresponding edge in \(E({\mathcal{N}})\setminus E_{\{x\}}\) with the same offspring, from which it follows that \({PD_{{\mathcal{N}}}}(S) \geq {PD_{{\mathcal{N}}'}}(S\setminus\{x\}) + {PD_{{\mathcal{N}}}}(\{x\})\).

Conversely, if \(x \in S \subseteq X\) then any edge in \(E_S \setminus E_{\{x\}}\) has a corresponding edge in \({\mathcal{N}}'\) affected by \(S \setminus \{x\}\), from which it follows that \({PD_{{\mathcal{N}}'}}(S\setminus \{x\}) \geq {PD_{{\mathcal{N}}}}(S) - {PD_{{\mathcal{N}}}}(\{x\})\).

The second claim follows immediately from the definition of \({PD_{{\mathcal{N}}}}(S)\). ◻

Proof. Correctness. Let \(v_{1,1}, v_{2,1}, \dots v_{|Y|,1}\) denote the vertices of \(Y\). Let \(v_{j,1} v_{j,2},\dots v_{j, \ell_j}\) be the side-vertices on the path from \(v_{j,1}\) to a core vertex for each \(j \in [|Y|]\). Let \(z_{j,i}\) be the leaf child of \(v_{j,i}\) for each \(j \in [|Y|]\), and \(i \in [\ell_j]\). This mapping is unique after [rr:trees,rr:deg-2] have been applied exhaustively. Observe that \(Z\) is the set \(\{v_{j,i} \mid 2 \leq j \leq |Y|, i \in [\ell_j]\}\).

Due to 3, we have \({\omega}((v_{j,1},y_{j,1})) > {\omega}((v_{j,i},y_{j,i})) + \sum_{h=1}^{i-1}{\omega}((v_{j,h},v_{j,h+1}))\) for each \(j \in [|Y|]\), and each \(i \in [\ell_j]\). Consequently, we may assume that if \(y_{j,i}\) is in a solution for some \(i > 1\), then so is \(y_{j,1}\).

Furthermore, for any solution that contains \(y_{j,i}\) and \(y_{j,1}\) for some \(i>1\), we can assume that the solution contains \(y^*\) as otherwise replacing \(y_{j,i}\) with \(y^*\) gives another solution, because \[\begin{align} && {\omega}((\rho,v_{y^*}))+ {\omega}((v_{y^*},y^*))\\ &\geq& {\omega}((\rho,v_{j,1})) + {\omega}((v_{j,1},y_{j,1}))\\ &>& {\omega}((\rho,v_{j,1})) + \sum_{h=1}^{i-1} {\omega}((v_{j,h},v_{j,h+1})) + {\omega}((v_{j,i},y_{j,i})) \end{align}\] where \(v_{y^*}\) is the parent of \(y^*\). Thus, if a solution \(S\) contains any element of \(Z_X\) we can assume \(S\) also contains \(y^*\).

Now, suppose \(k > |B| + |Y|\). Then, any solution \(S\) contains at least one element of \(A \cup Z_X\). This implies that \(S\) contains at least one taxon of \(A \cup \{y^*\}\) as \(S\) contains \(y^*\) if it contains any taxon in \(Z_X\). If \(a^* > c^*\), then \(S\) contains \(x^*\), as otherwise we could replace a taxon from \((A\setminus \{x^*\}) \cup \{y^*\}\) with \(x^*\). So, in this case, \(S\) contains \(x^*\), and we can save \(x^*\) by Lemma 8. Otherwise, we may assume \(S\) contains \(y^*\), as otherwise we can replace an element from \(A\) with \(y^*\), and we can save \(y^*\) by Lemma 8.

Running Time. We can compute the size of \(B\) and \(Y\) and find \(a^*\) and \(c^*\) in \(\mathcal{O}(n \log\max_{\omega})\) time. Saving \(x^*\) or \(y^*\) takes \(\mathcal{O}(m \log\max_{\omega})\) time. ◻

Proof. Correctness. Clearly, any solution for MapPD on instance \({\mathcal{I}}'\) is also a solution for MapPD on \(\mathcal{I}\). Conversely, let \(S\) be a solution for MapPD on \({\mathcal{I}}\). If \(S \cap \{x_{k+1},\dots,x_{|A|}\} = \emptyset\), then \(S\) is also a solution for MapPD on \({\mathcal{I}}'\). Assume that \(x_i \in S\) for some \(i\in \{k+1, \dots, |A|\}\). As \(|S| \le k\) we conclude that there is a taxon \(x_j\) for \(j\in [k]\) with \(x_j \not\in S\). Because \({\omega}((\rho,x_j)) \ge {\omega}((\rho,x_i))\), we conclude that \((S \cup \{x_j\}) \setminus \{x_i\}\) is also a solution for MapPD on \(\mathcal{I}\). Thus, we may assume that \(S \cap \{x_{k+1},\dots,x_{|A|}\} = \emptyset\).

Running Time. We can sort \(A\) in \(\mathcal{O}(n\log n \cdot \log\max_{{\omega}})\) time. ◻

Proof. Correctness. Because we applied [rr:trees,rr:deg-2,rr:a>a+b] exhaustively, each vertex \(z_i\) has exactly one leaf-child \(x_i\) and \({\omega}((z_i,x_i)) > {\omega}((z_{i+1},x_{i+1})) + {\omega}((z_i,z_{i+1}))\). Consequently, we can assume that if \(x_i\) is in a solution then so are \(x_0, \dots, x_{i-1}\). Therefore, \(x_{k}\) cannot be in a solution of size \(k\), and applying 7 is correct.

Running Time. Similar to the proof of 5, we can find an appropriate vertex \(z_k\) in \(\mathcal{O}(n)\) time and edit the network in \(\mathcal{O}(\log\max_{\omega})\) time. ◻

Proof of Theorem 8. For a given instance \({\mathcal{I}}= ({\mathcal{N}}= (V,E), k, D)\) apply all of the reduction rules exhaustively to receive an instance \({\mathcal{I}}' = ({\mathcal{N}}' = (V',' k', D')\) of MapPD in which none of the reduction rules apply. As discussed above, this instance may have vertices with in- and out-degree larger than \(1\), and edges with weight \(0\), neither of which are formally allowed by our definition of MapPD. We now discuss how the instance may be edited to fix these issues.

First, we replace each vertex \(v\) which has an in-degree and an out-degree of larger than 1 with a vertex \(v_{\text{in}}\) receiving all the incoming edges of \(v\) and a vertex \(v_{\text{out}}\) receiving all the outgoing edges, and add an edge \((v_{\text{in}},v_{\text{out}})\) of weight 0. Finally, we multiply each edge weight and \(D'\) by \((|E'|+1)\), and the edges with weight 0 to weight 1. Let \({\mathcal{I}}^* = ({\mathcal{N}}^* = (V^*,E^*), k^*, D^*)\) denote the resulting instance of MapPD.

In what follows we let \(R,Q,P\) and \(A,B,Y,Z\) denote the sets of vertices in \({\mathcal{N}}\) as defined in [def:cor-side,def:top-strings] respectively. We let \(R^*,Q^*,P^*\) and \(A^*,B^*,Y^*,Z^*\) denote the corresponding vertices in \({\mathcal{N}}^*\).

The correctness follows from the correctness of the reticulation rules.

Running time. Observe that [rr:top-strings,rr:A,rr:pathlength] remove one taxon each, while [rr:trees,rr:a>a+b] decrease \(|X\setminus A|\) by \(1\). As none of the reduction rules increase \(|X|\) or \(|X\setminus A|\), these rules are applied at most \(|X| + |X\setminus A| \leq 2 |X|\) times in total. For 2, we note that [rr:trees,rr:a>a+b,rr:top-strings,rr:A,rr:pathlength] each create one additional degree-2 vertex, and 4 does not create any. Thus, every application of 2 is either on at most \(n\) initial degree-2-vertices or occurs after an application of one of [rr:trees,rr:a>a+b,rr:top-strings,rr:A,rr:pathlength], and thus 2 is applied at most \(2 \cdot |X| + n\) times.

Each application of 4 reduces the number of side-paths starting at a non-root vertex of length of at least 2. None of the reduction rules increase this measure, and so the number of application of 4 is bounded by the number of side-paths in the original network, which is \(\mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\) by [obs:core-retic-bound].

Therefore, the total number of applications of all reduction rules is \(\mathcal{O}(|X| + n + {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}) \;\mathcal{O}(n)\). Note that a single application of any reduction rule takes \(\mathcal{O}((m+ n\log n)\cdot \log\max_{\omega})\) time by [lem:trees,lem:deg-2,lem:a>a+b,lem:strings,lem:top-strings,lem:A,lem:pathlength]. An application of 2 may increase \(\max_{\omega}\), but the total weight of the network never increases and therefore the maximum weight of any edge at any stage in the algorithm is at most the total weight of the network, or at most \(m \cdot \max_{\omega}\). Therefore, the maximum running time of any application of a reduction rule is \(\mathcal{O}((m+ n\log n)\cdot (\log m + \log\max_{\omega}))\). We conclude that applying all rules exhaustively takes \(\mathcal{O}((|X| + {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}) \cdot (m+ n\log n)\cdot (\log m + \log\max_{\omega}))\) time, which can be summarized as \(\mathcal{O}(m^2 \log^2 m \cdot \log \max_{\omega})\). The final step of replacing vertices with in-and out-degree greater than \(1\) and adjusting edge-weights can be done in \(\mathcal{O}(m \cdot (\log m + \log \max_{\omega}))\), and so the final running time remains \(\mathcal{O}(m^2 \log^2 m \cdot \log \max_{\omega})\).

Size. Each application of 4 increases the number of reticulation-edges by one. Therefore, note that by \(\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}\) we refer to the parameter in the original network.

Observe that none of the reduction rules (except for 4) change the number of reticulations or core vertices in the network. Reduction Rule 4 may turn some core vertices into reticulations but otherwise does not create new core vertices or reticulations. Therefore, we have \(|R^*| + |Q^*| = |R| + |Q| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\) by Observation [obs:core-retic-bound].

As 4 is exhaustively applied, we have that each side-path in \({\mathcal{N}}^*\) not leaving the root has at most one internal vertex, and this vertex has one leaf child. There are \(\mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\) side-paths in \({\mathcal{N}}^*\) by [obs:core-retic-bound] and the fact that none of the reduction rules increase the number of side-paths not leaving the root. Thus, we have that the total number of vertices reachable from \(R^* \cup (Q^*\setminus \rho)\) is at most \(\mathcal{O}(|R^*| + |Q^*|) + \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}) = \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\). That is, \(|B^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\).

The size of \(Y^*\) is the number of side-paths starting at the root. There are at most \(|Q| + 2\cdot{\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}\) such paths in the original instance. Each application of 4 adds one such path. We saw that \(|Q| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\) and 4 can be applied \(\mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\) times. We conclude \(|Y^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\).

After 5 has been applied exhaustively, we may conclude that \(k^* \le |B^*| + |Y^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\). After 6 has been applied exhaustively, there are at most \(k^*\) vertices in \(A^*\) and after 7 has been applied exhaustively, each side-path has length at most \(k^*\) such that \(|Y^*| + |Z^*| \le |Y^*| \cdot (k^* + 1) \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}^2)\). We conclude \(|V^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}^2)\).

We have \(\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}^*} \le {\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}+ |Q^*| + |R^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}})\). Because \({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}= |E| - |V|\) in any network, we conclude \(|E^*| = \mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}^*} + |V^*| \in \mathcal{O}({\mathop{\mathrm{{e-ret}}}_{{\mathcal{N}}}}^2)\). ◻