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

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.

• Just to streamline notation, you have $\hat{d}(A,B)=\ell(A\oplus B)$, where you can call $\ell(A)=\hat{d}(\emptyset,A)$ the Graev length of $A$. The question is about computing $\ell(A)$. – YCor Feb 1 at 19:20
• As I said, this reduces to a question with no reference to the symmetric difference and hence no group theory. It's a combinatorial optimization problem. I would rephrase more concisely the question in this way (and tag combinatorial-optimization) to hope for optimal feedback: "Let $X$ be a finite set of finite even cardinal. For every metric $d$ on $X$, define $L(d)$ as (...). How to compute $L(d)$?" – YCor Feb 1 at 23:01