Covering tree with stars
Tóm tắt
We study the tree edit distance (TED) 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
$$\mathcal {S}$$
of stars, can we connect the stars in
$$\mathcal {S}$$
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 TED considered here is also NP-hard, even when both input trees have 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
$$O(|V(T)|^2\cdot k\cdot |V(\mathcal{S})|^{2k})$$
time.
Tài liệu tham khảo
Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading
Akutsu T (2010) Tree edit distance problems: algorithms and applications to bioinformatics. IEICE Trans Inf Syst 93:208–218
Akutsu T, Fukagawa D, Takasu A, Tamura T (2011) Exact algorithms for computing the tree edit distance between unordered trees. Theor Comput Sci 412(4–5):352–364
Bille P (2005) A survey on tree edit distance and related problems. Theor Comput Sci 337(1–3):217–239
Blin G, Sikora F, Vialette S (2010) Querying graphs in protein–protein interactions networks using feedback vertex set. IEEE/ACM Trans Comput Biol Bioinform 7(4):628–635
Bunke H, Riesen K (2009) Graph edit distance—optimal and suboptimal algorithms with applications. Wiley-VCH Verlag GmbH and Co. KGaA, Weinheim
Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. IJPRAI 18(3):265–298
Demaine E, Mozes S, Rossman B, Weimann O (2007) An optimal decomposition algorithm for tree edit distance. In: Automata, , languages and programming. Lecture notes in computer science, vol 4596. Springer, Berlin, pp 146–157
Gao X, Xiao B, Tao D, Li X (2010) A survey of graph edit distance. Pattern Anal Appl 13(1):113–129
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco
Kirkpatrick DG, Hell P (1978) On the completeness of a generalized matching problem. In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC’78. ACM, New York, pp 240–245
Natanzon A, Shamir R, Sharan R (2001) Complexity classification of some edge modification problems. Discret Appl Math 113(1):109–128
Pawlik M, Augsten N (2011) RTED: a robust algorithm for the tree edit distance. PVLDB 5(4):334–345
Sharan R (2002) Graph modification problems and their applications to genomic research. PhD Thesis, Tel-Aviv University
Zhang K, Jiang T (1994) Some MAX SNP-hard results concerning unordered labeled trees. Inf Process Lett 49(5):249–254
Zhang K, Statman R, Shasha D (1992) On the editing distance between unordered labeled trees. Inf Process Lett 42(3):133–139