Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set

DOI10.1137/120864350MaRDI QIDQ4915192zbMATH OpenOpenAlexFDO

Authors Steven Kelk, Leo Van Iersel, Nela Lekić, Simone Linz, Celine Scornavacca, L. Stougie

Publication date 9 April 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.5359

zbMATH Keywords

approximationdirected feedback vertex sethybridization numberphylogenetic networks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Approximation algorithms (68W25) Combinatorial optimization (90C27) Taxonomy, cladistics, statistics in mathematical biology (92B10)

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.

Recommendations

• On the Cycle Polytope of a Directed Graph and Its Relaxations
• On the cycle polytope of a directed graph and its relaxations
• An introduction to competition-directed-cycle numbers of graphs
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• On cycle packings and feedback vertex sets
• A polynomial-time approximation scheme for embedding hypergraph in a cycle
• Approximating minimum feedback vertex sets in hypergraphs
• Improved approximation algorithms for embedding hyperedges in a cycle
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

Cited in

(11)

• Reconstruction of LGT networks from tri-LGT-nets
• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Deciding the existence of a cherry-picking sequence is hard on two trees
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• A quadratic kernel for computing the hybridization number of multiple trees
• Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
• Hybridization number on three rooted binary trees is EPT
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies
• Better practical algorithms for rSPR distance and hybridization number
• A tight kernel for computing the tree bisection and reconnection distance between two phylogenetic trees

This page was built for publication: Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4915192)