Edit distance between two partitions
This problem can be transformed into the assignment problem, also known as maximum weighted bipartite matching problem.

Note first that the edit distance equals the number of elements which need to change from one set to another.  This equals the total number of elements minus the number of elements which do not need to change.  So finding the minimum number of elements which do not change is equivalent to finding the maximum number of vertices that do not change.

Let $A = \{ A_1, A_2, ..., A_k \}$ and $B = \{ B_1, B_2, ..., B_l \}$ be partitions of $[1, 2, ..., n]$.  Also, without loss of generality, let $k \ge l$ (allowed because $edit(A, B) = edit(B, A)$).  Then let $B_{l+1}$, $B_{l+2}$, ..., $B_k$ all be the empty set.  Then the maximum number of vertices that do not change is:

$\max_f \sum_{i=1}^k |A_i \cap B_{f(i)} |$

where $f$ is a permutation of $[1, 2, ..., k]$.

This is exactly the assignment problem where the vertices are $A_1$, ..., $A_k$, $B_1$, ..., $B_k$ and the edges are pairs $(A_i, B_j)$ with weight $|A_i \cap B_j|$.  This can be solved in $O(|V|^2 \log |V| + |V||E|)$ time.