1
$\begingroup$

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.

Examples of minimum spanning subgraphs

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!

$\endgroup$
1
$\begingroup$

I just realised that example A is an instance of the Travelling Salesman Problem, which is NP-hard. So the best we can hope for is an approximation algorithm.

I also realised that this is problem is an instance of b-matching, where you want to select up to b edges incident on each node of minimal total weight. Here we have the additional constraint that b is even. I found a couple of papers that solve b-matching:

http://www.aporc.org/LNOR/10/ISORA2009F12.pdf http://proceedings.mlr.press/v15/huang11a/huang11a.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.