# HIKE: High Intensity Kaon Experiments at the CERN SPS

Matthew Moulson  for the HIKE Collaboration  INFN Laboratori Nazionali di
Frascati, 00044 Frascati RM, Italy<EMAIL_ADDRESS>
###### Abstract

The availability of high intensity kaon beams at the CERN SPS North Area gives
rise to unique possibilities for sensitive tests of the Standard Model in the
quark flavor sector. Precise measurements of the branching ratios for the
flavor-changing neutral current decays $K\to\pi\nu\bar{\nu}$ can provide
unique constraints on CKM unitarity and, potentially, evidence for new
physics. Building on the success of the NA62 experiment, plans are taking
shape at CERN for a comprehensive program that will include experimental
phases to measure the branching ratio for $K^{+}\to\pi^{+}\nu\bar{\nu}$ to
$\sim$5% and to $K_{L}\to\pi^{0}\nu\bar{\nu}$ to $\sim$20% precision. These
planned experiments would also carry out lepton flavor universality tests,
lepton number and flavor conservation tests, and perform other precision
measurements in the kaon sector, as well as searches for exotic particles in
kaon decays. We overview the physics goals, detector requirements, and project
status for the next generation of kaon physics experiments at CERN.

##  1 Introduction

Rare kaon decays provide information on the unitary triangle, as illustrated
in Figure 1. These are flavor-changing neutral current processes (FCNC) that
probe the $s\to d\nu\bar{\nu}$ or $s\to d\ell^{+}\ell^{-}$ transitions. They
are highly GIM-suppressed and their SM rates are very small. The
$K\to\pi\nu\bar{\nu}$ decays are the least affected by long-distance physics.
The branching ratios (BRs) for the $K\to\pi\nu\bar{\nu}$ decays are among the
observable quantities in the quark-flavor sector most sensitive to new
physics.

Figure 1: Determination of the unitary triangle with rare kaon decays.

In the SM, the uncertainties on the $K\to\pi\nu\bar{\nu}$ rates are entirely
dominated by the uncertainties on the CKM matrix elements $|V_{ub}|$ and
$|V_{cb}|$ and the angle $\gamma$. Using values for these parameters from the
analysis of tree-level observables, Buras et al. obtain [1]

$\begin{split}{\rm BR}(K_{L}\to\pi^{0}\nu\bar{\nu})&=(3.4\pm 0.6)\times
10^{-11},\\\ {\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})&=(8.4\pm 1.0)\times
10^{-11}.\end{split}$ (1)

Assuming no new-physics effects in $\epsilon_{K}$ and $\sin{2\beta}$ from
$B\to J/\psi K_{S}$, the BRs can be determined independently of $|V_{cb}|$ as
${\rm BR}(K_{L}\to\pi^{0}\nu\bar{\nu})=(2.94\pm 0.15)\times 10^{-11}$ and
${\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})=(8.60\pm 0.42)\times 10^{-11}$ [2]. The
intrinsic theoretical uncertainties, if the CKM parameters are taken to be
exact, are about 1.5% and 3.5%, respectively.

Because the amplitude for $K^{+}\to\pi^{+}\nu\bar{\nu}$ has both real and
imaginary parts, while the amplitude for $K_{L}\to\pi^{0}\nu\bar{\nu}$ is
purely imaginary, the decays have different sensitivity to new sources of $CP$
violation. Measurements of both BRs would therefore be extremely useful not
only to uncover evidence of new physics in the quark-flavor sector, but also
to distinguish between new physics models. More generally, measurement of all
of the FCNC kaon decays would allow the unitarity triangle to be
overconstrained as illustrated in Figure 1, potentially providing evidence of
new physics independently of and in comparison to results from $B$ and $D$
meson decays and providing important information about the flavor structure of
that physics.

##  2 The NA62 experiment

NA62 is a fixed-target experiment at the CERN SPS, the goal of which is to
measure ${\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})$ to within 10% [3]. The
secondary positive beam, consisting of 6% $K^{+}$ with a total rate of 750
MHz, is derived from the 400-GeV primary proton beam from the SPS incident at
zero angle on a beryllium target at a rate of $3\times 10^{12}$ protons per
pulse (ppp). The $K^{+}\to\pi^{+}\nu\bar{\nu}$ decay is detected in flight.
The signature is a $K^{+}$ entering the experiment and a $\pi^{+}$ leaving the
decay vertex, with missing momentum at the vertex and no other particles
observed in the final state. Principal backgrounds include those from the
abundant decays $K^{+}\to\mu^{+}\nu$ and $K^{+}\to\pi^{+}\pi^{0}$, as well as
backgrounds from upstream decays and interactions. The signal decay is
identified via selection in the $(p_{\pi},m^{2}_{\rm miss})$ plane to exclude
the abundant two-body decays, where $p_{\pi}$ is the momentum of the candidate
pion track and $m^{2}_{\rm miss}$ is the squared missing mass at the vertex.
The distinguishing features of the experiment include high-rate, precision
tracking for both the beam and secondary particles, redundant particle
identification systems and muon vetoes, and hermetic photon vetoes, including
a high-performance EM calorimeter.

Between 2016 and 2018, NA62 observed more than $4\times 10^{12}$ $K^{+}$
decays in its fiducial volume, with the expectation of observing 10 signal
events and 7 background events, principally from upstream decays and
interactions. A total of 20 events were observed, establishing the
$K^{+}\to\pi^{+}\nu\bar{\nu}$ decay with $3.4\sigma$ significance and
providing the most precise measurement to date for the branching ratio [4]:

${\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})=(10.6^{+4.0}_{-3.4}|_{\rm stat}\pm
0.9_{\rm syst})\times 10^{-11}.$

NA62 resumed data taking in July 2021 with a number of key modifications to
the beamline and detector to reduce background from upstream decays and
interactions and to allow data to be taken at the full nominal beam intensity.
The experiment is approved for data taking up to LHC Long Shutdown 3 (LS3),
currently foreseen for the end of 2025, and is expected to measure ${\rm
BR}(K^{+}\to\pi^{+}\nu\bar{\nu})$ to 10% precision by then. In the longer
term, fixed-target runs in the SPS North Area are foreseen at least through
2040. There is therefore an opportunity at the SPS for an integrated program
to pin down new physics in the kaon sector via measurement of all rare kaon
decay modes—both charged and neutral.

##  3 The HIKE physics program

The HIKE program (High Intensity Kaon Experiments at the CERN SPS) [5] is
foreseen to include three experimental phases for the comprehensive, high-
precision study of rare kaon decays during the period from the end of LS3 to
the FCC era:

  * •

Phase 1: A $K^{+}$ experiment running at four times the intensity of NA62
($1.2\times 10^{13}$ ppp) to measure ${\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})$
to 5% precision. Phase 1 will also focus on studies of lepton
universality/number/flavor violation through observables such as
$R_{K}=\Gamma(K^{+}\to e^{+}\nu)/\Gamma(K^{+}\to\mu^{+}\nu)$ and
$K^{+}\to\pi^{+}\ell\ell$, and searches for decays such as
$K^{+}\to\pi^{-}\ell^{+}\ell^{+}$ and $K^{+}\to\pi^{+}\mu e$. The experiment
will also make precision measurements of leptonic and semileptonic, radiative,
and Dalitz decays and chiral parameters of the kaon system.

  * •

Phase 2: An experiment with a neutral beam and tracking and PID systems
optimized for the measurement of decays like $K_{L}\to\pi^{0}\ell^{+}\ell^{-}$
and $K_{L}\to\mu^{+}\mu^{-}$, as well as studies of lepton
universality/number/flavor violation in $K_{L}$ decays, radiative $K_{L}$
decays and precision measurements, and measurements of $K_{L}$, $n$, and
$\Lambda$ fluxes in the neutral beam and halo to prepare for the final phase.

  * •

Phase 3: An experiment to measure ${\rm BR}(K_{L}\to\pi^{0}\nu\bar{\nu})$ to
20%, also known as KLEVER [6].

In addition, periodic runs will be taken in beam-dump mode, with the target
out and the collimator in the secondary beam line closed, to allow sensitive
searches for the decays of exotic, long-lived particles produced in the decays
of mesons from interactions in the beam dump, with the goal of collecting
$10^{19}$ protons on target (pot) in dump mode in Phase 1 and up to $5\times
10^{19}$ pot by the end of Phase 3.

The experimental setup for all three phases will rely to the maximum extent
possible on the reuse of the same detectors in different configurations. In
particular, when a detector for HIKE is newly built or extensively upgraded,
if at all possible, it is designed to meet the performance requirements for
all successive phases.

###  3.1 HIKE Phase 1

Figure 2: Experimental setup for HIKE Phase 1

The four-fold increase in primary intensity needed for the measurement of
${\rm BR}(K^{+}\to\pi^{+}\nu\bar{\nu})$ to 5% will require major upgrades of
the primary and secondary beamlines, as discussed in [7]. From the standpoint
of the experiment, the success of NA62 has validated the measurement technique
and proves that the background can be handled. The key challenge from the
intensity increase is that the time resolution of the detectors must be
improved across the board by a factor of four in order to maintain the loss of
events from accidental coincidence (random veto) to acceptable levels
($\lesssim 25\%$), which must be achieved while maintaining other key
performance specifications such as space-time reconstruction performance, low
material budget, high single photon efficiencies, etc. The experimental setup,
shown in Figure 2, is not very different from that of NA62, but most detectors
will need to be rebuilt or extensively overhauled to secure the needed
performance.

Of particular interest, the NA62 beam tracker (Gigatracker, GTK), consisting
of three stations of silicon pixel detectors, will need to be upgraded to
track at 3 GHz. A time resolution of better than 50 ps will be required, and
the detector will have to be able to handle rates of 8 MHz/mm2 and be
radiation resistant up for particle fluences of more than $2\times 10^{15}$
$n$ eq/cm2/yr. An excellent candidate technology is provided by the timeSPOT
project [8, 9], which is developing hybrid 3D-trenched pixels in which the
pixel electrode geometry is optimized for timing performance.

The experiment’s rate capability for secondary particles must be improved as
well. New straw-tube designs are being developed at CERN, based on past
collaboration with Dubna, that will allow straw chambers for use in vacuum to
be developed with 5-mm diameter straws with wall thickness of 20 $\mu$m.

It is natural to inquire whether the NA48 liquid-krypton (LKr) calorimeter
[10] used in NA62 can be reused for any of the HIKE phases. NA48-era studies
suggest and NA62 experience confirms that the photon detection efficiency is
sufficient for at least Phases 1 and 2. The time resolution, however, is
insufficient for the high-intensity program and would require improvement by
at least a factor of four. Two directions are being pursued. The first is to
examine whether the LKr can be used for HIKE Phase 1. In addition to necessary
consolidation work, this would require upgrades to make the calorimeter
faster, including an increase in the operating voltage to increase the drift
velocity and faster signal shaping and digitizers for the readout system. For
the $K_{L}$ phases, the diameter of the LKr inner bore limits the solid angle
of the beam that can be used, so a new calorimeter would be necessary in any
case. The new calorimeter could also be used in Phase 1, if it is ready in
time. An ideal choice of technologies appears to be the fine-sampling shashlyk
design used for the KOPIO and PANDA calorimeters [11], which has been shown to
provide excellent energy and time resolution. For HIKE, PID capability could
be added by including independently read out, 1-cm-thick “spy tiles” at key
points in the shashlyk stack (for example, at the front of the calorimeter for
charged-particle identification, at shower maximum, and deep in the stack).
Prototypes with this design have been tested at Protvino and DESY. Another
option under investigation is to construct the calorimeter with new-
generation, nanocomposite scintillators [12], which offer high light output,
fast response, and good radiation robustness.

###  3.2 HIKE Phase 2

Figure 3: Experimental setup for HIKE Phase 2

For HIKE Phase 2, a new neutral beamline is required. The baseline design is
the original 120-m beamline for KLEVER [13], featuring four collimation
stages, including an active final collimator that is incorporated into the
experiment and an oriented-crystal-metal photon converter at the center of the
dump collimator to reduce the flux of prompt photons in the beam [14]. The
collimation system defines a beam opening angle of 0.4 mrad. The neutral beam
is produced at $\theta=2.4$ mrad; $K_{L}$ mesons in the beam have an average
momentum of 79 GeV, while those decaying in the fiducial volume (FV) have an
average momentum of 46 GeV. Relative to the Phase-1 experiment, in addition to
the changes to the beamline and the removal of the beamline detectors for
charged particles, the RICH is removed and the spectrometer is moved further
downstream to increase the acceptance for decays such as
$K_{L}\to\pi^{0}\ell^{+}\ell^{-}$. The beamline and experimental setup are
illustrated in Figure 3.

At a primary intensity of $2\times 10^{13}$ ppp (a six-fold increase with
respect to NA62), nearly $2\times 10^{14}$ kaon decays will be observed in the
FV in five years of running. This will allow single-event sensitivities for
$K_{L}\to\pi^{0}\ell^{+}\ell^{-}$ to be improved by two orders of magnitude
with respect to the current best limits from KTeV [15, 16]. There are
topologically identical backgrounds to these channels from
$K_{L}\to\gamma\gamma\ell^{+}\ell^{-}$, with BRs that are 3–4 orders of
magnitude greater than for $K_{L}\to\pi^{0}\ell^{+}\ell^{-}$ [17]. Suppression
of these backgrounds relies on the excellent energy resolution of the HIKE EM
calorimeter for the reconstruction of the $\pi^{0}$ mass peak for the signal
decay. HIKE Phase 2 will be well positioned to make the first observation of
the $K_{L}\to\pi^{0}\ell^{+}\ell^{-}$ decay, as well as to measure ${\rm
BR}(K_{L}\to\mu^{+}\mu^{-})$ with a statistical precision of 0.2%, improving
on the current best result from BNL-E871 [18], and should also achieve BR
sensitivities of $O(10^{-12})$ for a broad range of rare and forbidden $K_{L}$
decays, such as lepton-flavor violating processes, representing improvement on
current best limits from BNL-E871 by up to a factor of 60.

###  3.3 HIKE Phase 3

Figure 4: Experimental setup for HIKE Phase 3 (KLEVER)

HIKE Phase 3 is a dedicated experiment, known as KLEVER, to measure ${\rm
BR}(K_{L}\to\pi^{0}\nu\bar{\nu})$ to 20%. Specifically, with a total exposure
of $6\times 10^{19}$ pot in five years at an intensity of $2\times 10^{13}$
ppp, the KLEVER goal is to detect 60 signal events at the Standard Model
branching ratio, with a signal-to-background ratio $S/B\sim 1$. The experiment
is complementary to KOTO, in the sense that the beam energy is significantly
higher. As a result, photons from $K_{L}$ decays receive a significant boost,
which makes photon vetoing easier. On the other hand, the length of the
experiment is much greater, and a very long beamline is required to allow
$\Lambda$ baryons and $K_{S}$ mesons to decay upstream of the fiducial volume.
Relative to the Phase-2 beamline, the KLEVER beamline needs to be extended by
an additional 150 m from target to final collimator. This in turn requires a
downstream extension of the ECN3 hall by a similar amount. For KLEVER running,
the production angle for the neutral beam will be increased from 2.4 to 8.0
mrad: this decreases the $n/K_{L}$ and $\Lambda/K_{L}$ ratios for the beam and
softens the momentum spectra so that the average $K_{L}$ momentum is 39 GeV at
production (26 GeV for $K_{L}$ mesons that decay in the FV). This also
decreases the absolute $K_{L}$ flux, which is further reduced by the need to
collimate the beam more tightly ($\Delta\theta=0.256$ mrad) for the extended
beamline. The need for additional construction to extend the ECN3 hall is a
major factor in scheduling KLEVER towards the end of the HIKE program. Cost
estimates are in progress.

From the standpoint of the experiment, the layout of the vacuum tank and
fiducial volume is roughly the same as for the other HIKE phases. The
spectrometer will be removed and the number of large-angle photon veto
detectors will be increased from 12 to 25 to extend the polar angle coverage
out to 100 mrad (from 50 mrad for Phases 1 and 2). The HIKE large-angle vetoes
themselves will be fine-segmented lead/scintillating tile detectors similar to
the VVS detectors for the planned but never realized CKM experiment [19]. One
particularly challenging detector for KLEVER is the small-angle calorimeter
(SAC), which sits in the neutral beam at the downstream end of the experiment
and which must reject photons from background decays such as
$K_{L}\to\pi^{0}\pi^{0}$ that would otherwise escape via the beam exit. The
SAC must have good photon detection efficiency, especially for high energy
photons (e.g., the inefficiency must be $<10^{-4}$ for photons with $E>30$
GeV) while being as insensitive as possible to the accidental coincidence of
nearly 600 MHz of neutral hadrons ($n$ and $K_{L}$) in the beam. The SAC must
also have $\sigma_{t}<100$ ps, be able to separate two pulses a few ns apart,
and be radiation hard to $10^{14}$ $n$/cm2 and $10^{5}$–$10^{6}$ Gy. Our
proposed solution is an ultra-fast, high-$Z$ crystal calorimeter based on a
Cerenkov radiator like PbF2 or an ultra-fast scintillator such as PWO-UF [20],
which has a dominant emission component with $\tau<0.7$ ns. The SAC will have
transverse and longitudinal segmentation for $\gamma/n$ discrimination. From
an engineering standpoint, it will be very similar to the CRILIN calorimeter
[21], and R&D is proceeding in concert between the HIKE and CRILIN
collaborations. An additional possibility under investigation is to exploit
the coherent interactions of high-energy photons in oriented crystals to
stimulate early pair conversion, allowing the calorimeter to be realized with
reduced thickness, increasing the transparency to neutral hadrons while
maintaining high detection efficiency for photons [22].

##  4 Conclusions

The HIKE project consists of a three-phase experimental program for the
comprehensive study of flavor physics in the kaon sector. The experimental
apparatus changes over time with a staged approach, allowing HIKE to evolve
and adapt its physics scope, an important feature for a project that embraces
a time scale of more than decade, during which the physics landscape could
change. Thanks to the successful experience of NA62 and its predecessor NA48,
the experimental techniques are well established and robust expectations of
sensitivity can be obtained from the extrapolation of existing data. The HIKE
Letter of Intent was submitted to the CERN SPSC at the beginning of November
2022 [5]. A formal proposal is in preparation for submission in fall 2023.

## References

## References

  * [1] Buras A J, Buttazzo D, Girrbach-Noe J and Knegjens R 2015 JHEP 11 033 (Preprint 1503.02693)
  * [2] Buras A J and Venturini E 2021 Acta Phys. Polon. B 53 A1 (Preprint 2109.11032)
  * [3] Cortina Gil E et al. (NA62) 2017 JINST 12 P05025 (Preprint 1703.08501)
  * [4] Cortina Gil E et al. (NA62) 2021 JHEP 06 093 (Preprint 2103.15389)
  * [5] Cortina Gil E et al. (HIKE) 2022 HIKE, High Intensity Kaon Experiments at the CERN SPS: Letter of Intent Tech. Rep. SPSC-2022-031/SPSC-I-257 CERN (Preprint 2211.16586) URL https://cds.cern.ch/record/2839661
  * [6] Ambrosino F et al. (KLEVER Project) 2019 (Preprint 1901.03099)
  * [7] Gatignon L, Bernhard J, Brugger M, Doble N et al. 2018 Report from the Conventional Beams Working Group to the Physics Beyond Collider Study and to the European Strategy for Particle Physics Tech. rep. CERN Geneva URL https://cds.cern.ch/record/2650989
  * [8] Lai A 2018 A system approach towards future trackers at high luminosity colliders: the timespot project (Sydney, NSW, Australia: IEEE) pp 1–3 ISBN 978-1-5386-8495-5 ISSN 1082-3654
  * [9] Lai A et al. 2022 Timespot project testbeam results and simulations talk given at ”1st MONOLITH Workshop on silicon sensors for timing and their applications”, Geneve, September 2022 URL https://indico.cern.ch/event/1179742/contributions/4961955/attachments/2502408/4298914/ Timing_ALai_UniGe.pdf
  * [10] Fanti V et al. (NA48) 2007 Nucl. Instrum. Meth. A574 433–471
  * [11] Atoian G S et al. 2008 Nucl. Instrum. Meth. A584 291–303 (Preprint 0709.4514)
  * [12] Gandini M et al. 2020 Nat. Nanotechnol. 15 462–468
  * [13] Van Dijk M et al. 2019 The K12 beamline for the KLEVER experiment URL doi.org/ 10.18429/JACoW-IPAC2019-THPGW061
  * [14] Soldani M et al. 2022 (Preprint 2203.07163)
  * [15] Alavi-Harati A et al. (KTeV) 2004 Phys. Rev. Lett. 93 021805 (Preprint hep-ex/0309072)
  * [16] Alavi-Harati A et al. (KTEV) 2000 Phys. Rev. Lett. 84 5279–5282 (Preprint hep-ex/0001006)
  * [17] Greenlee H B 1990 Phys. Rev. D 42 3724–3731
  * [18] Ambrose D et al. (E871) 2000 Phys. Rev. Lett. 84 1389–1392
  * [19] Ramberg E, Cooper P and Tschirhart R 2004 IEEE Trans. Nucl. Sci. 51 2201–2204
  * [20] Korzhik M et al. 2022 Nucl. Instrum. Meth. A 1034 166781
  * [21] Ceravolo S et al. 2022 JINST 17 P09033 (Preprint 2206.05838)
  * [22] Bandiera L, Haurylavets V and Tikhomirov V 2019 Nucl. Instrum. Meth. A 936 124–126


Leo van Iersel, Mark Jones, Jannik Schestag, Celine Scornavacca and Mathias
Weller TU Delft, The Netherlands and
https://leovaniersel.wordpress.com/l.j.j.vanIersel@tudelft.nlhttps://orcid.org/0000-0001-7142-4706Partially
funded by Netherlands Organization for Scientific Research (NWO) grant
OCENW.KLEIN.125 and OCENW.M.21.306. TU Delft, The Netherlands and
https://www.thenetworkcenter.nl/People/Postdocs/person/83/Dr-Mark-
Jonesm.e.l.jones@tudelft.nlhttps://orcid.org/0000-0002-4091-7089Partially
funded by Netherlands Organization for Scientific Research (NWO) grant
OCENW.KLEIN.125 and OCENW.M.21.306. Friedrich-Schiller-Universität Jena,
Germany; TU Delft, The Netherlandsj.t.schestag@uni-
jena.dehttps://orcid.org/0000-0001-7767-2970 ISEM, Université de Montpellier,
CNRS, IRD, EPHE, Montpellier, France and
https://sites.google.com/view/celinescornavaccaceline.scornavacca@umontpellier.frhttps://orcid.org/0009-0004-0179-9771Partially
funded by French Agence Nationale de la Recherche through the CoCoAlSeq
Project (ANR-19-CE45-0012). TU Berlin, Germanymathias.weller@tu-
berlin.dehttps://orcid.org/0000-0002-9653-3690 Applied computing Computational
biology Theory of computation Fixed parameter tractability Theory of
computation Problems, reductions and completeness

# Maximizing Network Phylogenetic Diversity

Leo van Iersel  Mark Jones  Jannik Schestag  Celine Scornavacca  Mathias
Weller

(June 2023 — )

###### 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 $\mathcal{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.

###### keywords:

phylogenetic diversity; phylogenetic networks; network phylogenetic diversity;
algorithms; computational complexity

##  1 Introduction

In a context where human activities are driving a sixth mass extinction [12],
and while waiting for a serious political response to this crisis [9],
studying _phylogenetic diversity_ (PD) is definitely 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 [15]. The concept of PD is an attempt at answering this question.
The concept has been introduced three decades ago and the seminal paper
establishing the notion [5] has been cited more than 5000 times. The underling
idea is simple: if we want to preserve as much biodiversity as possible 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\subseteq 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 be always appropriate, see [17].)

PD has been extensively used in the context of tree-like evolution, and, given
a tree $T$ and an integer $k$, the best algorithm to find an optimal subset of
$k$ species maximizing PD for $T$, is a fast and greedy one, which has the
nice property of also being optimal [14, 11].

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 [16, 2], one of
which is called Network-PD. The optimization problem linked to Network-PD,
i.e. computing the maximum $\text{Network-PD}_{\mathcal{N}}$ score over all
subsets of species of size at most $k$ for a given phylogenetic network
$\mathcal{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
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 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, 11] 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$, we let $[n]:=\\{1,\dots,n\\}$. Let
$[0,1]:=\\{x\in\mathbb{R}:0\leq x\leq 1\\}$ and
$(0,1):=\\{x\in\mathbb{R}:0<x<1\\}$. Let
$\mathbb{R}_{>0}:=\\{x\in\mathbb{R}:x>0\\}$ and similarly $\mathbb{R}_{\geq
0}:=\\{x\in\mathbb{R}:x\geq 0\\}$. For a set $Z$ and an integer $k$ with
$k\leq|Z|$, we denote by $\binom{Z}{k}$ the set of all subsets of $Z$ with
exactly $k$ elements. In this paper we will make use of both natural and
binary logarithms. We will write $\ln x$ to denote the logarithm of $x$ to the
base $e$, and $\log_{2}x$ to denote the logarithm of $x$ to the base $2$.

##### Phylogenetics.

Given a set of taxa $X$, a _phylogenetic network on $X$_ or _$X$ -network_ is
a directed acyclic graph $\mathcal{N}=(V,E)$ in which the _leaves_ (vertices
of indegree $1$ and outdegree $0$) are bijectively labelled with elements from
$X$, and in which there a single vertex of indegree $0$ and outdegree $2$ (the
_root_), and in which all other vertices either have indegree $1$ and
outdegree at least $2$ (the _tree nodes_) or indegree at least $2$ and
outdegree $1$ (the _reticulations_). 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 in-
degrees 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
of any maximal subgraph with no cut-arcs (which are arcs whose deletion would
disconnect the network).

For vertices $u,v\in V$, we say $u$ is an _ancestor of $v$_ and $v$ is a
_descendant of $u$_ if there 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$). If $e=uv$ is a directed edge in
$\mathcal{N}$, then we say that $u$ is a _parent_ of $v$ and $v$ is a _child_
of $u$. The set of _offspring_ of $e$, denoted $\operatorname{off}(e)$, is the
set of all $x\in X$ which are descendants of $v$. When $v$ is a reticulation,
we call the edge $uv$ a _reticulation edge_.

##### Diversity.

We assume that each edge $e$ in a network $\mathcal{N}=(V,E)$ has an
associated _weight_ $\omega(e)$, which is a positive integer. 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|\operatorname{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, a number of extensions of the definition to
phylogenetic networks have been recently proposed [2, 16]. In this paper we
focus $\text{Network-PD}_{\mathcal{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$ 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 $\text{Network-
PD}_{\mathcal{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^{p}_{Z}(uv)$ that a random feature
appearing in $u$ or developed on $uv$ will survive when preserving $Z$.

Formally, we define $\gamma^{p}_{Z}(uv)$ as follows:

######  Definition 2.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^{p}_{Z}:E\to[0,1]$ recursively for each edge $uv\in E$ as follows:

  * •

If $v$ is a leaf, then $\gamma^{p}_{Z}(uv):=p(uv)$ if $v\in Z$, and
$\gamma^{p}_{Z}(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^{p}_{Z}(uv)=p(uv)\cdot\gamma^{p}_{Z}(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^{p}_{Z}(uv)=1-\prod_{i}(1-\gamma^{p}_{Z}(vx_{i}))$. In the special
case that $v$ has two children, this is equivalent to
$\gamma^{p}_{Z}(vx)+\gamma^{p}_{Z}(vy)-\gamma^{p}_{Z}(vx)\cdot\gamma^{p}_{Z}(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^{p}_{Z}(e)$.

Observe that $\gamma^{p}_{Z}(e)$ and $\text{Network-PD}_{\mathcal{N}}(Z)$ are
monotone on $Z$, that is, $\gamma^{p}_{Z^{\prime}}(e)\leq\gamma^{p}_{Z}(e)$
and $\text{Network-PD}_{\mathcal{N}}^{p}(Z^{\prime})\leq\text{Network-
PD}_{\mathcal{N}}^{p}(Z)$ for all $Z^{\prime}\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 some $Z\subseteq X$ with
$|Z|\leq k$ and $\text{Network-PD}_{\mathcal{N}}(Z)\geq 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 $\operatorname{off}(e)\cap
Z\neq\emptyset$, and otherwise $\gamma_{Z}(uv)=0$ (see Lemma 3.4). 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 of the form $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

We solve a generalization of Max-Network-PD, 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)\leq 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 a unique 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 out-
degree, even if the input network is binary. However, the algorithm used to
solve the resulting non-binary tree can deal with such polytomies [10].

##### 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.

######  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)$.

######  Proof 3.1 (Correctness of 1).

Let
$\mathcal{I}^{\prime}=:(\mathcal{N}^{\prime},\omega^{\prime},p^{\prime},c,k,D^{\prime})$
be the result of applying 1 to $\mathcal{I}$. Clearly, we have
$\gamma^{p^{\prime}}_{Z}(e)=\gamma^{p}_{Z}(e)$ for any edge $e$ below $w$ and
all $Z$. So by construction $\gamma^{p^{\prime}}_{Z}(uw)=\gamma^{p}_{Z}(vw)$.
Observe that $p(uv)=1$ since $v$ is not a leaf and $r$ is the lowest
reticulation in $\mathcal{N}$; thus,
$\gamma^{p}_{Z}(uv)=\gamma^{p}_{Z}(vw)=\gamma^{p^{\prime}}_{Z}(uw)$. This
implies that $\gamma^{p^{\prime}}_{Z}(e)=\gamma^{p}_{Z}(e)$ for all $Z$ and
any $e\in E\setminus\\{uv,vw\\}$. So $\text{Network-
PD}_{\mathcal{N}}-\text{Network-
PD}_{\mathcal{N}^{\prime}}=\gamma^{p}_{Z}(uv)\cdot\omega(uv)+\gamma^{p}_{Z}(vw)\cdot\omega(vw)-\gamma^{p^{\prime}}_{Z}(uw)\cdot
w(uw)=\gamma^{p}_{Z}(uv)\cdot(w(uv)+w(vw)-w(uw))=0$.

######  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$.

######  Proof 3.2 (Correctness of 2).

Let $u$ be the unique parent of $v$, and let $v_{i}$ denote the non-$\ell$
children of $v$. Then
$\gamma^{p}_{Z}(uv)=1-(1-\gamma^{p}_{Z}(v\ell))\prod_{i}(1-\gamma^{p}_{Z}(uv_{i}))$
before removing $\ell$ and
$\gamma^{p}_{Z}(uv)=1-\prod_{i}(1-\gamma^{p}_{Z}(uv_{i}))$ after. Since
$\gamma^{p}_{Z}(v\ell)=0$ for all $Z$, the value of $\gamma^{p}_{Z}(uv)$ does
not change after removing $\ell$, and so neither does the score of $Z$.

######  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(rx)$ and
$\omega(z\ell_{z_{i}}):=\omega(z_{i}r)$. Finally, remove $r$ and $x$ and
decrease $D$ by $p(rx)\cdot\omega(rx)$.

######  Proof 3.3 (Correctness sketch of 3).

As $x$ has cost 0 and $\gamma^{p}_{Z}$ is monotone on $Z$, every maximal
solution for $\mathcal{I}$ contains $x$. Likewise, every maximal solution for
the modified instance $\mathcal{I}^{\prime}$ 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}^{\prime}$ and
this score is $p(rx)\cdot\omega(rx)$.

######  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. (1)

for each $uv\in E_{x}$, multiply $\omega(uv)$ by $1-\gamma^{p}_{Q}(uv)$,

  2. (2)

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

  3. (3)

reduce $D$ by $\sum_{e\in E_{x}}\gamma^{p}_{Q}(e)\cdot\omega(e)$, and

  4. (4)

add a new cost-0 leaf $\ell^{*}$ as a child of $x$ with $\omega(x\ell^{*})=0$
and $p(\ell^{*})=\gamma^{p}_{Q}(rx)$.

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

######  Lemma 3.4.

Let $e=uv$ be an edge in $\mathcal{N}$ such that all descendants of $v$
(including $v$) are tree nodes and let $Z$ be any leaf set of $\mathcal{N}$.
Then, $\gamma^{p}_{Z}(e)=1-\prod_{\ell\in\operatorname{off}(e)\cap
Z}(1-p(\ell))$.

######  Proof 3.5.

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^{p}_{Z}(e)=1-\prod_{\ell\in\operatorname{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,

$\displaystyle\gamma^{p}_{Z}(e)$
$\displaystyle\stackrel{{\scriptstyle\text{Def.\leavevmode\nobreak\
\ref{def:gamma}}}}{{=}}1-\prod_{i}\big{(}1-\gamma^{p}_{Z}(vx_{i})\big{)}\stackrel{{\scriptstyle
IH}}{{=}}1-\prod_{i}\bigg{(}1-\big{(}1-\;\smashoperator[]{\prod_{\ell\in\operatorname{off}(vx_{i})\cap
Z}^{}}\;(1-p(\ell))\big{)}\bigg{)}$
$\displaystyle=1-\prod_{i}\big{(}\;\;\;\;\;\smashoperator[]{\prod_{\ell\in\operatorname{off}(vx_{i})\cap
Z}^{}}\;(1-p(\ell))\big{)}=1-\;\smashoperator[]{\prod_{\ell\in\operatorname{off}(e)\cap
Z}^{}}\;(1-p(\ell))$

######  Proof 3.6 (Correctness of 4).

Let
$\mathcal{I}^{\prime}=:(\mathcal{N},\omega^{\prime},p^{\prime},c,k,D^{\prime})$
be the result of applying 4 to $\mathcal{I}$ and let
$Q^{\prime}:=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 $\text{Network-PD}_{\mathcal{N}}^{p}(Z)$ is monotone on $Z$. Let $Z$ and
$Z^{\prime}$ be any subsets of leaves of $\mathcal{N}$ and
$\mathcal{N}^{\prime}$, respectively, with $Q\subseteq Z$ and
$Z^{\prime}=Z\cup\\{\ell^{*}\\}$. We show that $Z$ is a solution for
$\mathcal{I}$ if and only if $Z^{\prime}$ is a solution for
$\mathcal{I}^{\prime}$.

We consider the contribution of each edge to the diversity score of $Z$ in
$\mathcal{N}$ and the diversity score of $Z^{\prime}$ in
$\mathcal{N}^{\prime}$. If $Z$ (and, thus, also $Z^{\prime}$) contains a
cost-1 leaf $\ell$ below $r$, then $p(\ell)=1$ and, by Lemma 3.4, we have
$\gamma^{p}_{Z}(rx)=1=\gamma^{p^{\prime}}_{Z^{\prime}}(rx)$. Otherwise,
$\gamma^{p}_{Z}(rx)=\gamma^{p}_{Q}(rx)=p^{\prime}(\ell^{*})=\gamma^{p^{\prime}}_{\\{\ell^{*}\\}}(rx)=\gamma^{p^{\prime}}_{Z^{\prime}}(rx)$.
In both cases, $\gamma^{p}_{Z}(e)=\gamma^{p^{\prime}}_{Z^{\prime}}(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^{p^{\prime}}_{Z^{\prime}}(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

$\displaystyle\gamma^{p}_{Z}(e)$
$\displaystyle\stackrel{{\scriptstyle\text{\lx@cref{creftypecap~refnum}{lem:tree
score}}}}{{=}}1-\smashoperator[]{\prod_{\ell\in\operatorname{off}(e)\cap
Z}^{}}\,(1-p(\ell))=1-\smashoperator[]{\prod_{\ell\in\operatorname{off}(e)\cap
Q}^{}}\,(1-p(\ell))\cdot\smashoperator[]{\prod_{\ell\in\operatorname{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
$\displaystyle\gamma^{p}_{Z}(e)$
$\displaystyle=\begin{cases}\underbrace{1-\smashoperator[]{\prod_{\ell\in\operatorname{off}(e)\cap
Q}^{}}\,(1-p(\ell))}_{\gamma^{p}_{Q}(e)}&\text{if }\operatorname{off}(e)\cap
Z\subseteq Q\\\ 1&\text{otherwise}\end{cases}$ and the same holds for
$p^{\prime}$ and $Z^{\prime}$ instead of $p$ and $Z$ since the leaves below
$e$ in $\mathcal{N}$ are exactly the leaves below $e$ in
$\mathcal{N}^{\prime}$ ($\ell^{*}$ cannot be below $e$ in
$\mathcal{N}^{\prime}$ since $e\in E_{x}$). Now, since $p^{\prime}(\ell)=0$
for all $\ell\in Q$ by construction, we have
$\displaystyle\gamma^{p^{\prime}}_{Z^{\prime}}(e)$
$\displaystyle=\begin{cases}0&\text{if }\operatorname{off}(e)\cap Z\subseteq
Q\\\ 1&\text{otherwise}\end{cases}$

implying
$\gamma^{p}_{Z}(e)=\gamma^{p^{\prime}}_{Z^{\prime}}(e)\cdot(1-\gamma^{p}_{Q}(e))+\gamma^{p}_{Q}(e)$.
Then,

$\displaystyle\sum_{e\in
E}\gamma^{p}_{Z}(e)\cdot\omega(e)-\smashoperator[]{\sum_{e\in
E\cup\\{x\ell^{*}\\}}^{}}\gamma^{p^{\prime}}_{Z^{\prime}}(e)\cdot\omega^{\prime}(e)$
$\displaystyle=\sum_{e\in
E_{x}}(\gamma^{p}_{Z}(e)\cdot\omega(e)-\gamma^{p^{\prime}}_{Z^{\prime}}(e)\cdot\omega^{\prime}(e))$
$\displaystyle\stackrel{{\scriptstyle\text{Def'n\leavevmode\nobreak\
$\omega^{\prime}$}}}{{=}}\sum_{e\in
E_{x}}\big{(}\gamma^{p}_{Z}(e)-\gamma^{p^{\prime}}_{Z^{\prime}}(e)\cdot(1-\gamma^{p}_{Q}(e))\big{)}\cdot\omega(e)$
$\displaystyle=\sum_{e\in E_{x}}\gamma^{p}_{Q}(e)\cdot\omega(e)=D-D^{\prime}$

Thus, $\sum_{e\in E}\gamma^{p}_{Z}(e)\cdot\omega(e)\geq D$ if and only if
$\sum_{e\in E}\gamma^{p^{\prime}}_{Z}(e)\cdot\omega(e)\geq D^{\prime}$.

##### 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 choses any cost-1 leaf below $r$, then there is also a solution
choosing a “heaviest” cost-1 leaf below $r$ instead.

######  Lemma 3.7.

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 $\text{Network-
PD}_{\mathcal{N}}^{p}(Z^{*})\geq\text{Network-PD}_{\mathcal{N}}^{p}(Z)$.

######  Proof 3.8.

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})\geq\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^{p}_{Z}(e_{b})=\gamma^{p}_{Z^{*}}(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^{p}_{Z^{*}}(e)\omega(e)-\sum_{e\in
E}\gamma^{p}_{Z}(e)\omega(e)=\omega(q_{a})-\omega(q_{b})\geq 0$.

$r$$\rho$$x$$r$$\rho$$x$$r$$\rho$$x$

$\leadsto$

$\leadsto$

$0$$0$$0$$0$$1$$1$$1$$0$$1$$0$$1$$0$$\ell$$0$$\ell$$0$ Figure 1: Example for 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 inheritence probability one. Costs are written below the leaves.
Note that the budget for $\mathcal{I}_{1}$ is $k-1$ and that applying 4 may
change the target diversity.

Now, we can present and prove the correctness of our main branching rule,
solving 0/1-cost Max-Network-PD in $O^{*}(\binom{|R|}{k})$ time, where $R$ is
the set of reticulations in the input network and $k$ is the budget.

######  Branching Rule 1 (See Figure 1).

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. 1.

create the instance
$\mathcal{I}_{0}:=(\mathcal{N}_{0},\omega_{0},p_{0},c_{0},k,D)$ by

    1. (a)

setting $p_{0}(t):=0$ for all cost-1 leaves $t$ below $r$,

    2. (b)

replacing $rx$ with $\rho{}x$, setting $\omega_{0}(\rho{}x):=\omega(rx)$ and,

    3. (c)

adding a new leaf $\ell$ to $r$ with $p_{0}(\ell):=\gamma^{p}_{Q}(rx)$ and
$c_{0}(\ell):=\omega_{0}(r\ell):=0$, and

  2. 2.

create the instance
$\mathcal{I}_{1}:=(\mathcal{N}_{1},\omega_{1},p_{1},c_{1},k-1,D)$ by

    1. (a)

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

    2. (b)

replacing $rx$ with $\rho{}x$, setting $\omega_{1}(\rho{}x):=\omega(rx)$ and

    3. (c)

adding a new leaf $\ell$ to $r$ with $p_{1}(\ell):=1$ and
$c_{1}(\ell):=\omega_{1}(r\ell):=0$.

######  Proof 3.9 (Correctness of 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

$\displaystyle\gamma^{p_{i}}_{Z_{i}}(\rho{}x)=\begin{cases}\gamma^{p}_{Q}(rx)&\text{if
$i=0$}\\\ 1&\text{if
$i=1$}\end{cases}=p_{i}(\ell)=\gamma^{p_{i}}_{Z_{i}}(r\ell)$ and
$\displaystyle\gamma^{p}_{Z}(rx)=\begin{cases}\gamma^{p}_{Q}(rx)&\text{if
$Z\cap P=\emptyset$}\\\ 1&\text{if $Z\cap P\neq\emptyset$}\end{cases}$ (1)

so, under the condition $Z\cap P=\emptyset\iff i=0$, we have
$\gamma^{p_{i}}_{Z_{i}}(\rho{}x)=\gamma^{p}_{Z}(rx)$ and, thus,

$\displaystyle\gamma^{p_{i}}_{Z_{i}}(\rho{}x)\cdot\underbrace{\omega_{i}(\rho{}x)}_{=\omega(rx)}+\gamma^{p_{i}}_{Z_{i}}(r\ell)\cdot\underbrace{\omega_{i}(r\ell)}_{=0}\stackrel{{\scriptstyle\eqref{eq:rho
and x}}}{{=}}\gamma^{p}_{Z}(rx)\cdot\omega(rx).$ (2)

######  Claim 1.

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

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^{\prime}$ in
$\mathcal{I}_{i}$.

First, consider any arc $e$ in $\mathcal{N}$ that is not below $r$. Since, by
(1), we have $\gamma^{p}_{Z}(rx)=\gamma^{p_{i}}_{Z^{\prime}}(r\ell)$, and
since $p(\ell^{\prime})=p_{0}(\ell^{\prime})$ for any leaf
$\ell^{\prime}\neq\ell$, we inductively infer that
$\gamma^{p_{i}}_{Z^{\prime}}(e)=\gamma^{p}_{Z}(e)$ as these values only depend
on the values of 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^{\prime}$ 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^{\prime}$, so
$p(\ell^{\prime})=p_{0}(\ell^{\prime})$ for all
$\ell^{\prime}\in\operatorname{off}(e)\cap Z=\operatorname{off}(e)\cap
Z^{\prime}$. If $i=1$, then $p(\ell^{\prime})=p_{1}(\ell^{\prime})$ for all
leaves in $\operatorname{off}(e)$. Thus, by Lemma 3.4,

$\displaystyle\gamma^{p_{i}}_{Z^{\prime}}(e)=1-\smashoperator[]{\prod_{\ell^{\prime}\in\operatorname{off}(e)\cap
Z^{\prime}}^{}}\,(1-p_{i}(\ell^{\prime}))=1-\smashoperator[]{\prod_{\ell^{\prime}\in\operatorname{off}(e)\cap
Z}^{}}\,(1-p(\ell^{\prime}))=\gamma^{p}_{Z}(e).$

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

Finally, we show that $c(Z)=c_{i}(Z^{\prime})-i$. If $i=0$, then this holds
since $c_{0}(\ell)=0$. If $i=1$ then $Z$ intersects $P$ and, by Lemma 3.7, 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^{\prime})=c(Z)-1$.

Now, we can prove the promised equivalence. First, if $Z$ is a solution for
$\mathcal{I}$, then $Z^{\prime}:=Z\cup\\{\ell\\}$ is a solution for
$\mathcal{I}_{i}$ with $i=\operatorname{sgn}(|Z\cap P|)$. Second, if $Z_{0}$
is a solution for $\mathcal{I}_{0}$, then $Z_{0}^{\prime}:=Z_{0}\setminus P$
is also a solution for $\mathcal{I}_{0}$ since $p_{0}(\ell^{\prime})=0$ for
all $\ell^{\prime}\in P$ and, by 1, $Z:=Z_{0}^{\prime}\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 1. Thus, $Z$ is a solution for $\mathcal{I}$.

We can now solve 0/1-cost Max-Network-PD as follows. If $k=0$, then
monotonicity of $\text{Network-PD}_{\mathcal{N}}^{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 1. Note
that, in each new instance, $r$ has a leaf child with cost $0$. Thus, 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 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 $\mathcal{O}(n\log k)$ time [10]. 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 $\mathcal{O}(|E|)=\mathcal{O}(n+r)$ amortized time in
total.

######  Theorem 3.10.

On binary, $n$-leaf networks with $r$ reticulations, 0/1-cost Max-Network-PD
and Max-Network-PD can be solved in
$\mathcal{O}(\sum_{i=0}^{\min\\{k,r\\}}\binom{r}{i}\cdot\log
k\cdot(n+r))\subseteq\mathcal{O}(2^{r}\cdot\log k\cdot(n+r))$ time, where $k$
is the budget.111Note that this running time degenerates to $o(2^{r}\cdot n)$
if $k\leq r/3$

Theorem 3.10 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 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^{p}_{Z}(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 [8]:

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|\leq k$ and
$\sum_{e\in E}\gamma^{\prime}_{Z}(e)\cdot\omega(e)\geq D$, where
$\gamma^{\prime}_{Z}(e):=(1-\prod_{x\in\operatorname{off}(e)\cap Z}(1-p(x)))$?

Note that $\gamma^{\prime}_{Z}(e)$ corresponds to the probability that at
least one taxa in $\operatorname{off}(e)$ survives, under the assumption that
every taxa $x\in Z$ survives independently with probability $p(x)$, and every
taxa in $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.

The first part of the hardness proof shows 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 the definition of Subset Product is slightly different here from the
formulation that appears in e.g. 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 a 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 [4] and we reproved it for our
slightly adapted variant in the appendix.

######  Lemma 4.1 ([4]).

There is a polynomial-time reduction from X3C to Subset Product.

Since X3C is NP-hard [6], the NP-hardness of Subset Product follows
immediately.

##### Penalty Sum.

Komusiewicz and Schestag [8, Theorems 5.3 & 5.4] showed that unit-cost-NAP is
NP-hard if the following problem is:

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\mathbb{(}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}\geq D$?

We set out to show Penalty Sum NP-hard by reducing Subset Product to it. To
communicate the main ideas of this reduction, we first describe a simple
transformation that turns an instance of Subset Product into an equivalent
‘instance’ of Penalty Sum, but one in which the numbers involved are
irrational (and as such, cannot be produced in polynomial time). We then show
how this transformation can be turned into a polynomial-time reduction by
replacing the irrational numbers with suitably chosen rationals.

Finally, we reduce unit-cost-NAP to Max-Network-PD on level-1 networks,
showing that this restriction of Max-Network-PD is also NP-hard.

###  4.1 Hardness of Penalty Sum

The reduction from Subset Product to Penalty Sum can be informally described
as follows: For an instance $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$ of Subset
Product and a big integer $A$, we let $a_{i}$ be (a rational close to) $A-\ln
v_{i}$ and let $b_{i}:=1/v_{i}$, for each $i\in[n]$. Let $Q:=M$, let
$k:=k^{\prime}$, and let $D$ be (a rational close to) $kA-\ln Q-1$.

Note that we cannot set $a_{i}:=A-\ln v_{i}$ 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 $\sum_{i\in
S}a_{i}-Q\cdot\prod_{i\in S}b_{i}$ 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.

####  4.1.1 Reduction with irrational numbers

######  Construction 1.

Let $(\\{v_{1},\dots v_{m}\\},M,k)$ be an instance of Subset Product. Let us
define the following (not necessarily rational) numbers.

  * •

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

  * •

Let $a_{i}^{*}:=A-\ln v_{i}$ for each $i\in[m]$;

  * •

Let $b_{i}:=1/v_{i}$ for each $i\in[m]$;

  * •

Let $Q:=M$;

  * •

Let $D^{*}:=kA-\ln Q-1$.

Finally, output the instance $(\\{(a^{*}_{i},b_{i}):i\in[m]\\},k,Q,D^{*})$ of
Penalty Sum.

We note the purpose of $A$ in 1 is simply to ensure that $a_{i}^{*}>0$ for
each $i\in[m]$, as is required by the formulation of Penalty Sum. Now, let
$f^{*}:\binom{[m]}{k}\rightarrow\mathbb{R}$ be defined by

$\displaystyle f^{*}(S):=\sum_{i\in S}a^{*}_{i}-Q\cdot\prod_{i\in S}b_{i}.$

######  Lemma 4.2.

For any $S\in\binom{[m]}{k}$:

  1. 1.

$f^{*}(S)\leq D^{*}$, and

  2. 2.

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

######  Proof 4.3.

First, observe that given $|S|=k$, the function $f^{*}(S)$ can be written as

$\displaystyle f^{*}(S)=kA-\sum_{i\in S}\ln v_{i}-Q/\prod_{i\in
S}v_{i}=kA-\ln\big{(}\prod_{i\in S}v_{i}\big{)}-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^{\prime}$ when $\frac{dg^{*}}{dx}(x^{\prime})=0$. Since
$\frac{dg^{*}}{dx}=-x^{-1}+Qx^{-2}$, this occurs exactly when
${x^{\prime}}^{-1}=Q{x^{\prime}}^{-2}$, i.e. when $x^{\prime}=Q$. Moreover,
for $Q>x>0$, we have $Qx^{-1}>1$, implying

$\displaystyle\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

$\displaystyle\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})\leq g^{*}(Q)=kA-\ln Q-1=D^{*}.$ (3)

With equality if and only if $x_{S}=\prod_{i\in S}v_{i}=Q$.

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^{\prime})$ 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$.

####  4.1.2 Reduction with rational numbers

Let $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$ be an instance of Subset Product,
and let $a_{i}^{*},b_{i},Q,k,D^{*}$ be defined as previously. Then by Lemma
4.2, $f^{*}(S)=\sum_{i\in S}a^{*}_{i}-Q\cdot\prod_{i\in S}b_{i}\geq 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}\geq 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 which 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
$\mathcal{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}\leq 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$\dots$, the binary expression of $\lfloor{\pi}\rfloor_{3}$ is 11.001).
Similarly, let $\lceil{x}\rceil_{H}:=s_{x}/2^{H}$, where $s_{x}$ is the
smallest integer such that $x\leq s_{x}/2^{H}$. Finally, let
$\delta:=1/{2^{H}}$.

Let $x\in\mathbb{R}$. Then, $x-\delta<\lfloor{x}\rfloor_{H}\leq
x\leq\lceil{x}\rceil_{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:=\lceil\max_{i\in[m]}(\ln v_{i})\rceil+1$;

  * •

Let $a_{i}:=\lceil{a_{i}^{*}}\rceil_{H}=\lceil{A-\ln v_{i}}\rceil_{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:\binom{[m]}{k}\rightarrow\mathbb{R}$ be defined by

$\displaystyle 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\binom{[m]}{k}$ such that
$f(S)\geq 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 4.4.

Let $S\in\binom{[m]}{k}$. Then, $f^{*}(S)\leq f(S)<f^{*}(S)+k\delta$ and
$D^{*}-\delta<D\leq D^{*}.$

######  Proof 4.5.

Observe that $f(S)-f^{*}(S)=\sum_{i\in S}(a_{i}-a_{i}^{*})$ and $|S|=k$. Then,
by Section 4.1.2, we have $0\leq a_{i}-a_{i}^{*}<\delta$ for all $i\in[m]$.
Thus, $0\leq f(S)-f^{*}(S)<k\delta$, from which the first claim follows. The
second claim follows immediately from Section 4.1.2 and the fact that
$D=\lfloor{D^{*}}\rfloor_{H}$.

######  Corollary 4.6.

Let $S\in\binom{[m]}{k}$ such that $\prod_{i\in S}v_{i}=Q$. Then, $f(S)\geq
D$.

######  Proof 4.7.

$D\stackrel{{\scriptstyle\text{Lem.\leavevmode\nobreak\
\ref{lem:fDbounds}}}}{{\leq}}D^{*}\stackrel{{\scriptstyle\text{Lem.\leavevmode\nobreak\
\ref{lem:PenSumIrrationalMax}\leavevmode\nobreak\
(2)}}}{{=}}f^{*}(S)\stackrel{{\scriptstyle\text{Lem.\leavevmode\nobreak\
\ref{lem:fDbounds}}}}{{\leq}}f(S)$.

We now have that $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$ 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\binom{[m]}{k}$ that $\prod_{i\in
S}v_{i}=Q^{\prime}\neq 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\leq
D^{*}-\delta$, that is $(k+1)\delta\leq D^{*}-f^{*}(S)$. To do this, we first
establish a lower bound on $D^{*}-f^{*}(S^{\prime})$ in terms of $Q$, using
the following technical lemma, whose proof is deferred to the appendix.

######  Lemma 4.8.

Let $Q,Q^{\prime}\in\mathbb{N}_{+}$ with $Q\geq 2$ and $Q\neq Q^{\prime}$.
Then, $\ln Q^{\prime}-\ln Q+Q/Q^{\prime}-1>Q^{-4}$.

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

######  Corollary 4.9.

Suppose $\prod_{i\in S}v_{i}=Q^{\prime}\neq Q$ for some $Q\geq 2$ and
$S\in\binom{[m]}{k}$. Then $D^{*}-f^{*}(S)>Q^{-4}$.

######  Proof 4.10.

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^{\prime}-Q/Q^{\prime}$. Then
$D^{*}-f^{*}(S)=\ln Q^{\prime}-\ln Q+Q/Q^{\prime}-1$. It follows from Lemma
4.8 that $D^{*}-f^{*}(S)>Q^{-4}$.

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

######  Corollary 4.11.

Let $H=5\lceil\log_{2}Q\rceil$ 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}\geq(k+1)\delta$.

######  Proof 4.12.

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

We now have all necessary pieces to reduce Subset Product to Penalty Sum.

######  Theorem 4.13.

Penalty Sum is NP-hard.

######  Proof 4.14.

Given an instance $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$ of Subset Product,
let $Q:=M$, $H:=5\lceil\log_{2}Q\rceil$, 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^{\prime}$; $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^{\prime})$ is a
yes-instance of Subset Product. Suppose first that $(\\{v_{1},\dots
v_{m}\\},M,k^{\prime})$ is a yes-instance of Subset Product. Then there is
some $S\in\binom{[m]}{k}$ such that $\prod_{i\in S}v_{i}=M=Q$. Then by
Corollary 4.6, $f(S)\geq 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\binom{[m]}{k}$ such that
$f(S)\geq D$. By Lemma 4.4 and Corollary 4.11, we have that
$f^{*}(S)>f(S)-k\delta\geq D-k\delta>D^{*}-(k+1)\delta\geq D^{*}-Q^{-4}$. Thus
$D^{*}-f^{*}(S)\leq Q^{-4}$, which by Corollary 4.9 implies that $\prod_{i\in
S}v_{i}=Q$, and so $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$ 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=\lceil\max_{i\in[m]}(\ln v_{i})\rceil$ 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\leq A\leq\lceil\max_{i\in[m]}\log_{2}v_{i}\rceil$ and so we can find $A$ in
polynomial time by checking all integers in this range.

For each $i\in[m]$, $a_{i}=\lceil{A-\ln v_{i}}\rceil_{H}=r_{i}/2^{H}$, where
$r_{i}$ is the minimum integer such that $A-\ln v_{i}\leq r_{i}/2^{H}$. Thus,
we can compute $r_{i}$ by checking $e^{A-r_{i}/2^{H}}\leq v_{i}$ with
$r_{i}=2^{H}\cdot(A-\lceil{\ln v_{i}}\rceil_{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 $\mathcal{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
$\mathcal{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
$\mathcal{O}(\log_{2}v_{i})$ time to construct. $Q$ and $k$ are taken directly
from the instance $(\\{v_{1},\dots v_{m}\\},M,k^{\prime})$.

###  4.2 Hardness of Network-Diversity

Finally, reducing from unit-cost-NAP, we show the following main result.

######  Theorem 4.15.

Max-Network-PD is NP-hard even if the input network has level 1 and the
distance between the root and each leaf is 4.

######  Proof 4.16.

Because Penalty Sum is NP-hard, we know that unit-cost-NAP is NP-hard on trees
of height 2 [8]. 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.

$QM^{2}$$q/2$$q/(2-q)$$\ell$$v_{\ell}^{1}$$v_{\ell}^{2}$$\ell^{-}$$\ell^{*}$
Figure 2: Illustration of the leaf-gadget. Omitted edge-weights are 1 and
$q(\ell)$ is abbreviated to $q$.

We define a leaf-gadget which is illustrated in Figure 2. 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 which results from replacing each leaf of
$\mathcal{T}$ with the corresponding leaf-gadget. The leaves of $\mathcal{N}$
are $L^{\prime}:=\\{\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 that every $q(\ell)$ is expressible as
$c^{\prime}/d^{\prime}$ for some pair of integers $c,d$ such that
$d^{\prime}\leq d$. Let $M$ and $Q$ be large integers, such that $M$ is bigger
than $\text{PD}_{\mathcal{T}}(L)\geq|L|\geq 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^{\prime}(e)=kQ\cdot\omega(e)$. For each $\ell\in
L$ we set $\omega^{\prime}(v_{\ell}^{2}\ell^{*}):=Q\cdot M^{2}$ and
$\omega^{\prime}(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}}^{\prime}:=(\mathcal{N},\omega^{\prime},p,k,D^{\prime}:=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 in $\mathcal{N}$ is 4.

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

$\gamma^{p}_{Z}(e)=1-(1-\gamma^{p}_{Z}(\ell
v_{\ell}^{1}))(1-\gamma^{p}_{Z}(\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).$
(4)

"$\Rightarrow$": 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|\leq k$
and $\text{PD}_{\mathcal{T}}(S)\geq D$. Let
$S^{\prime}:=\\{\ell^{*}\mid\ell\in S\\}$ be a subset of $L^{\prime}$. Clearly
$|S^{\prime}|=|S|\leq k$. Because $\mathcal{T}$ does not contain reticulation
edges and $\gamma^{p}_{Z}(e)=q(\ell)$ with $e$ being the edge incoming at
$\ell$, we conclude that

$\displaystyle\text{Network-PD}_{\mathcal{N}}(S^{\prime})\geq
kQ\cdot\text{PD}_{\mathcal{T}}(S)+k\cdot\omega^{\prime}(v_{\ell}^{2}\ell^{*})\geq
kQ\cdot(D+M^{2})=D^{\prime}$

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

"$\Leftarrow$": Let $S^{\prime}$ be a solution of ${\mathcal{I}}^{\prime}$.
Let $S^{-}=S\cap\\{\ell^{-}\mid\ell\in L\\}$ and
$S^{*}=S\cap\\{\ell^{*}\mid\ell\in L\\}$. Towards a contradiction, assume
$S^{-}\neq\emptyset$. Then however, using $3<Q\cdot D$,

$\displaystyle\text{Network-PD}_{\mathcal{N}}(S^{\prime})$
$\displaystyle\leq\sum_{\ell^{-}\in
S^{-}}(\omega^{\prime}(v_{\ell}^{1}\ell^{-})+\omega^{\prime}(\ell
v_{\ell}^{1}))+|S^{*}|(QM^{2}+3)+\sum_{e\in E(\mathcal{T})}\omega^{\prime}(e)$
$\displaystyle\leq 2|S^{-}|+|S^{*}|(QM^{2}+3)+kQM$ $\displaystyle\leq
2+(k-1)(QM^{2}+3)+kQM$ $\displaystyle<kQM^{2}-QM^{2}+kQM+3k$
$\displaystyle<k(QM^{2}+3)<k(QM^{2}+QD)=D^{\prime}$

contradicts that $S^{\prime}$ is a solution. Therefore, we conclude that
$S^{\prime}\subseteq\\{\ell^{*}\mid\ell\in L\\}$ and $|S^{\prime}|=k$. Define
$S:=\\{\ell\mid\ell^{*}\in S^{\prime}\\}$. Subsequently, with (4) we conclude

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

It follows that
$\text{PD}_{\mathcal{T}}(S)\geq\frac{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^{\prime}_{S}(e)=(1-\prod_{\ell\in\operatorname{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^{\prime}|\leq k$ we conclude that $S$ is a solution of $\mathcal{I}$.
Thus, $\mathcal{I}$ is a yes-instance of unit-cost-NAP.

##  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. First of all, can Max-
Network-PD be solved in pseudo-polynomial time on level-1 networks? Secondly,
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? Finally, is Max-Network-PD W[1]-hard when the parameter is the number
of species $k$ to save plus the level of the network?

From a practical point-of-view however, the most important task is to assess
which variants of phylogenetic diversity on networks (see [16]) 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.

## References

  * Atkin and Bernstein [2004] A. O. L. Atkin and D. J. Bernstein.  Prime sieves using binary quadratic forms.  _Mathematics of Computation_ , 73:1023–1030, January 2004\.
  * Bordewich et al. [2022] Magnus Bordewich, Charles Semple, and Kristina Wicke.  On the Complexity of optimising variants of Phylogenetic Diversity on Phylogenetic Networks.  _Theoretical Computer Science_ , 917:66–80, 2022.
  * Dusart [1999] Pierre Dusart.  The kth prime is greater than k(ln k + ln ln k - 1) for k $\geq$ 2\.  _Mathematics of Computation_ , 68(225):411–415, 1999.  URL http://www.jstor.org/stable/2585122.
  * E. [1997] Moret B M E.  _The theory of computation_.  Addison-Wesley, 1997.
  * Faith [1992] Daniel P Faith.  Conservation evaluation and phylogenetic diversity.  _Biological conservation_ , 61(1):1–10, 1992\.
  * Garey and Johnson [1979] M. R. Garey and David S. Johnson.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  W. H. Freeman, 1979.  ISBN 0-7167-1044-7.
  * Huson et al. [2010] Daniel H Huson, Regula Rupp, and Celine Scornavacca.  _Phylogenetic networks: concepts, algorithms and applications_.  Cambridge University Press, 2010.
  * Komusiewicz and Schestag [2023] Christian Komusiewicz and Jannik Schestag.  A Multivariate Complexity Analysis of the Generalized Noah’s Ark Problem.  In _Cologne-Twente Workshop on Graphs and Combinatorial Optimization_ , pages 109–121. Springer, 2023.
  * Merz et al. [2023] Joseph J Merz, Phoebe Barnard, William E Rees, Dane Smith, Mat Maroni, Christopher J Rhodes, Julia H Dederer, Nandita Bajaj, Michael K Joy, Thomas Wiedmann, and Rory Sutherland.  World scientists’ warning: The behavioural crisis driving ecological overshoot.  _Science Progress_ , 106(3), 2023.  URL https://doi.org/10.1177/00368504231201372.
  * Minh et al. [2006] Bui Quang Minh, Steffen Klaere, and Arndt von Haeseler.  Phylogenetic Diversity within Seconds.  _Systematic Biology_ , 55(5):769–773, 10 2006\.  ISSN 1063-5157.  10.1080/10635150600981604.  URL https://doi.org/10.1080/10635150600981604.
  * Pardi and Goldman [2005] Fabio Pardi and Nick Goldman.  Species choice for comparative genomics: being greedy works.  _PLoS Genetics_ , 1(6):e71, 2005.  URL https://doi.org/10.1371/journal.pgen.0010071.
  * Ripple et al. [2017] William J. Ripple, Christopher Wolf, Thomas M. Newsome, Mauro Galetti, Mohammed Alamgir, Eileen Crist, Mahmoud I. Mahmoud, William F. Laurance, and 364 scientist signatories from 184 countries 15.  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.
  * Rosser [1941] Barkley Rosser.  Explicit bounds for some functions of prime numbers.  _American Journal of Mathematics_ , 63(1):211–232, 1941.  URL http://www.jstor.org/stable/2371291.
  * Steel [2005] Mike Steel.  Phylogenetic diversity and the greedy algorithm.  _Systematic Biology_ , 54(4):527–529, 2005.
  * Weitzman [1998] Martin L Weitzman.  The Noah’s ark problem.  _Econometrica_ , pages 1279–1298, 1998.
  * Wicke and Fischer [2018] Kristina Wicke and Mareike Fischer.  Phylogenetic diversity and biodiversity indices on phylogenetic networks.  _Mathematical Biosciences_ , 298:80–90, 2018.
  * Wicke et al. [2021] Kristina Wicke, Arne Mooers, and Mike Steel.  Formal links between feature diversity and phylogenetic diversity.  _Systematic Biology_ , 70(3):480–490, 2021.

##  Appendix 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
postitive 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
$\mathcal{O}(\log_{2}(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 $\mathcal{O}(\log_{2}(p)+\log_{2}(q))$ bits.

For rational numbers which are a multiple of a power of 2, (such as
$1/8=2^{-3}$, or $5/8=5\cdot 2^{-3}$), 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 $\texttt{101}\times 2^{\texttt{-11}}$.
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.

##  Appendix B Omitted Proofs

To prove Lemma 4.1, 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 $|C|=3$ for every $C\in\mathcal{C}$
Question: Is there a collection $\mathcal{C}^{\prime}\subseteq\mathcal{C}$
such that each element of $x$ appears in exactly one set of
$\mathcal{C}^{\prime}$?

######  Proof B.1 (Proof of Lemma 4.1).

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}^{\prime}:=\\{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^{\prime}}$, then we can define
$S:=\\{i\in[m]:C_{i}\in\mathcal{C}^{\prime}\\}$. Since every element of $X$
appears in exactly one $C_{i}\in\mathcal{C}^{\prime}$ and $|C_{i}|=3$ for all
$i\in[m]$, we have that $|\mathcal{C}^{\prime}|=|X|/3=n=k$, and $\prod_{i\in
S}v_{i}=p_{1},\cdot\dots\cdot 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\geq 6$, [13, 3] 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.

######  Proof B.2 (Proof of Lemma 4.8).

We first show that it is enough to consider the cases $Q^{\prime}=Q+1$ and
$Q^{\prime}=Q-1$. Fix an integer $Q\in\mathbb{N}_{+}$ with $Q\geq 2$. Consider
the function $h_{Q}:\mathbb{R}_{>0}\rightarrow\mathbb{R}$ given by

$h_{Q}(x)=\ln x-\ln Q+Q/x-1.$

So our aim is to show that $h_{Q}(Q^{\prime})\geq Q^{-4}$. Similar to the
proof of Lemma 4.2, 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^{\prime})\geq h_{Q}(Q-1)$ if
$Q^{\prime}\leq Q-1$ and $h_{Q}(Q^{\prime})\geq h_{Q}(Q+1)$ if $Q^{\prime}\geq
Q+1$. Since either $Q^{\prime}\leq Q-1$ or $Q^{\prime}\geq Q+1$ for any
integer $Q^{\prime}\neq 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}_{\geq 2}$: Let
$\lambda:\mathbb{R}_{>0}\rightarrow\mathbb{R}$ be the function given by

$\displaystyle\lambda(Q)$ $\displaystyle=$ $\displaystyle h_{Q}(Q-1)-Q^{-4}$
$\displaystyle=$ $\displaystyle\ln(Q-1)-\ln Q+Q/(Q-1)-1-Q^{-4}$
$\displaystyle=$ $\displaystyle\ln(Q-1)-\ln Q+1/(Q-1)-Q^{-4}.$

Then

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

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\geq 2$, and thus $h_{Q}(Q-1)>Q^{-4}$.

To show that $h_{Q}(Q+1)>Q^{-4}$ for all $Q\in\mathbb{N}_{\geq 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\geq 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:

$\displaystyle\ln\left(\frac{Q+1}{Q}\right)=\ln(1+\frac{1}{Q})=\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

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

Then

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

where the last two inequalities use $Q\geq 3$.