Consider an undirected graph on $n$ Euclidean points distributed uniformly at random in the unit square.
A monopartite Euclidean matching is an independent edge set of this graph. A perfect monopartite Euclidean matching is one where the matching contains all $n$ distinct vertices.
Sometimes Auction algorithms are used to find a matching of minimal Euclidean length (the sum of Euclidean edge lengths is minimal over all possible matchings). But this only works for bipartite graphs.
If any vertex may be paired with any other, such as in a monopartite matching, where a set is matched with itself, can an Auction algorithm still be used?
I had thought you would have to start an auction at some point, and let it spread like a branching process throughout the graph, with conflicts resolved somehow. But is there a known technique?
This is an example matching in the bipartite case:
