BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On the Complexity of the Quartet Challenge - Linz\, S (Tbingen)
DTSTART:20110620T111000Z
DTEND:20110620T113000Z
UID:TALK31789@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION: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 decid
 ing whether or not a set of quartets is compatible is an NP-complete probl
 em.  A natural extension of this problem asks if\, given a phylogenetic tr
 ee 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 complexit
 y 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 wheth
 er 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).\
 n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR