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

 

  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.