7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, I did not expect it would be that easy! Great, thanks. :) $\endgroup$ – Jukka Suomela Dec 18 '15 at 18:24
  • $\begingroup$ 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. $\endgroup$ – Jukka Suomela Dec 19 '15 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.