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. 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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2012, 26 (4), pp.1635-1656
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00765019
Contributeur : Marie-France Sagot <>
Soumis le : jeudi 21 juillet 2016 - 15:52:11
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25

Fichier

CycleKillerSIDMA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00765019, version 1
  • ARXIV : 1112.5359

Collections

Citation

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, Society for Industrial and Applied Mathematics, 2012, 26 (4), pp.1635-1656. 〈hal-00765019〉

Partager

Métriques

Consultations de la notice

205

Téléchargements de fichiers

54