COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > On the Complexity of the Quartet Challenge

## On the Complexity of the Quartet ChallengeAdd to your list(s) Download to your calendar using vCal - Linz, S (Tbingen)
- Monday 20 June 2011, 12:10-12:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Phylogenetics A collection of quartets (unrooted phylogenetic trees on four taxa) is compatible if there exists a phylogenetic tree that explains all ancestral relationships given by the quartets. It is well-known that deciding whether or not a set of quartets is compatible is an NP-complete problem. A natural extension of this problem asks if, given a phylogenetic tree T that is compatible with the input, is T the only such tree. Several graph-theoretic characterizations have been established to approach this problem, which is known as the Quartet Challenge. However, the complexity of this challenge remains open. In this talk, we show that the Quartet Challenge is ASP -complete (i.e. it is computationally hard to decide whether another solution exists) by using a particular type of polynomial-time reduction from a variation of the Betweenness problem. This is joint work with Maria Luisa Bonet (UPC, Spain) and Katherine St. John (CUNY, USA ). This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsCavendish Graduate Student Conference 2010 Inference Group Maths Knowledge Transfer## Other talksCambridge - Corporate Finance Theory Symposium September 2018 - Day 2 Frontiers in paediatric cancer research Neurodevelopment disorders of genetic origin – what can we learn? A continuum theory for the fractures in brittle and ductile solids Cellular recycling: role of autophagy in aging and disease High-Dimensional Collocation for Lognormal Diffusion Problems |