Inexact labelled binary tree matching

Question

Does anyone recognise the following problems? Do they have names? Are they hard?

If we were looking for an exact match (0 mismatches), these would be solvable in polynomial time (using e.g. standard algorithms for rooted tree isomorphism). But what about the inexact case?

Variant 1

Input:

• A rooted perfect full binary tree $T$ with $2^k-1$ nodes; let $V$ be the set of nodes.
• Functions $x\colon V\to \{0,1\}$ and $y\colon V\to \{0,1\}$.

Output:

• Automorphism $f\colon V \to V$ of tree $T$ that minimises the number of nodes $v \in V$ with $x(v) \ne y(f(v))$ — these are called mismatches.

Put otherwise, the task is to find a labelling $x'$ such that $x'$ is as close to $x$ as possible (minimise the number of elements that differ) and the labelled trees $(T,x')$ and $(T,y)$ are isomorphic.

Variant 2

The same as above, but only leaf nodes can have non-zero labels.

Answer 1

I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows:

We have two $0$-$1$-labeled rooted perfect full binary trees $(A, x)$ and $(B, y)$ with $2^k-1$ nodes. We compute the minimum number of mismatches in any isomorphism between the trees denoted by $F(A, B)$ recursively by using the $F$-values of the subtrees. We have essentially two options when choosing the isomorphism: either we swap the child subtrees of the root in one of the trees or we do not swap anything. Therefore $F(X, Y)$ is obtained as a minimum of $F(X_{\text{left}}, Y_{\text{left}}) + F(X_{\text{right}}, Y_{\text{right}})$ and $F(X_{\text{left}}, Y_{\text{right}}) + F(X_{\text{right}}, Y_{\text{left}})$, increased by one if the $x$-label of the root of $X$ and the $y$-label of the root of $Y$ are distinct. If we use dynamic programming to optimize this recursion, we have to compute $F(X, Y)$ only once for every pair of subtrees $X$ and $Y$ of the original tree with equal heights.