Algorithm for finding optimal node pairs in hexagonal graph

0
votes

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):

enter image description here

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.

2
algorithmgraphcomplexity-theorymathematical-optimizationgraph-algorithm

2 Answers

1
votes

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(n4) for n vertices, but it can be pushed down to O(n1/2m) for n vertices and m edges using the algorithm of Micali and Vazirani (sorry, couldn't find a PDF for that).

0
votes

This seems related to the minimum edge cover problem, with the additional constraint that there can only be one edge per node, and that you're trying to minimize the cost rather than the number of edges. Maybe you can find some answers by searching for that phrase.

Failing that, your problem can be phrased as an integer linear programming problem, which is NP-complete, which means that you might get dreadful performance for even medium-sized problems. (This does not necessarily mean that the problem itself is NP-complete, though.)