Reduction from OV to Largest Common Subtree
Jump to navigation
Jump to search
FROM: OV TO: Largest Common Subtree
Description
Implications
assume: OVH
then: for all constants $d \geq {2}$, target on two rooted trees of size at most $n$, degree $d$, and height $h \leq \log_d n + O(\log \log n)$ cannot be solved in truly subquadtratic $O(n^{2-\epsilon})$ time
Year
2018
Reference
Abboud, A., Backurs, A., Hansen, T. D., Vassilevska Williams, V., & Zamir, O. (2018). Subtree isomorphism revisited. ACM Transactions on Algorithms (TALG), 14(3), 1-23.