Paper Info
Title
Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set.
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 O(log r log log r) approximation for the hybridization number where r is the correct value.
Year
DOI
Venue
2012
10.1137/120864350
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
hybridization number,phylogenetic networks,directed feedback vertex set,approximation
Discrete mathematics,Combinatorics,Vertex (graph theory),Cycle graph,Directed graph,Neighbourhood (graph theory),Directed acyclic graph,Vertex cover,Feedback vertex set,Mathematics,Feedback arc set
Journal
Volume
Issue
ISSN
26
4
0895-4801
Citations 
PageRank 
References 
8
0.60
16
Authors
6
Name
Order
Citations
PageRank
Steven Kelk119325.60
Leo van Iersel221524.58
Nela Lekic3244.19
Simone Linz411214.50
Celine Scornavacca521618.80
Leen Stougie6892107.93