## Invited Session Mon.2.H 2033

#### Monday, 13:15 - 14:45 h, Room: H 2033

**Cluster 12: Life sciences & healthcare** [...]

### Evolution and phylogenetics

**Chair: Leo van Iersel**

**Monday, 13:15 - 13:40 h, Room: H 2033, Talk 1**

**Mareike Fischer**

When sets of species make an evolutionary tree unique

**Abstract:**

In a recent study, Sanderson and Steel defined and characterized so-called phylogenetically decisive sets of species sets. A set is called phylogenetically decisive if regardless of the evolutionary trees chosen for each of its species sets, as long as these trees are compatible with one another, their supertree is always unique. It remained unknown whether the decision if a set of species sets is phylogenetically decisive can always be made in polynomial time. This question was one of the "Penny Ante'' questions of the Annual New Zealand Phylogenetics Meeting 2012. In my talk, I will explain phylogenetic decisiveness and demonstrate a new mathematical characterization, which then leads to a polynomial time algorithm - both for the (simpler) case of rooted trees as well as for the (more complicated) unrooted case.

**Monday, 13:45 - 14:10 h, Room: H 2033, Talk 2**

**Steven Kelk**

Cycle killer … {} qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set

**Coauthors: Nela Lekic, Simone Linz, Celine Scornavacca, Leen Stougie, Leo van Iersel**

**Abstract:**

We show that the problem of computing the hybridization number of two rooted binary phylogenetic

trees on the same set of taxa X has a constant factor polynomial-time approximation if and only if the problem of

computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time

approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed

graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete

problems. Despite considerable attention from the combinatorial optimization community, it remains to

this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places

the (in)approximability of hybridization number in a much broader complexity context. On the positive side, we use results from the DFVS literature to give an *O({**log*} r {*log* *log*} r) approximation for the hybridization number where r is the

correct value.

**Monday, 14:15 - 14:40 h, Room: H 2033, Talk 3**

**Celine Scornavacca**

Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

**Coauthor: Steven Kelk**

**Abstract:**

Here we show that, given a set of clusters *C* on a set of taxa *X*, where *|X|=n*, it is possible to determine in

time *f(k) · poly(n)* whether there exists a level-* ≤ k* network (i.e. a network where each biconnected component has reticulation number at most *k*) that represents all the clusters in *C* in the softwired sense, and if so to construct such a network. This extends a polynomial time result from Kelk et al (On the elusiveness of clusters, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2012).

By generalizing the concept of "level-*k* generator'' to general networks, we then extend this fixed parameter tractability result to the problem where *k* refers not to the level but to the reticulation number of the whole network.