Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2012

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

Résumé

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. However, 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 hybridization number 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 hybridization number, where r is the value of an optimal solution to the hybridization number problem.
Fichier principal
Vignette du fichier
CycleKillerSIDMA.pdf (450.28 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00765019 , version 1 (21-07-2016)

Identifiants

Citer

Steven Kelk, Leo van Iersel, Nela Lekic, Simone Linz, Celine Scornavacca, et al.. Cycle killer... qu'est-ce que c'est? On the comparative approximability of hybridization number and directed feedback vertex set. SIAM Journal on Discrete Mathematics, 2012, 26 (4), pp.1635-1656. ⟨10.1137/120864350⟩. ⟨hal-00765019⟩
275 Consultations
134 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More