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.