Maximum common edge subgraph of two trees in polynomial time? Is it possible to find a maximum common edge subgraph of two trees in polynomial time? This paper by Akutsu et al. seems to claim so in the introduction by using a maximum weight matching algorithm.
However, this paper by Grohe et al., seem to claim that computing the distance $d(G,H)$ of two trees $G,H$ is NP-hard, as shown in Theorem 3.2.
These two results are not in contradiction per se, but it seems that if they are both true then P=NP. Specifically, define $d(G,H)=\min_{\pi\in S_n}|A_G^\pi-A_H|$ where $A_G,A_H$ are the adjacency matrices of $G$ and $H$ respectively, $A^\pi$ is the matrix whose $(i,j)$ entry is $A_{\pi(i)\pi(j)}$ and $|M|$ is the Frobenius norm of $M$; namely, $|M|^2=\sum_{i,j}M_{ij}^2$. It should be easy to show that $d(G,H)^2=2(|E(G)|+|E(H)|-k)$ if, and only if, the maximum common edge subgraph has $k$ edges. Thus, if finding the maximum common edge subgraph of trees $G,H$ can be done in polynomial time, then $d(G,H)$ can also be computed in polynomial time in spite of being NP hard...
 A: The two problems are not equivalent.
Akatsu and Tamura are looking the problem of finding the maximum common connected subgraph. On the other hand, the graph distance problem in Grohe et al. is equivalent to finding the maximum common subgraph whether or not it is connected.
For further confirmation: if we look at the reduction from unary 3-partition in the proof of Theorem 8 in Grohe et al.'s paper, we see that it begins by looking at the problem for two path forests: one with $m$ paths of a fixed length $A$, and one with $3m$ paths of varying lengths $a_1, a_2, \dots, a_{3m}$ with $\frac A4 < a_i < \frac A2$ for all $i$. (Path lengths are counted by number of vertices.) To determine if there is a common subgraph with $m(A-3)$ edges, we need to check if we can partition $a_1, a_2, \dots, a_{3m}$ into $m$ triples, each adding up to $A$.
On the other hand, the maximum common connected subgraph can be found quickly: we just need to find the longest path in the second graph, and place it on top of one of the paths in the first graph.
