problem: find the largest common isomorphic subtree of two trees.

Let’s call the trees vertex sets \(A,B\). If all the trees in question were binary trees, the simple DP solution would be: for each pair of vertices \(a,b\in A \times B\), store the largest common subtree of \(T_a, T_b\) rooted at \(a,b\) respectively, where \(T_a,T_b\) are the subtrees rooted at \(a,b\). Then, to compute a DP-value for a new pair \(x,y\), given the value for all of their children, we simply take the max over both ways of pairing their children.

Then, at the end, we can scan the vertices to find which vertex we should root the tree at. This solution is great! It runs in time \(|A||B|.\)

But this isn’t the problem we want to solve. We want to solve it for arbitrary trees. Which can have large degree on some vertices.

Now a naive DP will use \(d!\) time per DP update by trying all the permutations.

But there is a clever save! We can do a flow-based maximum matching instead of checking all permutations. This is super cool