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

S.M. Kelk, L.J.J. Iersel, van, N. Lekic, S. Linz, C. Scornavacca, L. Stougie

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)
48 Downloads (Pure)

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, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an $\text{O}( \log r \log \log r)$ approximation for the hybridization number where $r$ is the correct value.
Original languageEnglish
Pages (from-to)1635-1656
JournalSIAM Journal on Discrete Mathematics
Volume26
Issue number4
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set'. Together they form a unique fingerprint.

Cite this