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

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

Talk 2 of the invited session Mon.2.H 2033

**"Evolution and phylogenetics"** [...]

Cluster 12

**"Life sciences & healthcare"** [...]