Friedrich-Schiller-Universität Jena, Germanyc.komusiewicz@uni-
jena.dehttps://orcid.org/0000-0003-0829-7032 Friedrich-Schiller-Universität
Jena, Germanyj.t.schestag@uni-jena.dehttps://orcid.org/0000-0001-7767-2970
Applied computing Computational biology Theory of computation Fixed parameter
tractability Christian Komusiewicz and Jannik Schestag

# Maximizing Phylogenetic Diversity under Ecological Constraints: A
Parameterized Complexity Study

Christian Komusiewicz  Jannik Schestag

###### Abstract

In the NP-hard Optimizing PD with Dependencies (PDD) problem, the input
consists of a phylogenetic tree $\mathcal{T}$ over a set of taxa $X$, a food-
web that describes the prey-predator relationships in $X$, and integers $k$
and $D$. The task is to find a set $S$ of $k$ species that is viable in the
food-web such that the subtree of $\mathcal{T}$ obtained by retaining only the
vertices of $S$ has total edge weight at least $D$. Herein, viable means that
for every predator taxon of $S$, the set $S$ contains at least one prey taxon.

We provide the first systematic analysis of PDD and its special case s-PDD
from a parameterized complexity perspective. For solution-size related
parameters, we show that PDD is FPT with respect to $D$ and with respect to
$k$ plus the height of the phylogenetic tree. Moreover, we consider structural
parameterizations of the food-web. For example, we show an FPT-algorithm for
the parameter that measures the vertex deletion distance to graphs where every
connected component is a complete graph. Finally, we show that s-PDD admits an
FPT-algorithm for the treewidth of the food-web. This disproves a conjecture
of Faller et al. [Annals of Combinatorics, 2011] who conjectured that s-PDD is
NP-hard even when the food-web is a tree.

###### keywords:

phylogenetic diversity; food-webs; structural parameterization; color-coding;
dynamic programming

inline,color=red!25!green!50] 15 pages excluding references, the front page
(authors, affiliation, keywords, abstract, etc.) and a brief appendix (of up
to 5 pages)

##  1 Introduction

Human activity has greatly accelerated the rate at which biological species go
extinct. The conservation of biological diversity is thus one of mankind’s
most urgent tasks. The inherently limited amount of resources that one may
devote to this task, however, necessitates decisions on which conservation
strategies to pursue. To support such decisions, one needs to incorporate
quantitative information on the possible impact and the success
likelihood,color=red!25!green!50] sounds like probabilities of conservation
strategies. In this context, one task is to compute an optimal conservation
strategy in light of this information.

To find a conservation strategy with the best positive impact, one would
ideally aim to maximize the functional,color=red!25!green!50] what is that?
diversity of the surviving taxa (species). However, measuring this diversity
is hard or impossible in many scenarios [17]. As a result, maximizing
phylogenetic diversity has become the standard, albeit imperfect, surrogate
for maximizing functional diversity [10, 12, 17]. Informally, phylogenetic
diversity measures the evolutionary distance of a set of taxa. In its most
simple form, this measurement is based on an edge-weighted phylogenetic tree
${\mathcal{T}}$ of the whole set of taxa $X$, and the phylogenetic diversity
of a subset of taxa $S$ is the sum of the weights of the edges of the subtree
of ${\mathcal{T}}$ obtained by retaining only the taxa of $S$. Assuming equal
protection costs for all taxa, the task is to find a set $S$ of at most $k$
taxa that achieves maximal phylogenetic diversity. This problem, called
Maximize Phylogenetic Diversity [8], can be solved very efficiently by a
greedy algorithm [8, 18, 22, 27].

Computing an optimal conservation strategy becomes much more difficult,
however, when the success likelihood,color=red!25!green!50] sounds like
probabilities of a strategy is included in the model. One way to achieve this
is to add concrete survival probabilities,color=red!25!green!50] Fine for me
here for protected taxa, leading in its most general form to the NP-hard
Generalized Noah’s Ark Problem [11, 15]. This problem formulation, however,
still has a central drawback: It ignores that the survival of some taxa may
also depend on the survival of other taxa. This aspect was first considered by
Moulton et al. [20] in the Optimizing PD with Dependencies (PDD) problem.
Here, the input additionally contains a directed acyclic graph $D$ with vertex
set $X$ where an arc $uv$ is present if the existence of taxa $u$ provides all
the necessary foundations for the existence of $B$. In other words, $D$ models
ecological dependencies between taxa. Now, a taxon $v$ may survive only if (i)
it does not depend on other taxa at all, that is, it has no incoming arcs, or
(ii) at least one taxon $u$ survives such that $D$ contains the arc $uv$. The
most-wide spread interpretation of such ecological dependency networks are
food-webs where the arc $uv$ means that taxon $v$ feeds on taxon $u$.111We
remark that previous works [20, 9] consider a reversed interpretation of the
arcs. We define the order such that a source of the network also corresponds
to a source of the ecosystem. A set of taxa $X$ where every vertex fulfills
(i) or (ii) is called _viable_. The task in PDD is to select a _viable_ set of
$k$ taxa that achieves a maximal phylogenetic diversity. In this work, we
study PDD from an algorithmic point of view.

Moulton et al. [20] showed that PDD can be solved by the greedy algorithm if
the objective of maximizing phylogenetic diversity agrees with the viability
constraint in a precise technical sense. Later, PDD was conjectured to be NP-
hard in [26]. This conjecture was confirmed by Faller et al. [9], who showed
that PDD is NP-hard even if the food-web $D$ is a tree. Further, Faller et al.
[9] considered s-PDD, the special case where the phylogenetic tree is
restricted to be a star, and showed that s-PDD is NP-hard even for food-webs
which have a bipartite graph as underlying graph. Finally, polynomial-time
algorithms were provided for very restricted special cases, for example for
PDD when the food-web is a _directed_ tree [9].

,color=red!25!green!50] T: Giulio Dalla Riva C: What do you mean exactly?

,color=red!30] Importance of food-webs [4]

,color=red!30] Why mention the following: “Famous book [elton]”?

##### Our contribution

As PDD is NP-hard even on very restricted instances [9], we turn to
parameterized complexity in order to overcome this intractability. In
particular, we aim to identify problem-specific parameters $\kappa$ such that
PDD can be solved in $f(k)\cdot|I|^{\mathcal{O}(1)}$
time,color=red!25!green!50] Define here and in Sec. 2.1? (these are called
FPT-algorithms) or to show that such algorithms are unlikely, by showing
W[1]-hardness for the parameter $\kappa$. Here, we consider the most natural
parameters related to the solution, such as the solution size $k$ and the
threshold of diversity $D$, and parameters that describe the structure of the
input food-web $D$. We formally consider the decision problem, where we ask
for the existence of a viable solution with diversity at least $D$, but our
algorithms actually solve the optimization problem as well.

Our most important results are the following; Table 1 gives an overview. In
Theorem 3.5, we prove that PDD is FPT when parameterized with the solution
size $k$ plus the height of the phylogenetic tree ${\mathcal{T}}$. This also
implies that PDD is FPT with respect to $D$, the diversity threshold. We also
consider the dual parameter $\overline{D}$, that is, the amount of diversity
that is lost from ${\mathcal{T}}$ and show that PDD is W[1]-hard with respect
to $\overline{D}$.

We then consider the structure of the food-web. In particular, we consider the
special case that each connected component of the food-web $D$ is a complete
digraph. This case is structurally equivalent to the case that each connected
component of $D$ is a star with one source vertex. Thus, this case describes a
particularly simple dependency structure, where taxa are either completely
independent or have a common source. We show that PDD is NP-hard in this
special case while s-PDD has an FPT-algorithm when parameterized by the vertex
deletion distance to this special case. Finally, we show that s-PDD is FPT
with respect to the treewidth of the food-web and therefore can be solved in
polynomial time if the food-web is a tree (Theorem 5.9). Our result disproves
a conjecture of Faller et al. [9, Conjecture 4.2] that PDD is NP-hard even
when the food-web is a tree.

Parameter | s-PDD | PDD
---|---|---
Budget $k$ | FPT | Thm. 3.2 | XP (FPT is _open_) | Obs. 3
Diversity $D$ | FPT | Thm. 4.1 | FPT | Thm. 4.1
Species-loss ${\overline{k}}$ | W[1]-hard, XP | Prop. 4.2, Obs. 3 | W[1]-hard, XP | Prop. 4.2, Obs. 3
Diversity-loss ${\overline{D}}$ | W[1]-hard, XP | Prop. 4.2, Obs. 3 | W[1]-hard, XP | Prop. 4.2, Obs. 3
D.t. Cluster | FPT | Thm. 5.1 | NP-h for 0 | Thm. 5.4
D.t. Co-Cluster | FPT | Thm. 5.7 | FPT | Thm. 5.7
Treewidth | FPT | Thm. 5.9 | NP-h for 1 | [9]

Table 1: An overview over the parameterized complexity results for PDD and
s-PDD.

##### Structure of the paper

In Section 2, we formally define Optimizing PD with Dependencies, give an
overview of previous results and our contribution, and prove some simple
initial results. In Section 3, we study s-PDD and PDD with respect to $k$, the
solution size. In Section 4, we show that PDD is FPT with respect to the
desired diversity but W[1]-hard for the acceptable loss of diversity. In
Section 5, we consider parameterization by structural parameters of the food-
web. Finally, in Section 6, we discuss future research ideas. Theorems,
lemmas, and observations marked with $(\star)$ are deferred to the appendix.

##  2 Preliminaries

###  2.1 Definitions

For a positive integer $a$, by $[a]$ we denote the set $\\{1,2,\dots,a\\}$,
and by $[a]_{0}$ the set $\\{0\\}\cup[a]$. We generalize functions $f:A\to B$,
where $B$ is a family of sets, to handle subsets $A^{\prime}\subseteq A$ of
the domain by defining $f(A^{\prime}):=\bigcup_{a\in A^{\prime}}f(a)$.

inline,color=red!25!green!50] neighbors, spanning tree, connected component

For any graph $G$, we write $V(G)$ and $E(G)$, respectively, to denote the set
of vertices and edges of $G$. We write $\\{u,v\\}$ for an undirected edge
between $u$ and $v$. For a directed edge from $u$ to $v$, we write $uv$ or
$(u,v)$ to increase readability. For a vertex set $V^{\prime}\subseteq V(G)$,
we let $G[V^{\prime}]:=(V^{\prime},\\{e\in E(G)\mid\text{both endpoints
of\leavevmode\nobreak\ $e$ are in $V(G)$}\\})$ denote the subgraph of $G$
induced by $V^{\prime}$. Moreover, with $G-V^{\prime}:=G[V\setminus
V^{\prime}]$ we denote the graph obtained from $G$ by removing $V^{\prime}$
and its incident edges.

##### Phylogenetic Trees and Phylogenetic Diversity.

A tree $T=(V,E)$ is a directed graph in which the _root_ is the only vertex
with an in-degree of zero, each other vertex has an in-degree of one. The root
is denoted with $\rho$. The _leaves_ of a tree are the vertices which have an
out-degree of zero. We refer to the non-leaf vertices of a tree as _internal
vertices_. A tree is a star if the root is the only internal vertex and all
other vertices are leafs. For a given set $X$, a _phylogenetic $X$-tree
${\mathcal{T}}=(V,E,{\omega})$_ is a tree $T=(V,E)$ with an _edge-weight_
function ${\omega}:E\to\mathbb{N}_{>0}$ and a bijective labeling of the leaves
with elements from $X$ where all non-leaves in $\mathcal{T}$ have out-degree
at least two. We write $\max_{\omega}$ to denote the biggest edge weight in
${\mathcal{T}}$. The set $X$ is a set of  _taxa_ (species). Because of the
bijective labeling, we interchangeably use the words taxon and leaf. In
biological applications, the set $X$ is a set of taxa, the internal vertices
of ${\mathcal{T}}$ correspond to biological ancestors of these taxa and
${\omega}(e)$ describes the phylogenetic distance between the endpoints of
$e$, as these endpoints correspond to distinct taxa, we may assume this
distance is greater than zero.,color=red!25!green!50] Probably add this
sentence to intro and remove here.

For a directed edge $uv\in E$, we say $u$ is the _parent_ of $v$ and $v$ is a
_child_ of $u$. If there is a directed path from $u$ to $v$ in ${\mathcal{T}}$
(including when $u=v$), we say that $u$ is an _ancestor_ of $v$ and $v$ is a
_descendant_ of $u$. The sets of ancestors and descendants of $v$ are denoted
by $\operatorname{anc}(v)$ and $\operatorname{desc}(v)$, respectively. The set
of descendants of $v$ which are in $X$ are _offspring_ $\operatorname{off}(v)$
of a vertex $v$. For an edge $e=uv\in E$, we denote
$\operatorname{off}(e)=\operatorname{off}(v)$.

For a tree $T=(V,E)$ and a vertex set $V^{\prime}\subseteq V$, the _spanning
tree of $V^{\prime}$_ is denoted by $T\langle V^{\prime}\rangle$. The
_subtree of $T$ rooted at $v$_ is
$T\langle\\{v\\}\cup\operatorname{off}(v)\rangle$ and denoted by $T_{v}$, for
some vertex $v\in V$. Given a set of taxa $A\subseteq X$, let
$E_{{\mathcal{T}}}(A)$ denote the set of edges in $e\in E$ with
$\operatorname{off}(e)\cap A\neq\emptyset$. The _phylogenetic diversity_
${PD_{{\mathcal{T}}}}(A)$ of $A$ is defined by

${PD_{{\mathcal{T}}}}(A):=\sum_{e\in E_{{\mathcal{T}}}(A)}{\omega}(e).$ (1)

In other words, the phylogenetic diversity ${PD_{{\mathcal{T}}}}(A)$ of a set
$A$ of taxa is the sum of the weights of edges which have offspring in $A$.

##### Food Webs.

For a given set of taxa $X$, a _food-web ${\mathcal{F}}=(X,E)$ on $X$_ is a
directed acyclic graph. If $xy$ is an edge of $E$ then $x$ is _prey_ of $y$
and $y$ is a _predator_ of $x$. The set of prey and predators of $x$ is
denoted with ${N_{<}(x)}$ and ${N_{>}(x)}$, respectively. A taxon $x$ without
prey is a _source_ and ${\operatorname{sources}({\mathcal{F}})}$ denotes the
set of sources in the food-web $\mathcal{F}$.

For a given taxon $x\in X$ we define $X_{\leq x}$ to be the set of taxa $X$
which can reach $x$ in $\mathcal{F}$. Analogously, $X_{\geq x}$ is the set of
taxa which $x$ can reach in $\mathcal{F}$.

For a given food-web $\mathcal{F}$ and a set $Z\subseteq X$ of taxa, a set of
taxa $A\subseteq Z$ is _$Z$ -viable_ if
${\operatorname{sources}({\mathcal{F}}[A])}\subseteq{\operatorname{sources}({\mathcal{F}}[Z])}$.
A set of taxa $A\subseteq X$ is _viable_ if $A$ is $X$-viable. In other words,
a set $A\subseteq Z$ is $Z$-viable or viable if each vertex with in-degree 0
in ${\mathcal{F}}[A]$ also has in-degree 0 in ${\mathcal{F}}[Z]$ or in
$\mathcal{F}$, respectively.

##### Problem Definitions and Parameterizations.

Formally, the main problem we regard in this paper is defined as follows.

> Optimizing PD with Dependencies (PDD)
>  Input: A phylogenetic $X$-tree ${\mathcal{T}}$, a foodweb ${\mathcal{F}}$
> on $X$, and integers $k$ and $D$. Question: Is there a viable set
> $S\subseteq X$ such that $|S|\leq k$, and ${PD_{{\mathcal{T}}}}(S)\geq D$?

,color=red!25!green!50] Probably add to intro.

Additionally in Optimizing PD in Vertex-Weighted Food-Webs (s-PDD) we consider
the special case of PDD in which the phylogenetic $X$-tree ${\mathcal{T}}$ is
a star.,color=red!25!green!50] Name is given by Faller et al.

Throughout the paper, we adopt the common convention that $n$ is the number of
taxa $|X|$ and we let $m$ denote the number of edges in the food-web
$|E({\mathcal{F}})|$. Observe that $\mathcal{T}$ has $\mathcal{O}(n)$ edges.

For an instance ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ of PDD, we
define ${\overline{D}}:={PD_{{\mathcal{T}}}}(X)-D=\sum_{e\in E}{\omega}(e)-D$.
Informally, ${\overline{D}}$ is the acceptable loss of diversity: If we save a
set of taxa $A\subseteq X$ with ${PD_{{\mathcal{T}}}}(A)\geq D$, then the
total amount of diversity we lose from ${\mathcal{T}}$ is at most
${\overline{D}}$. Similarly, we define ${\overline{k}}:=|X|-k$. That is,
$\overline{k}$ is the minimum number of species that need to become extinct.

inline,color=red!25!green!50] Also define structural parameters?

##### Parameterized Complexity.

Throughout this paper, we consider a number of parameterizations of PDD and
s-PDD. For a detailed introduction to parameterized complexity refer to the
standard monographs [5, 7]; we only give a brief overview here.

A parameterization of a problem $\Pi$ associates with each input instance
${\mathcal{I}}$ of $\Pi$ a specific _parameter_ $\kappa$. A parameterized
problem $\Pi$ is _fixed-parameter tractable_ (FPT) with respect to some
parameter $\kappa$ if there exists an algorithm solving every instance
$({\mathcal{I}},\kappa)$ of $\Pi$ in time
$f(\kappa)\cdot|{\mathcal{I}}|^{\mathcal{O}(1)}$. A parameterized problem
$\Pi$ is _slice-wise polynomial_ (XP) with respect to some parameter $\kappa$
if there exists an algorithm solving every instance $({\mathcal{I}},\kappa)$
of $\Pi$ in time $|{\mathcal{I}}|^{f(\kappa)}$. Here, in both cases, $f$ is
some computable function only depending on $\kappa$. Parameterized problems
that are _W[1] -hard_ are believed not to be FPT. We use the
$\mathcal{O}^{*}$-notation which omits factors polynomial in the input size.

##### Color Coding.

For an in-depth treatment of color coding, we refer the reader to [5, Sec. 5.2
and 5.6] and [1]. Here, we give some definitions which we use throughout the
paper.

For integers $n$ and $k$, an  _$(n,k)$ -perfect hash family $\mathcal{H}$_ is
a family of functions $f:[n]\to[k]$ such that for every subset $Z$ of $[n]$ of
size $k$, some $f\in\mathcal{H}$ exists which is injective when restricted to
$Z$. For any integers $n,k\geq 1$ an $(n,k)$-perfect hash family which
contains $e^{k}k^{\mathcal{O}(\log k)}\cdot\log n$ functions can be
constructed in time $e^{k}k^{\mathcal{O}(\log k)}\cdot n\log n$ [21, 5].

###  2.2 Preliminary observations

We start with some observations and reduction rules which we use throughout
the paper.

Let ${\mathcal{F}}$ be a food-web. A set $A\subseteq X$ is viable if and only
if there are edges $E_{A}\subseteq E({\mathcal{F}})$ such that every connected
component in the graph $(A,E_{A})$ is a tree with root in
${\operatorname{sources}({\mathcal{F}})}$.

###### Proof.

If $A$ is viable then ${\operatorname{sources}({\mathcal{F}}[A])}$ is a subset
of $\operatorname{sources}({\mathcal{F}})$. It follows that for each taxon
$x\in A$, either $x$ is a source in $\mathcal{F}$ or $A$ contains a prey $y$
of $x$. Conversely, if such a graph $(A,E_{A})$ exists then explicitly the
sources of ${\mathcal{F}}[A]$ are a subset of
$\operatorname{sources}({\mathcal{F}})$. ∎

Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be a yes-instance of
PDD. Then $k>n$ or a viable set $S\subseteq X$ with
${PD_{{\mathcal{T}}}}(S)\geq D$ exists which has size exactly $k$.

###### Proof.

Let $S$ be a solution for $\mathcal{I}$. If $S$ has a size of $k$, nothing
remains to show. Otherwise, observe that $S\cup\\{x\\}$ is viable and
${PD_{{\mathcal{T}}}}(S\cup\\{x\\})\geq{PD_{{\mathcal{T}}}}(S)$ for each taxon
$x\in({N_{>}(S)}\cup{\operatorname{sources}({\mathcal{F}})})\setminus S$.
Because $({N_{>}(S)}\cup{\operatorname{sources}({\mathcal{F}})})\setminus S$
is non-empty unless $S=X$, we conclude that $S\cup\\{x\\}$ is a solution and
iteratively, there is a solution of size $k$. ∎

[$\star$] Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an instance
of PDD. In $\mathcal{O}(|{\mathcal{I}}|^{2})$ time one can compute an
equivalent instance
${\mathcal{I}}^{\prime}:=({\mathcal{T}}^{\prime},{\mathcal{F}}^{\prime},k^{\prime},D^{\prime})$
of PDD with only one source in ${\mathcal{F}}^{\prime}$ and
$D^{\prime}\in\mathcal{O}(D)$.

######  Reduction Rule 1.

Let $R\subseteq X$ be the set of taxa which have a distance of at least $k$ to
every source. Then, set ${\mathcal{F}}^{\prime}:={\mathcal{F}}-R$ and
${\mathcal{T}}^{\prime}:={\mathcal{T}}-R$.

######  Lemma 2.1.

1 is correct and can be applied exhaustively in $\mathcal{O}(n+m)$ time.

######  Proof 2.2.

By definition, each viable set of taxa which has a size of $k$ is disjoint
from $R$. Therefore, the set $R$ is disjoint from every solution. The set $R$
can be found in $\mathcal{O}(n+m)$ time by breadth-first search. This is also
the total running time since one application of the rule is exhaustive.

######  Reduction Rule 2.

Apply 1 exhaustively. If $\max_{\omega}\geq D$ return yes.

After 1 has been applied exhaustively, for any taxon $x\in X$ there is a
viable set $S_{x}$ of size at most $k$ with $x\in S_{x}$. If edge $e$ has
weight at least $D$, then for each taxon $x$ which is an offspring of $e$, the
set $S_{x}$ is viable, has size at most $k$, and
${PD_{{\mathcal{T}}}}(S_{x})\geq{PD_{{\mathcal{T}}}}(\\{x\\})\geq D$. So,
$S_{x}$ is a solution.

######  Reduction Rule 3.

Given an instance ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ of PDD in
with $vw,uw\in E({\mathcal{F}})$ for each $u\in{N_{<}(v)}$. If $v$ is not a
source, then remove $vw$ from $E({\mathcal{F}})$.

######  Lemma 2.3.

3 is correct and can be applied exhaustively in $\mathcal{O}(n^{3})$ time.

######  Proof 2.4.

Correctness. If ${\mathcal{I}}^{\prime}$ is a yes-instance, then so is
${\mathcal{I}}$.

Conversely, let ${\mathcal{I}}$ be a yes-instance of PDD with solution $S$. If
$v\not\in S$, then $S$ is also a solution for instance
${\mathcal{I}}^{\prime}$. If $v\in S$ then because $S$ is viable in
${\mathcal{F}}$ and ${N_{<}(v)}=\\{u\\}$ we conclude $u\in S$. Consequently,
$S$ is also viable in ${\mathcal{F}}-vw$, as $w$ still could be fed by $u$ (if
$w\in S$).

Running time. For a tuple of taxa $v$ and $w$, we can check
${N_{<}(v)}\subseteq{N_{<}(w)}$ in $\mathcal{O}(n)$. Consequently, an
exhaustive application of 3 takes $\mathcal{O}(n^{3})$ time.

##  3 The solution size $k$

In this section, we consider parameterization by the size of the solution $k$.
First, we observe that PDD is XP when parameterized by $k$ and $\overline{k}$.
In Section 3.1 we show that s-PDD is FPT with respect to $k$. We generalize
this result in Section 3.2 by showing that PDD is FPT when parameterized by
$k+\operatorname{height}_{{\mathcal{T}}}$. Recall that ${\overline{k}}:=n-k$.

PDD can be solved in $\mathcal{O}(n^{k+2})$ and
$\mathcal{O}(n^{{\overline{k}}+2})$ time.

######  Proof 3.1.

Algorithm. Iterate over the sets $S$ of $X$ of size $k$. Return yes if there
is a viable set $S$ with ${PD_{{\mathcal{T}}}}(S)\geq D$. Return no if there
is no such set.

Correctness and Running time. The correctness of the algorithm follows from
Section 2.2. Checking whether a set $S$ is viable and has diversity of at
least $D$ can be done $\mathcal{O}(n^{2})$ time. The claim follows because
there are $\binom{n}{k}=\binom{n}{n-k}=\binom{n}{{\overline{k}}}$ subsets of
$X$ of size $k$.

###  3.1 s-PDD with $k$

We show that s-PDD is FPT when parameterized by the size of the solution $k$.

######  Theorem 3.2.

s-PDD can be solved in $\mathcal{O}(2^{3.03k+o(k)}\cdot nm\cdot\log n)$ time.

In order to prove this theorem, we color the taxa and require that a solution
should contain at most one taxon of each color. Formally, the auxiliary
problem which we consider is defined as follows. In $k$-colored Optimizing PD
in Vertex-Weighted Food-Webs ($k$-c-s-PDD), alongside the usual input
$({\mathcal{T}},{\mathcal{F}},k,D)$ of s-PDD, we are given a coloring
$c:X\to[k]$ which assigns each taxon a _color_ $c(x)\in[k]$. We ask whether
there is a viable set $S\subseteq X$ of taxa such that
${PD_{{\mathcal{T}}}}(S)\geq D$, and $c(S)$ is _colorful_. A set $c(S)$ is
colorful if $c$ is injective on $S$. Observe that each colorful set $S$ holds
$|S|\leq k$. We continue to show how to solve $k$-c-s-PDD before we apply
tools of the color-coding toolbox to extend this result to the uncolored
version.

######  Lemma 3.3.

$k$-c-s-PDD can be solved in $\mathcal{O}(3^{k}\cdot n\cdot m)$ time.

######  Proof 3.4.

Table definition. Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D,c)$ be
an instance of $k$-c-s-PDD and by Section 2.2 we assume that $\star\in X$ is
the only source in $\mathcal{F}$.

Given $x\in X$, a set of colors $C\subseteq[k]$, and a set of taxa
$X^{\prime}\subseteq X$: A set $S\subseteq X^{\prime}\subseteq X$ is
_$(C,X^{\prime})$ -feasible_ if  a) $c(S)=C$,  b) $c(S)$is colorful, and  c)
$S$is $X^{\prime}$-viable.

We define a dynamic programming algorithm with tables $\operatorname{DP}$ and
$\operatorname{DP}^{\prime}$. For $x\in X$, $C\subseteq[k]$ we want entry
$\operatorname{DP}[x,C]$ to store the maximum ${PD_{{\mathcal{T}}}}(S)$ of
$(C,X_{\geq x})$-feasible sets $S$. Recall $X_{\geq x}$ is the set of taxa
which $x$ can reach in ${\mathcal{F}}$. If no $(C,X_{\geq x})$-feasible set
$S\subseteq X^{\prime}$ exists, we want $\operatorname{DP}[x,C]$ to store
$-\infty$. (Or a big negative constant.)

In other words, in $\operatorname{DP}[x,C]$ we store the biggest phylogenetic
diversity of a set $S$ which is $X_{\geq x}$-viable and $c$ bijectively maps
$S$ to $C$.

For any taxon $x$, let $y_{1},\dots,y_{q}$ be an arbitrary but fixed order of
${N_{>}(x)}$. In the auxiliary table $\operatorname{DP}^{\prime}$, we want
entry $\operatorname{DP}^{\prime}[x,p,C]$ for $p\in[q]$, and $C\subseteq[k]$
to store the maximum ${PD_{{\mathcal{T}}}}(S)$ of $(C,X^{\prime})$-feasible
sets $S\subseteq X^{\prime}$, where $X^{\prime}=\\{x\\}\cup X_{\geq
y_{1}}\cup\dots\cup X_{\geq y_{p}}$. If no $(C,X^{\prime})$-feasible set
$S\subseteq X^{\prime}$ exists, we want $\operatorname{DP}^{\prime}[x,p,C]$ to
store $-\infty$.

Algorithm. As a basic case for each $x\in X$ and $p\in[|{N_{>}(x)}|]$ let
$\operatorname{DP}[x,\emptyset]$ and $\operatorname{DP}[x,p,\emptyset]$ store
0 and let $\operatorname{DP}[x,C]$ store $-\infty$ if $C$ is non-empty and
$c(x)\not\in C$. For each $x\in X$ with ${N_{>}(x)}=\emptyset$, we store
${\omega}(\rho x)$ in $\operatorname{DP}[x,\\{\hat{c}(x)\\}]$.

Fix a taxon $x\in X$. For every $Z\subseteq C\setminus\\{c(x)\\}$, we set
$\operatorname{DP}^{\prime}[x,1,\\{c(x)\\}\cup
Z]:=\operatorname{DP}[y_{1},Z]$. To compute further values, once
$\operatorname{DP}^{\prime}[x,p,Z]$ for each $p\in[q-1]$, and every
$Z\subsetneq C$ is computed, for $Z\subseteq C\setminus\\{c(x)\\}$ we use the
recurrence

$\operatorname{DP}^{\prime}[x,p+1,\\{c(x)\\}\cup Z]:=\max_{Z^{\prime}\subseteq
Z}\operatorname{DP}^{\prime}[x,p,\\{c(x)\\}\cup Z\setminus
Z^{\prime}]+\operatorname{DP}[y_{p+1},Z^{\prime}].$ (2)

Finally, we set $\operatorname{DP}[x,C]:=\operatorname{DP}^{\prime}[x,q,C]$
for every $C\subseteq[k]$.

We return yes if $\operatorname{DP}[\star,C]$ stores 1 for some
$C\subseteq[k]$. Otherwise, we return no.

Correctness. The basic cases are correct.

The tables are computed first for taxa further away from the source and with
an increasing size of $C$. Assume that for a fixed taxon $x$ with predators
$y_{1},\dots,y_{q}$ and a fixed $p\in[q]$, the entries
$\operatorname{DP}[x^{\prime},Z]$ and
$\operatorname{DP}^{\prime}[x,p^{\prime},Z]$ for each
$x^{\prime}\in{N_{>}(x)}$, for each $p^{\prime}\in[p]$, and every
$Z\subseteq[k]$ store the desired value. Fix a set $C\subseteq[k]$ with
$c(x)\in C$. We show that if $\operatorname{DP}^{\prime}[x,p+1,C]$ stores $d$
then there is a $(C,X^{\prime})$-feasible set $S\subseteq X^{\prime}\cup
X_{\geq y_{p+1}}$ for $X^{\prime}:=\\{x\\}\cup X_{\geq y_{1}}\cup\dots\cup
X_{\geq y_{p}}$ with ${PD_{{\mathcal{T}}}}(S)=d$. Afterward, we show that if
$S\subseteq X^{\prime}\cup X_{\geq y_{p+1}}$ with ${PD_{{\mathcal{T}}}}(S)=d$
is a $(C,X^{\prime})$-feasible set then $\operatorname{DP}^{\prime}[x,p+1,C]$
stores at least $d$.

If $\operatorname{DP}^{\prime}[x,p,C]=d>0$ then by Recurrence (2), there is a
set $Z\subseteq C\setminus\\{c(x)\\}$ such that
$\operatorname{DP}^{\prime}[x,p,C\setminus Z]=d_{x}$ and
$\operatorname{DP}[y_{p+1},Z]=d_{y}$ with $d=d_{x}+d_{y}$. Therefore, there is
a $(C\setminus Z,X^{\prime})$-feasible set $S_{x}\subseteq X^{\prime}$ with
${PD_{{\mathcal{T}}}}(S_{x})=d_{x}$ and a $(Z,X_{\geq y_{p+1}})$-feasible set
$S_{y}\subseteq X_{\geq y_{p+1}}$ with ${PD_{{\mathcal{T}}}}(S_{y})=d_{y}$.
Define $S:=S_{x}\cup S_{y}$ and observe that ${PD_{{\mathcal{T}}}}(S)=d$. It
remains to show that $S$ is a $(C,X^{\prime}\cup X_{\geq y_{p+1}})$-feasible
set. First, observe that because $C\setminus Z$ and $Z$ are disjoint, we
conclude that $c(S)$ is colorful. Then, $c(S)=c(S_{x})\cup c(S_{y})=C\setminus
Z\cup Z=C$ where the first equation holds because $c(S)$ is colorful. The taxa
$x$ and $y_{p+1}$ are the only sources in ${\mathcal{F}}[X_{\geq x}]$ and
${\mathcal{F}}[X_{\geq y_{p+1}}]$, respectively. Therefore, $x$ is in $S_{x}$
and $y_{p+1}$ is in $S_{y}$ unless $S_{y}$ is empty. If $S_{y}=\emptyset$ then
$S=S_{x}$ and $S$ is $X^{\prime}\cup X_{\geq y_{p+1}}$-viable because $S$ is
$X^{\prime}$-viable. Otherwise, if $S_{y}$ is non-empty then because $S_{y}$
is $X_{\geq y_{p+1}}$-viable, we conclude
${\operatorname{sources}({\mathcal{F}}[S_{y}])}=\\{y_{p+1}\\}$. As $x\in S$
and $y_{p+1}\in{N_{>}(x)}$ we conclude
${\operatorname{sources}({\mathcal{F}}[S])}=\\{x\\}$ and so $S$ is
$X^{\prime}\cup X_{\geq y_{p+1}}$-viable. Therefore, $S$ is a
$(C,X^{\prime}\cup X_{\geq y_{p+1}})$-feasible set.

Conversely, let $S\subseteq X^{\prime}\cup X_{\geq y_{p+1}}$ be a non-empty
$(C,X^{\prime}\cup X_{\geq y_{p+1}})$-feasible set with
${PD_{{\mathcal{T}}}}(S)=d$. Observe that $X^{\prime}$ and $X_{\geq y_{p+1}}$
are not necessarily disjoint. We define $S_{y}$ to be the set of taxa of
$X_{\geq y_{p+1}}$ which are connected to $y_{p+1}$ in ${\mathcal{F}}[X_{\geq
y_{p+1}}]$. Further, define $Z:=c(S_{y})$ and define $S_{x}:=S\setminus
S_{y}$. As $c(S)$ is colorful especially $c(S_{x})$ and $c(S_{y})$ are
colorful. Thus, $S_{y}$ is a $(Z,X_{\geq y_{p+1}})$-feasible time. Further,
$c(S_{x})=C\setminus c(S_{y})=C\setminus Z$. As
${\operatorname{sources}({\mathcal{F}}[S])}={\operatorname{sources}({\mathcal{F}}[X^{\prime}\cup
X_{\geq y_{p+1}}])}=\\{x\\}$, we conclude $x\in S$. Because $\mathcal{F}$ is a
DAG, $x$ is not in $X_{\geq y_{p+1}}$ and so $x$ is in $S_{x}$. Each vertex of
$S$ which can reach $y_{p+1}$ in ${\mathcal{F}}[S]$ is in $F_{\geq y_{p+1}}$
and subsequently in $S_{y}$. Consequently, because $S$ is $X^{\prime}\cup
X_{\geq y_{p+1}}$-viable we conclude
${\operatorname{sources}({\mathcal{F}}[S_{x}])}=\\{x\\}$. Thus, $S_{x}$ is
$(C\setminus Z,X^{\prime})$-feasible. So,
$\operatorname{DP}[y_{p+1},Z]={PD_{{\mathcal{T}}}}(S_{x})$ and
$\operatorname{DP}^{\prime}[x,p,C\setminus Z]={PD_{{\mathcal{T}}}}(S_{y})$.
Hence, $\operatorname{DP}^{\prime}[x,p+1,C]$ stores at least
${PD_{{\mathcal{T}}}}(S)$.

Running time. The basic cases can be checked in $\mathcal{O}(k)$ time. As each
$c\in[k]$ in Recurrence (2) can either be in $Z^{\prime}$, in $\\{c(x)\\}\cup
Z\setminus Z^{\prime}$ or in $[k]\setminus(\\{c(x)\\}\cup Z)$, all entries of
the tables can be computed in $\mathcal{O}(3^{k}\cdot n\cdot m)$ time.

For the following proof we construct a perfect hash family $\mathcal{H}$ which
is defined in Section 2.1 Central for proving Theorem 3.2 is to define and
solve an instance of $k$-c-s-PDD for each function in $\mathcal{H}$. The proof
uses standard color-coding and therefore is deferred to the appendix.

Unluckily, we were unable to prove whether PDD is FPT with respect to
$k$.,color=red!25!green!50] Probably pimp this sentence to not stand there so
lonely.

###  3.2 PDD with $k+\operatorname{height}_{{\mathcal{T}}}$

In this subsection, we generalize the result of the previous subsection and we
show that PDD is FPT when parameterized with the size of the solution $k$ plus
$\operatorname{height}_{{\mathcal{T}}}$, the height of the phylogenetic
tree.,color=red!30] Note: Height is here unrelated to branch lengths This
algorithm uses the techniques of color-coding, data reduction by reduction
rules, and the enumeration of trees.

######  Theorem 3.5.

PDD can be solved in $\mathcal{O}^{*}(K^{K}\cdot 2^{4.47K+o(K)})$ time where
$K:=k\cdot\operatorname{height}_{{\mathcal{T}}}$.

We define a _pattern-tree_ ${\mathcal{T}}_{P}=(V_{P},E_{P},c_{P})$ to be a
tree $(V_{P},E_{P})$ with a vertex-coloring
$c_{P}:V_{P}\to[k\cdot\operatorname{height}_{{\mathcal{T}}}]$. Recall that
${\mathcal{T}}\langle Y\rangle$ is the spanning tree of the vertices in $Y$.

To show the result above, we use a subroutine for solving the following
problem. In Optimizing PD with Pattern-Dependencies (PDD-pattern), we are
given alongside the usual input $({\mathcal{T}},{\mathcal{F}},k,D)$ of PDD a
pattern-tree ${\mathcal{T}}_{P}=(V_{P},E_{P},c_{P})$, and a vertex-coloring
$c:V({\mathcal{T}})\to[k\cdot\operatorname{height}_{{\mathcal{T}}}]$. We ask
whether there is a viable set $S\subseteq X$ of taxa such that $S$ has a size
of at most $k$, $c({\mathcal{T}}\langle S\cup\\{\rho\\}\rangle)$ is colorful,
and ${\mathcal{T}}\langle S\cup\\{\rho\\}\rangle$ and ${\mathcal{T}}_{P}$ are
_color-equal_. That is, there is an edge $uv$ of ${\mathcal{T}}\langle
S\cup\\{\rho\\}\rangle$ with $c(u)=c_{u}$ and $c(v)=c_{v}$ if and only if
there is an edge $u^{\prime}v^{\prime}$ of ${\mathcal{T}}_{P}$ with
$c(u^{\prime})=c_{u}$ and $c(v^{\prime})=c_{v}$. Informally, given a pattern-
tree and want that it matches in colors with the spanning tree induced by the
root and a solution.

With these reduction rules, we can reduce the phylogenetic tree of a given
instance of PDD-pattern to only be a star and then solve PDD-pattern by
applying Theorem 3.2.

Next we present reduction rules with which we can reduce the phylogenetic tree
in an instance of PDD-pattern to be a star which subsequently can be solved
with Theorem 3.2. Afterward, we show how to apply this knowledge to compute a
solution for PDD.

######  Reduction Rule 4.

Let $uv$ be an edge of ${\mathcal{T}}$. If there is no edge
$u^{\prime}v^{\prime}\in E_{P}$ with $c_{P}(u^{\prime})=c(u)$ and
$c_{P}(v^{\prime})=c(v)$, then set
${\mathcal{T}}^{\prime}:={\mathcal{T}}-\operatorname{desc}(v)$ and
${\mathcal{F}}^{\prime}:={\mathcal{F}}-\operatorname{off}(v)$.

######  Reduction Rule 5.

Let $u^{\prime}v^{\prime}$ be an edge of ${\mathcal{T}}_{P}$. For each vertex
$u\in V({\mathcal{T}})$ with $c(u)=c_{P}(u^{\prime})$ such that $u$ has no
child $v$ with $c(v)=c_{P}(v^{\prime})$, set
${\mathcal{T}}^{\prime}:={\mathcal{T}}-\operatorname{desc}(v)$ and
${\mathcal{F}}^{\prime}:={\mathcal{F}}-\operatorname{off}(v)$.

######  Reduction Rule 6.

If $\mathcal{T}$ has leaf set $L$ and $\mathcal{F}$ has vertex set $X$ with
$L\subsetneq X$, then compute the set $R\subseteq X$ of vertices $v$ which on
every path from $v$ to a source of $\mathcal{F}$ contain a vertex of
$X\setminus L$, set ${\mathcal{T}}^{\prime}:={\mathcal{T}}-R$ and
${\mathcal{F}}^{\prime}:={\mathcal{F}}-R$.

######  Reduction Rule 7.

Apply Reduction Rules 4, 5, and 6 exhaustively. Let $\rho$ be the root of
$\mathcal{T}$ and let $\rho_{P}$ be the root of ${\mathcal{T}}_{P}$. Let
$v^{\prime}$ be a grand-child of $\rho_{P}$ and let $u^{\prime}$ be the parent
of $v^{\prime}$.  1. For each vertex $u$ of ${\mathcal{T}}$ with
$c(u)=c_{P}(u^{\prime})$ add edges $\rho v$ to ${\mathcal{T}}$ for every child
$v$ of $u$.  2. Set the weight of $\rho v$ to be ${\omega}(uv)$ if $c(v)\neq
c_{P}(v^{\prime})$ or ${\omega}(uv)+{\omega}(\rho u)$ if
$c(v)=c_{P}(v^{\prime})$.  3. Add edges $\rho_{P}w^{\prime}$ to
${\mathcal{T}}_{P}$ for every child $w^{\prime}$ of $u^{\prime}$.  4. Set
${\mathcal{T}}_{P}^{\prime}:={\mathcal{T}}_{P}-u^{\prime}$ and
${\mathcal{T}}^{\prime}:={\mathcal{T}}-u$.

$u^{\prime}$$v^{\prime}$(1)

6131245242311222

(2)

61345211424242

Figure 1: A example for 7. (1) An instance of PDD-pattern (2) The instance
after an application of 7 to the marked vertices. In both instances, the
pattern-tree is on the left and the phylogenetic tree is on the right.

Figure 1 depicts an application of an application of 7.

######  Lemma 3.6 ($\star$).

Reduction rules 4, 5, 6, and 7 are correct and can be applied exhaustively in
$\mathcal{O}(n^{2}\cdot(n+m))$ time.

######  Lemma 3.7.

PDD-pattern can be solved in $\mathcal{O}(2^{3.03k+o(k)}\cdot
n^{2}\cdot(n+m))$ time.

######  Proof 3.8.

Algorithm. Let an instance
${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D,{\mathcal{T}}_{P}=(V_{P},E_{P},c_{P}),c)$
of PDD-pattern be given. If there is a vertex $v\in V_{P}$ and
$c_{P}(v)\not\in c(V({\mathcal{T}}))$ then return no. If $c(\rho)\neq
c_{P}(\rho_{P})$ where $\rho$ and $\rho_{P}$ are the roots of $\mathcal{T}$
and ${\mathcal{T}}_{P}$ respectively, return no.

Apply 7 exhaustively. Then, both ${\mathcal{T}}_{P}$ and $\mathcal{T}$ are
stars. Return yes if and only if $({\mathcal{T}},{\mathcal{F}},k,D)$ is a yes-
instance of s-PDD.

Correctness. If ${\mathcal{T}}_{P}$ contains a vertex $v$ with
$c_{P}(v)\not\in c(V({\mathcal{T}}))$, or if $c(\rho)\neq c_{P}(\rho_{P})$,
then $\mathcal{I}$ is a no-instance. Then, the correctness follows by Lemma
3.6 and Lemma 3.3.

Running time. 7 can be applied exhaustively in $\mathcal{O}(n^{2}\cdot(n+m))$
time. With the application of Lemma 3.3, the overall running time is
$\mathcal{O}(3^{k\cdot\operatorname{height}_{{\mathcal{T}}}}\cdot n\cdot m)$.

To prove Theorem 3.5 we reduce from PDD to PDD-pattern and apply Lemma 3.7.
For this, we use the fact that there are $n^{n-2}$ labeled directed trees with
$n$ vertices [25] which can be enumerated in $\mathcal{O}(n^{n-2})$ time [2].
To solve instance $\mathcal{I}$ of PDD, we will check each of these trees as a
pattern tree for a given coloring of the phylogenetic tree. These colorings
will be defined with a perfect hash family as defined in Section 2.1. Recall
that $K=k\cdot\operatorname{height}_{{\mathcal{T}}}$.

######  Proof 3.9 (Proof of Theorem 3.5).

Algorithm. Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an
instance of PDD. Let the vertices of $\mathcal{T}$ be
$v_{1},\dots,v_{|V({\mathcal{T}})|}$. Iterate over
$i\in[\min\\{K,|V({\mathcal{T}})|\\}]$. Compute a
$(|V({\mathcal{T}})|,i)$-perfect hash family $\mathcal{H}_{i}$. Compute the
set $\mathcal{P}_{i}$ of labeled directed trees with $i$ vertices.

For every ${\mathcal{T}}_{P}=(V_{P},E_{P},c_{P})\in\mathcal{P}_{i}$ precede as
follows. Assume that the labels of ${\mathcal{T}}_{P}$ are in $[i]$. For every
$f\in\mathcal{H}_{i}$, let $c_{f}$ be a coloring such that $c_{f}(v_{j})=f(j)$
for each $v_{j}\in V({\mathcal{T}})$.

For every $f\in\mathcal{H}_{i}$, solve instance
${\mathcal{I}}_{{\mathcal{T}}_{P},f}:=({\mathcal{T}},{\mathcal{F}},k,D,{\mathcal{T}}_{P},c_{f})$
of PDD-pattern using Lemma 3.7. Return yes if and only if
${\mathcal{I}}_{{\mathcal{T}}_{P},f}$ is a yes-instance for some
$f\in\mathcal{H}_{i}$ and some ${\mathcal{T}}_{P}\in\mathcal{P}_{i}$.

Correctness. Any solution of an instance ${\mathcal{I}}_{{\mathcal{T}}_{P},f}$
of PDD-pattern clearly is a solution for ${\mathcal{I}}$.

Conversely, we show that if $S$ is a solution for $\mathcal{I}$, then there
are ${\mathcal{T}}_{P}$ and $f$ such that
${\mathcal{I}}_{{\mathcal{T}}_{P},f}$ is a yes-instance of PDD-pattern. So let
$S$ be a viable set of taxa with $|S|\leq k$ and ${PD_{{\mathcal{T}}}}(S)\geq
D$. Let $V^{*}\subseteq V({\mathcal{T}})$ be the set of vertices $v$ that have
offspring in $S$. It follows
$|V^{*}|\leq\operatorname{height}_{{\mathcal{T}}}\cdot|S|\leq K$. Then, there
is a hash function $f\in\mathcal{H}_{V^{*}}$ mapping $V^{*}$ bijectively to
$[|V^{*}|]$. Consequently, $\mathcal{P}_{|V^{*}|}$ contains a tree
${\mathcal{T}}_{P}$ which is isomorphic to ${\mathcal{T}}[V^{*}]$ with labels
$c_{f}$. Hence, ${\mathcal{I}}_{{\mathcal{T}}_{P},f}$ is a yes-instance of
PDD-pattern.

Running Time. For a fixed $i\in[K]$, the set $\mathcal{H}_{i}$ contains
$e^{i}i^{\mathcal{O}(\log i)}\cdot\log n$ hash functions and the set
$\mathcal{P}_{i}$ contains $\mathcal{O}(i^{i-2})$ labeled trees. Both sets can
be computed in $\mathcal{O}(i^{i-2}\cdot n\log n)$ time.

Each instance ${\mathcal{I}}_{{\mathcal{T}}_{P},f}$ of PDD-pattern is
constructed in $\mathcal{O}(n)$ time and can be solved in
$\mathcal{O}(2^{3.03k+o(k)}\cdot n^{3}\cdot m)$ time. Thus, the overall
running time is $\mathcal{O}(K\cdot e^{K}K^{K-2+\mathcal{O}(\log K)}\cdot
2^{3.03k+o(k)}\cdot n^{3}m\log n)$, which summarizes to
$\mathcal{O}(K^{K}\cdot 2^{3.03k+1.44K+o(K)}\cdot n^{3}m\log n)$.

##  4 Parameterization by desired diversity and accepted diversity loss

In this section, we first consider parameterization with the diversity
threshold $D$. For this parameter, we present an FPT algorithm for PDD.
Afterward, we show that s-PDD is intractable with respect to $\overline{D}$,
the acceptable loss of phylogenetic diversity. As the edge-weights are
integers, we conclude that we can return yes if $k\geq D$ or if the height of
the phylogenetic tree $\mathcal{T}$ is at least $D$, after 1 has been applied
exhaustively. Otherwise,
$k+\operatorname{height}_{{\mathcal{T}}}\in\mathcal{O}(D)$ and thus the FPT
algorithm for $k+\operatorname{height}_{{\mathcal{T}}}$ (Theorem 3.5) directly
gives an FPT algorithm for PDD in that case.

Here, we present another algorithm with a faster running time. To obtain this
algorithm, we subdivide edges of the phylogenetic tree according to their edge
weights. We then use color coding on the vertices of the subdivided tree. Let
us remark that this technique is closely related to an algorithm of Jones and
Schestag [14] for another hard problem related to diversity maximization.

######  Theorem 4.1 ($\star$).

PDD can be solved in $\mathcal{O}(2^{3.03(D+k)+o(D)}\cdot nm+n^{2})$ time.

In some instances, the diversity threshold $D$ may be very large. Then,
however, the acceptable loss of diversity $\overline{D}$ could be relatively
small. Recall ${\overline{D}}$ is defined as ${PD_{{\mathcal{T}}}}(X)-D$.
Encouraged by this observation, recently, several problems on maximizing
phylogenetic diversity have been studied with respect to the acceptable
diversity loss [13, 14]. In this section, we show that, unfortunately, s-PDD
is already ${W[1]}$-hard with respect to ${\overline{D}}$ even if edge-weights
are at most two.

To show this result, we reduce from Red-Blue Non-Blocker. In Red-Blue Non-
Blocker, the input is an undirected bipartite graph $G$ with vertex
bipartition $V=V_{r}\cup V_{b}$ and an integer $k$. The question is whether
there is a set $S\subseteq V_{r}$ of size at least $k$ such that the
neighborhood of $V_{r}\setminus S$ is $V_{b}$. Red-Blue Non-Blocker is
W[1]-hard when parameterized by the size of the solution $k$ [6].

######  Proposition 4.2.

s-PDD is ${W[1]}$-hard with respect to ${\overline{D}}$, even if
$\max_{\omega}=2$.

######  Proof 4.3.

Reduction. Let ${\mathcal{I}}:=(G=(V=V_{r}\cup V_{b},E),k)$ be an instance of
Red-Blue Non-Blocker. We construct an instance
${\mathcal{I}}^{\prime}=({\mathcal{T}},{\mathcal{F}},k^{\prime},D)$ of s-PDD
as follows. Let $\mathcal{T}$ be a star with root $\rho\not\in V$ and leaves
$V$. In $\mathcal{T}$, an edge $e=(\rho,u)$ has weight 1 if $u\in V_{r}$ and
otherwise ${\omega}(e)=2$, if $u\in V_{b}$. Define a food-web $\mathcal{F}$
with vertices $V$ and for each edge $\\{u,v\\}\in E$, and every tuple of
vertices $u\in V_{b}$, $v\in V_{r}$, add an edge $(u,v)$ to $\mathcal{F}$.
Finally, set $k^{\prime}:=|V|-k$ and $D:=2\cdot|V_{b}|+|V_{r}|-k$, or
equivalently ${\overline{k}}={\overline{D}}=k$.

Correctness. The reduction can be computed in polynomial time. We show that if
$\mathcal{I}$ is a yes-instance of Red-Blue Non-Blocker then
${\mathcal{I}}^{\prime}$ is a yes-instance of PDD. Afterward, we show the
converse.

Assume that ${\mathcal{I}}$ is a yes-instance of Red-Blue Non-Blocker.
Therefore, there is a set $S\subseteq V_{r}$ of size at least $k$ such that
$N_{G}(V_{r}\setminus S)=V_{b}$. (We assume $|S|=k$ as $N_{G}(V_{r}\setminus
S)=V_{b}$ still holds if we shrink $S$.) We define $S^{\prime}:=V\setminus S$
and show that $S^{\prime}$ is a solution for ${\mathcal{I}}^{\prime}$. The
size of $S^{\prime}$ is $|V\setminus S|=|V|-|S|=k^{\prime}$. Further,
${PD_{{\mathcal{T}}}}(S)=2\cdot|V_{b}|+|V_{r}\setminus
S|=2\cdot|V_{b}|+|V_{r}|-k=D$. By definition, the vertices in $V_{r}$ are
sources. Further, because $S$ is a solution for $\mathcal{I}$, each vertex of
$V_{b}$ has a neighbor in $V_{r}\setminus S$. So, $S^{\prime}$ is viable and
${\mathcal{I}}^{\prime}$ is a yes-instance of s-PDD.

Conversely, let $S^{\prime}\subseteq V$ be a solution for instance
${\mathcal{I}}^{\prime}$ of s-PDD. Without loss of generality, $S^{\prime}$
contains $r$ vertices from $V_{r}$ and $b$ vertices of $V_{b}$. Consequently,
$|V|-k\geq|S^{\prime}|=b+r$ and
$2\cdot|V_{b}|+|V_{r}|-k=D\leq{PD_{{\mathcal{T}}}}(S^{\prime})=2b+r$. We
conclude $r\leq|V|-k-b$ and so $2b\geq 2\cdot|V_{b}|+|V_{r}|-k-r\geq
2\cdot|V_{b}|+|V_{r}|-k-(|V|-k-b)=|V_{b}|+b$. Therefore, $b=|V_{b}|$ and
$V_{b}\subseteq S^{\prime}$. Further, $r=|V_{r}|-k$. We define
$S:=V_{r}\setminus S^{\prime}$ and conclude $|S|=|V_{r}|-r=k$. Because
$S^{\prime}$ is viable, each vertex in $V_{b}$ has a neighbor in
$S^{\prime}\setminus V_{b}$. Therefore, $S$ is a solution for the yes-instance
$\mathcal{I}$ of Red-Blue Non-Blocker.

##  5 Structural parameters of the food-web

In this section, we study how the structure of the food-web affects the
complexity of s-PDD and PDD. In the first subsection, we have an in-depth look
into the parameterization with respect to the distance of the food-web to a
cluster graph, denoted $\operatorname{cvd}$. We show that PDD is NP-hard even
if the food-web is a cluster graph but s-PDD is FPT when parameterized by
$\operatorname{cvd}$. Afterward, we show that PDD is FPT with respect to the
distance to co-cluster and s-PDD is FPT with respect to the treewith of the
food-web, donoted by ${\operatorname{{tw}}_{{\mathcal{F}}}}$.

###  5.1 Distance to cluster

In this subsection, we consider the special case that given an instance of PDD
or s-PDD, we need to remove few vertices from the undirected underlying graph
of the food-web $\mathcal{F}$ to receive a cluster graph. Here, a graph is a
cluster graph if every connected component is a clique. Because $\mathcal{F}$
is acyclic, we have the following: Every clique in $\mathcal{F}$ has exactly
one vertex $v_{0}\in V(C)$ such that $v_{0}\in{N_{<}(v)}$ for each $v\in
V(C)\setminus\\{v_{0}\\}$. After applying 3 exhaustively to a cluster graph,
each connected component of the food-web is an out-star.

In Theorem 5.1, we show that s-PDD is FPT with respect to the distance to
cluster. Herein, for a graph $G=(V,E)$ the _distance to cluster
$\operatorname{cvd}(G)$_ is the smallest number $d$ such that there exists a
set $Y\subseteq V$ of size at most $d$ such that $G-Y$ is a cluster graph.
,color=red!30] Does it also work with parameter distance to out-stars? Does it
also work with distance to “every component has a dominating source”?
Afterward, we show that PDD however is NP-hard on cluster graphs.

######  Theorem 5.1.

s-PDD can be solved in $\mathcal{O}(6^{d}\cdot n^{2}\cdot m\cdot k^{2})$ time,
when we are given a set $Y\subseteq X$ of size $d$ such that ${\mathcal{F}}-Y$
is a cluster graph.

To prove this theorem, we first show how to solve the case where we want to
save all taxa in $Y$. We then show the theorem by reducing the general case to
this special case. This can be done as follows: We iterate over the
$\mathcal{O}(2^{d})$ subsets of $Y$. For each each subset $Z\subseteq Y$,
compute whether there is a solution $S$ for $\mathcal{I}$ with $S\cap Y=Z$.

######  Lemma 5.2.

Given an instance ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ of s-PDD
and a set $Y\subseteq X$ of size $d$ such that ${\mathcal{F}}-Y$ is a cluster
graph, we can compute whether there is a viable set $S\cup Y$ with $|S\cup
Y|\leq k$ and ${PD_{{\mathcal{T}}}}(S\cup Y)\geq D$ in $\mathcal{O}(3^{d}\cdot
n\cdot k^{2})$ time.

######  Proof 5.3.

We provide a dynamic programming algorithm. Let $C_{1},\dots,C_{c}$ be the
connected components of ${\mathcal{F}}-Y$ and let
$x_{1}^{(i)},\dots,x_{|C_{i}|}^{(i)}$ be an order of $C_{i}$ such that
$(x_{j_{1}}^{(i)},x_{j_{2}}^{(i)})\in E({\mathcal{F}})$ for $j_{1}<j_{2}$.

Table definition. A set $S\subseteq X\setminus Y$ of taxa is _$(\ell,Z)$
-feasible_, if $|S|\leq\ell$ and $S\cup Z$ is viable. The dynamic programming
algorithm has tables $\operatorname{DP}$ and $\operatorname{DP}_{i}$ for each
$i\in[c]$. The entry $\operatorname{DP}[i,\ell,Z]$ for $i\in[c]$,
$j\in[|C_{i}|]$, $\ell\in[k]_{0}$, $Z\subseteq Y$, and $b\in\\{0,1\\}$ stores
the largest phylogenetic diversity ${PD_{{\mathcal{T}}}}(S)$ of an
$(\ell,Z)$-feasible set $S\subseteq C_{1}\cup\dots\cup C_{i}$ and $-\infty$ if
no such set $S$ exists.

The table entries $\operatorname{DP}_{i}[j,b,\ell,Z]$ additionally have a
dimension $b$ with $b\in\\{0,1\\}$. For $b=0$, an entry
$\operatorname{DP}_{i}[j,b,\ell,Z]$ with $b\in\\{0,1\\}$ stores the largest
phylogenetic diversity ${PD_{{\mathcal{T}}}}(S)$ of an $(\ell,Z)$-feasible set
$S\subseteq\\{x_{1}^{(i)},\dots,x_{j}^{(i)}\\}$. For $b=1$, additionally some
vertex $v_{j^{\prime}}^{(i)}$ with $j^{\prime}<j$ needs to be contained in
$S$.

Algorithm. Iterate over the edges of ${\mathcal{F}}$. For each edge $uv\in
E({\mathcal{F}})$ with $u,v\in Y$, remove all edges incoming at $v$, including
$uv$, from $E({\mathcal{F}})$. After this removal, $v$ is a new source.

We initialize the base cases of $\operatorname{DP}_{i}$ by setting
$\operatorname{DP}_{i}[j,0,0,Z]:=0$ for each $i\in[c]$, each $j\in[|C_{i}|]$,
and every $Z\subseteq{\operatorname{sources}({\mathcal{F}})}$. Moreover,
$\operatorname{DP}_{i}[1,b,\ell,Z]:={\omega}(\rho v_{1}^{(i)})$ if $\ell\geq
1$ and
$Z\subseteq{N_{>}(v_{1}^{(i)})}\cup{\operatorname{sources}({\mathcal{F}})}$;
and $\operatorname{DP}_{i}[1,b,\ell,Z]:=-\infty$, otherwise.

To compute further values for $j\in[|C_{i}|-1]$, $b\in\\{0,1\\}$, and
$\ell\in[k]$ we use the recurrences

$\operatorname{DP}_{i}[j+1,b,\ell,Z]=\max\\{\operatorname{DP}_{i}[j,b,\ell,Z],\operatorname{DP}_{i}[j,b^{\prime},\ell-1,Z\setminus{N_{>}(v_{j+1}^{{(i)}})}]+{\omega}(\rho
v_{j+1}^{{(i)}})\\},$ (3)

where $b^{\prime}=0$ if there is an edge from a vertex in $Y$ to
$x_{j+1}^{(i)}$ and otherwise $b^{\prime}=1$.

Finally, we set
$\operatorname{DP}[1,\ell,Z]:=\operatorname{DP}_{1}[|C_{1}|,0,\ell,Z]$ and
compute further values with

$\operatorname{DP}[i+1,\ell,Z]=\max_{Z^{\prime}\subseteq
Z,\ell^{\prime}\in[\ell]_{0}}\operatorname{DP}[i,\ell^{\prime},Z^{\prime}]+\operatorname{DP}_{i+1}[|C_{i+1}|,0,\ell-\ell^{\prime},Z\setminus
Z^{\prime}].$ (4)

There is a viable set $S\cup Y$ with $|S\cup Y|\leq k$ and
${PD_{{\mathcal{T}}}}(S\cup Y)\geq D$ if and only if
$\operatorname{DP}[c,k-|Y|,Z]\geq D-{PD_{{\mathcal{T}}}}(Y)$.

Correctness. Assume that $\operatorname{DP}$ stores the intended values. Then,
if $\operatorname{DP}[c,k-|Y|,Z]\geq D-{PD_{{\mathcal{T}}}}(Y)$, there is an
$(\ell,Z)$-feasible set $S\subseteq X\setminus Y$. First, this implies that
$S\cup Y$ is viable, Moreover, since $S$ has size at most $k-|Y|$, we obtain
$|S\cup Y|=k$. Finally, because $\mathcal{T}$ is a star,
${PD_{{\mathcal{T}}}}(S)\geq D-{PD_{{\mathcal{T}}}}(Y)$ implies
${PD_{{\mathcal{T}}}}(S\cup Y)\geq D$. The converse direction can be shown
analogously.

It remains to show that $\operatorname{DP}$ and $\operatorname{DP}_{i}$ store
the right values. The basic cases are correct. Towards the correctness of
Recurrence (3), as an induction hypothesis, assume that
$\operatorname{DP}_{i}[j,b,\ell,Z]$ stores the desired value for a fixed
$j\in[|C_{i}|-1]$, each $i\in[c]$, $b\in\\{0,1\\}$, $\ell\in[k]_{0}$ and every
$Z\subseteq Y$. Let $\operatorname{DP}_{i}[j+1,b,\ell,Z]$ store $d$. We show
that there is an $(\ell,Z)$-feasible set
$S\subseteq\\{x_{1}^{(i)},\dots,x_{j+1}^{(i)}\\}$. By Recurrence (3),
$\operatorname{DP}_{i}[j,b,\ell,Z]$ stores $d$ or
$\operatorname{DP}_{i}[j,1,\ell-1,Z\setminus{N_{>}(v_{j+1}^{{(i)}})}]$ stores
$d-{\omega}(\rho v_{j+1}^{{(i)}})$. If $\operatorname{DP}_{i}[j,b,\ell,Z]$
stores $d$ then there is an $(\ell,Z)$-feasible set
$S\subseteq\\{x_{1}^{(i)},\dots,x_{j}^{(i)}\\}\subseteq\\{x_{1}^{(i)},\dots,x_{j+1}^{(i)}\\}$.
If $\operatorname{DP}_{i}[j,1,\ell-1,Z\setminus{N_{>}(v_{j+1}^{{(i)}})}]$
stores $d-{\omega}(\rho v_{j+1}^{{(i)}})$ then there is an
$(\ell-1,Z\setminus{N_{>}(v_{j+1}^{{(i)}})})$-feasible set
$S\subseteq\\{x_{1}^{(i)},\dots,x_{j}^{(i)}\\}$ containing $x_{1}^{(i)}$ or
$x_{j^{\prime}}^{(i)}\in{N_{>}(Y)}$. Consequently, also
$S\cup\\{x_{j+1}^{(i)}\\}$ is $(\ell,Z)$-feasible.

Now, let $S\subseteq\\{x_{1}^{(i)},\dots,x_{j+1}^{(i)}\\}$ be an
$(\ell,Z)$-feasible set. We show that $\operatorname{DP}_{i}[j+1,b,\ell,Z]$
stores at least ${PD_{{\mathcal{T}}}}(S)$. If
$S\subseteq\\{x_{1}^{(i)},\dots,x_{j}^{(i)}\\}$ then we know from the
induction hypothesis that $\operatorname{DP}_{i}[j,b,\ell,Z]$ stores
${PD_{{\mathcal{T}}}}(S)$ and then also $\operatorname{DP}_{i}[j+1,b,\ell,Z]$
stores ${PD_{{\mathcal{T}}}}(S)$. If $x_{j+1}^{(i)}\in S$, then $S$ contains
$x_{1}^{(i)}$ or some $x_{j^{\prime}}^{(i)}\in{N_{>}(Y)}$. Define
$S^{\prime}:=S\setminus\\{x_{j+1}^{(i)}\\}$. Then, $|S^{\prime}|=\ell-1$ and
$S^{\prime}\cup(Z\setminus{N_{>}(x_{j+1}^{(i)})})$ is viable because $S$ is
$(\ell,Z)$-feasible. Consequently,
$\operatorname{DP}_{i}[j,1,\ell-1,Z\setminus{N_{>}(x_{j+1}^{(i)})}]\geq{PD_{{\mathcal{T}}}}(S^{\prime})={PD_{{\mathcal{T}}}}(S)-{\omega}(\rho
x_{j+1}^{(i)})$. Therefore,
$\operatorname{DP}_{i}[j+1,b,\ell,Z]\geq{PD_{{\mathcal{T}}}}(S)$.

Now, we focus on the correctness of Recurrence (4). Let
$\operatorname{DP}[i+1,\ell,Z]$ store $d$. We show that there is an
$(\ell,Z)$-feasible set $S\subseteq C_{1}\cup\dots\cup C_{i+1}$ with
${PD_{{\mathcal{T}}}}(S)=d$. Because $\operatorname{DP}[i+1,\ell,Z]$ stores
$d$, by Recurrence (4), there are $Z^{\prime}\subseteq Z$ and
$\ell^{\prime}\in[\ell]_{0}$ such that
$\operatorname{DP}[i,\ell^{\prime},Z^{\prime}]=d_{1}$,
$\operatorname{DP}_{i+1}[|C_{i+1}|,0,\ell-\ell^{\prime},Z\setminus
Z^{\prime}]=d_{2}$ and $d_{1}+d_{2}=d$. By the induction hypothesis, there is
an $(\ell^{\prime},Z^{\prime})$-feasible set $S_{1}\subseteq
C_{1}\cup\dots\cup C_{i}$ and an $(\ell-\ell^{\prime},Z\setminus
Z^{\prime})$-feasible set $S_{2}\subseteq C_{i+1}$ such that
${PD_{{\mathcal{T}}}}(S_{1})=d_{1}$ and ${PD_{{\mathcal{T}}}}(S_{2})=d_{2}$.
Then, $S:=S_{1}\cup S_{2}$ holds
$|S|\leq|S_{1}|+|S_{2}|\leq\ell^{\prime}+(\ell-\ell^{\prime})=\ell$. Further,
because $Y$ has no outgoing edges
$Z^{\prime}\subseteq{N_{>}(S_{1})}\cup{\operatorname{sources}({\mathcal{F}})}$
and $Z\setminus
Z^{\prime}\subseteq{N_{>}(S_{2})}\cup{\operatorname{sources}({\mathcal{F}})}$.
Therefore, $Z\subseteq{N_{>}(S)}\cup{\operatorname{sources}({\mathcal{F}})}$
and $S\cup Z$ is viable. We conclude that $S$ is the desired set.

Let there be an $(\ell,Z)$-feasible set $S\subseteq C_{1}\cup\dots\cup
C_{i+1}$ with ${PD_{{\mathcal{T}}}}(S)=d$. We show that
$\operatorname{DP}[i+1,\ell,Z]$ stores at least $d$. Define
$S_{1}:=S\cap(C_{1}\cup\dots\cup C_{i})$ and $Z^{\prime}:={N_{>}(S_{1})}\cap
Z$. We conclude that $S_{1}\cap Z^{\prime}$ is viable. Then, $S_{1}$ is
$(\ell^{\prime},Z^{\prime})$-feasible, where $\ell^{\prime}:=|S_{1}|$. Define
$S_{2}:=S\cap C_{i+1}=S\setminus S_{1}$. Because $S\cup Z$ is viable and $Z$
does not have outgoing edges, we know that
$Z\subseteq{N_{>}(S)}\cup{\operatorname{sources}({\mathcal{F}})}$. So,
$Z\setminus
Z^{\prime}\subseteq{N_{>}(S_{2})}\cup{\operatorname{sources}({\mathcal{F}})}$
and because $|S_{2}|=|S|-|S_{1}|=\ell-\ell^{\prime}$ we conclude that $S_{2}$
is $(\ell-\ell^{\prime},Z\setminus Z^{\prime})$-feasible. Consequently,
$\operatorname{DP}[i,\ell^{\prime},Z^{\prime}]\geq{PD_{{\mathcal{T}}}}(S_{1})$
and $\operatorname{DP}_{i+1}[|C_{i+1}|,\ell-\ell^{\prime},Z\setminus
Z^{\prime}]\geq{PD_{{\mathcal{T}}}}(S_{2})$. Hence,
$\operatorname{DP}[i+1,\ell,Z]\geq{PD_{{\mathcal{T}}}}(S_{1})+{PD_{{\mathcal{T}}}}(S_{2})={PD_{{\mathcal{T}}}}(S)$
because $\mathcal{T}$ is a star.

Running time. The tables $\operatorname{DP}$ and $\operatorname{DP}_{i}$ for
$i\in[c]$ have $\mathcal{O}(2^{d}\cdot n\cdot k)$ entries in total. Whether
one of the basic cases applies can be checked in linear time. We can compute
the set $Z\setminus{N_{>}(x)}$ for any given $Z\subseteq Y$ and $x\in X$ in
$\mathcal{O}(d^{2})$ time. Therefore, the $\mathcal{O}(2^{d}\cdot n\cdot k)$
times we need to apply Recurrence (5) consume $\mathcal{O}(2^{d}d^{2}\cdot
n\cdot k)$ time in total. In Recurrence (6), each $x\in Y$ can be in
$Z^{\prime}$, in $Z\setminus Z^{\prime}$ or in $Y\setminus Z$ so that we can
compute all the table entries of $\operatorname{DP}$ in
$\mathcal{O}(3^{d}\cdot n\cdot k^{2})$ which is also the overall running
time.,color=red!25!green!50] Use subset convolutions?

Next, we show that, in contrast to s-PDD, PDD is NP-hard even when the food-
web is restricted to be a cluster graph. We obtain this hardness by a
reduction from Vertex Cover on cubic graphs. In cubic graphs, the degree of
each vertex is _exactly_ three. In Vertex Cover we are given an undirected
graph $G=(V,E)$ and an integer $k$ and ask whether a set $C\subseteq V$ of
size at most $k$ exists such that $u\in C$ or $v\in C$ for each $\\{u,v\\}\in
E$. The set $C$ is called a _vertex cover_. Vertex Cover remains NP-hard on
cubic graphs [19].

######  Theorem 5.4.

PDD is NP-hard even if the food-web is a cluster graph.

######  Proof 5.5.

Reduction. Let $(G,k)$ be an instance of Vertex Cover, where $G=(V,E)$ is
cubic. We define an instance
${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k^{\prime},D)$ of PDD as follows.
Let ${\mathcal{T}}$ have a root $\rho$. For each vertex $v\in V$, we add a
child $v$ of $\rho$. For each edge $e=\\{u,v\\}\in E$, we add a child $e$ of
$\rho$ and two children $[u,e]$ and $[v,e]$ of $e$. Let $N$ be a big integer.
We set the weight of $\rho e$ to $N-1$ for each edge $e$ of $E$. All other
edges of $\mathcal{T}$ have weight 1. Additionally, for each edge
$e=\\{u,v\\}\in E$ we add edges $(u,[u,e])$ and $(v,[v,e])$ to $\mathcal{F}$.
Finally, we set $k^{\prime}:=|E|+k$ and $D:=N\cdot|E|+k$.

Correctness. Instance $\mathcal{I}$ of PDD is constructed in polynomial time.
The sources of $\mathcal{F}$ are $V$. Let $e_{1}$, $e_{2}$, and $e_{3}$ be the
edges incident with $v\in V(G)$. Each connected component in $\mathcal{F}$
contains four vertices, $v$, and $[v,e_{i}]$ for $i\in\\{1,2,3\\}$.

We show that $(G,k)$ is a yes-instance of Vertex Cover if and only if
$\mathcal{I}$ is a yes-instance of PDD. Let $C\subseteq V$ be a vertex cover
of $G$ of size at most $k$. If necessary, add vertices to $C$ until $|C|=k$.
For each edge $e\in E$, let $v_{e}$ be an endpoint of $e$ that is contained in
$C$. Note that $v_{e}$ exists since $C$ is a vertex cover. We show that
$S:=C\cup\\{[v_{e},e]\mid e\in E\\}$ is a solution for $\mathcal{I}$: The size
of $S$ is $|C|+|E|=k+|E|$. By definition, for each taxon $[v_{e},e]$ we have
$v_{e}\in C\subseteq S$, so $S$ is viable. Further, as $S$ contains the taxon
$[v_{e},e]$ for each edge $e\in E$, we conclude that
${PD_{{\mathcal{T}}}}(S)\geq N\cdot|E|+{PD_{{\mathcal{T}}}}(C)=N\cdot|E|+k=D$.
Therefore, $S$ is a solution of $\mathcal{I}$.

Let $S$ be a solution of instance $\mathcal{I}$ of PDD. Define $C:=S\cap V(G)$
and define $S^{\prime}:=S\setminus C$. Because ${PD_{{\mathcal{T}}}}(S)>D$, we
conclude that for each $e\in E$ at least one vertex $[u,e]$ with $u\in e$ is
contained in $S^{\prime}$. Thus, $|S^{\prime}|\geq|E|$ and we conclude that
$|C|\leq k$. Because $S$ is viable we conclude that $u\in C$ for each
$[u,e]\in S^{\prime}$. Therefore, $C$ is a vertex cover of size at most $k$ of
$G$.

###  5.2 Distance to co-cluster

In this section, we show that PDD is FPT with respect to the distance to co-
cluster of the food-web. A graph is a co-cluster graph if its complement graph
is a cluster graph. Herein, the complement graph is the graph obtained by
replacing edges with non-edges and vice versa. In other words, a graph is a
co-cluster graph if its vertex set can be partitioned into independent sets
such that each pair of vertices from different independent sets is adjacent.

We define an auxiliary problem Hitting Set with Tree-Profits in which we are
given a universe $\mathcal{U}$, a family of sets $\mathcal{W}$ over
$\mathcal{U}$, a $\mathcal{U}$-tree $\mathcal{T}$, and integers $k$ and $D$.
We ask whether there is a set $S\subseteq\mathcal{U}$ of size at most $k$ such
that ${PD_{{\mathcal{T}}}}(S)\geq D$ and $S\cap W\neq\emptyset$ for each
$W\in\mathcal{W}$. Solutions to this problem can be found with a dynamic
programming algorithm over the tree, similar to the idea in [23]. The proof is
therefore in the appendix.

######  Lemma 5.6 ($\star$).

Hitting Set with Tree-Profits can be solved in
$\mathcal{O}(3^{|\mathcal{W}|}\cdot n)$ time.

In the following we reduce from PDD to Hitting Set with Tree-Profits. Herein,
we select a subset of the modulator $Y$ to survive. Additionally, we select
the first taxon $x_{i}$ which survives in $X\setminus Y$. Because
${\mathcal{F}}-Y$ is a co-cluster graph, $x_{i}$ is in a specific independent
set $I\subseteq X$ and any taxon $X\setminus(I\cup Y)$ feed on $x_{i}$. Then,
by selecting taxon $x_{j}\in X\setminus(I\cup Y)$, any other taxon in
$X\setminus Y$ has some prey. Subsequently, a solution is found by Lemma 5.6.

######  Theorem 5.7.

PDD can be solved in $\mathcal{O}(6^{d}\cdot n^{3})$ time, when we are given a
set $Y\subseteq X$ of size $d$ such that ${\mathcal{F}}-Y$ is a co-cluster
graph.

######  Proof 5.8.

Algorithm. Given an instance ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$
of PDD. Let $x_{1},\dots,x_{n}$ be a topological ordering of $X$ which is
induced by $\mathcal{F}$. Iterate over the subsets $Z$ of $Y$. Let $P_{Z}$ be
the sources of $\mathcal{F}$ in $X\setminus Y$ and let $Q_{Z}$ be
${N_{>}(Z)}\setminus Y$, the taxa in $X\setminus Y$ which are being fed by
$Z$. Further, define $R_{Z}:=P_{Z}\cup Q_{Z}\subseteq X\setminus Y$. Iterate
over the vertices $x_{i}\in R_{Z}$. Let $x_{i}$ be from the independent set
$I$ of the co-cluster graph ${\mathcal{F}}-Y$. Iterate over the vertices
$x_{j}\in X\setminus(Y\cup I)$.

For each set $Z$, and taxa $x_{i}$, $x_{j}$, with Lemma 5.6 we compute the
optimal solution for the case that $Z$ is the set of taxa of $Y$ that survive
while all taxa of $Y\setminus Z$ go extinct, $x_{i}$ is the first taxon in
$X\setminus Y$, and $x_{j}$ the first taxon in $X\setminus(Y\cup I)$ to
survive. (The special cases that only taxa from $I\cup Y$ or only from $Y$
survive are omitted here.)

We define an instance ${\mathcal{I}}_{Z,i,j}$ of Hitting Set with Tree-Profits
as follows. Let the universe $\mathcal{U}_{i,j}$ be the union of
$\\{x_{i+1},\dots,x_{j-1}\\}\cap I$ and $\\{x_{j+1},\dots,x_{n}\\}\setminus
Y$. For each taxon $x\in Z$ compute ${N_{<}(x)}$. If
$x\not\in{\operatorname{sources}({\mathcal{F}})}$ and
${N_{<}(x)}\cap(Z\cup\\{x_{i},x_{j}\\})=\emptyset$, then add
${N_{<}(x)}\setminus Y$ to the family of sets $\mathcal{W}_{Z,i,j}$. Contract
edges $e\in E({\mathcal{T}})$ with
$\operatorname{off}(e)\cap(Z\cup\\{x_{i},x_{j}\\})\neq\emptyset$ to receive
${\mathcal{T}}_{Z,i,j}$. Finally, we define $k^{\prime}:=k-|Z|-2$ and
$D^{\prime}:=D-{PD_{{\mathcal{T}}}}(Z\cup\\{x_{i},x_{j}\\})$.

Solve ${\mathcal{I}}_{Z,i,j}$. If ${\mathcal{I}}_{Z,i,j}$ is a yes-instance
then return yes. Otherwise, continue with the iteration. If
${\mathcal{I}}_{Z,i,j}$ is a no-instance for every $Z\subseteq Y$, and each
$i,j\in[n]$, then return no.

Correctness. We show that if the algorithm returns yes, then ${\mathcal{I}}$
is a yes-instance of PDD. Afterward, we show the converse.

Let the algorithm return yes. Then, there is a set $Z\subseteq Y$, and there
are taxa $x_{i}\in X\setminus Y$ and $x_{j}\in X\setminus(Y\cup V(I))$
${\mathcal{I}}_{Z,i,j}$ is a yes-instance of Hitting Set with Tree-Profits.
Here, $I$ is the independent set such that $v\in V(I)$ Consequently, there is
a set $S\subseteq\mathcal{U}_{i,j}$ of size at most $k-|Z|-2$ such that
${PD_{{\mathcal{T}}_{Z,i,j}}}(S)\geq
D^{\prime}=D-{PD_{{\mathcal{T}}}}(Z\cup\\{x_{i},x_{j}\\})$ and $S\cap
W\neq\emptyset$ for each $W\in\mathcal{W}_{Z,i,j}$. We show that $S^{*}:=S\cup
Z\cup\\{x_{i},x_{j}\\}$ is a solution for instance $\mathcal{I}$ of PDD.
Clearly, $|S^{*}|=|S|+|Z|+2\leq k$ and
${PD_{{\mathcal{T}}}}(S^{*})={PD_{{\mathcal{T}}_{Z,i,j}}}(S)+{PD_{{\mathcal{T}}}}(Z\cup\\{x_{i},x_{j}\\})\geq
D$ as ${\mathcal{T}}_{Z,i,j}$ is the $Z\cup\\{x_{i},x_{j}\\}$-contraction of
${\mathcal{T}}$. Further, by definition
$x_{i}\in({\operatorname{sources}({\mathcal{F}})}\cup{N_{>}(Z)})\setminus Y$.
Because ${\mathcal{F}}-Y$ is a co-cluster graph and $x_{j}$ is not in $I$, the
independent set in which $x_{i}$ is, we conclude that
$x_{j}\in{N_{>}(x_{i})}$. As $S\cap W\neq\emptyset$ for each
$W\in\mathcal{W}_{Z,i,j}$, each taxon $x\in Z$ holds
${N_{<}(x)}\cap(Z\cup\\{x_{i},x_{j}\\})=\emptyset$ or ${N_{<}(x)}\cap
S\neq\emptyset$ so that ${N_{<}(x)}\cap S^{*}\neq\emptyset$. Therefore,
$S^{*}$ is viable and indeed a solution for $\mathcal{I}$.

Assume now that $S$ is a solution for instance $\mathcal{I}$ of PDD. We define
$Z:=S\cap Y$ and let $x_{i}$ and $x_{j}$ be the taxa in $S\setminus Y$,
respectively $S\setminus(Y\cup I)$, with the smallest index. As before, $I$ is
the independent set of $x_{i}$. We show that instance ${\mathcal{I}}_{Z,i,j}$
of Hitting Set with Tree-Profits has solution
$S^{*}:=S\setminus(Z\cup\\{x_{i},x_{j}\\})$. Clearly, $|S^{*}|=|S|-|Z|-2\leq
k^{\prime}$ and by the definition of ${\mathcal{T}}_{Z,i,j}$ we also conclude
${PD_{{\mathcal{T}}_{Z,i,j}}}(S^{*})\geq D^{\prime}$. Let
$M\in\mathcal{W}_{Z,i,j}$. By definition, there is a taxon $z\in Z$ with
$M={N_{<}(z)}\setminus Y$, and
$z\not\in{\operatorname{sources}({\mathcal{F}})}$, and
${N_{<}(z)}\cap(Z\cup\\{x_{i},x_{j}\\})=\emptyset$. Consequently, as $S$ is
viable, there is a taxon $x\in S\cap{N_{<}(z)}$ so that $S\cap
M\neq\emptyset$. Hence, $S^{*}$ is a solution of instance
${\mathcal{I}}_{Z,i,j}$ of Hitting Set with Tree-Profits.

Running time. For a given $Z\subseteq Y$, we can compute the topological order
$x_{1},\dots,x_{n}$ and the set $R_{Y}$ in $\mathcal{O}(n^{2})$ time. The
iterations over $x_{i}$ and $x_{j}$ take $\mathcal{O}(n^{2})$ time. Observe,
$|\mathcal{W}_{Z,i,j}|\leq|Z|$. By Lemma 5.6 checking whether
${\mathcal{I}}_{Z,i,j}$ is a yes-instance takes $\mathcal{O}(3^{d}n)$ time
each. The overall running time is $\mathcal{O}(6^{d}\cdot n^{3})$ time.

###  5.3 Treewidth

Conjecture 4.2. formulated by Faller et al. [9] supposes that s-PDD remains
NP-hard on instances where the underlying graph of the food-web is a tree. In
this subsection, we disprove this conjecture by showing that s-PDD can be
solved in polynomial time on food-webs which are trees (assuming P$\neq$NP).
We even show a stronger result: s-PDD is FPT with respect to the treewidth of
the food-web.

######  Theorem 5.9 ($\star$).

s-PDD can be solved in
$\mathcal{O}(9^{\operatorname{{tw}}_{{\mathcal{F}}}}\cdot nk)$ time.

To show Theorem 5.9, we define a dynamic programming algorithm over a tree-
decomposition of $\mathcal{F}$. In each bag, we divide the taxa into three
sets indicating that they a) are supposed to go extinct, b) will be saved but
still need prey, c) or will be saved without restrictions. The algorithm is
similar to the standard treewidth algorithm for Dominating Set [5].

##  6 Discussion

In this paper, we studied the algorithmic complexity PDD and s-PDD with
respect to various parameterizations. PDD is FPT when parameterized with the
solution size plus the height of the phylogenetic tree. Consequently, PDD is
FPT with respect to $D$, the threshold of diversity. Further, unlike some
other problems on maximizing phylogenetic diversity [13, 14], PDD probably
does not admit an FPT-algorithm with respect to $\overline{D}$, the acceptable
loss of phylogenetic diversity.

We also considered the structure of the food-web. Among other results, we
showed that PDD remains NP-hard even if the food-web is a cluster graph but
PDD is FPT with respect to the number of vertices that need to be removed from
the food web to receive a co-cluster. On the positive side, we proved that
s-PDD is FPT with respect to the treewidth of the food-web and therefore can
be solved in polynomial time if the food-web is a tree.

Several interesting questions remain open after our examination of PDD and
s-PDD. Arguably the most relevant one is whether PDD is FPT with respect to
$k$, the size of the solution. Also, it remains open whether PDD can be solved
in polynomial time if each connected component in the food-web contains at
most two vertices.

Clearly, further structural parameterizations can be considered. We only
considered structural parameters which consider the underlying graph. But
parameters which also consider the orientation of edges, such as the longest
anti-chain, could give a better view on the structure of the food-web than
parameters which only consider the underlying graph.

Liebermann et al. [16] introduced and analyzed weighted food-webs. Such a
weighted model may provide a more realistic view of a species’ effect on and
interaction with other species [4]. Maximizing phylogenetic diversity with
respect to a weighted food-web in which one potentially needs to save several
prey per predator would be an interesting generalization for our work and has
the special case in which one needs to save all prey for each predator.

Recent works consider the maximization of phylogenetic diversity in
phylogenetic networks [29, 3, 13, 28] which may provide a more realistic
evolutionary model of the considered species. It would be interesting to study
these problems also under ecological constraints. Do the resulting problems
become much harder than PDD? Finally, it has been reported that maximizing
phylogenetic diversity is only marginally better than selecting a random set
of species when it comes to maximizing the functional diversity of the
surviving species [17]. The situation could be different, however, when
ecological constraints are incorporated. Here, investigating the following two
questions seems fruitful: First, do randomly selected viable species sets have
a higher functional diversity than randomly selected species? Second, do
viable sets with maximal phylogenetic diversity have a higher functional
diversity than randomly selected viable sets?

## References

  * [1] N. Alon, R. Yuster, and U. Zwick.  Color-coding.  Journal of the Association for Computing Machinery (JACM), 42(4):844–856, 1995.
  * [2] T. Beyer and S. M. Hedetniemi.  Constant time generation of rooted trees.  SIAM Journal on Computing, 9(4):706–712, 1980.
  * [3] M. Bordewich, C. Semple, and K. Wicke.  On the Complexity of optimising variants of Phylogenetic Diversity on Phylogenetic Networks.  Theoretical Computer Science, 917:66–80, 2022.
  * [4] A. R. Cirtwill, G. V. Dalla Riva, M. P. Gaiarsa, M. D. Bimler, E. F. Cagua, C. Coux, and D. M. Dehling.  A review of species role concepts in food webs.  Food Webs, 16:e00093, 2018.
  * [5] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.  Parameterized Algorithms.  Springer, 2015.
  * [6] R. G. Downey and M. R. Fellows.  Fixed-parameter tractability and completeness II: On completeness for W[1].  Theoretical Computer Science, 141(1-2):109–131, 1995.
  * [7] R. G. Downey and M. R. Fellows.  Fundamentals of Parameterized Complexity.  Texts in Computer Science. Springer, 2013.
  * [8] D. P. Faith.  Conservation evaluation and Phylogenetic Diversity.  Biological Conservation, 61(1):1–10, 1992.
  * [9] B. Faller, C. Semple, and D. Welsh.  Optimizing phylogenetic diversity with ecological constraints.  Annals of Combinatorics, 15(2):255–266, 2011.
  * [10] P. Gerhold, J. F. Cahill Jr, M. Winter, I. V. Bartish, and A. Prinzing.  Phylogenetic patterns are not proxies of community assembly mechanisms (they are far better).  Functional Ecology, 29(5):600–614, 2015.
  * [11] K. Hartmann and M. Steel.  Maximizing phylogenetic diversity in biodiversity conservation: Greedy solutions to the Noah’s Ark problem.  Systematic Biology, 55(4):644–651, 2006.
  * [12] N. J. Isaac, S. T. Turvey, B. Collen, C. Waterman, and J. E. Baillie.  Mammals on the edge: conservation priorities based on threat and phylogeny.  PloS one, 2(3):e296, 2007.
  * [13] M. Jones and J. Schestag.  How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks.  In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2023.
  * [14] M. Jones and J. Schestag.  Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead.  arXiv preprint arXiv:2403.14217, 2024.
  * [15] C. Komusiewicz and J. 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.
  * [16] E. Lieberman, C. Hauert, and M. A. Nowak.  Evolutionary dynamics on graphs.  Nature, 433(7023):312–316, 2005.
  * [17] F. Mazel, M. W. Pennell, M. W. Cadotte, S. Diaz, G. V. Dalla Riva, R. Grenyer, F. Leprieur, A. O. Mooers, D. Mouillot, C. M. Tucker, et al.  Prioritizing phylogenetic diversity captures functional diversity unreliably.  Nature Communications, 9(1):2888, 2018.
  * [18] B. Q. Minh, S. Klaere, and A. von Haeseler.  Phylogenetic Diversity within Seconds.  Systematic Biology, 55(5):769–773, 10 2006.
  * [19] B. Mohar.  Face covers and the genus problem for apex graphs.  Journal of Combinatorial Theory, Series B, 82(1):102–117, 2001\.
  * [20] V. Moulton, C. Semple, and M. Steel.  Optimizing phylogenetic diversity under constraints.  Journal of Theoretical Biology, 246(1):186–194, 2007.
  * [21] M. Naor, L. J. Schulman, and A. Srinivasan.  Splitters and near-optimal Derandomization.  Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 182–191, 1995.
  * [22] F. Pardi and N. Goldman.  Species Choice for Comparative Genomics: Being Greedy Works.  PLoS Genetics, 1, 2005.
  * [23] F. Pardi and N. Goldman.  Resource-aware taxon selection for maximizing phylogenetic diversity.  Systematic Biology, 56(3):431–444, 2007.
  * [24] N. Robertson and P. D. Seymour.  Graph minors. X. Obstructions to tree-decomposition.  Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991\.
  * [25] P. W. Shor.  A new proof of Cayley’s formula for counting labeled trees.  Journal of Combinatorial Theory, Series A, 71(1):154–158, 1995\.
  * [26] A. Spillner, B. T. Nguyen, and V. Moulton.  Computing phylogenetic diversity for split systems.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2):235–244, 2008.
  * [27] M. Steel.  Phylogenetic Diversity and the greedy algorithm.  Systematic Biology, 54(4):527–529, 2005.
  * [28] L. van Iersel, M. Jones, J. Schestag, C. Scornavacca, and M. Weller.  Maximizing network phylogenetic diversity.  arXiv preprint arXiv:2405.01091, 2024.
  * [29] K. Wicke and M. Fischer.  Phylogenetic Diversity and biodiversity indices on Phylogenetic Networks.  Mathematical Biosciences, 298:80–90, 2018.

##  A.1 Appendix

#### Proof of Lemma 3.6

######  Proof A.1.1 (Correctness of 4).

Correctness. Assume $S\subseteq X$ is a solution of the instance of PDD-
pattern. As there is no edge $u^{\prime}v^{\prime}\in E_{P}$ with
$c_{P}(u^{\prime})=c(u)$ and $c_{P}(v^{\prime})=c(v)$ we conclude that
$S\cap\operatorname{desc}(v)=\emptyset$ and so the reduction rule is safe.

Running Time. To check whether 4 can be applied, we need to iterate over both
$E({\mathcal{T}})$ and $E_{P}$. Therefore, a single application can be
executed in $\mathcal{O}(n^{2})$ time. In each application of 4 we remove at
least one vertex so that an exhaustive application can be computed in
$\mathcal{O}(n^{3})$ time.

######  Proof A.1.2 (Correctness of 5).

Correctness. Let $S$ be a solution for the instance of PDD-pattern. The
spanning tree ${\mathcal{T}}\langle S\cup\\{\rho\\}\rangle$ contains exactly
one vertex $w$ with color $c(u)$. As $c(w)=c_{P}(u^{\prime})$ we conclude that
$w$ has a child $w^{\prime}$ and $c(w^{\prime})=c(v^{\prime})$. Consequently,
$w\neq u$ and $S\cap\operatorname{desc}(u)=\emptyset$.

Running Time. Like in 4, iterate over the edges of $\mathcal{T}$ and
${\mathcal{T}}_{P}$. Each application either removes at least one vertex or
concludes that the reduction rule is applied exhaustively.

######  Proof A.1.3 (Correctness of 6).

Correctness. By definition, each set $S\subseteq X$ with $S\cap
R\neq\emptyset$ is not viable. Therefore, 6 is correct.

Running Time. Iterate over the taxa $x\in X\setminus L$ and compute whether
there is a path from $x$ to some vertex of
${\operatorname{sources}({\mathcal{F}})}$ in ${\mathcal{F}}[X\setminus L]$. If
not add $x$ to $R$. With breadth-first search, this computation can be done in
$\mathcal{O}(m\cdot n^{2})$ time, where the quadratic factor arises from the
iteration over $X\setminus L$ and ${\operatorname{sources}({\mathcal{F}})}$. A
single application is exhaustive.,color=red!25!green!50] True??

######  Proof A.1.4 (Correctness of 7).

Correctness. Assume that $\mathcal{I}$ is a yes-instance of PDD-pattern with
solution $S$. Because ${\mathcal{T}}\langle S\cup\\{\rho\\}\rangle$ and
${\mathcal{T}}_{P}$ are color-equal also ${\mathcal{T}}^{\prime}\langle
S\cup\\{\rho\\}\rangle$ and ${\mathcal{T}}_{P}^{\prime}$ are color-equal. Let
$u^{*}$ and $w_{1}$ be the unique vertices in ${\mathcal{T}}\langle
S\cup\\{\rho\\}\rangle$ with $c(u^{*})=c_{P}(u^{\prime})$ and
$c(w_{1})=c_{P}(v^{\prime})$. Let $w_{2},\dots,w_{\ell}$ be the other children
of $u^{*}$. As ${PD_{{\mathcal{T}}^{\prime}}}(S)$ is the sum of the weights of
the edges of ${\mathcal{T}}^{\prime}\langle S\cup\\{\rho\\}\rangle$ we
conclude
${PD_{{\mathcal{T}}^{\prime}}}(S)={PD_{{\mathcal{T}}}}(S)-({\omega}(\rho
u^{*})+\sum_{i=1}^{\ell}{\omega}(u^{*}w_{i}))+\sum_{i=1}^{\ell}{\omega}^{\prime}(\rho
w_{i})$. Since ${\omega}^{\prime}(\rho w_{1})={\omega}(\rho
u^{*})+{\omega}(u^{*}w_{1})$ and ${\omega}^{\prime}(\rho
w_{i})={\omega}(u^{*}w_{i})$ for $i\in[\ell]\setminus\\{1\\}$, we conclude
that ${PD_{{\mathcal{T}}^{\prime}}}(S)={PD_{{\mathcal{T}}}}(S)\geq D$.
Therefore, $S$ is a solution for ${\mathcal{I}}^{\prime}$.

The other direction is shown analogously.

Running Time. For a given grand-child $v^{\prime}$ of $\rho_{P}$, one needs to
perform $\mathcal{O}(n)$ color-checks and add $\mathcal{O}(n)$ edges. As the
reduction rule can be applied at most
$|{\mathcal{T}}_{P}|\in\mathcal{O}(K)\in\mathcal{O}(n)$ times, an exhaustive
application takes $\mathcal{O}(n^{2})$ time. (Plus the other reduction rules.)

#### Proof of Theorem 4.1

We define $D$-colored Optimizing PD with Dependencies ($D$-c-PDD), a colored
version of PDD, as follows. In addition to the usual input of PDD, we receive
two colorings $c$ and $\hat{c}$ which assign each edge $e\in E({\mathcal{T}})$
a subset $c(e)$ of $[D]$, called _a set of colors_ , which is of size
${\omega}(e)$ and each taxon $x\in X$ a _color_ $\hat{c}(x)\in[k]$. We extend
the function $c$ to also assign color sets to taxa $x\in X$ by defining
$c(x):=\bigcup_{e\in E^{\prime}}c(e)$ where $E^{\prime}$ is the set of edges
with $x\in\operatorname{off}(e)$. In $D$-c-PDD, we ask whether there is a
viable set $S\subseteq X$ of taxa exists such that $c(S)=[D]$, and $\hat{c}$
is colorful.

Finding a solution for $D$-c-PDD can be done with techniques similar to Lemma
3.3.

######  Lemma A.1.5.

$D$-c-PDD can be solved in $\mathcal{O}(3^{D+k}\cdot n\cdot m)$ time.

######  Proof A.1.6.

Table definition. Let
${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D,c,\hat{c})$ be an instance of
$D$-c-PDD and we assume that $\star\in X$ is the only source in $\mathcal{F}$
by Section 2.2.

Given $x\in X$, sets of colors $C_{1}\subseteq[D]$, $C_{2}\subseteq[k]$, and a
set of taxa $X^{\prime}\subseteq X$: A set $S\subseteq X^{\prime}\subseteq X$
is $(C_{1},C_{2},X^{\prime})$-feasible if  a) $C_{1}$is a subset of $c(S)$,
b) $\hat{c}(S)=C_{2}$,  c) $\hat{c}(S)$is colorful,  d) $S$is
$X^{\prime}$-viable.

We define a dynamic programming algorithm with tables $\operatorname{DP}$ and
$\operatorname{DP}^{\prime}$. We want that entry
$\operatorname{DP}[x,C_{1},C_{2}]$ for $x\in X$ and $C_{1}\subseteq[D]$,
$C_{2}\subseteq[k]$ to stores 1 if a $(C_{1},C_{2},X_{\geq x})$-feasible set
$S$ exists. Otherwise, we want $\operatorname{DP}[x,C_{1},C_{2}]$ to store 0.

For any taxon $x\in X$ let $y_{1},\dots,y_{q}$ be an arbitrary but fixed order
of ${N_{>}(x)}$. In the auxiliary table $\operatorname{DP}^{\prime}$ we want
entry $\operatorname{DP}^{\prime}[x,p,C_{1},C_{2}]$ for $p\in[q]$, and
$C_{1}\subseteq[D]$, $C_{2}\subseteq[k]$ to store 1 if a
$(C_{1},C_{2},X^{\prime})$-feasible set $S\subseteq X^{\prime}$ exists, where
$X^{\prime}:=\\{x\\}\cup X_{\leq y_{1}}\cup\dots\cup X_{\leq y_{p}}$. If no
$(C_{1},C_{2},X^{\prime})$-feasible set $S\subseteq X^{\prime}$ exists, we
want $\operatorname{DP}^{\prime}[x,p,C_{1},C_{2}]$ to store
0.,color=red!25!green!50] Potentially cut here some space for the Conference
version by referring to Thm 3.1.

Algorithm. As a basic case for each $x\in X$ and each $p\in[|{N_{>}(x)}|]$ let
$\operatorname{DP}[x,\emptyset,\emptyset]$ and
$\operatorname{DP}^{\prime}[x,p,\emptyset,\emptyset]$ store 1. Further, let
$\operatorname{DP}[x,C_{1},C_{2}]$ and
$\operatorname{DP}^{\prime}[x,p,C_{1},C_{2}]$ store 0 if $C_{1}\not\subseteq
c(x)$, or $\hat{c}(x)\not\in C_{2}$, or $|C_{2}|>|X_{\geq x}|$ for each $x\in
X$ and every $C_{1}\subseteq[D]$, $C_{2}\subseteq[k]$. For each $x\in X$ with
${N_{>}(x)}=\emptyset$, we store 1 in $\operatorname{DP}[x,C_{1},C_{2}]$ if
$C_{1}=C_{2}=\emptyset$ or if $C_{1}\subseteq c(x)$ and
$C_{2}=\\{\hat{c}(x)\\}$. Otherwise, we store 0.

Fix a taxon $x\in X$. Assume $\operatorname{DP}[y,C_{1},C_{2}]$ is computed
for each $y\in{N_{>}(x)}$, every $C_{1}\subseteq[D]$, and every
$C_{2}\subseteq[k]$. For $C_{1}\subseteq[D]\setminus c(x)$ and
$C_{2}\subseteq[k]\setminus\\{\hat{c}(x)\\}$, we set

$\operatorname{DP}^{\prime}[x,1,c(x)\cup C_{1},\\{\hat{c}(x)\\}\cup
C_{2}]:=\operatorname{DP}[y_{1},C_{1},C_{2}].$ (5)

Fix an integer $p\in[q]$. We assume
$\operatorname{DP}^{\prime}[x,p,C_{1},C_{2}]$ is computed for every
$C_{1}\subseteq[D]$, and every $C_{2}\subseteq[k]$. Then for
$C_{1}\subseteq[D]\setminus c(x)$ and
$C_{2}\subseteq[k]\setminus\\{\hat{c}(x)\\}$ we use the recurrence

$\begin{array}[]{l}\operatorname{DP}^{\prime}[x,p+1,c(x)\cup
C_{1},\\{\hat{c}(x)\\}\cup C_{2}]:=\\\ \max_{C_{1}^{\prime}\subseteq
C_{1},C_{2}^{\prime}\subseteq C_{2}}\operatorname{DP}^{\prime}[x,p,c(x)\cup
C_{1}\setminus C_{1}^{\prime},\\{\hat{c}(x)\\}\cup C_{2}\setminus
C_{2}^{\prime}]\cdot\operatorname{DP}[y_{p+1},C_{1}^{\prime},C_{2}^{\prime}].\end{array}$
(6)

Finally, we set
$\operatorname{DP}[x,C_{1},C_{2}]:=\operatorname{DP}^{\prime}[x,q,C_{1},C_{2}]$
for every $C_{1}\subseteq[D]$, and every $C_{2}\subseteq[k]$.

Return yes if $\operatorname{DP}[\star,[D],C_{2}]$ stores 1 for some
$C_{2}\subseteq[k]$. Otherwise, return no.

Correctness. The correctness and the running time can be shown analogously to
proof of Lemma 3.3.

We can now prove Theorem 4.1 by showning how the standard PDD can be reduced
to $D$-c-PDD via color coding.

######  Proof A.1.7 (Proof of Theorem 4.1).

Reduction. Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an
instance of PDD. We assume that $\mathcal{F}$ only has one source by Section
2.2 and that $\max_{\omega}<D$ by 2.

Let $e_{1},\dots,e_{|E({\mathcal{T}})|}$ and $x_{1},\dots,x_{n}$ be the edges
and taxa of $\mathcal{T}$, respectively. We define integers $W_{0}:=0$ and
$W_{j}:=\sum_{i=1}^{j}{\omega}(e_{i})$ for each $j\in[|E({\mathcal{T}})|]$.
Set $W:=W_{|E({\mathcal{T}})|}$.

Compute a $(W,D)$-perfect hash family $\mathcal{H}_{D}$ and a $(n,k)$-perfect
hash family $\mathcal{H}_{k}$. For every $g\in\mathcal{H}_{k}$, let $c_{g,2}$
be a coloring such that $c_{g,2}(x_{j})=f(j)$ for each $x_{j}\in X$. For every
$f\in\mathcal{H}_{D}$, let $c_{f,1}$ be a coloring such that
$c_{f,1}(e_{j})=\\{f(W_{j-1}+1),\dots,f(W_{j})\\}$ for each $e_{j}\in
E({\mathcal{T}})$.

For hash functions $f\in\mathcal{H}_{D}$ and $g\in\mathcal{H}_{k}$, construct
an instance
${\mathcal{I}}_{f,g}=({\mathcal{T}},{\mathcal{F}},k,D,c_{f,1},c_{g,2})$ of
$D$-c-PDD. Solve every instance ${\mathcal{I}}_{f,g}$ using Lemma A.1.5 and
return yes if and only if ${\mathcal{I}}_{f,g}$ is a yes-instance for some
$f\in\mathcal{H}_{D}$, $g\in\mathcal{H}_{k}$.

Correctness. We first show that if $\mathcal{I}$ is a yes instance then
${\mathcal{I}}_{f,g}$ is a yes-instance for some $f\in\mathcal{H}_{D}$,
$g\in\mathcal{H}_{k}$. For any set of edges $E^{\prime}$ with
${\omega}(E^{\prime})\geq D$, there is a corresponding subset of $[W]$ of size
at least $D$. Since $\mathcal{H}_{k}$ is a $(W,D)$-perfect hash family,
$c_{f,1}(E^{\prime})=[D]$, for some $f\in\mathcal{H}_{D}$. Analogously, for
each set $X^{\prime}$ of taxa with $|X^{\prime}|=k$ there is a hash function
$g\in\mathcal{H}_{k}$ such that $c_{g,2}(X^{\prime})=[k]$. Thus in particular,
if $S\subseteq X$ is a solution of size $k$ for ${\mathcal{I}}$, then
$c_{f,1}(S)=[D]$, for some $f\in\mathcal{H}_{D}$ and $c_{g,2}(S)=[k]$, for
some $g\in\mathcal{H}_{k}$. It follows that one of the constructed instances
of $D$-c-PDD is a yes-instance.

Conversely, a solution for ${\mathcal{I}}_{f,g}$ for some
$f\in\mathcal{H}_{D}$, $g\in\mathcal{H}_{k}$ is also a solution for
${\mathcal{I}}$.

Running Time. We require $\mathcal{O}(n^{2})$ time for 2 and Section 2.2. We
can construct $\mathcal{H}_{D}$ and $\mathcal{H}_{k}$ in
$e^{D}D^{\mathcal{O}(\log D)}\cdot W\log W$ time. Solving instances of
$D$-c-PDD takes $\mathcal{O}(3^{D+k}\cdot nm)$ time each, and the number of
instances is $|\mathcal{H}_{D}|\cdot|\mathcal{H}_{k}|=e^{D}D^{\mathcal{O}(\log
D)}\cdot\log W\cdot e^{k}k^{\mathcal{O}(\log k)}\cdot\log n\in
e^{D+k+o(D)}\cdot\log W$.

Thus, the total running time is $\mathcal{O}(e^{D+k+o(D)}\cdot\log
W\cdot(W+3^{D+k}\cdot nm))$. Because $W={PD_{{\mathcal{T}}}}(X)<2n\cdot D$
this simplifies to $\mathcal{O}((3e)^{D+k+o(D)}\cdot nm+n^{2})$.

#### All other proofs

######  Proof A.1.8 (Proof of Section 2.2).

Construction. Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an
instance of PDD. Add a new taxon $\star$ to $\mathcal{F}$ and add edges from
$\star$ to each taxon $x$ of ${\operatorname{sources}({\mathcal{F}})}$ to
receive ${\mathcal{F}}^{\prime}$. To receive ${\mathcal{T}}^{\prime}$, add
$\star$ as a child to the root $\rho$ of $\mathcal{T}$ and set
${\omega}^{\prime}(\rho\star)=D+1$ and ${\omega}^{\prime}(e)={\omega}(e)$ for
each $e\in E({\mathcal{T}})$. Finally, set $k^{\prime}:=k+1$ and
$D^{\prime}:=2\cdot D+1$.

Correctness. All steps can be performed in $\mathcal{O}(|{\mathcal{I}}|^{2})$
time. Because $S\subseteq X$ is a solution for $\mathcal{I}$ if and only if
$S\cup\\{\star\\}$ is a solution for ${\mathcal{I}}^{\prime}$, the instance
${\mathcal{I}}^{\prime}=({\mathcal{T}}^{\prime},{\mathcal{F}}^{\prime},k+1,2\cdot
D+1)$ is a yes-instance of PDD if and only if $\mathcal{I}$ is a yes-instance
of PDD.

######  Proof A.1.9 (Proof of Theorem 3.2).

Reduction. Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an
instance of PDD. We assume that $\mathcal{F}$ only has one source by Section
2.2.

Let $x_{1},\dots,x_{n}$ be the taxa. Compute an $(n,k)$-perfect hash family
$\mathcal{H}$. For every $f\in\mathcal{H}$, let $c_{f}$ be a coloring such
that $c_{f}(x_{j})=f(j)$ for each $x_{j}\in X$.

For every $f\in\mathcal{H}$, construct an instance
${\mathcal{I}}_{f}=({\mathcal{T}},{\mathcal{F}},k,D,c_{f})$ of $k$-c-s-PDD and
solve ${\mathcal{I}}_{f}$ using Lemma 3.3. Return yes if and only if
${\mathcal{I}}_{f}$ is a yes-instance for some $f\in\mathcal{H}$.

Correctness. We show that if $\mathcal{I}$ has a solution $S$ then there is an
$f\in\mathcal{H}$ such that ${\mathcal{I}}_{f}$ is a yes-instance of $k$-c-s-
PDD. Let $S$ be a solution for $\mathcal{I}$. Thus, $S$ is viable,
${PD_{{\mathcal{T}}}}(S)\geq D$, and $S$ has a size of at most $k$. We may
assume $|S|=k$ by Section 2.2. By the definition of $(n,k)$-perfect hash
families, a function $f\in\mathcal{H}$ exists such that $c_{f}(S)$ is
colorful. So, $S$ is a solution for ${\mathcal{I}}_{f}$. Conversely, a
solution of ${\mathcal{I}}_{f}$ for any $f\in\mathcal{H}$ is a solution for
$\mathcal{I}$.

Running Time. The instances ${\mathcal{I}}_{f}$ can be constructed in
$e^{k}k^{\mathcal{O}(\log k)}\cdot n\log n$ time. An instance of $k$-c-s-PDD
can be solved in $\mathcal{O}(3^{k}\cdot n\cdot m)$ time, and the number of
instances is $|\mathcal{C}|=e^{k}k^{\mathcal{O}(\log k)}\cdot\log n$. Thus,
the total running time is $\mathcal{O}^{*}(e^{k}k^{\mathcal{O}(\log k)}\log
n\cdot(3^{k}\cdot nm))$ which simplifies to $\mathcal{O}((3e)^{k}\cdot
2^{\mathcal{O}(\log^{2}(k))}\cdot nm\cdot\log n)$.

######  Proof A.1.10 (Proof of Lemma 5.6).

We adopt the dynamic programming algorithm with which one can solve Max-PD
with weighted costs for saving taxa in pseudo-polynomial time [23].

Table definition. We define two tables $\operatorname{DP}$ and and an
auxiliary table $\operatorname{DP}^{\prime}$. We want that entry
$\operatorname{DP}[v,0,\mathcal{M}]$ for $v\in V({\mathcal{T}})$, and
$\mathcal{M}\subseteq\mathcal{W}$ stores 0 if $\mathcal{M}$ is empty and
$\operatorname{DP}[v,1,\mathcal{M}]$ stores the biggest phylogenetic diversity
${PD_{{\mathcal{T}}_{v}}}(S)$ of a set $S\subseteq\operatorname{off}(v)$ in
the subtree ${\mathcal{T}}_{v}$ rooted at $v$ where $S\cap M\neq\emptyset$ for
each $M\in\mathcal{M}$. Otherwise, we store $-\infty$. For a vertex $v\in
V({\mathcal{T}})$ with children $w_{1},\dots,w_{j}$, in
$\operatorname{DP}^{\prime}[v,i,b,\mathcal{M}]$ we only consider
$S\subseteq\operatorname{off}(w_{1})\cup\dots\cup\operatorname{off}(w_{i})$.

Algorithm. For a leaf $u\in\mathcal{U}$ of $\mathcal{T}$, in
$\operatorname{DP}[u,1,\mathcal{M}]$ store 0 if $u\in M$ for each
$M\in\mathcal{M}$. Otherwise, store $-\infty$. For a given vertex $v$ of
$\mathcal{T}$, in $\operatorname{DP}[v,0,\mathcal{M}]$ and
$\operatorname{DP}^{\prime}[v,i,0,\mathcal{M}]$ store 0 if
$\mathcal{M}=\emptyset$. Otherwise, store $-\infty$.

Let $v$ be an internal vertex of $\mathcal{T}$ with children
$w_{1},\dots,w_{z}$. We set
$\operatorname{DP}^{\prime}[v,1,b,\mathcal{M}]:=\operatorname{DP}[w_{1},b,\mathcal{M}]+b\cdot{\omega}(vw_{1})$.
To compute further values, we use the recurrence

$\operatorname{DP}^{\prime}[v,i+1,1,\mathcal{M}]=\max_{\mathcal{M}^{\prime},b_{1},b_{2}}\operatorname{DP}^{\prime}[v,i,b_{1},\mathcal{M}^{\prime}]+\operatorname{DP}[w_{i+1},b_{2},\mathcal{M}\setminus\mathcal{M}^{\prime}]+b_{2}\cdot{\omega}(vw_{i+1}).$
(7)

Here, the maximum is taken over $\mathcal{M}^{\prime}\subseteq\mathcal{M}$ and
$b_{1},b_{2}\in\\{0,1\\}$ where we additionally require $b_{1}+b_{2}\geq 1$.
Finally,
$\operatorname{DP}[v,b,\mathcal{M}]:=\operatorname{DP}^{\prime}[v,z,b,\mathcal{M}]$.

If $\operatorname{DP}[\rho,1,\mathcal{W}]\geq D$, return yes. Otherwise,
return no.

Correctness. The basic cases are correct. Overall, the correctness of
Recurrence (7) can be shown analogously to [23].

Running time. As a tree has at most $2n$ vertices, the overall size of
$\operatorname{DP}$ and $\operatorname{DP}^{\prime}$ is
$\mathcal{O}(2^{|\mathcal{W}|}\cdot n)$. In Recurrence (7), there are three
options for each $M\in\mathcal{W}$. Hence that the total number of terms
considered in the entire table can be computed in
$\mathcal{O}(3^{|\mathcal{W}|}\cdot n)$ time.

######  Proof A.1.11 (Proof of Theorem 5.9).

Let ${\mathcal{I}}=({\mathcal{T}},{\mathcal{F}},k,D)$ be an instance of s-PDD.
We define a dynamic programming algorithm over a nice tree-decomposition $T$
of ${\mathcal{F}}=(V_{\mathcal{F}},E_{\mathcal{F}})$.

We do not define tree-decompositions. Common definitions can be found in [24,
5].

For a node $t\in T$, let $Q_{t}$ be the bag associated with $t$ and let
$V_{t}$ be the union of bags in the subtree of $T$ rooted a $t$.

Definition of the Table. We index solutions by a partition $R\cup G\cup B$ of
$Q_{t}$, and a non-negative integer $s$. For a set of taxa $Y\subseteq V_{t}$,
we call a vertex $u\in V_{t}$ _red with respect to $Y$_ if $u$ is in $Y$ and
$u$ has a predator but no prey in $Y$. We call $u$ _green with respect to $Y$_
if $u$ is in $Y$ and a) $u$ is a source in $\mathcal{F}$, or b) has prey in
$Y$. Finally, we call $u$ _black with respect to $Y$_ if $u$ is not in $Y$.

For a node $t$ of the tree-decomposition, a partition $R\cup G\cup B$ of
$Q_{t}$, and an integer $s$, a set of taxa $Y\subseteq V_{t}$ is called
_$(t,R,G,B,s)$ -feasible_, if all the following conditions hold.  (T1) Each
vertex in $Y\setminus Q_{t}$ is green with respect to $Y$.  (T2) The vertices
$R\subseteq Q_{t}$ are red with respect to $Y$.  (T3) The vertices $G\subseteq
Q_{t}$ are green with respect to $Y$.  (T4) The vertices $B\subseteq Q_{t}$
are black with respect to $Y$.  (T5) The size of $Y$ is $s$.

In table entry $\operatorname{DP}[t,A,R,G,B,s]$, we store the largest
diversity ${PD_{{\mathcal{T}}}}(Y)$ of a $(t,R,G,B,s)$-feasible set $Y$. If
there is no $(t,R,G,B,s)$-feasible sets $Y$, we store $-\infty$. Let $r$ be
the root of the nice tree-decomposition $T$. Then,
$\operatorname{DP}[r,\emptyset,\emptyset,\emptyset,k]$ stores an optimal
diversity. So, we return yes if
$\operatorname{DP}[r,\emptyset,\emptyset,\emptyset,k]\geq D$ and no otherwise.

We regard the different types of nodes of a tree-decomposition separately and
discuss their correctness.

Leaf Node. For a leaf $t$ of $T$ the bags $Q_{t}$ and $V_{t}$ are empty. We
store

$\displaystyle\operatorname{DP}[t,\emptyset,\emptyset,\emptyset,0]$
$\displaystyle=$ $\displaystyle 0.$ (8)

For all other values, we store $\operatorname{DP}[t,R,G,B,s]=-\infty$.

Recurrence (8) is correct by definition.

Introduce Node. Suppose that $t$ is an _introduce node_ , that is, $t$ has a
single child $t^{\prime}$ with $Q_{t}=Q_{t^{\prime}}\cup\\{v\\}$. We store
$\operatorname{DP}[t,R,G,B,s]=\operatorname{DP}[t^{\prime},R,G,B\setminus\\{v\\},s]$
if $v\in B$. If $v\in G$ but $v$ is not a source and ${N_{<}(v)}\cap(R\cup
G)=\emptyset$, we store $\operatorname{DP}[t,R,G,B,s]=-\infty$. Otherwise, we
store

$\displaystyle\operatorname{DP}[t,R,G,B,s]$ $\displaystyle=$
$\displaystyle\max_{A\subseteq{N_{>}(v)}\cap(R\cup
G)}\operatorname{DP}[t^{\prime},R^{\prime},G^{\prime},B,s-1]+{\omega}(\rho
v).$ (9)

Herein, $R^{\prime}$ and $G^{\prime}$ are defined as
$R^{\prime}=(R\setminus(\\{v\\}\cup{N_{>}(v)}))\cup A$ and
$G^{\prime}=(G\cup({N_{>}(v)}\cap(R\cup G)))\setminus(A\cup\\{v\\})$.

If $v\in B$, then $v\not\in Y$ for any $(t,R,G,B,s)$-feasible set $Y$. If
$v\in G$ but is not a source and has no prey in $R\cup G$, then $v$ is not
green with respect to $Y$ for any $Y$. So, these two cases store the desired
value. Towards the correctness of Recurrence (9): If $v\in G\cup R$, then we
want to select $v$ and therefore we need to add ${\omega}(\rho v)$ to the
value of $\operatorname{DP}[t,R,G,B,s]$. Further, by the selection of $v$ we
know that the predators of $v$ could be green (but maybe are still stored as
red) in $t$, but in $t^{\prime}$ could be red and therefore we reallocate
${N_{>}(v)}\cap(R\cup G)$ and let $A$ be red beforehand.

Forget Node. Suppose that $t$ is a _forget node_ , that is, $t$ has a single
child $t^{\prime}$ and $Q_{t}=Q_{t^{\prime}}\setminus\\{v\\}$. We store

$\displaystyle\operatorname{DP}[t,R,G,B,s]=\max\\{\operatorname{DP}[t^{\prime},R,G\cup\\{v\\},B,s];\operatorname{DP}[t^{\prime},R,G,B\cup\\{v\\},s]\\}.$
(10)

Recurrence (10) follows from the definition that vertices in $v\in
V_{t}\setminus Q_{t}$ are either black or green with respect to
$(t,R,G,B,s)$-feasible sets.

Join Node. Suppose that $t\in T$ is a _join node_ , that is, $t$ has two
children $t_{1}$ and $t_{2}$ with $Q_{t}=Q_{t_{1}}=Q_{t_{2}}$. We call two
partitions $R_{1}\cup G_{1}\cup B_{1}$ and $R_{2}\cup G_{2}\cup B_{2}$ of
$Q_{t}$ _qualified_ for $R\cup G\cup B$ if $R=(R_{1}\cup
R_{2})\setminus(G_{1}\cup G_{2})$ and $G=G_{1}\cup G_{2}$ (and consequently
$B=B_{1}\cap B_{2}$). See Figure 2. We store

$\displaystyle\operatorname{DP}[t,R,G,B,s]$ $\displaystyle=$
$\displaystyle\max_{(\pi_{1},\pi_{2})\in{\cal
Q},s^{\prime}}\leavevmode\nobreak\
\operatorname{DP}[t_{1},R_{1},G_{1},B_{1},s^{\prime}]+\operatorname{DP}[t_{2},R_{2},G_{2},B_{2},s-s^{\prime}],$
(11)

where ${\cal Q}$ is the set of pairs of partitions $\pi_{1}=R_{1}\cup
G_{1}\cup B_{1}$ and $\pi_{2}=R_{2}\cup G_{2}\cup B_{2}$ that are qualified
for $R,G,B$, and $s^{\prime}\in[s]_{0}$.

By Figure 2 we observe that in Recurrence (11) we consider the correct
combinations of $R$, $G$, and $B$.

| $B_{1}$ | $R_{1}$ | $G_{1}$
---|---|---|---
$B_{2}$ | $B$ | $R$ | $G$
$R_{2}$ | $R$ | $R$ | $G$
$G_{2}$ | $G$ | $G$ | $G$
Figure 2: This table shows the relationship between the partitions $R_{1}\cup
G_{1}\cup B_{1}$, $R_{2}\cup G_{2}\cup B_{2}$ and $R\cup G\cup B$ in the case
of a join node, when $R_{1}\cup G_{1}\cup B_{1}$ and $R_{2}\cup G_{2}\cup
B_{2}$ are qualified for $R\cup G\cup B$. The table shows which of the set
$R,G$, or $B$ an element $v\in Q_{t}$ will be in, depending on its membership
in $R_{1},G_{1},B_{1},R_{2},G_{2}$, and $B_{2}$. For example if $v\in R_{1}$
and $v\in B_{2}$, then $v\in R$.

Running Time. The table contains
$\mathcal{O}(3^{\operatorname{{tw}}_{{\mathcal{F}}}}\cdot nk)$ entries, as a
tree decomposition contains $\mathcal{O}(n)$ nodes. Each leaf and forget node
can be computed in linear time. An introduce node can be computed in
$\mathcal{O}(2^{\operatorname{{tw}}_{{\mathcal{F}}}}\cdot n)$ time. In a join
node, considering only the qualified sets, $(\pi_{1},\pi_{2})$ already define
$R$, $G$, and $B$. Thus, all join nodes can be computed in
$\mathcal{O}(9^{\operatorname{{tw}}_{{\mathcal{F}}}}\cdot nk)$ time, which is
also the overall running time.