{"entities":{"Q1682616":{"pageid":1693357,"ns":120,"title":"Item:Q1682616","lastrevid":71184492,"modified":"2026-04-13T20:08:23Z","type":"item","id":"Q1682616","labels":{"en":{"language":"en","value":"On the complexity of computing MP distance between binary phylogenetic trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6814142"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$896EC304-8197-497E-AF87-61F55E26C5C4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"09fc9f377d9cb8a0dd50bf1a922a25c72f4029ca","datavalue":{"value":{"text":"On the complexity of computing MP distance between binary phylogenetic trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1682616$EACCE502-D2D9-441F-BF79-8AB33284EF1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b53783ac3a6302d24ac623768a3d73194e91a662","datavalue":{"value":"1380.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$C12916DB-9389-4C2F-82D8-AA9984C84B44","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb78bde6986234ab8c5e29bd67bd9dfbc4fa3355","datavalue":{"value":{"entity-type":"item","numeric-id":259723,"id":"Q259723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$8726EE93-B388-4BC5-B6F0-DE8EC4C8ACCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"69a84022b0dcc717fd5cc339b3497499a0349f35","datavalue":{"value":{"entity-type":"item","numeric-id":120015,"id":"Q120015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$F195AA67-8670-4360-A4BC-4A28E77F26A0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"710cc084d2ed0d09beceb5d2d7c52611268d6193","datavalue":{"value":{"entity-type":"item","numeric-id":159225,"id":"Q159225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$1B2D45DD-150D-4AA3-B4B1-9A38F3B9CE7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28d31949957a358834adbb14abf4b54da4205a45","datavalue":{"value":{"time":"+2017-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1682616$A3E012C9-DE95-4BEF-AEB3-7B7BE9DE897C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3a2e83f13fe14e97e8bcd3e5f8132023f9be9251","datavalue":{"value":"https://arxiv.org/abs/1412.4076","type":"string"},"datatype":"url"},"type":"statement","id":"Q1682616$30B5F1A4-8774-46A5-AF0B-DB66EB952D4B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ad11f868e9aec466ccdd02792f49ed4f5ac791d","datavalue":{"value":"Distance based measures are used to quantify the dissimilarity of two trees in Phylogenetics. Maximum Parsimony distance (MP-distance) is a recent addition to those measures. The MP-distance requires the search for a character which has a low parsimony score on one of the trees involved and a high score on the other one. In this article, authors show that the computation of the MP-distance on two Phylogenetic binary trees is NP-hard.  A rooted phylogenetic \\(X\\)-tree is a rooted tree \\(T=(V(T),E(T))\\) on a leaf set \\(X=\\{1,2,\\dots,n\\}\\subset V(T)\\). A character \\(f\\) is a function \\(f:X\\to \\mathcal{C}\\), where \\(\\mathcal{C}\\) is a set \\(\\{c_1,c_2,c_3,\\ldots, c_k\\}\\) of \\(k\\) character states, \\(k\\) being a positive integer. If \\(|f(X)|=r\\), then \\(f\\) is said to be an \\(r\\)-state character. An extension of a character \\(f\\) to \\(V(T)\\) is a map \\(g:V(T)\\to \\mathcal{C}\\) such that \\(g(i)=f(i)\\) for all \\(i\\in X\\). The parsimony score or parsimony length of a character \\(f\\) on \\(T\\), denoted by \\(l_f(T)\\), is obtained by minimizing \\(l_g(T)\\) over all possible extensions \\(g\\) of \\(f\\).  The maximum parsimony distance \\(d_{MP}\\) of two phylogenetic trees \\(T_1\\) and \\(T_2\\) on the same set \\(X\\) is defined as \\(d_{MP}(T_1,T_2)=\\max_f\\{|l_f(T_1)-l_f(T_2)|\\}\\), where this maximum is taken over all characters \\(f\\) on \\(X\\). With the help of an interesting symmetry breaking construction, a couple of lemmas and an observation, authors establish that the computation of \\(d_{MP}(T_1,T_2)\\) on binary trees is NP-hard. The proof of this result is pretty lengthy, logical and intuitive and progress by constructing will construct two trees \\(T_E\\) and \\(T_V\\) such that, for a certain integer \\(P\\), \\(d_{MP}(T_E,T_V)=P\\) if and only if \\(\\chi^\\prime(G)=3\\), and the authors establish many interesting properties on the phylogenetic trees \\(T_E\\) and \\(T_V\\).  Following this result, the authors also prove that the computation of \\(d^2_{MP}(T_1,T_2)\\) is also NP-hard in a similar way and also show that computation of \\(d^2_{MP}(T_1,T_2)\\) is APX-hard as well. In the final section, the authors also present an integer linear programming formulation for binary instances.  The article is well-written, innovative and interesting. As mentioned earlier, the content of this paper is logical, intuitive and presented sequentially in brilliant manner. The authors deserve much appreciation for the preparation of such a marvellous paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1682616$D5ED22DA-06B4-4090-B3BA-71078823380F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$FCB8742D-F3CF-47A2-B156-AF104C16F795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$EEC820BF-1884-4490-81DE-ED2CE2960F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$DEFFCD03-5EDF-4CBB-B23E-C29AC3327104","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$DC987062-8BAF-4C45-BD43-92BCACB5FAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"628b6504534c9c491a1aed9f9fa031e89a793c1f","datavalue":{"value":"92D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$4A972FA3-87DC-40FC-94E9-88D00AB651F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$C5227DE6-F704-42E9-A45C-45EBDD0B86A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a88c6410389484131d98be964ac00646e17e8a9d","datavalue":{"value":"6814142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$64AD028B-67F3-438A-B805-C479A016814D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1dc3dddd1072953193ad279b802561a3faee80d4","datavalue":{"value":"maximum parsimony distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1682616$7F1B79B4-F127-4895-8053-326B91A5F177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e93111d6d30bf1467281dfe51817a0e43ca91c69","datavalue":{"value":"phylogenetics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1682616$ED2777C4-0C49-4CCC-8682-863160B21FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cfab7320641965853a62ff5e5c00f87e266c99b","datavalue":{"value":"binary trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1682616$8B8A2EEE-707F-4C39-ABF2-E6FD11FFE94A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1682616$B8CE94B2-3D89-4A86-B637-82B8A98601D6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$C78090F2-9B90-4826-BF4C-C33E81559077","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e384ade0c1a26ebe1e1acd17b8b2da9ea7d26015","datavalue":{"value":"W2962870195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$54E4A29D-306A-4277-94A5-6F36D45B5F20","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"44b77e4bff3cee7284c15badad37f347df6aefaa","datavalue":{"value":"Q59528943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$3711F817-F158-4E4A-A409-38E916158FF0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f44a76b5719daa58c59d178eeffb178e71bb9e","datavalue":{"value":{"entity-type":"item","numeric-id":1566710,"id":"Q1566710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$C4AB07D6-7644-4B01-A0CB-18355BB32AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc38dff52c1e7b4e85f991fca6d86203f0ab452c","datavalue":{"value":{"entity-type":"item","numeric-id":1764471,"id":"Q1764471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$238C1B1B-EF86-4963-9488-F3C233326476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$21EF9D16-A12C-4A34-B9DB-C44415C77770","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3a382ef19b67eac53ba93f1005e6fa2ed0da35a","datavalue":{"value":{"entity-type":"item","numeric-id":259724,"id":"Q259724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$47BA79F7-966A-4CDF-B6EC-859E69AE7044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2353e9686194fd62ace9c7950ccc0878a1a03ba","datavalue":{"value":{"entity-type":"item","numeric-id":2380829,"id":"Q2380829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$D8351BFE-977E-4432-9A5C-7CD0612ADD2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"364257321cdf0a3be0da6da15b6b71e96edc9b9c","datavalue":{"value":{"entity-type":"item","numeric-id":4981700,"id":"Q4981700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$0ABAAF7F-4BFA-4155-820F-4141420AF698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$A31EB0C0-F227-4B8E-9AE1-CEB09B312875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$B696BB2D-9D31-4D3B-8744-4BB1FEE5C3D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8278f14e4411c69a61972c76cfe480f6f26c9b27","datavalue":{"value":"10.1007/S00026-017-0361-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1682616$7FFD3C99-A21E-4460-91E3-A90D90A96887","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dfb692aa7e50314c609430d6cb899d78fe35d79","datavalue":{"value":{"entity-type":"item","numeric-id":259724,"id":"Q259724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d24dfced82e7643dbeb783082f8017d9f1c71a87","datavalue":{"value":{"amount":"+0.9146391153335572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1682616$94171EC1-CB50-45A2-9D28-1D9DB09DB367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ca8da40954e476347a2f99b2ee18388f622d812","datavalue":{"value":{"entity-type":"item","numeric-id":306268,"id":"Q306268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0ffa841ff2fa4006b20b04714729ab240b0aee4","datavalue":{"value":{"amount":"+0.8564708828926086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1682616$11F4B36E-1F86-47A9-A836-07C8770CCBF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ed867486f8ebb9d258cf36c9fb6e7061f320634","datavalue":{"value":{"entity-type":"item","numeric-id":2221808,"id":"Q2221808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"376e0f6add5806b2792bcf575437637658177a5b","datavalue":{"value":{"amount":"+0.8444833159446716","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1682616$D4492DAA-8599-4377-955A-00CD72956A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3622e995b3752ef1c0fa0c8f80265a0e65a9c67b","datavalue":{"value":{"entity-type":"item","numeric-id":1764471,"id":"Q1764471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"531f202871e939717dfef49fa5cc3e0a2017125c","datavalue":{"value":{"amount":"+0.8436680436134338","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1682616$531F4CE0-4C24-4E21-B31F-3BCDE5D74912","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caeffcfe5e91f314f18956c76f37431c9d83b836","datavalue":{"value":{"entity-type":"item","numeric-id":5165594,"id":"Q5165594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2e6ed4a6553936fd24a803413d2e66458924212","datavalue":{"value":{"amount":"+0.8098831176757812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1682616$73276AF6-8CE1-4304-9364-AB1902830A49","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1682616$C900545F-5960-437F-9DBC-BDBB38F086FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of computing MP distance between binary phylogenetic trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_computing_MP_distance_between_binary_phylogenetic_trees"}}}}}