<p>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:</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-18T18:24:58.890Z
Oh, I did not expect it would be _that_ easy! Great, thanks. :)
Jukka Suomela
CC BY-SA 3.0
2015-12-19T23:48:45.433Z
Apparently the same approach works for any kind of rooted trees, not just binary trees. For each candidate pair of parents, we can simply use max-weight bipartite matching to find the best mapping between their children. And we can plug in any penalty function for unmatched branches.
Jukka Suomela
CC BY-SA 3.0
2015-12-18T15:39:31.760Z
2015-12-18T17:14:42.097Z
2015-12-18T17:14:42.097Z
Topi Talvitie
<p>Does anyone recognise the following problems? Do they have names? Are they hard?</p>
<p>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?</p>
<h2>Variant 1</h2>
<p><strong>Input:</strong></p>
<ul>
<li>A rooted perfect full binary tree <span class="math-container">$T$</span> with <span class="math-container">$2^k-1$</span> nodes; let <span class="math-container">$V$</span> be the set of nodes.</li>
<li>Functions <span class="math-container">$x\colon V\to \{0,1\}$</span> and <span class="math-container">$y\colon V\to \{0,1\}$</span>.</li>
</ul>
<p><strong>Output:</strong></p>
<ul>
<li>Automorphism <span class="math-container">$f\colon V \to V$</span> of tree <span class="math-container">$T$</span> that minimises the number of nodes <span class="math-container">$v \in V$</span> with <span class="math-container">$x(v) \ne y(f(v))$</span> — these are called <em>mismatches</em>.</li>
</ul>
<p>Put otherwise, the task is to find a labelling <span class="math-container">$x'$</span> such that <span class="math-container">$x'$</span> is as close to <span class="math-container">$x$</span> as possible (minimise the number of elements that differ) and the labelled trees <span class="math-container">$(T,x')$</span> and <span class="math-container">$(T,y)$</span> are isomorphic.</p>
<h2>Variant 2</h2>
<p>The same as above, but only leaf nodes can have non-zero labels.</p>

<ds.algorithms><reference-request><optimization><tree><binary-trees>
Inexact labelled binary tree matching
Jukka Suomela
# Inexact labelled binary tree matching

(Asked by: username_0 on 2015-12-12)

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.

**Tags:** ds.algorithms, reference-request, optimization, tree, binary-trees

---

## 1 answers

### Answer by username_1 on 2015-12-18. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: Oh, I did not expect it would be _that_ easy! Great, thanks. :)  
> **username_0**: Apparently the same approach works for any kind of rooted trees, not just binary trees. For each candidate pair of parents, we can simply use max-weight bipartite matching to find the best mapping between their children. And we can plug in any penalty function for unmatched branches.  

---

