Algorithm for finding optimal node pairs in hexagonal graph

Question

I'm searching for an algorithm to find pairs of adjacent nodes on a hexagonal (honeycomb) graph that minimizes a cost function.

• each node is connected to three adjacent nodes
• each node "i" should be paired with exactly one neighbor node "j".

• each pair of nodes defines a cost function

  c = pairCost( i, j )

• The total cost is then computed as

  totalCost = 1/2 sum_{i=1:N} ( pairCost(i, pair(i) ) )

Where pair(i) returns the index of the node that "i" is paired with. (The sum is divided by two because the sum counts each node twice). My question is, how do I find node pairs that minimize the totalCost?

The linked image should make it clearer what a solution would look like (thick red line indicates a pairing):

Some further notes:

• I don't really care about the outmost nodes
• My cost function is something like || v(i) - v(j) || (distance between vectors associated with the nodes)
• I'm guessing the problem might be NP-hard, but I don't really need the truly optimal solution, a good one would suffice.
• Naive algos tend to get nodes that are "locked in", i.e. all their neighbors are taken.

Note: I'm not familiar with the usual nomenclature in this field (is it graph theory?). If you could help with that, then maybe that could enable me to search for a solution in the literature.

Answer 1

This is an instance of the maximum weight matching problem in a general graph - of course you'll have to negate your weights to make it a minimum weight matching problem. Edmonds's paths, trees and flowers algorithm (Wikipedia link) solves this for you (there is also a public Python implementation). The naive implementation is O(n⁴) for n vertices, but it can be pushed down to O(n^1/2m) for n vertices and m edges using the algorithm of Micali and Vazirani (sorry, couldn't find a PDF for that).