1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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)$. $\endgroup$
    – YCor
    Feb 1, 2019 at 19:20
  • 1
    $\begingroup$ 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)$?" $\endgroup$
    – YCor
    Feb 1, 2019 at 23:01

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.