On the Complexity of the Quartet Challenge
20 mins 44 secs,
86.40 MB,
Flash Video
484x272,
29.97 fps,
44100 Hz,
568.98 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Linz, S (Tübingen)
Monday 20 June 2011, 12:10-12:30 |
|---|
| Created: | 2011-06-23 16:50 | ||||
|---|---|---|---|---|---|
| Collection: | Phylogenetics | ||||
| Publisher: | Isaac Newton Institute | ||||
| Copyright: | Linz, S | ||||
| Language: | eng (English) | ||||
| Distribution: |
World
(downloadable)
|
||||
| Credits: |
|
||||
| Explicit content: | No | ||||
| Aspect Ratio: | 16:9 | ||||
| Screencast: | No | ||||
| Bumper: | UCS Default | ||||
| Trailer: | UCS Default | ||||
| Abstract: | 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). |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.85 Mbits/sec | 287.70 MB | View | Download | |
| WebM | 640x360 | 664.63 kbits/sec | 100.60 MB | View | Download | |
| Flash Video * | 484x272 | 568.98 kbits/sec | 86.40 MB | View | Download | |
| iPod Video | 480x270 | 506.47 kbits/sec | 76.91 MB | View | Download | |
| MP3 | 44100 Hz | 125.06 kbits/sec | 18.79 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||