The complexity on calculation of the Graev metric on the free Boolean group of a metric space

Question

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.

Answer 1

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. This paper cites some other papers which suggest it should be solvable in $O(|A \oplus B|^3)$ time at worst.