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


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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.