{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:40:09Z","timestamp":1787337609683,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>\n                    Given a set of species and their similarity data, an important problem in evolutionary biology is how to reconstruct a phylogeny (also called evolutionary tree) so that species are close in the phylogeny if and only if they have high similarity. Assume that the similarity data are represented as a graph G = (V, E), where each vertex represents a species and two vertices are adjacent if they represent species of high similarity. The phylogeny reconstruction problem can then be abstracted as the problem of finding a (phylogenetic) tree T from the given graph G such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) $(u, v) \\in E$ if and only if $d_T(u, v) \\le k$ for some fixed threshold k, where d\n                    <jats:sub>T<\/jats:sub>\n                    (u,v) denotes the distance between u and v in tree T. This is called the phylogenetic kth root problem (PRk), and such a tree T, if it exists, is called a phylogenetic kth root of graph G. The computational complexity of PRk} is open, except for $k \\le 4$. In this paper, we investigate PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. Our main contribution is a linear-time algorithm that determines if G has such a phylogenetic kth root, and if so, demonstrates one. On the other hand, because in practice the collected similarity data are usually not perfect and may contain errors, we propose to study a generalized version of PRk where the output phylogeny is required only to be an approximate root of the input graph. We show that this and other related problems are computationally intractable.\n                  <\/jats:p>","DOI":"10.1137\/s0097539701389154","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"864-879","source":"Crossref","is-referenced-by-count":40,"title":["Computing Phylogenetic Roots with Bounded Degrees and Errors"],"prefix":"10.1137","volume":"32","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Hans Bodlaender, NC\u2010algorithms for graphs with small treewidth, Lecture Notes in Comput. Sci., Vol. 344, Springer, Berlin, 1989, 1\u2013101024836","DOI":"10.1007\/3-540-50728-0_32"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"R3","unstructured":"Z.\u2010Z. Chen, T. Jiang, and G.\u2010H. Lin,\n                      Computing Phylogenetic Roots with Bounded Degrees and Errors\n                      , Technical Report TR03\u201006, Department of Computing Science, University of Alberta, 2003."},{"key":"R4","unstructured":"T. Jiang, G.\u2010H. Lin, and J. Xu,\n                      On the Closest Tree kth Root Problem\n                      , manuscript, Department of Computer Science, University of Waterloo, 2000."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.9999"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289116"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Guo\u2010Hui Lin, Paul Kearney, Tao Jiang, Phylogenetic k\u2010root and Steiner k\u2010root, Lecture Notes in Comput. Sci., Vol. 1969, Springer, Berlin, 2000, 539\u20135512002i:68094","DOI":"10.1007\/3-540-40996-3_46"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019120016X"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00023-9"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Naomi Nishimura, Prabhakar Ragde, Dimitrios Thilikos, On graph powers for leaf\u2010labeled trees, Lecture Notes in Comput. Sci., Vol. 1851, Springer, Berlin, 2000, 125\u20131382001f:05139","DOI":"10.1007\/3-540-44985-X_12"},{"key":"R12","unstructured":"D. L. Swofford, G. J. Olsen, P. J. Waddell, and D. M. Hillis,\n                      Phylogenetic inference\n                      , in Molecular Systematics, 2nd ed., D. M. Hillis, C. Moritz, and B. K. Mable, eds., Sinauer Associates, Sunderland, MA, 1996, pp. 407\u2013514."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539701389154","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:58Z","timestamp":1787336398000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539701389154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0097539701389154"],"URL":"https:\/\/doi.org\/10.1137\/s0097539701389154","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}