Subtree Isomorphism Revisited
Subtree Isomorphism Revisited
复制标题
重温子树同构
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Or Zamir
中科院分区：
文献类型：
--
作者：
Amir Abboud;A. Backurs;Thomas Dueholm Hansen;V. V. Williams;Or Zamir
子树同构问题是指一棵给定的树是否包含在另一棵给定的树中。这个问题具有根本性的重要性，自20世纪60年代以来一直在研究。对于一些变体，例如有序树，近线性时间算法是已知的，但对于一般情况，真正的次二次算法仍然难以捉摸。我们的第一个结果是从正交向量问题归结为子树同构，表明后者的一个真正的次二次算法驳斥了强指数时间假设(SEH)。根据这个条件下界，我们将重点放在没有真正的次二次算法已知的自然特殊情况下。我们针对二次障碍对这些情况进行了分类，特别表明：·即使对于有根的二叉树，一个真正的次二次算法也反驳了Seth。·即使对于深度为O(Loglogn)的根树(其中n是顶点总数)，一个真正的次二次算法也反驳了Seth。对于每个常数d，都有一个常数εd>；0和一个随机化的、真正的次二次算法，以求深度至多(1+εd)logDn的d次根树。特别地，对于深度为h的二叉树，有一个O(min{2.85h，n2})算法。我们的简化利用了新的“树小工具”，这些小工具可能对未来基于Seth的树问题的下界有用。我们的上界应用了来自随机决策树复杂性的民俗结果。
The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is 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 the general case truly subquadratic algorithms remain elusive. Our first result is a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the Strong Exponential Time Hypothesis (SETH). In light of this conditional lower bound, we focus on natural special cases for which no truly subquadratic algorithms are known. We classify these cases against the quadratic barrier, showing in particular that: • Even for binary, rooted trees, a truly subquadratic algorithm refutes SETH. • Even for rooted trees of depth O(log log n), where n is the total number of vertices, a truly subquadratic algorithm refutes SETH. • For every constant d, there is a constant εd> 0 and a randomized, truly subquadratic algorithm for degree-d rooted trees of depth at most (1+ εd) logdn. In particular, there is an O(min { 2.85h ,n2 }) algorithm for binary trees of depth h. Our reductions utilize new “tree gadgets” that are likely useful for future SETH-based lower bounds for problems on trees. Our upper bounds apply a folklore result from randomized decision tree complexity.