Tuesday, January 08, 2008

Study progress - [JKL01-SICOMP]

為了加強對於 quartet consistency 的背景知識,我正研讀 Tao Jiang et al. 的 paper:

T. Jiang, P. Kearney, and M. Li: A polynomial time approximation scheme for inferring evolutionary trees from quartet topologies and its application. SIAM J. Comput. 30 (2001) 1942--1961. [link]

這篇 paper 主要是介紹 MQC (maximum quartet consistency) 問題的一個 PTAS,以及重要的技巧: quartet cleaning。目前為止,我覺得這篇 paper 蠻容易懂的,希望不是假象。

至於之前研讀的 "The complexity of reconstructing trees from qualitative characters and subtrees" by M. Steel,符號和文句都不容易理解,但其實它最主要的貢獻也只在證明 (incomplete) MQC (MQI; minimum quartet inconsistency) 問題為 NPC,所以我想大概看看就可以了。

在讀了 related work 之後,我才驚覺我可能搞錯了某些觀念。當 input Q 不一定為 complete 時, M. Steel 證明了 MQC 為 NPC,於是可以得到 MQI 也為 NPC。但是當 input 為 complete 時,MQC 和 MQI 問題亦為 NPC,這個結果是由 V. Berry, T. Jiang, P. Kearney, M. Li 與 T. Wareham 在 ESA'99 (proceedings of the 7th Annual European Symposium on Algorithms) 共同發表的文章中提到的,因此並不是 M. Steel 證明的。

No comments: