title: The complexity of finding multiple solutions to betweenness and quartet compatibility.
abstract: We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of BETWEENNESS, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that QUARTET COMPATIBILITY, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel’s QUARTET CHALLENGE, which asks whether a solution to QUARTET COMPATIBILITY is unique, is coNP-complete.
authors.affiliation: Universitat Politecnica de Catalunya (UPC), Barcelona.
authors.forename: Maria Luisa
authors.initials: ML
authors.lastname: Bonet
authors.forename: Simone
authors.initials: S
authors.lastname: Linz
authors.forename: Katherine
authors.initials: K
authors.lastname: St John
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D010802:Phylogeny