# Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond.

Leo van Iersel, Mark Jones, Jannik Theodor Schestag, Celine Scornavacca, Mathias Weller

► To cite this version:

Leo van Iersel, Mark Jones, Jannik Theodor Schestag, Celine Scornavacca, Mathias Weller. Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond. The 22nd RECOMB-CG conference, Apr 2025, Seoul, South Korea. 24 p. hal-04987366

HAL Id: hal-04987366

https://hal.science/hal-04987366v1

Submitted on 10 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Phylogenetic Network Diversity Parameterized
by Reticulation Number and Beyond

Leo van Iersel¹,[0000-0001-7142-4706]*, Mark Jones¹,[0000-0002-4091-7089]*,
Jannik Schestag¹,[0000-0001-7767-2970]**,
Celine Scornavacca²,[0009-0004-0179-9771]***, and
Mathias Weller³,[0000-0002-9653-3690]

1 TU Delft, The Netherlands {l.j.j.vanIersel,j.t.schestag}@tudelft.nl

² ISEM, Université de Montpellier, CNRS, IRD, EPHE, France
celine.scornavacca@umontpellier.fr

³ LIGM, CNRS, Université Gustave Eiffel, France mathias.weller@u-pem.fr

**Abstract.** Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the MAX-NETWORK-PD problem: given such a network, find *k* species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in $O(2^r \log(k)(n+r))$ time, with *n* the total number of species in the network and *r* its reticulation number. Furthermore, we show that MAX-NETWORK-PD is NP-hard for level-1 networks, proving that, unless P=NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.

# 1 Introduction

As human activities drive a sixth mass extinction [15], and in the absence of a serious political response to this crisis [11], studying phylogenetic diversity (PD) is timely.

Indeed, when experiencing a widespread and rapid decline in Earth's biodiversity, one could wonder where to put our efforts in order to preserve a maximum amount of *biodiversity*, given some temporal and economic constraints [18]. The concept of PD is an attempt at answering this question. The concept has been introduced three decades ago in an impactful paper by Daniel Faith [4]. The underlying idea is simple: if we want to preserve as much biodiversity as possible

<footnote>* Partially funded by the Dutch Research Council (NWO) grant OCENW.KLEIN.125 and OCENW.M.21.306.</footnote>

<footnote>** Partially funded by the Dutch Research Council (NWO), project "Optimization for and with Machine Learning (OPTIMAL)" OCENW.GROOT.2019.015.</footnote>

<footnote>*** Partially funded by French Agence Nationale de la Recherche through the CoCoAlSeq Project (ANR-19-CE45-0012).</footnote>
within a group X of species and we can rescue at most *k* species, then we should focus our effort on a size-*k* subset *S* ⊆ X of species that showcase, overall, a wide range of features, that is, the distinct traits and qualities covered by the species of *S* are maximum among all such subsets. This *feature diversity* (FD) of *S* is often approximated using the PD of *S*, which is in turn defined as follows: Given a tree *T* representing the evolution of the species in *X*, the PD of *S* (in *T*) is the sum of the branch lengths of the subtree connecting the root and the species in *S*. (Note that approximating FD with PD may not always be appropriate, see [20].)

PD has been extensively used in the context of tree-like evolution, and, given
a tree *T* and an integer *k*, an optimal solution with *k* species can be found with
a greedy algorithm [14, 17].

However, when the evolution of the species under interest is also shaped by
reticulate events such as hybrid speciation, lateral gene transfer, or recombination,
then the picture is no longer as rosy. In the case of reticulate events, a single species
may inherit genetic material and, thus, features from multiple direct ancestors,
and its evolution should be represented by a phylogenetic network [7] rather
than a tree. Several ways of extending the notion of PD for networks have been
proposed [2, 8, 19], one of which is called Network-PD. The optimization problem
linked to Network-PD, i.e. computing the maximum Network-PD$_N$ score over all
subsets of species of size at most *k* for a given phylogenetic network *N*, is named
MAX-NETWORK-PD. Bordewich et al. [2] proved that MAX-NETWORK-PD is
NP-hard and cannot be approximated in polynomial time with an approximation
ratio better than $1 - \frac{1}{e}$ unless P = NP; furthermore, it remains NP-hard even
for the restricted class of phylogenetic networks called “normal” networks.

The contribution of this paper is twofold. First, we present an algorithm
for MAX-NETWORK-PD parameterized by the reticulation number of the input
network. Herein, we leverage the greedy algorithm for PD on trees [14, 17] to
efficiently process the subtree below a reticulate event. Surprisingly, we show
that this algorithm cannot be generalized to use the “level” as parameter unless
P = NP. The level of a network is a measure of its treelikeness, formally defined
in the next section, which can be smaller than the reticulation number. More
precisely, we prove that MAX-NETWORK-PD is NP-hard even on level-1 networks
(which are networks without overlapping cycles), thereby answering an open
question of Bordewich et al. [2].

## 2 Preliminaries

For a positive integer $n$, denote $[n] := \{1, \dots, n\}$. Let $(0,1) := \{x \in \mathbb{R} : 0 < x < 1\}$ and $[0,1] := (0,1) \cup \{0,1\}$. Let $\mathbb{R}_{>0} := \{x \in \mathbb{R} : x > 0\}$ and $\mathbb{R}_{\ge 0} := \mathbb{R}_{>0} \cup \{0\}$. For a set $Z$ and an integer $k$ with $k \le |Z|$, by $\binom{Z}{k}$ we denote the set of all subsets of $Z$ with exactly $k$ elements. In this paper, we make use of both natural and binary logarithms. We write $\ln x$, and $\log_2 x$, to denote the logarithm of $x$ to the base $e$ and 2, respectively.

**Phylogenetics.** Consider the example network of Figure 1. Given a set of taxa *X*, a *phylogenetic network on* *X* or *X-network* is a directed acyclic graph *N* = (*V*, *E*)
<figure><img src="image_2.png" /><figcaption>Fig. 1: A hypothesized heritage of several species of fish in a phylogenetic network [9]. We take the inheritance probabilities to be 0.4 for reticulation edges and 1 for other edges. Edge weights are indicated by integers to the right of each edge. Edge weights and inheritance probabilities are not based on data and for illustrative purposes only. The three reticulations are depicted as black filled vertices. The biggest subgraph without cut edges is shaded. The level and the reticulation number of the network are 3. It can be shown that the sets {B, D} and {B, C, D, F} maximize Network-PD$_N$ among all size-2 and size-4 subsets of taxa, respectively. As an example, we illustrate how to compute the Network-PD score for $Z = \{A, B, D\}$. The decimal numbers left of the edges indicate the $\gamma_Z^p(e)$-values (see Definition 1), leading to a score of Network-PD$_N^p(Z) = 195.968$. Dashed edges have $\gamma_Z^p(e) = 0$ and hence do not contribute towards the Network-PD score.</figcaption></figure>

in which the *leaves*, vertices of indegree 1 and outdegree 0, are bijectively labeled with elements from $X$, and in which the *root* is the single vertex of indegree 0 and outdegree 2, and in which all other vertices either are *tree vertices* and have indegree 1 and outdegree at least 2 or are *reticulations* and have indegree at least 2 and outdegree 1. Edges incoming at reticulations are *reticulation edges*. When $X$ is clear from context, we refer to an $X$-network simply as a *network* or *phylogenetic network*. A *phylogenetic tree* $\mathcal{T} = (V, E)$ on $X$ or $X$-tree is an $X$-network with no reticulations. A network is *binary* if the maximum indegree and outdegree of any vertex is 2.

The *reticulation number* of a network $\mathcal{N}$ is the sum of the indegrees of all reticulations minus the number of reticulations. If $\mathcal{N}$ is binary, then the reticulation number is exactly the number of reticulations. The *level* of $\mathcal{N}$ is the maximum reticulation number among subgraphs with no cut-arcs (arcs whose removal disconnects the network).

For each edge $e = uv$ we say that $u$ is a *parent* of $v$ and $v$ is a *child* of $u$. For vertices $u, v \in V$, we say $u$ is an *ancestor* of $v$ and $v$ is a *descendant* of $u$ if there
<figure><img src="image_3.png" /></figure>

<table><caption>Fig. 2: An example for calculating $\gamma_Z^p(e)$. Reticulations are black. The chosen sets are $Z_1 = \{\ell_1\}$, $Z_2 = \{\ell_2\}$, $Z_3 = \{\ell_1, \ell_2\}$. Network-PD$_N^p(Z)$ for $Z = Z_1, Z_2, Z_3$ is 55, 50.4, and 72.8, respectively.</caption><thead><tr><th></th><th>ρv<sub>1</sub></th><th>ρv<sub>2</sub></th><th>v<sub>1</sub>v<sub>2</sub></th><th>v<sub>2</sub>v<sub>3</sub></th><th>v<sub>1</sub>v<sub>4</sub></th><th>v<sub>3</sub>v<sub>4</sub></th><th>v<sub>3</sub>ℓ<sub>1</sub></th><th>v<sub>4</sub>ℓ<sub>2</sub></th></tr></thead><tbody><tr><td>ω(e)</td><td>50</td><td>40</td><td>10</td><td>5</td><td>30</td><td>8</td><td>4</td><td>2</td></tr><tr><td>p(e)</td><td>1</td><td>0.4</td><td>0.5</td><td>1</td><td>0.2</td><td>0.6</td><td>1</td><td>1</td></tr><tr><td>γ<sup>p</sup><sub>Z1</sub>(e)</td><td>0.5</td><td>0.4</td><td>0.5</td><td>1</td><td>0</td><td>0</td><td>1</td><td>0</td></tr><tr><td>γ<sup>p</sup><sub>Z2</sub>(e)</td><td>0.44</td><td>0.24</td><td>0.3</td><td>0.6</td><td>0.2</td><td>0.6</td><td>0</td><td>1</td></tr><tr><td>γ<sup>p</sup><sub>Z3</sub>(e)</td><td>0.6</td><td>0.4</td><td>0.5</td><td>1</td><td>0.2</td><td>0.6</td><td>1</td><td>1</td></tr></tbody></table>

is a directed path from $u$ to $v$ in $\mathcal{N}$. If in addition $u \neq v$, we say $u$ is a *strict* ancestor of $v$ and $v$ a *strict* descendant of $u$. The set of *offspring* of $e$, denoted $\text{off}(e)$, is the set of all $x \in X$ which are descendants of $v$. Throughout this paper, we use the terms taxon/taxa, species, and leaf/leaves interchangeably.

**Diversity.** We assume that each edge $e$ in a network $\mathcal{N} = (V, E)$ has an associated positive integer weight $\omega(e)$. These weights are used to represent some measure of difference between two species. Given an $X$-tree $\mathcal{T}$ and a weight function $\omega: E \to \mathbb{N}$, the *phylogenetic diversity* $\text{PD}_{\mathcal{T}}(Z)$ of any subset $Z \subseteq X$ is given by $\text{PD}_{\mathcal{T}}(Z) := \sum_{e \in \text{off}(e) \cap Z \neq \emptyset} \omega(e)$. That is, $\text{PD}_{\mathcal{T}}(Z)$ is the total weight of all edges in $\mathcal{T}$ that are above some leaf in $Z$.

The phylogenetic diversity model assumes that features of interest appear along edges of the tree with frequency proportional to the weight of that edge, and that any feature belonging to one species is inherited by all its descendants. Thus, $\text{PD}_{\mathcal{T}}(Z)$ corresponds to the expected number of distinct features appearing in all species in $Z$.

Initially defined only for trees, several extensions of the definition to phylogenetic networks have recently been proposed [2, 19]. In this paper, we focus Network-PD$_N$ (defined below), which allows the case that reticulations may not inherit all of the features from every parent. This is modeled via an *inheritance probability* $p(e) \in [0, 1]$ on each reticulation edge $e = uv$. Here, $p(e)$ represents the expected proportion of features present in $u$ that are also present in $v$; or equivalently, $p(e)$ is the probability that a feature in $u$ is inherited by $v$. Non-reticulation edges can be considered as having inheritance probability 1.

For a subset of taxa $Z \subseteq X$, the measure Network-PD$_N(Z)$ represents the expected number of distinct features appearing in taxa in $Z$ [2]. For each evolutionary branch $uv$, this measure is obtained by multiplying the number $\omega(uv)$ of features developed on the branch $uv$ (which is assumed to be proportional to the length of the branch) with the probability $\gamma_Z^p(uv)$ that a random feature appearing in $u$ or developed on $uv$ will survive when preserving $Z$.

Formally, we define $\gamma_Z^p(uv)$ as follows. Consider an example in Figure 2.
**Definition 1.** Given a network $\mathcal{N} = (V, E)$ with edge weights $\omega: E \to \mathbb{N}$, probabilities $p: E \to [0, 1]$ and a set of taxa $Z \subseteq X$, we define $\gamma_Z^p: E \to [0, 1]$ recursively for each edge $uv \in E$ as follows:

- If $v$ is a leaf, then $\gamma_Z^p(uv) := p(uv)$ if $v \in Z$, and $\gamma_Z^p(uv) = 0$ otherwise. (Intuition: The features of $v$ survive if and only if $v$ is preserved by $Z$.) In most of the paper, with the notable exception of Section 3, $p(uv) = 1$ if $v$ is a leaf.

- If $v$ is a reticulation with outgoing arc $vx$, then $\gamma_Z^p(uv) = p(uv) \cdot \gamma_Z^p(vx)$. (Intuition: $v$'s features are a mixture of features of its parents and the features of $u$ have a certain probability $p(uv)$ of being included in this mix and, thereby, survive in preserved descendants of $x$.)

- If $v$ is a tree node with children $x_i$, then $\gamma_Z^p(uv) = 1 - \prod_i(1 - \gamma_Z^p(vx_i))$. In the special case that $v$ has two children, this is equal to $\gamma_Z^p(vx) + \gamma_Z^p(vy) - \gamma_Z^p(vx) \cdot \gamma_Z^p(vy)$. (Intuition: To lose a feature of $v$, it has to be lost in both children $x$ and $y$ of $v$, which are assumed to be independent events, since both copies of the feature develop independently.)

When clear from the context, we will omit the superscript $p$. Further, we only consider values of $p$ on edges incoming to leaves or reticulations, so we may restrict the domain of $p$ to those edges. We can now define the measure $\text{Network-PD}_{\mathcal{N}}^p(Z)$ for a subset of taxa $Z$ as follows: $\text{Network-PD}_{\mathcal{N}}^p(Z) = \sum_{e \in E} \omega(e) \cdot \gamma_Z^p(e)$.
Since we assume that all weights are non-negative, we observe that both $\gamma_Z^p(e)$ and $\text{Network-PD}_{\mathcal{N}}(Z)$ are monotone on $Z$, that is, $\gamma_{Z'}^p(e) \le \gamma_Z^p(e)$ and $\text{Network-PD}_{\mathcal{N}}^p(Z') \le \text{Network-PD}_{\mathcal{N}}^p(Z)$ for all $Z' \subseteq Z \subseteq X$. We can now formally define the main problem studied in this paper:

**MAX-NETWORK-PD**

**Input:** A phylogenetic network $\mathcal{N} = (V, E)$ on $X$ with edge weights $\omega: E \to \mathbb{N}$, inheritance probabilities $p: E \to [0, 1]$, and integers $k, D \in \mathbb{N}$.

**Question:** Is there a $Z \subseteq X$ with $|Z| \le k$ and $\text{Network-PD}_{\mathcal{N}}(Z) \ge D$?

Note that, if $p(e) = 1$ for all edges $e$ incoming to leaves (all "preservation projects" succeed with probability 1) and a node $v$ has no reticulation descendants, then $\gamma_Z(uv) = 1$ if $\text{off}(e) \cap Z \ne \emptyset$, and otherwise $\gamma_Z(uv) = 0$ (see Lemma 1). In this setting, $\text{Network-PD}_{\mathcal{N}}$ coincides with $\text{PD}_{\mathcal{N}}$ if $\mathcal{N}$ is a tree. This holds even if all leaves are weighted and the total weight of $Z$ must not exceed $k$.

Throughout the paper, we assume that integers are encoded in binary and that rational numbers $p/q$ (with $p$ and $q$ coprime integers) are encoded using binary encodings of $p$ and $q$. See Appendix A for details.

## 3 A Branching Algorithm

In this section, we show that $\text{MAX-NETWORK-PD}$ is fixed-parameter tractable with respect to the reticulation number of the input network. To facilitate the explanation of our algorithm, we solve a generalization of $\text{MAX-NETWORK-PD}$,
<figure><img src="image_4.png" /><figcaption>Fig. 3: Examples of Reduction Rules 1 and 2 are depicted on the left and on the right, respectively. White leaves have an inheritance probability of zero. Costs are written below the leaves.</figcaption></figure>

where (a) each leaf $\ell$ is assigned a cost $c(\ell) \in \{0, 1\}$, (b) the leaf-edges may have inheritance probability $p(v\ell) \le 1$ (as well as the reticulation edges), with the condition that $p(v\ell) = 1$ if $c(\ell) = 1$, and (c) we look for a subset $Z$ of leaves with total cost at most $k$ (instead of cardinality $k$). We refer to this problem as 0/1-COST MAX-NETWORK-PD and we use $p(\ell)$ instead of $p(v\ell)$ whenever $\ell$ is a leaf with parent $v$.

In the following, let $\mathcal{I} := (\mathcal{N}, \omega, p, c, k, D)$ be an instance for 0/1-COST MAX-NETWORK-PD, let $r$ be a lowest reticulation in $\mathcal{N}$ with outgoing edge $rx$. Our algorithm “guesses” whether or not any cost-1 leaf below $r$ is in a solution $Z$. If not, then we remove all cost-1 leaves below $r$ and use reduction rules to (a) turn the resulting subtree into a single leaf below $r$ and (b) turn $r$ into two new cost-0 leaves with inheritance probabilities according to $\gamma_Z rx$. If some (unknown) cost-1 leaf below $r$ is in a solution, we show that such a leaf can be picked greedily. Then, we decrement $k$, set the cost of that leaf to zero, and use the knowledge that $\gamma_Z rx = 1$ to remove $r$ from the network.

Note that our reduction and branching rules may create nodes with high outdegree, even if the input network is binary. However, the algorithm used to solve the resulting non-binary tree can deal with such polytomies [12].

**Reduction.** Let $r$ be a lowest reticulation in $\mathcal{N}$ and let $E_r$ be the set of edges below $r$. The following reduction rules simplify $\mathcal{I}$ by getting rid of cost-0 leaves below $r$. Note that each rule assumes that $\mathcal{I}$ is reduced with respect to the previous rules. See Figure 3 for examples of Reduction Rules 1 and 2, and Figure 4 for examples of Reduction Rules 3 and 4.

**Reduction Rule 1.** Let $uv \in E_r$ such that $v$ has a single child $w$. Then, contract $v$ onto $u$ and set $\omega(uw) := \omega(uv) + \omega(vw)$, $p(uw) = p(vw)$.

**Correctness of Reduction Rule 1.** Let $\mathcal{I}' := (\mathcal{N}', \omega', p', c, k, D')$ be the result of applying Reduction Rule 1 to $\mathcal{I}$. Clearly, we have $\gamma_Z^{p'}(e) = \gamma_Z^p(e)$ for any edge $e$ below $w$ and all $Z$. So by construction $\gamma_Z^{p'}(uw) = \gamma_Z^p(vw)$. Observe that $p(uv) = 1$ since $v$ is not a leaf and $r$ is the lowest reticulation in $\mathcal{N}$; thus, $\gamma_Z^p(uv) = \gamma_Z^p(vw) = \gamma_Z^{p'}(uw)$. This implies that $\gamma_Z^{p'}(e) = \gamma_Z^p(e)$ for all $Z$ and any
<figure><img src="image_5.png" /><figcaption>Fig. 4: Examples of Reduction Rules 3 and 4 are depicted on the left and on the right, respectively. Black leaves have a positive inheritance probability. Costs are written below the leaves.</figcaption></figure>

$e \in E \setminus \{uv, vw\}$. So, Network-PD$_N(Z)$ - Network-PD$_{N'}(Z) = \gamma_Z^p(uv) \cdot \omega(uv) + \gamma_Z^p(vw) \cdot \omega(vw) - \gamma_Z^{p'}(uw) \cdot w(uw) = \gamma_Z^p(uv) \cdot (w(uv) + w(vw) - w(uw)) = 0. \square$

**Reduction Rule 2.** Let $v\ell \in E_r$ such that $\ell$ is a leaf, $v \neq r$, and $p(v\ell) = 0$. Then, remove $\ell$.

*Correctness of Reduction Rule 2.* Let $u$ be the parent of $v$, and let $v_1, \dots, v_t$ denote the children of $v$ with $v_i \neq \ell$. Then $1 - (1 - \gamma_Z^p(v\ell)) \prod_i (1 - \gamma_Z^p(uv_i))$ is the value of $\gamma_Z^p(uv)$ before removing $\ell$ which equals $1 - \prod_i (1 - \gamma_Z^p(uv_i))$, the value afterward, since $\gamma_Z^p(v\ell) = 0$ for all $Z$. $\square$

**Reduction Rule 3.** Let the unique child $x$ of $r$ be a leaf with cost $c(x) = 0$. Then, for each parent $z_i$ of $r$, add a new leaf $\ell_{z_i}$ to $z_i$ with $c(\ell_{z_i}) := 0$ and $p(\ell_{z_i}) := p(z_i r) \cdot p(r x)$ and $\omega(z \ell_{z_i}) := \omega(z_i r)$. Finally, remove $r$ and $x$ and decrease $D$ by $p(r x) \cdot \omega(r x)$.

*Correctness sketch of Reduction Rule 3.* As $x$ has cost 0 and $\gamma_Z^p$ is monotone on $Z$, every maximal solution for $\mathcal{I}$ contains $x$. Likewise, every maximal solution for the modified instance $\mathcal{I}'$ contains all $\ell_{z_i}$. Then, one can verify that maximal solutions for $\mathcal{I}$ collect exactly the score of $rx$ more than maximal solutions for $\mathcal{I}'$, which is $p(r x) \cdot \omega(r x)$. $\square$

**Reduction Rule 4.** Let $x$ be the unique child of $r$, let $Q$ be the set of cost-0 leaves below $r$, and let $E_x := E_r \setminus \{rx\}$. Then,

(1) for each $uv \in E_x$, multiply $\omega(uv)$ by $1 - \gamma_Q^p(uv)$,

(2) for each $\ell \in Q$, set $p(\ell) := 0$,

(3) reduce $D$ by $\sum_{e \in E_x} \gamma_Q^p(e) \cdot \omega(e)$, and

(4) add a new cost-0 leaf $\ell^*$ as a child of $x$ with $\omega(x\ell^*) = 0$ and $p(\ell^*) = \gamma_Q^p(r x)$.

To prove the correctness of Reduction Rule 4, we use the following lemma.

**Lemma 1.** Let $uv$ be an edge in $\mathcal{N}$ such that all descendants of $v$ (including $v$) are tree nodes and let $Z$ be a leaf set of $\mathcal{N}$. Then, $\gamma_Z^p(uv) = 1 - \prod_{\ell \in \text{off}(uv) \cap Z} (1 - p(\ell))$.
**Proof.** We prove the claim by induction on the length of a longest path from $v$ to a leaf. In the induction base, $v$ is a leaf and, thus, $\gamma_Z^p(e) = 1 - \prod_{\ell \in \text{off}(e) \cap Z} (1-p(\ell))$ since this is $1 - (1-p(v)) = p(v)$ if $v \in Z$ and $0$ otherwise. For the induction step, let $v$ be a tree node with children $x_i$ and assume the claim is true for each edge $vx_i$. Then,

$$ \gamma_Z^p(e) \stackrel{\text{Def. 1}}{=} 1 - \prod_i (1 - \gamma_Z^p(vx_i)) \stackrel{\text{IH}}{=} 1 - \prod_i \left(1 - \left(1 - \prod_{\ell \in \text{off}(vx_i) \cap Z} (1-p(\ell))\right)\right) \\ = 1 - \prod_i \left( \prod_{\ell \in \text{off}(vx_i) \cap Z} (1-p(\ell)) \right) = 1 - \prod_{\ell \in \text{off}(e) \cap Z} (1-p(\ell)) \quad \square $$

*Correctness of Reduction Rule 4.* Let $\mathcal{I}' = (\mathcal{N}, \omega', p', c, k, D')$ be the result of applying Reduction Rule 4 to $\mathcal{I}$ and let $Q' := Q \cup \{\ell^*\}$. We assume all solutions $Z$ to be maximal, implying that they contain all cost-0 leaves. Note that generality is not lost since Network-PD$^p_{\mathcal{N}}(Z)$ is monotone on $Z$. Let $Z$ and $Z'$ be any subsets of leaves of $\mathcal{N}$ and $\mathcal{N}'$, respectively, with $Q \subseteq Z$ and $Z' = Z \cup \{\ell^*\}$. We show that $Z$ is a solution for $\mathcal{I}$ if and only if $Z'$ is a solution for $\mathcal{I}'$.

We consider the contribution of each edge to the diversity score of $Z$ in $\mathcal{N}$ and the diversity score of $Z'$ in $\mathcal{N}'$. If $Z$ (and, thus, also $Z'$) contains a cost-1 leaf $\ell$ below $r$, then $p(\ell) = 1$ and, by Lemma 1, we have $\gamma_Z^p(rx) = 1 = \gamma_{Z'}^{p'}(rx)$. Otherwise, $\gamma_Z^p(rx) = \gamma_Q^p(rx) = p'(\ell^*) = \gamma_{\{\ell^*\}}^{p'}(rx) = \gamma_{Z'}^{p'}(rx)$. In both cases, $\gamma_Z^p(e) = \gamma_{Z'}^{p'}(e)$ for all $e \in E \setminus E_r$ since these values only depend on the values of the edges below $e$. Further, note that $\omega(x\ell^*) \cdot \gamma_{Z'}^{p'}(x\ell^*) = \omega(x\ell^*) \cdot p(\ell^*) = 0$. Thus, it remains to consider the edges in $E_x := E_r \setminus \{rx\}$. For any such edge $e \in E_x$, we observe

$$ \gamma_Z^p(e) \stackrel{\text{Lemma 1}}{=} 1 - \prod_{\ell \in \text{off}(e) \cap Z} (1-p(\ell)) = 1 - \prod_{\ell \in \text{off}(e) \cap Q} (1-p(\ell)) \cdot \prod_{\ell \in \text{off}(e) \cap Z \setminus Q} (1-p(\ell)) $$

and, since $p(\ell) = 1$ for all $\ell \in Z \setminus Q$ by convention stated in the problem definition, we have

$$ \gamma_Z^p(e) = \begin{cases} 1 - \prod_{\ell \in \text{off}(e) \cap Q} (1-p(\ell)) & \text{if } \text{off}(e) \cap Z \subseteq Q \\ \frac{\gamma_Q^p(e)}{1} & \text{otherwise} \end{cases} $$

and the same holds for $p'$ and $Z'$ instead of $p$ and $Z$ since the leaves below $e$ in $\mathcal{N}$ are exactly the leaves below $e$ in $\mathcal{N}'$ ($\ell^*$ cannot be below $e$ in $\mathcal{N}'$ since $e \in E_x$). Now, since $p'(\ell) = 0$ for all $\ell \in Q$ by construction, we have

$$ \gamma_{Z'}^{p'}(e) = \begin{cases} 0 & \text{if } \text{off}(e) \cap Z \subseteq Q \\ 1 & \text{otherwise} \end{cases} $$
implying $\gamma_Z^p(e) = \gamma_{Z'}^{p'}(e) \cdot (1 - \gamma_Q^p(e)) + \gamma_Q^p(e)$. Then,

$$ 
\begin{aligned}
\sum_{e \in E} \gamma_Z^p(e) \cdot \omega(e) - \sum_{e \in E \cup \{x\ell^*\}} \gamma_{Z'}^{p'}(e) \cdot \omega'(e) &= \sum_{e \in E_x} (\gamma_Z^p(e) \cdot \omega(e) - \gamma_{Z'}^{p'}(e) \cdot \omega'(e)) \\
&\stackrel{\text{Defn } \omega'}{=} \sum_{e \in E_x} (\gamma_Z^p(e) - \gamma_{Z'}^{p'}(e) \cdot (1 - \gamma_Q^p(e))) \cdot \omega(e) \\
&= \sum_{e \in E_x} \gamma_Q^p(e) \cdot \omega(e) = D - D'
\end{aligned}
$$

Thus, $\sum_{e \in E} \gamma_Z^p(e) \cdot \omega(e) \ge D$ if and only if $\sum_{e \in E} \gamma_{Z'}^{p'}(e) \cdot \omega(e) \ge D'$. $\square$

**Branching.** Observe that, if no reduction rule applies to $\mathcal{N}$, then the subtree below any lowest reticulation $r$ has at least one cost-1 leaf and at most one cost-0 leaf. An important part of the correctness of our branching algorithm is that solutions may be assumed to pick cost-1 leaves “greedily”, that is, if a solution chooses any cost-1 leaf below $r$, then there is also a solution choosing a “heaviest” cost-1 leaf below $r$ instead.

**Lemma 2.** Let $r$ be a lowest reticulation in $\mathcal{N}$ and let $a$ be a cost-1 leaf below $r$ in $\mathcal{N}$ maximizing the weight of the $r$-a-path. Let $Z$ be any set of leaves of $\mathcal{N}$ containing a cost-1 leaf below $r$. Then, there is a set $Z^*$ of leaves of $\mathcal{N}$ with the same cost as $Z$ with $a \in Z^*$ and Network-$PD_{\mathcal{N}}^p(Z^*) \ge Network-$PD_{\mathcal{N}}^p(Z)$.

*Proof.* Suppose that $a \notin Z$ as otherwise, the claim is trivial. Let $b \in Z$ be a cost-1 leaf below $r$ such that $u := LCA(a, b)$ is lowest possible (has maximal (unweighted) distance from $r$), and let $Z^* := (Z \setminus \{b\}) \cup \{a\}$. Let $q_a$ and $q_b$ be the unique paths from $u$ to $a$ and $b$, respectively, and note that $\omega(q_a) \ge \omega(q_b)$ by choice of $a$. Furthermore, for each edge $uv$ on $q_a$, we know that $Z$ contains no leaf below $v$ (by maximality of the $r$-u-path). Since both $a$ and $b$ are cost-1 leaves, we have $p(a) = p(b) = 1$ by convention stated in the problem definition, implying that $\gamma_Z^p(e_b) = \gamma_{Z^*}^p(e_a) = 1$ for all edges $e_a$ on $q_a$ and $e_b$ on $q_b$. Thus, $\text{Network-$PD_{\mathcal{N}}^p(Z^*)$} - \text{Network-$PD_{\mathcal{N}}^p(Z)$} = \sum_{e \in E} \gamma_{Z^*}^p(e)\omega(e) - \sum_{e \in E} \gamma_Z^p(e)\omega(e) = \omega(q_a) - \omega(q_b) \ge 0$. $\square$

Now, we can present and prove the correctness of our main branching rule, solving 0/1-COST MAX-NETWORK-PD in $O^*((|R|/k))$ time, where $R$ is the set of reticulations in the input network and $k$ is the budget.

**Branching Rule 1** (See Figure 5). Let $\rho$ be the root of $\mathcal{N}$. Let $r$ be a lowest reticulation in $\mathcal{N}$ whose unique child $x$ is not a 0-cost leaf. Let $Q$ be the set of cost-0 leaves below $r$. Then,

1. create the instance $\mathcal{I}_0 := (\mathcal{N}_0, \omega_0, p_0, c_0, k, D)$ by

(a) setting $p_0(t) := 0$ and $c(t) := 0$ for all cost-1 leaves $t$ below $r$,

(b) replacing $rx$ with $\rho x$, setting $\omega_0(\rho x) := \omega(r x)$ and,

(c) adding a new leaf $\ell$ to $r$ with $p_0(\ell) := \gamma_Q^p(r x)$ and $c_0(\ell) := \omega_0(r \ell) := 0$, and

2. create the instance $\mathcal{I}_1 := (\mathcal{N}_1, \omega_1, p_1, c_1, k-1, D)$ by
<figure><img src="image_6.png" /><figcaption>Fig. 5: An example of Branching Rule 1 with $\mathcal{I}_0$ ("do not select a cost-1 leaf below $r$") on the left and $\mathcal{I}_1$ ("select a cost-1 leaf below $r$") on the right. Black leaves have an inheritance probability of one. Costs are written below the leaves. Note that the budget for $\mathcal{I}_1$ is $k-1$ and that applying Reduction Rule 4 may change the target diversity.</figcaption></figure>

(a) finding a cost-1 leaf a below $r$ maximizing the weight of the $r$-a-path and setting $c_1(a) := 0$,

(b) replacing $rx$ with $\rho x$, setting $\omega_1(\rho x) := \omega(rx)$ and

(c) adding a new leaf $\ell$ to $r$ with $p_1(\ell) := 1$ and $c_1(\ell) := \omega_1(r\ell) := 0$.

Correctness of Branching Rule 1. Let $P$ denote the set of cost-1 leaves below $r$ in $\mathcal{I}$ and recall that $Q$ contains all cost-0 leaves below $r$ in $\mathcal{I}$, and that $c(Q) = c_0(Q) = 0$. We show that $\mathcal{I}$ has a solution $Z$ if and only if $\mathcal{I}_0$ or $\mathcal{I}_1$ has a solution. Without loss of generality, we may assume solutions to be maximal, that is, they contain all cost-0 leaves. For any leaf-set $Z$ containing all cost-0 leaves in $\mathcal{I}$ and any leaf-set $Z_i$ containing all cost-0 leaves in $\mathcal{I}_i$ for some $i \in \{0, 1\}$, we then have

$$ \gamma_{Z_i}^{p_i}(\rho x) = \begin{cases} \gamma_Q^p(rx) & \text{if } i=0 \\ 1 & \text{if } i=1 = p_i(\ell) = \gamma_{Z_i}^{p_i}(r\ell) \text{ and } \gamma_Z^p(rx) = \begin{cases} \gamma_Q^p(rx) & \text{if } Z \cap P = \emptyset \\ 1 & \text{if } Z \cap P \neq \emptyset \end{cases} \end{cases} \quad (1) $$

so, under the condition $Z \cap P = \emptyset \iff i=0$, we have $\gamma_{Z_i}^{p_i}(\rho x) = \gamma_Z^p(rx)$, so

$$ \gamma_{Z_i}^{p_i}(\rho x) \cdot \underbrace{\omega_i(\rho x)}_{=\omega(rx)} + \gamma_{Z_i}^{p_i}(r\ell) \cdot \underbrace{\omega_i(r\ell)}_{=0} \stackrel{(1)}{=} \gamma_Z^p(rx) \cdot \omega(rx). \quad (2) $$

*Claim.* Let $Z$ be a leaf-set in $\mathcal{N}$, let $Z' := Z \cup \{\ell\}$, and let $i := \operatorname{sgn}(|Z \cap P|)$. Then, $Z$ is a solution for $\mathcal{I}$ if and only if $Z'$ is a solution for $\mathcal{I}_i$.

*Proof.* Note that $Z \cap P = \emptyset \iff i=0$ is satisfied. In the following, we compare the value of $Z$ in $\mathcal{I}$ and the value of $Z'$ in $\mathcal{I}_i$.

First, consider any arc $e$ in $\mathcal{N}$ that is not below $r$. Since, by (1), we have $\gamma_Z^p(rx) = \gamma_{Z'}^{p_i}(r\ell)$, and since $p(\ell') = p_0(\ell')$ for any leaf $\ell' \neq \ell$, we inductively infer that $\gamma_{Z'}^{p_i}(e) = \gamma_Z^p(e)$ as these values only depend on the edges below $e$.

Second, by (2), the contribution of the arc $rx$ to the value of the solution $Z$ for $\mathcal{I}$ equals the contribution of $\rho x$ and $r\ell$ to the value of the solution $Z'$ for $\mathcal{I}_i$.
It remains to compare the contributions of the arcs $e$ below $x$ in $\mathcal{N}$. In the following, consider such an arc $e$. If $i = 0$, then $Z$ avoids $P$ and so does $Z'$, so $p(\ell') = p_0(\ell')$ for all $\ell' \in \text{off}(e) \cap Z = \text{off}(e) \cap Z'$. If $i = 1$, then $p(\ell') = p_1(\ell')$ for all leaves in $\text{off}(e)$. Thus, by Lemma 1,

$$ \gamma_{Z'}^{p_i}(e) = 1 - \prod_{\ell' \in \text{off}(e) \cap Z'} (1 - p_i(\ell')) = 1 - \prod_{\ell' \in \text{off}(e) \cap Z} (1 - p(\ell')) = \gamma_Z^p(e). $$

Thus, we conclude that $Z$ and $Z'$ score exactly the same in $\mathcal{I}$ and $\mathcal{I}'$, respectively.

Finally, we show that $c(Z) = c_i(Z') - i$. If $i = 0$, then this holds since $c_0(\ell) = 0$. If $i = 1$ then $Z$ intersects $P$ and, by Lemma 2, we can assume that $Z$ contains $a$. Then, since $c(a) = 1$ and $c_1(\ell) = c_1(a) = 0$, we have $c_1(Z') = c(Z) - 1$. $\blacksquare$

Now, we can prove the promised equivalence. First, if $Z$ is a solution for $\mathcal{I}$, then $Z' := Z \cup \{\ell\}$ is a solution for $\mathcal{I}_i$ with $i = \text{sgn}(|Z \cap P|)$. Second, if $Z_0$ is a solution for $\mathcal{I}_0$, then $Z'_0 := Z_0 \setminus P$ is also a solution for $\mathcal{I}_0$ since $p_0(\ell') = 0$ for all $\ell' \in P$ and, by Section 3, $Z := Z'_0 \setminus \{\ell\}$ is a solution for $\mathcal{I}$. Third, if $Z_1$ is a solution for $\mathcal{I}_1$ then we can assume $a \in Z_1$ since $c_1(a) = 0$ so, for $Z := Z_1 \setminus \{\ell\}$, we have $Z \cap P \neq \emptyset$, thereby satisfying the conditions of Section 3. Thus, $Z$ is a solution for $\mathcal{I}$. $\square$

We can now solve 0/1-COST MAX-NETWORK-PD as follows. If $k = 0$, then the monotonicity of Network-PD$^{p}$($Z$) in $Z$ implies that “taking” all cost-0 leaves in $\mathcal{N}$ is optimal. Otherwise, we repeatedly find a lowest reticulation $r$ in $\mathcal{N}$, apply all reduction rules, and if $r$ survives, branch into two instances using Branching Rule 1. Note that, in each new instance, $r$ has a leaf child with cost 0. Thus, Reduction Rule 3 will apply and remove $r$ before another branching occurs. If no branching or reduction rules apply, then $\mathcal{N}$ is a tree. In this tree, a slight variation of Reduction Rule 4 can be used to remove all cost-0 leaves, so all remaining leaves have cost 1 and, therefore (by convention), inheritance probability 1. Such an instance can be solved in $O(n \log k)$ time [12]. Note that the budget $k$ is decreased for one of the two branches and $|R|$ is reduced in each branch, so no more than $\binom{|R|}{k}$ branches need to be explored. Finally, with careful bookkeeping the reduction and branching can be implemented to run in $O(|E|) = O(n+r)$ amortized time in total.

**Theorem 1.** On binary, $n$-leaf networks with $r$ reticulations, 0/1-COST MAX-NETWORK-PD and MAX-NETWORK-PD can be solved in $O(\sum_{i=0}^{\min\{k,r\}} \binom{r}{i} \log k \cdot (n+r)) \subseteq O(2^r \log k \cdot (n+r))$ time, where $k$ is the budget.<fnref n="4" />

Theorem 1 shows that MAX-NETWORK-PD is fixed-parameter tractable with respect to the number of reticulations. In light of this, one might expect that MAX-NETWORK-PD is also fixed-parameter tractable with respect to the “level” (maximum number of reticulations in any biconnected component (“blob”) of the network, since many tractability results for the reticulation number also extend

<footnote n="4">⁴ Note that this running time degenerates to $o(2^r \cdot n)$ if $k \le r/3$</footnote>
to the level by applying the algorithm separately to each blob, with minimal
adjustment, in such a way that the problem parameterized by level reduces to the
problem parameterized by reticulation number. Unfortunately, this approach does
not work for MAX-NETWORK-PD– for a given blob, it may be better to pay some
diversity score within the blob in order to increase $\gamma_Z^p(e)$ for the incoming edge of
that blob. This trade-off means that we need to consider many possible solutions
for each blob. Indeed, we will see in the next section that MAX-NETWORK-PD
is NP-hard even on level-1 networks.

4 NP-hardness Results

Complementing the positive result of the previous section, we now show that
MAX-NETWORK-PD is NP-hard on level-1 networks, answering an open question
in the literature [2, Section 9]. On our way to showing this hardness result, we
also show NP-hardness of the following problem, answering an open question of
Komusiewicz and Schestag [10]:

UNIT-COST-NAP

**Input:** A tree $\mathcal{T} = (V, E)$ with leaves $L$, edge weights $\omega : E \to \mathbb{N}$, success probabilities $p : L \to [0, 1]$, and some $k, D \in \mathbb{N}$.

**Question:** Is there some $Z \subseteq L$ with $|Z| \le k$ and $\sum_{e \in E} \gamma'_Z(e) \cdot \omega(e) \ge D$, where $\gamma'_Z(e) := (1 - \prod_{x \in \text{off}(e) \cap Z} (1 - p(x)))$?

Note that $\gamma'_Z(e)$ corresponds to the probability that at least one taxa in $\text{off}(e)$ survives, under the assumption that every taxon $x \in Z$ survives independently with probability $p(x)$, and every taxon $x \in L \setminus Z$ does not survive. Thus, UNIT-COST-NAP can be viewed as the problem of maximizing the expected phylogenetic diversity on a tree, where each species we choose to save has a certain probability of surviving.

**Subset Product.** First, we show that the following problem is NP-hard.

SUBSET PRODUCT

**Input:** A multiset of positive integers $\{v_1, v_2, \dots, v_m\}$, integers $M, k \in \mathbb{N}$.

**Question:** Is there any $S \subseteq [m]$ with $|S| = k$ such that $\prod_{i \in S} v_i = M$?

We note that the definition of SUBSET PRODUCT is slightly different here from
the formulation of Garey and Johnson [6]. In particular, we assume that the
size $k$ of the set $S$ is given and that all integers are positive. This makes the
subsequent NP-hardness reductions in this paper slightly simpler.

The NP-hardness of SUBSET PRODUCT is not a new result. It was stated
by Garey and Johnson [6] without full proof (the authors indicate that the
problem is NP-hard by reduction from EXACT COVER BY 3-SETS (X3C), citing
“Yao, private communication”) and a full proof appears in [13] and we reproved
it for our slightly adapted variant in the appendix.

**Lemma 3 ([13]).** X3C reduces to SUBSET PRODUCT in polynomial time.
As X3C is NP-hard [6], so is SUBSET PRODUCT.

**Penalty Sum.** Komusiewicz and Schestag [10, Theorems 5.3 & 5.4] showed that, if the following problem is NP-hard, then so is UNIT-COST-NAP:

**PENALTY SUM**

**Input:** A set of tuples {$t_i = (a_i, b_i) \mid i \in [m], a_i \in \mathbb{Q}_+ \cup \{0\}, b_i \in (0, 1)$}, integers $k$, $Q$, and a number $D \in \mathbb{Q}_+$.

**Question:** Is there some $S \subseteq [m]$ with $|S| = k$ such that $\sum_{i \in S} a_i - Q \cdot \prod_{i \in S} b_i \ge D$?

In the following, we reduce SUBSET PRODUCT to PENALTY SUM, to prove the NP-hardness of PENALTY SUM and UNIT-COST-NAP. Afterward, we show that, even on level-1 networks, MAX-NETWORK-PD is NP-hard by a reduction from UNIT-COST-NAP.

**4.1 Hardness of Penalty Sum**

The full proof of the NP-hardness of PENALTY SUM is given in Appendix B; Here, we give a brief overview of the main ideas. For an instance ($\{v_1, \dots, v_m\}, M, k$) of SUBSET PRODUCT, we let $Q := M$ and $D := \ln(1/M) - 1$, and let $t_i := (\ln(1/v_i), 1/v_i)$ for each $i \in [n]$. Then, in the instance ($\{t_i \mid i \in [m]\}, k, Q, D$) of PENALTY SUM, the aim is to find $S \subseteq [m]$ with $|S| = k$ optimizing $\sum_{i \in S} \ln(1/v_i) - M \cdot \prod_{i \in S} (1/v_i) = \ln(\prod_{i \in S} 1/v_i) - M \cdot (\prod_{i \in S} 1/v_i)$. This value maximizes in $\ln(1/M) - 1 = D$, with equality if and only if $\prod_{i \in S} v_i = M$. Thus, ($\{t_i \mid i \in [m]\}, k, Q, D$) is a yes-instance of PENALTY SUM if and only if ($\{v_1, \dots, v_m\}, M, k$) is a yes-instance of SUBSET PRODUCT. The full reduction requires additional work in order to ensure that all numbers involved are non-negative rationals.

**4.2 Hardness of Network-Diversity**

Finally, reducing from UNIT-COST-NAP, we show the following main result.

**Theorem 2.** MAX-NETWORK-PD is NP-hard even if the input network has level 1, all weights are positive, and the distance between the root and each leaf is 4.

*Proof.* Because PENALTY SUM is NP-hard, we know that UNIT-COST-NAP is NP-hard on trees of height 2 [10]. Let $\mathcal{T}$ be an $L$-tree of height 2 for some $L$ and let an instance $\mathcal{I} = (\mathcal{T}, \omega, q, k, D)$ of UNIT-COST-NAP be given.

We define a leaf-gadget which is illustrated in Figure 6. Let $\ell \in L$ be a leaf with success-probability $q(\ell)$. Add four vertices $v_\ell^1, v_\ell^2, \ell^*, \ell^-$ and edges $\ell v_\ell^1, \ell v_\ell^2, v_\ell^1 v_\ell^2, v_\ell^1 \ell^-$, and $v_\ell^2 \ell^*$. The only reticulation in this gadget is $v_\ell^2$ with incoming edges $\ell v_\ell^2$ and $v_\ell^1 v_\ell^2$. We set the inheritance probabilities $p(\ell v_\ell^2) := q(\ell)/(2-q(\ell))$ and $p(v_\ell^1 v_\ell^2) := q(\ell)/2$ which are both in $[0, 1]$ because $q(\ell) \in [0, 1]$.

Let $\mathcal{N}$ be the network that results from replacing each leaf of $\mathcal{T}$ with the corresponding leaf-gadget. The leaves of $\mathcal{N}$ are $L' := \{\ell^*, \ell^- \mid \ell \in L\}$. Let $d$ denote the largest denominator in a success-probability $q(\ell)$ of a leaf $\ell$ of $\mathcal{T}$, so
<figure><img src="image_7.png" /><figcaption>Fig. 6: Illustration of the leaf-gadget. Omitted edge-weights are 1 and $q(\ell)$ is abbreviated to $q$.</figcaption></figure>

that every $q(\ell)$ is expressible as $c'/d'$ for some pair of integers $c, d$ such that $d' \le d$. Let $M$ and $Q$ be large integers, such that $M$ is bigger than $\mathrm{PD}_{\mathcal{T}}(L) \ge |L| \ge k$, and $Q \cdot D$ and $Q \cdot d^{-k}$ are both bigger than 3.

Observe that the number of bits necessary to write $M$ and $Q$ is polynomial in the size of $\mathcal{I}$. We set the weight of edges $e \in E(\mathcal{T})$ in $\mathcal{N}$ to $\omega'(e) = kQ \cdot \omega(e)$. For each $\ell \in L$ we set $\omega'(v_{\ell}^2 \ell^*) := Q \cdot M^2$ and $\omega'(e) := 1$ for $e \in \{\ell v_{\ell}^1, \ell v_{\ell}^2, v_{\ell}^1 v_{\ell}^2, v_{\ell}^1 \ell^-\}$.

Finally let $\mathcal{I}' := (\mathcal{N}, \omega', p, k, D' := kQ(M^2 + D))$ be an instance of MAX-NETWORK-PD. Each leaf-gadget is a level-1 network. As the leaf-gadgets are connected by a tree, $\mathcal{N}$ is a level-1 network. Recall that the height of the tree $\mathcal{T}$ is 2, and as such the distance between the root and each leaf in $\mathcal{N}$ is 4.

Before showing that $\mathcal{I}$ and $\mathcal{I}'$ are equivalent, we show that $\gamma_Z^p(e) = q(\ell)$ in the case that $\ell^* \in Z$ but $\ell^- \notin Z$. Indeed because $\ell^- \notin Z$, we conclude that $\gamma_Z^p(\ell v_{\ell}^2) = p(\ell v_{\ell}^2) = q(\ell)/(2-q(\ell))$ and $\gamma_Z^p(\ell v_{\ell}^1) = \gamma_Z^p(v_{\ell}^1 v_{\ell}^2) = p(v_{\ell}^1 v_{\ell}^2) = q(\ell)/2$. Subsequently,

$$ \gamma_Z^p(e) = 1 - (1 - \gamma_Z^p(\ell v_{\ell}^1))(1 - \gamma_Z^p(\ell v_{\ell}^2)) = 1 - \frac{2 - q(\ell)}{2} \cdot \frac{2 - 2q(\ell)}{2 - q(\ell)} = 1 - \frac{2 - 2q(\ell)}{2} = q(\ell). \quad (3) $$

“⇒”: Suppose that $\mathcal{I}$ is a yes-instance of UNIT-COST-NAP and that $S \subseteq L$ is a solution of $\mathcal{I}$, that is $|S| \le k$ and $\mathrm{PD}_{\mathcal{T}}(S) \ge D$. Let $S' := \{\ell^* | \ell \in S\}$ be a subset of $L'$. Clearly $|S'| = |S| \le k$. Because $\mathcal{T}$ does not contain reticulation edges and $\gamma_Z^p(e) = q(\ell)$ with $e$ being the edge incoming at $\ell$, we conclude that

$$ \mathrm{Network-PD}_{\mathcal{N}}(S') \ge kQ \cdot \mathrm{PD}_{\mathcal{T}}(S) + k \cdot \omega'(v_{\ell}^2 \ell^*) \ge kQ \cdot (D + M^2) = D' $$

hence, $S'$ is a solution of $\mathcal{I}'$.

“⇔”: Let $S'$ be a solution of $\mathcal{I}'$. Let $S^- = S \cap \{\ell^- | \ell \in L\}$ and $S^* = S \cap \{\ell^* | \ell \in L\}$. Towards a contradiction, assume $S^- \ne \emptyset$. Then, however, using $3 < Q \cdot D$,

$$ \begin{align*} \mathrm{Network-PD}_{\mathcal{N}}(S') &\le \sum_{\ell^- \in S^-} (\omega'(v_{\ell}^1 \ell^-) + \omega'(\ell v_{\ell}^1)) + |S^*|(QM^2 + 3) + \sum_{e \in E(\mathcal{T})} \omega'(e) \\ &\le 2|S^-| + |S^*|(QM^2 + 3) + kQM \\ &\le 2 + (k-1)(QM^2 + 3) + kQM \\ &< kQM^2 - QM^2 + kQM + 3k \\ &< k(QM^2 + 3) < k(QM^2 + QD) = D' \end{align*} $$
contradicts that $S'$ is a solution. Therefore, we conclude that $S' \subseteq \{\ell^* | \ell \in L\}$ and $|S'| = k$. Define $S := \{\ell | \ell^* \in S'\}$. Subsequently, with (3) we conclude

$$kQ(M^2 + D) = D' \leq \text{Network-PD}_{\mathcal{N}}(S') = k \cdot QM^2 + \sum_{\ell \in S} \left( \underbrace{\frac{q(\ell)}{2} + \frac{q(\ell)}{2} + \frac{q(\ell)}{2 - q(\ell)}}_{\leq 3} \right) + kQ \cdot \text{PD}_{\mathcal{T}}(S).$$

It follows that $\text{PD}_{\mathcal{T}}(S) \geq 1/kQ \cdot (kQ(M + D) - kQM - 3k) = D - 3/Q$.

It remains to show that $\text{PD}_{\mathcal{T}}(S)$ cannot take any values in the range $[D - 3/Q, D)$, i.e. that $\text{PD}_{\mathcal{T}}(S) \geq D - 3/Q$ implies that $\text{PD}_{\mathcal{T}}(S) \geq D$. To this end, let $c_\ell, d_\ell$ be the unique positive integers such that $q(\ell) = c_\ell/d_\ell$ for each leaf $\ell$ in $\mathcal{T}$. Then $q(\ell)$ is a multiple of $1/d_\ell$ by construction, as is $(1 - q(\ell))$. It follows that for any edge $e$ in $\mathcal{T}$, $\gamma'_S(e) = (1 - \prod_{\ell \in \text{off}(e) \cap S} (1 - q(\ell)))$ is a multiple of $1/(\prod_{\ell \in S} d_\ell)$. As all edge weights are integers, we also have that $\text{PD}_{\mathcal{T}}(S)$ is a multiple of $1/(\prod_{\ell \in S} d_\ell)$. It follows that either $\text{PD}_{\mathcal{T}}(S) \geq D$ or $D - \text{PD}_{\mathcal{T}}(S) \geq 1/(\prod_{\ell \in S} d_\ell)$. As $d_\ell \leq d$ for any $\ell$, this difference is at least $d^{-k} > 3/Q$. It follows that if $\text{PD}_{\mathcal{T}}(S) \geq D - 3/Q$ then in fact $\text{PD}_{\mathcal{T}}(S) \geq D$.

We conclude $\text{PD}_{\mathcal{T}}(S) \geq D$. Hence with $|S| = |S'| \leq k$ we conclude that $S$ is a solution of $\mathcal{I}$. Thus, $\mathcal{I}$ is a yes-instance of UNIT-COST-NAP. $\square$

# 5 Discussion

In this paper, we have studied MAX-NETWORK-PD from a theoretical point of view. These results do have some practical implications. In particular, they show that we can only hope to solve MAX-NETWORK-PD efficiently for evolutionary histories that are reasonably tree-like in the sense that the number of reticulate events is small. For this case, we present an algorithm that is theoretically efficient. How well it works in practice is still to be evaluated.

Some open questions on the theoretical front remain. Can MAX-NETWORK-PD be solved in pseudo-polynomial time on level-1 networks? Is MAX-NETWORK-PD polynomial time solvable on level-1 networks if we require the network to be ultrametric, i.e. when all root-leaf paths have the same length? Is MAX-NETWORK-PD FPT when parameterized with the number of selected species $k$ to save plus the level of the network? Is MAX-NETWORK-PD FPT when parameterized with the number of different weights and probabilities? If this is the case, then rounding the weights or probabilities to magnitudes could significantly speed up the running time [5].

From a practical point-of-view however, the most important task is to assess which variants of phylogenetic diversity on networks (see [19]) are biologically most relevant. This could of course depend on the type of species considered and in particular on the type of reticulate evolutionary events. Even if the maximization problem cannot be solved efficiently, having a good measure of phylogenetic diversity can still have great practical use by measuring how diverse a given set of species is.
Bibliography

[1] Atkin, A.O.L., Bernstein, D.J.: Prime sieves using binary quadratic forms. Mathematics of Computation **73**, 1023–1030 (Jan 2004)

[2] Bordewich, M., Semple, C., Wicke, K.: On the Complexity of optimising variants of Phylogenetic Diversity on Phylogenetic Networks. Theoretical Computer Science **917**, 66–80 (2022)

[3] Dusart, P.: The $k$th prime is greater than $k(\ln k + \ln \ln k - 1)$ for $k \ge 2$. Mathematics of Computation **68**(225), 411–415 (1999), URL http://www.jstor.org/stable/2585122

[4] Faith, D.P.: Conservation evaluation and phylogenetic diversity. Biological conservation **61**(1), 1–10 (1992)

[5] Fellows, M.R., Gaspers, S., Rosamond, F.A.: Parameterizing by the number of numbers. Theory of Computing Systems **50**, 675–693 (2012)

[6] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979), ISBN 0-7167-1044-7

[7] Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press (2010)

[8] Jones, M., Schestag, J.: How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks. In: Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), Schloss-Dagstuhl-Leibniz Zentrum für Informatik (2023)

[9] Koblmüller, S., Duftner, N., Sefc, K.M., Aibara, M., Stipacek, M., Blanc, M., Egger, B., Sturmbauer, C.: Reticulate phylogeny of gastropod-shell-breeding cichlids from Lake Tanganyika—the result of repeated introgressive hybridization. BMC Evolutionary Biology **7**, 1–13 (2007)

[10] Komusiewicz, C., Schestag, J.: A Multivariate Complexity Analysis of the Generalized Noah’s Ark Problem. In: Proceedings of the 19th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pp. 109–121, Springer (2023)

[11] Merz, J.J., Barnard, P., Rees, W.E., Smith, D., Maroni, M., Rhodes, C.J., Dederer, J.H., Bajaj, N., Joy, M.K., Wiedmann, T., Sutherland, R.: World scientists’ warning: The behavioural crisis driving ecological overshoot. Science Progress **106**(3) (2023), URL https://doi.org/10.1177/00368504231201372

[12] Minh, B.Q., Klaere, S., von Haeseler, A.: Phylogenetic Diversity within Seconds. Systematic Biology **55**(5), 769–773 (10 2006), ISSN 1063-5157, https://doi.org/10.1080/10635150600981604

[13] Moret, B.M.: The theory of computation. Addison-Wesley (1997)

[14] Pardi, F., Goldman, N.: Species choice for comparative genomics: being greedy works. PLoS Genetics **1**(6), e71 (2005), URL https://doi.org/10.1371/journal.pgen.0010071

[15] Ripple, W.J., Wolf, C., Newsome, T.M., Galetti, M., Alamgir, M., Crist, E., Mahmoud, M.I., Laurance, W.F., 15, s.s.f.c.: World Scientists’ Warning to
Humanity: A Second Notice. BioScience **67**(12), 1026–1028 (11 2017), ISSN 0006-3568, URL https://doi.org/10.1093/biosci/bix125

[16] Rosser, B.: Explicit bounds for some functions of prime numbers. American Journal of Mathematics **63**(1), 211–232 (1941), URL http://www.jstor.org/stable/2371291

[17] Steel, M.: Phylogenetic diversity and the greedy algorithm. Systematic Biology **54**(4), 527–529 (2005)

[18] Weitzman, M.L.: The Noah’s ark problem. Econometrica pp. 1279–1298 (1998)

[19] Wicke, K., Fischer, M.: Phylogenetic diversity and biodiversity indices on phylogenetic networks. Mathematical Biosciences **298**, 80–90 (2018)

[20] Wicke, K., Mooers, A., Steel, M.: Formal links between feature diversity and phylogenetic diversity. Systematic Biology **70**(3), 480–490 (2021)

A A note about binary representation of rational numbers

As most of the problems here involve rational numbers as part of the input, it
is worth drawing attention to how those numbers are represented, in particular
how they affect the input size of an instance. As is standard, we assume that
positive integers are represented in binary (so that, for instance, the numbers 3,
4 and 5 are written as 11, 100 and 101 respectively). Thus the number of bits
required to represent the integer *n* is O(log₂(*n*)). In the case of rational numbers,
we assume throughout that a rational *p/q* (with *p* and *q* coprime integers) can be
represented by binary representations of *p* and *q*. Thus for example, the number
3/5 may be written as 11/101. It follows that *p/q* can be represented using
O(log₂(*p*) + log₂(*q*)) bits.

For rational numbers which are a multiple of a power of 2, (such as 1/8 = 2⁻³,
or 5/8 = 5·2⁻³), we can write the number by extending the binary representation
'past the decimal point', so that e.g. 1/8 would be written as 0.001 and 5/8
as 0.101. There is also the 'floating point' representation, where the number is
expressed as an integer *t* times 2 to some integer *c*, and the numbers *t* and *c* are
expressed in binary. Thus for example 5/8 would be written as 101 × 2⁻¹¹. Both
of these methods of representing rationals have the drawback that they cannot
represent rationals that are not a multiple of a power of 2. The number 1/3, for
instance, cannot be expressed exactly under either method.

This distinction becomes important in Section 4.1, where our reduction from SUBSET PRODUCT to PENALTY SUM produces rational numbers that are not multiples of a power of 2. Do our hardness results for PENALTY SUM, UNIT-COST-NAP and MAX-NETWORK-PD still hold when one insists on a different method of representing rationals? This is an interesting question, and we make no attempt to answer it.
## B Hardness of Penalty Sum

The reduction from SUBSET PRODUCT to PENALTY SUM can be informally described as follows: For an instance ({v₁, ..., vₘ}, M, k') of SUBSET PRODUCT and a big integer A, we let aᵢ be (a rational close to) A - ln vᵢ and let bᵢ := 1/vᵢ, for each i ∈ [m]. Let Q := M, let k := k', and let D be (a rational close to) kA - ln Q - 1.

Note that we cannot set aᵢ := A - ln vᵢ or D := kA - ln Q - 1 exactly, because in general these numbers are irrational and cannot be calculated exactly in finite time (nor stored in finite space). Towards showing the correctness of the reduction, we temporarily forget about the need for rational numbers, and consider how the function Σ_{i∈S} aᵢ - Q ⋅ Π_{i∈S} bᵢ behaves when we drop the ‘(a rational close to)’ qualifiers from the descriptions above. In particular we will show that the function reaches its theoretical maximum exactly when S is a solution to the SUBSET PRODUCT instance.

### Reduction with irrational numbers

**Construction 1.** Let ({v₁, ..., vₘ}, M, k) be an instance of SUBSET PRODUCT. Let us define the following (not necessarily rational) numbers.

- Let A := [maxᵢ∈[m] (ln vᵢ)] + 1;

- Let aᵢ* := A - ln vᵢ for each i ∈ [m];

- Let bᵢ := 1/vᵢ for each i ∈ [m];

- Let Q := M;

- Let D* := kA - ln Q - 1.

Finally, output the instance ({(aᵢ*, bᵢ) : i ∈ [m]}, k, Q, D*) of PENALTY SUM.

We note that the purpose of A in Construction 1 is simply to ensure that aᵢ* > 0 for each i ∈ [m], as required by the formulation of PENALTY SUM. Now, let f* : ([m]k) → ℝ be defined by

$$f^*(S) := \sum_{i \in S} a_i^* - Q \cdot \prod_{i \in S} b_i.$$

**Lemma 4.** For any S ∈ ([m]k):

1. $f^*(S) \le D^*$, and

2. $f^*(S) = D^*$ if and only if $\prod_{i \in S} v_i = Q$.

*Proof.* First, observe that given $|S| = k$, the function $f^*$ can be written as

$$f^*(S) = kA - \sum_{i \in S} \ln v_i - Q/\prod_{i \in S} v_i = kA - \ln \left( \prod_{i \in S} v_i \right) - Q/\prod_{i \in S} v_i$$
Letting $x_S := \prod_{i \in S} v_i$, we therefore have $f^*(S) = kA - \ln x_S - Qx_S^{-1}$. Let $g^*$: $\mathbb{R}_{>0} \to \mathbb{R}$ be defined by $g^*(x) := kA - \ln x - Qx^{-1}$ and note that $f^*(S) = g^*(x_S)$ for any $S \in \binom{[m]}{k}$. Recall that $g^*(x)$ has a critical point at $x'$ when $\frac{dg^*}{dx}(x') = 0$. Since $\frac{dg^*}{dx} = -x^{-1} + Qx^{-2}$, this occurs exactly when $x'^{-1} = Qx'^{-2}$, i.e. when $x' = Q$. Moreover, for $Q > x > 0$, we have $Qx^{-1} > 1$, implying

$$ \frac{dg^*}{dx} = -x^{-1} + Qx^{-2} > -x^{-1} + x^{-1} = 0. $$

On the other hand, for $x > Q > 0$, we have $Qx^{-1} < 1$, implying

$$ \frac{dg^*}{dx} = -x^{-1} + Qx^{-2} < -x^{-1} + x^{-1} = 0. $$

It follows that $g^*(x)$ is strictly increasing on the range $0 < x < Q$ and strictly decreasing on the range $x > Q$. Thus, $g^*(x)$ has a unique maximum on the range $x > 0$, and this maximum is achieved at $x = Q$. In particular, for all $S \in \binom{[m]}{k}$, we have

$$ f^*(S) = g^*(x_S) \le g^*(Q) = kA - \ln Q - 1 = D^*. \quad (4) $$

With equality if and only if $x_S = \prod_{i \in S} v_i = Q$. $\square$

The above result implies that, abusing terminology slightly, $(\{(a_i^*, b_i) \mid i \in [m]\}, k, Q, D^*)$ is a yes-instance of 'PENALTY SUM' if and only if $(\{v_1, \dots, v_m\}, M, k')$ is a yes-instance of SUBSET PRODUCT.

We are now ready to fully describe the polynomial-time reduction from SUBSET PRODUCT to PENALTY SUM, showing how we can adapt the ideas above to work for rational $a_i$ and $D$.

**Reduction with rational numbers** Let $(\{v_1, \dots, v_m\}, M, k')$ be an instance of SUBSET PRODUCT, and let $a_i^*, b_i, Q, k, D^*$ be defined as previously. Then by Lemma 4, $f^*(S) = \sum_{i \in S} a_i^* - Q \cdot \prod_{i \in S} b_i \ge D^*$ if and only if $\prod_{i \in S} v_i = Q = M$ for any $S \in \binom{[m]}{k}$.

Our task now is to show how to replace $a_i^*$ and $D^*$ with rationals $a_i$ and $D$, in such a way that the same property holds (i.e. that $\sum_{i \in S} a_i - Q \cdot \prod_{i \in S} b_i \ge D$ if and only if $\prod_{i \in S} v_i = M$), and such that the instance $(\{(a_i, b_i) \mid i \in [m]\}, k, Q, D)$ can be constructed in polynomial time. The key idea is to find rational numbers that can be encoded in polynomially many bits but that are close enough to their respective irrationals that the difference between $f^*(S)$ and $f(S)$ (and between $D^*$ and $D$) is guaranteed to be small. To this end, let us fix a positive integer $H$ to be defined later, and we will require all $a_i, b_i, D$ to be a multiple of $2^{-H}$. This ensures that the denominator part of any of these rationals can be encoded using $O(H)$ bits.

Given any $x \in \mathbb{R}$ and a positive integer $H$, let $\lfloor x \rfloor_H := r_x/2^H$, where $r_x$ is the largest integer such that $r_x/2^H \le x$. For example $\lfloor \pi \rfloor_3 = 3.125 = 25/2^3$, because $25/2^3 < \pi < 26/2^3$ (one may think of $\lfloor x \rfloor_H$ as the number derived from the binary representation of $x$ by deleting all digits more than $H$ positions after
the binary point. Thus, as the binary expression of $\pi$ begins 11.00100 10000 11111..., the binary expression of $\lfloor \pi \rfloor_3$ is 11.001). Similarly, let $\lfloor x \rfloor_H := s_x/2^H$, where $s_x$ is the smallest integer such that $x \le s_x/2^H$. Finally, let $\delta := 1/2^H$.

**Observation 1.** Let $x \in \mathbb{R}$. Then, $x - \delta < \lfloor x \rfloor_H \le x \le \lfloor x \rfloor_H < x + \delta$.

We can now describe the reduction from SUBSET PRODUCT to PENALTY SUM.

**Construction 2.** Let $(\{v_1, \dots, v_m\}, M, k)$ be an instance of SUBSET PRODUCT.

- Let $A := \max_{i \in [m]}(\ln v_i) + 1$;

- Let $a_i := [a_i^*]_H = [A - \ln v_i]_H$ for each $i \in [m]$;

- Let $b_i := 1/v_i$ for each $i \in [m]$;

- Let $Q := M$;

- Let $D := \lfloor D^* \rfloor_H = \lfloor kA - \ln Q - 1 \rfloor_H$.

Finally, output the instance $\mathcal{I} := (\{(a_i, b_i) \mid i \in [m]\}, k, Q, D)$ of PENALTY SUM.

In the following, we show that the two instances are equivalent. To this end, let $f: (\begin{bmatrix} m \\ k \end{bmatrix}) \to \mathbb{R}$ be defined by

$$f(S) := \sum_{i \in S} a_i - Q \cdot \prod_{i \in S} b_i.$$

Note that $f$ is the same as the function $f^*$ defined previously, but with each $a_i^*$ replaced by $a_i$. Then, $\mathcal{I}$ is a yes-instance of PENALTY SUM if and only if there is some $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$ such that $f(S) \ge D$. The next lemma shows the close relation between $f^*$ and $f$ (and between $D^*$ and $D$), which will be used in both directions to show the equivalence between yes-instances of SUBSET PRODUCT and PENALTY SUM.

**Lemma 5.** Let $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$. Then, $f^*(S) \le f(S) < f^*(S) + k\delta$ and $D^* - \delta < D \le D^*$.

*Proof.* Observe that $f(S) - f^*(S) = \sum_{i \in S} (a_i - a_i^*)$ and $|S| = k$. Then, by Observation 1, we have $0 \le a_i - a_i^* < \delta$ for all $i \in [m]$. Thus, $0 \le f(S) - f^*(S) < k\delta$, from which the first claim follows. The second claim follows immediately from Observation 1 and the fact that $D = \lfloor D^* \rfloor_H$. $\square$

**Corollary 1.** Let $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$ such that $\prod_{i \in S} v_i = Q$. Then, $f(S) \ge D$.

$$\textit{Proof.} \ D \stackrel{\text{Lem. 5}}{\le} D^* \stackrel{\text{Lem. 4 (2)}}{=} f^*(S) \stackrel{\text{Lem. 5}}{\le} f(S). \quad \square$$

We now have that $(\{v_1, \dots, v_m\}, M, k')$ being a yes-instance of SUBSET PRODUCT implies $\mathcal{I}$ being a yes-instance of PENALTY SUM. To show the converse, we show for all $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$ that $\prod_{i \in S} v_i = Q' \ne Q$ implies $f(S) < D$. Since $f(S) < f^*(S) + k\delta$ and $D^* - \delta < D$, it is sufficient to show that $f^*(S) + k\delta \le D^* - \delta$, that is $(k+1)\delta \le D^* - f^*(S)$. To do this, we first establish a lower bound on $D^* - f^*(S')$ in terms of $Q$, using the following technical lemma, whose proof is deferred to the appendix.
**Lemma 6.** Let $Q, Q' \in \mathbb{N}_+$ with $Q \ge 2$ and $Q \ne Q'$. Then, $\ln Q' - \ln Q + Q/Q' - 1 > Q^{-4}$.

We explicitly note that we use the natural logarithm. For other logarithms, say $\log_2 Q$, this lemma is not true. For example for $Q = 2$ and $Q' = 1$ we have $\log_2(1) - \log_2(2) + 2/1 - 1 = 0 - 1 + 2 - 1 = 0 < 2^{-4}$.

**Corollary 2.** Suppose $\prod_{i \in S} v_i = Q' \ne Q$ for some $Q \ge 2$ and $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$. Then $D^* - f^*(S) > Q^{-4}$.

*Proof.* Recall that $D^* = kA - \ln Q - 1$ and that $f^*(S) = kA - \ln(\prod_{i \in S} v_i) - Q/(\prod_{i \in S} v_i) = kA - \ln Q' - Q/Q'$. Then $D^* - f^*(S) = \ln Q' - \ln Q + Q/Q' - 1$. It follows from Lemma 6 that $D^* - f^*(S) > Q^{-4}$. $\square$

Given the above we can now fix a suitable value for $H$. Given that we wanted $D^* - f^*(S) \ge (k+1)\delta = (k+1)/2^H$ when $\prod_{i \in S} v_i \ne Q$, and assuming without loss of generality that $k < Q$, it is sufficient to set $H = 5[\log_2 Q]$.

**Corollary 3.** Let $H = 5[\log_2 Q]$ and $\delta = (1/2^H)$. Then for $\{(a_i, b_i) \mid i \in [m]\}, k, Q, D$ constructed as above, it holds that $Q^{-4} \ge (k+1)\delta$.

*Proof.* W.l.o.g. we may assume $k < Q$. Then, $(k+1)\delta \le Q/2^H \le Q/Q^5 = Q^{-4}$. $\square$

We now have all necessary pieces to reduce SUBSET PRODUCT to PENALTY SUM.

**Theorem 3.** PENALTY SUM is NP-hard.

*Proof.* Given an instance $\{(v_1, \dots, v_m\}, M, k')$ of SUBSET PRODUCT, let $Q := M$, $H := 5[\log_2 Q]$, and $\delta := (1/2^H)$. Construct $A, a_i, b_i, k, D$ as described above, that is: $A := \lceil \max_{i \in [m]} (\ln v_i) \rceil + 1$; $a_i := \lceil a_i^* \rceil_H = \lceil A - \ln v_i \rceil_H$ for each $i \in [m]$; $b_i := 1/v_i$ for each $i \in [m]$; $k := k'$; $D := \lfloor D^* \rfloor_H = \lfloor kA - \ln Q - 1 \rfloor_H$. Let $\{(a_i, b_i) \mid i \in [m]\}, k, Q, D$ be the resulting instance of PENALTY SUM.

We first show that $\{(a_i, b_i) \mid i \in [m]\}, k, Q, D$ is a yes-instance of PENALTY SUM if and only if $\{v_1, \dots, v_m\}, M, k'$ is a yes-instance of SUBSET PRODUCT. Suppose first that $\{v_1, \dots, v_m\}, M, k'\}$ is a yes-instance of SUBSET PRODUCT. Then there is some $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$ such that $\prod_{i \in S} v_i = M = Q$. Then by Corollary 1, $f(S) \ge D$ and so $\{(a_i, b_i) \mid i \in [m]\}, k, Q, D$ is a yes-instance of PENALTY SUM.

Conversely, suppose that $\{(a_i, b_i) \mid i \in [m]\}, k, Q, D$ is a yes-instance of PENALTY SUM. Then there is some $S \in (\begin{bmatrix} m \\ k \end{bmatrix})$ such that $f(S) \ge D$. By Lemma 5 and Corollary 3, we have that $f^*(S) > f(S) - k\delta \ge D - k\delta > D^* - (k+1)\delta \ge D^* - Q^{-4}$. Thus $D^* - f^*(S) \le Q^{-4}$, which by Corollary 2 implies that $\prod_{i \in S} v_i = Q$, and so $\{v_1, \dots, v_m\}, M, k'\}$ is a yes-instance of SUBSET PRODUCT.

It remains to show that the reduction takes polynomial time. For this, it is sufficient to show that the rationals $A, k, D$ and $a_i, b_i$ for $i \in [m]$ can all
be calculated in polynomial time. Observe that $A = [\max_{i \in [m]}(\ln v_i)]$ is the unique integer such that $e^A > \max_{i \in [m]} v_i > e^{A-1}$. Since $\ln v_i < \log_2 v_i$, we have $1 \le A \le [\max_{i \in [m]} \log_2 v_i]$ and so we can find $A$ in polynomial time by checking all integers in this range.

For each $i \in [m]$, $a_i = [A - \ln v_i]_H = r_i/2^H$, where $r_i$ is the minimum integer such that $A - \ln v_i \le r_i/2^H$. Thus, we can compute $r_i$ by checking $e^{A-r_i/2^H} \le v_i$ with $r_i = 2^H \cdot (A - [\ln v_i]_H)$, setting $r_i$ to its successor if the inequality is not satisfied. Thus we can construct $a_i$ in polynomial time, and $a_i$ can be represented in $O(\log_2 r + H)$ bits. The construction of $D$ can be handled in a similar way.

For each $i \in [m]$, rational $b_i = 1/v_i$ can be represented in $O(\log_2 v_i)$ bits (recall that we represent $1/v_i$ with binary representations of the integers 1 and $v_i$) and takes $O(\log_2 v_i)$ time to construct. $Q$ and $k$ are taken directly from the instance $(\{v_1, \dots, v_m\}, M, k')$. $\square$

## C Omitted Proofs

To prove Lemma 3, we reduce the following problem to SUBSET PRODUCT.

**EXACT COVER BY 3-SETS (X3C)**

**Input:** A set $X$ with $|X| = 3n$, a collection $\mathcal{C}$ of subsets of $X$ with $|\mathcal{C}| = 3$ for every $C \in \mathcal{C}$.

**Question:** Is there a collection $\mathcal{C}' \subseteq \mathcal{C}$ such that each element of $x$ appears in exactly one set of $\mathcal{C}'$?

*Proof of Lemma 3.* Let $(X := \{x_1, \dots, x_{3n}\}, \mathcal{C} := \{C_1, \dots, C_m\})$ be an instance of X3C. Let $p_1, \dots, p_{3n}$ be the first $3n$ prime numbers, so that we may associate each $x_j \in X$ with a unique prime number $p_j$. For each set $C_i = \{x_a, x_b, x_c\}$, let $v_i := p_a \cdot p_b \cdot p_c$, that is, $v_i$ is the product of the three primes associated with the elements of $C_i$. Now let $M := \prod_{j=1}^{3n} p_j$, i.e. $M$ is the product of the prime numbers $p_1, \dots, p_{3n}$. Finally let $k = n$. This completes the construction of an instance $(\{v_1, \dots, v_m\}, M, k)$ of SUBSET PRODUCT.

Now observe that if $\prod_{i \in S} v_i = M$ for some $S \subseteq [m]$, then by uniqueness of prime factorization, every prime number $p_1, \dots, p_m$ must appear exactly once across the prime factorizations of all numbers in $\{v_i : i \in S\}$. It follows by construction that the collection of subsets $\mathcal{C}' := \{C_i : i \in S\}$ contains each element of $X$ exactly once. Thus, if $(\{v_1, \dots, v_m\}, M, k)$ is a yes-instance of SUBSET PRODUCT then $(X, \mathcal{C})$ is a yes-instance of X3C. Conversely, if $(X, \mathcal{C})$ is a yes-instance of X3C with solution $\mathcal{C}'$, then we can define $S := \{i \in [m] : C_i \in \mathcal{C}'\}$. Since every element of $X$ appears in exactly one $C_i \in \mathcal{C}'$ and $|C_i| = 3$ for all $i \in [m]$, we have that $|\mathcal{C}'| = |X|/3 = n = k$, and $\prod_{i \in S} v_i = p_1 \cdots p_{3n} = M$. Thus $(\{v_1, \dots, v_m\}, M, k)$ is a yes-instance of SUBSET PRODUCT.

It remains to show that the construction of $(\{v_1, \dots, v_m\}, M, k)$ from $(X, \mathcal{C})$ takes polynomial time. In particular, we need to show that each of the primes $p_1, \dots, p_{3n}$ (and thus the product $M$) can be constructed in polynomial time. This can be shown using two results from number theory: $p_j < j(\ln j + \ln \ln j)$ for $j \ge 6$, [3, 16] and the set of all prime numbers in $[Z]$ can be computed in time
$\mathcal{O}(Z/\ln \ln Z)$ [1]. Combining these, we have that the first $3n$ prime numbers can be generated in time $\mathcal{O}(n \ln n/\ln \ln n)$.

Given the prime numbers $p_1, \dots, p_{3n}$, it is clear that the numbers $\{v_i : i \in [m]\}$ can also be computed in polynomial time. The number $M$, being the product of $3n$ numbers each less than $3n(\ln 3n + \ln \ln 3n)$, can also be computed in time polynomial in $n$ (though $M$ itself is not polynomial in $n$). It follows that $(\{v_1, \dots, v_m\}, M, k)$ can be constructed in polynomial time. $\square$

*Proof of Lemma 6.* We first show that it is enough to consider the cases $Q' = Q+1$ and $Q' = Q-1$. Fix an integer $Q \in \mathbb{N}_+$ with $Q \ge 2$. Consider the function $h_Q : \mathbb{R}_{>0} \to \mathbb{R}$ given by

$$h_Q(x) = \ln x - \ln Q + Q/x - 1.$$

So our aim is to show that $h_Q(Q') \ge Q^{-4}$. Similar to the proof of Lemma 4, we can observe that

$$\frac{dh_Q}{dx} = x^{-1} - Qx^{-2} = \frac{1}{x}\left(1 - \frac{Q}{x}\right)$$

is less than 0 when $x < Q$, exactly 0 when $x = Q$, and greater than 0 when $x > Q$. It follows that on the range $x > 0$, the function $h_Q$ has a unique minimum at $x = Q$, and is decreasing on the range $x < Q$ and increasing on the range $x > Q$. Thus in particular $h_Q(Q') \ge h_Q(Q-1)$ if $Q' \le Q-1$ and $h_Q(Q') \ge h_Q(Q+1)$ if $Q' \ge Q+1$. Since either $Q' \le Q-1$ or $Q' \ge Q+1$ for any integer $Q' \ne Q$, it remains to show that $h_Q(Q-1) > Q^{-4}$ and $h_Q(Q+1) > Q^{-4}$.

To show $h_Q(Q-1) > Q^{-4}$ for any $Q \in \mathbb{N}_{\ge 2}$: Let $\lambda : \mathbb{R}_{>0} \to \mathbb{R}$ be the function given by

$$\begin{aligned} \lambda(Q) &= h_Q(Q-1) - Q^{-4} \\ &= \ln(Q-1) - \ln Q + Q/(Q-1) - 1 - Q^{-4} \\ &= \ln(Q-1) - \ln Q + 1/(Q-1) - Q^{-4}. \end{aligned}$$

Then

$$\begin{aligned} \frac{d\lambda}{dQ} &= (Q-1)^{-1} - Q^{-1} + (Q-1)^{-2} + 4Q^{-5} \\ &> (Q-1)^{-2} + 4Q^{-5} \\ &> 0. \end{aligned}$$

It follows that $\lambda$ is a (strictly) increasing function. Since $\lambda(2) = 0 - \ln 2 + 1 - 1/16 \approx 0.244 > 0$, it follows that $\lambda(Q) > 0$ for all $Q \ge 2$, and thus $h_Q(Q-1) > Q^{-4}$.

To show that $h_Q(Q+1) > Q^{-4}$ for all $Q \in \mathbb{N}_{\ge 2}$: First observe that if $Q = 2$, then $h_Q(Q+1) = \ln(3) - \ln(2) + 2/3 - 1 \approx 0.0721 > 0.0625 = 2^{-4}$ and so the claim is true. For $Q \ge 3$, observe that $h_Q(Q+1) = \ln(Q+1) - \ln Q + \frac{Q}{Q+1} - 1 =$
$\ln(\frac{Q+1}{Q}) - \frac{1}{Q+1}$. We use the Mercator series for the natural logarithm:

$$ \ln\left(\frac{Q+1}{Q}\right) = \ln\left(1+\frac{1}{Q}\right) = \sum_{k=1}^{\infty} \frac{(-1)^{k+1}}{kQ^k} = \frac{1}{Q} - \frac{1}{2Q^2} + \frac{1}{3Q^3} - \frac{1}{4Q^4} + \dots $$

Since $\frac{1}{kQ^k} - \frac{1}{(k+1)Q^{k+1}} > 0$ for all $k > 0$, we can omit all but the first two terms to get

$$ \ln\left(\frac{Q+1}{Q}\right) > \frac{1}{Q} - \frac{1}{2Q^2} \\ = \frac{2Q-1}{2Q^2}. $$

Then

$$ \ln\left(\frac{Q+1}{Q}\right) - \frac{1}{Q+1} > \frac{2Q-1}{2Q^2} - \frac{1}{Q+1} \\ = \frac{(2Q-1)(Q+1) - 2Q^2}{2Q^2(Q+1)} \\ = \frac{2Q^2 + Q - 1 - 2Q^2}{2Q^2(Q+1)} \\ = \frac{Q-1}{2Q^2(Q+1)} \\ \ge \frac{1}{Q^2(Q+1)} \\ > \frac{1}{Q^4} $$

where the last two inequalities use $Q \ge 3$. $\square$