I have an unusual problem that I am struggling to solve. I have a set of nodes (with positive distances between them) that I want to connect into a single component. In particular, I want to form a minimum-distance spanning subgraph such that all its nodes have an even degree. Note that the subgraph can have multiple edges between a pair of nodes (multigraph). Below are some examples:
A) We have 8 nodes arranged in a circle, where adjacent nodes are separated by distance 1. We connect them into a single cycle of length 8.
B) The top figure shows all the possible distances. If we use the three single edges then we will have a subgraph of weight 1+1+3=5. But we can do better if we use double edges, giving us a total weight of 1+1+1+1=4 (bottom figure). Note that the center node has degree 4, but this is ok since it is still even.
C) Here all adjacent nodes are separated by distance 1. If we use double edges in the shape of the Sum sign (Sigma) then we will get a subgraph of weight 8. But we can do better by using single edges, giving us a total weight of 6.
D) Here the best way to include the top-right node is to use double edges.
I have come up with an outline for an algorithm for solving this problem, but it is not quite complete. First we compute the minimum spanning tree. This will give us some of the edges of the subgraph. It will also give us some nodes (leaves of the tree) with degree 1. We now greedily connect these nodes to their closest neighbours. This is the bit that I haven't quite worked out. Because if we always pick the closest neighbour then we will get the same edges as the MST. Clearly this will fail in A. So perhaps we want to prioritise connections to other degree-1 nodes. Also at the end of this step, we may still have some nodes with an odd-degree remaining which also need to be connected.
Any help would be greatly appreciated!
