Reduction from OV to Subtree Isomorphism

FROM: OV TO: Subtree Isomorphism

Implications

assume: OVH
then: for all $d \geq {2}$, target on two rooted unordered trees of size $O(n)$, degree $d$, and height $h \leq {2}\log_d n + O(\log \log n)$ cannot be solved in truly subquadratic $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.

https://dl.acm.org/doi/pdf/10.1145/3093239