Covering tree with stars

Jan Baumbach, Jiong Guo, Rashid Ibragimov

Research output: Contribution to journalJournal articleResearchpeer-review


We study the tree edit distance problem with edge deletions and edge insertions as edit operations. We reformulate a special case of this problem as Covering Tree with Stars (CTS): given a tree T and a set of stars, can we connect the stars in by adding edges between them such that the resulting tree is isomorphic to T? We prove that in the general setting, CST is NP-complete, which implies that the tree edit distance considered here is also NP-hard, even when both input trees having diameters bounded by 10. We also show that, when the number of distinct stars is bounded by a constant k, CTS can be solved in polynomial time by presenting a dynamic programming algorithm running in time. © 2013 Springer-Verlag Berlin Heidelberg.
Original languageEnglish
JournalJournal of Combinatorial Optimization
Issue number1
Pages (from-to)141-152
Publication statusPublished - 2015


Cite this