title: On Determining if Tree-based Networks Contain Fixed Trees.
abstract: We address an open question of Francis and Steel about phylogenetic networks and trees. They give a polynomial time algorithm to decide if a phylogenetic network, N, is tree-based and pose the problem: given a fixed tree T and network N, is N based on T? We show that it is [Formula: see text]-hard to decide, by reduction from 3-Dimensional Matching (3DM) and further that the problem is fixed-parameter tractable.
authors.affiliation: Queensborough Community College, City University of New York (CUNY), Bayside, NY, USA.
authors.forename: Maria
authors.initials: M
authors.lastname: Anaya
authors.affiliation: City College of New York, City University of New York (CUNY), New York, NY, USA.
authors.forename: Olga
authors.initials: O
authors.lastname: Anipchenko-Ulaj
authors.affiliation: Queensborough Community College, City University of New York (CUNY), Bayside, NY, USA.
authors.forename: Aisha
authors.initials: A
authors.lastname: Ashfaq
authors.affiliation: Brooklyn College, City University of New York (CUNY), Brooklyn, NY, USA.
authors.forename: Joyce
authors.initials: J
authors.lastname: Chiu
authors.affiliation: Department of Mathematics and Computer Science, Lehman College, City University of New York (CUNY), Bronx, NY, 10468, USA.
authors.forename: Mahedi
authors.initials: M
authors.lastname: Kaiser
authors.affiliation: Brooklyn College, City University of New York (CUNY), Brooklyn, NY, USA.
authors.forename: Max Shoji
authors.initials: MS
authors.lastname: Ohsawa
authors.affiliation: Department of Mathematics and Computer Science, Lehman College, City University of New York (CUNY), Bronx, NY, 10468, USA. megan.owen@lehman.cuny.edu.
authors.forename: Megan
authors.identifier: 0000-0003-2418-5268
authors.initials: M
authors.lastname: Owen
authors.affiliation: Sarah Lawrence College, Bronxville, NY, USA.
authors.forename: Ella
authors.initials: E
authors.lastname: Pavlechko
authors.affiliation: Department of Mathematics and Computer Science, Lehman College, City University of New York (CUNY), Bronx, NY, 10468, USA.|Division of Invertebrate Zoology, American Museum of Natural History, New York, NY, 10024, USA.
authors.forename: Katherine
authors.initials: K
authors.lastname: St John
authors.affiliation: Brooklyn College, City University of New York (CUNY), Brooklyn, NY, USA.
authors.forename: Shivam
authors.initials: S
authors.lastname: Suleria
authors.affiliation: College of Staten Island, City University of New York (CUNY), Staten Island, NY, USA.
authors.forename: Keith
authors.initials: K
authors.lastname: Thompson
authors.affiliation: Sarah Lawrence College, Bronxville, NY, USA.
authors.forename: Corrine
authors.initials: C
authors.lastname: Yap
mesh_terms: D000465:Algorithms; D019143:Evolution, Molecular; D055641:Mathematical Concepts; D008957:Models, Genetic; D010802:Phylogeny
keywords: 3-Dimensional Matching; Analysis of algorithms; Phylogenetic network; Phylogenetic tree