Largest Common Subtree (Graph Isomorphism Problem)

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/doi/pdf/10.1145/3093239	link