# Largest Common Subtree (Graph Isomorphism Problem)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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

## 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