For a set $X$ by $B(X)$ we denote the family of all finite subsets of $X$ endowed with the operation $\oplus$ of symmetric difference. This operation turns $B(X)$ into a Boolean group, which can be identified with the free Boolean group over $X$.


Let us recall that a group is *Boolean* if each its element has order at most 2.


The group $B(X)$ contains a subgroup $B\_0(X)$ of index two, consisting of sets of even cardinality. 


Each metric $d$ on $X$ determines the *Graev metric* $\hat d$ on $B\_0(X)$ defined as 
$$\hat d(A,B)=\inf\sum\_{i=1}^kd(x\_i,y\_i)$$ where the infimum is taken over all partitions of the symmetric difference $A\oplus B$ into pairwise disjoint doubletons $\{x\_1,y\_1\},\dots,\{x\_k,y\_k\}$.


This definition suggests a brute force algorithm for calculation of the Graev distance $\hat d(A,B)$: Let $k=\frac12|A\oplus B|$ and compare the sums for all possible $\frac{(2k)!}{2^kk!}$ partitions of $A\oplus B$ into $k$ doubletons. 


Unfortunately such algorithm has (more than) exponential complexity.



> 
> **Question.** Is there a more simple (for example, polynomial time) algorithm for calculating the Graev distance on $B\_0(X)$?
> 
> 
> 


**Remark.** It seems that the naive approach (to find the shortest doubleton in $A\oplus B$, delete it, find next shortest etc), does not work.



The complexity on calculation of the Graev metric on the free Boolean group of a metric space
If I understand the problem correctly, then based on YCor's comment, your problem is equivalent to finding a minimum-weight perfect matching on $A \oplus B$, where the weights are given by the metric. If so, then a version of Edmond's "blossom algorithm" should be able to solve it in polynomial time.


Check out Kolmogorov's [Blossom V: A new implementation of a minimum cost perfect matching algorithm](http://pub.ist.ac.at/~vnk/papers/blossom5.pdf). This paper cites some other papers which suggest it should be solvable in $O(|A \oplus B|^3)$ time at worst.


