Largest Common Subtree (Graph Isomorphism Problem)
Jump to navigation
Jump to search
Description
Find a largest tree which occurs as a common subgraph in a given collection of trees.
Related Problems
Generalizations: Graph Isomorphism, General Graphs
Subproblem: Subtree Isomorphism
Related: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences
Parameters
$n$: number of vertices in the largest tree in the collection
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| McKay | 1981 | $O((m1 + m2)n^{3} + m2 n^{2} L)$ | ${2}mn+{10}n+m+(m+{4})K+{2}mL$ | Exact | Deterministic | Time |
| Schmidt & Druffel | 1976 | $O(n*n!)$ | $O(n^{2})$ | Exact | Deterministic | Time |
| Babai | 2017 | {2}^{$O(\log n)$^3} | Exact | Deterministic | Time |
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| OV | 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 |
2018 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/3093239 | link |