Subtree isomorphism revisited

摘要: The Subtree Isomorphism problem asks whether a given tree is contained in another tree. of fundamental importance and has been studied since the 1960s. For some variants, e.g., ordered trees, near-linear time algorithms are known, but for general case truly subquadratic remain elusive.Our first result reduction from Orthogonal Vectors to Isomorphism, showing that algorithm latter refutes Strong Exponential Time Hypothesis (SETH).In light this conditional lower bound, we focus on natural special cases which no known. We classify these against quadratic barrier, particular that:• Even binary, rooted SETH.• trees depth O(log log n), where n total number vertices, every constant d, there ed> 0 randomized, degree-d at most (1+ ed) logdn. In particular, an O(min l 2.85h ,n2 r) binary h.Our reductions utilize new “tree gadgets” likely useful future SETH-based bounds problems trees. Our upper apply folklore randomized decision complexity.