Connect nodes to maximize total edge weight

Question

I am working on a problem which could be reduced to a graph optimization problem as below.

• A set of colored nodes is given. They are all unconnected i.e. there is no edge in the graph.

• The edges are to be inserted between the nodes.

• A node can have only 4 edges at max.

• A table provides rules for profit contribution from the edges.

  Eg.,

  • An edge connecting red to red: profit is 10

  • An edge connecting red to blue: profit is 20

• The total number of nodes is around 100.

• The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.

The problem is to optimize the connections (edges) such that the total profit is maximized.

I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.

Answer 1

You can convert this to a problem of finding a perfect matching of maximum cost, which can be solved in polynomial time (e.g. using a variant of the Blossom algorithm )

The conversion is to split each node of degree d into d left nodes and d-4 right nodes.

For each pair of vertices u,v in the original graph, add an edge between an unconnected vertex u left node and an unconnected vertex v left node of weight equivalent to the profit of joining u and v.

Next add extra edges (of weight 0) between every pair of left and right nodes (for the same vertex).

Now construct the max weight perfect matching in this new graph.

The point is that the extra edges use up all but 4 of the left nodes. This means that each vertex can only make profit from 4 of the profitable edges.

Example

Suppose we have a problem with 7 coloured nodes. I have drawn the section of the expanded graph that corresponds to the part for a single green node and a single red node.

Note that there are 6 left green nodes, one less than the total number of coloured nodes. There are 2 right green nodes, four less than the number of left nodes. There is a single curved edge joining a greenleft node and a red left node. If this curved edge is chosen in the perfect matching it means that the red node should be joined to the green node.

Answer 2

This sounds similar to the 0-1 Knapsack problem where the maximum is calculated if an item is either placed into the knapsack or is not placed into the knapsack. Here is an example:

def knapsack(numItems, capacity, sizes, values):   # if no more items left to put in knapsack or knapsack is full   if (numItems == 0 or capacity == 0):     return 0    # if can't fit item into knapsack, try the next item   if (sizes[numItems-1] > capacity):     knapsack(numItems-1, capacity, sizes, values)    # find the max of including or not including item in knapsack   return max(     values[values-1] + knapsack(numItems-1,capacity - weights[numitems-1], sizes, values),     knapsack(numItems-1, capacity, sizes, values)) 

Here you are seeking the maximum when a node is either connected with another node or not. When a node is connected, the value that results depends on the node's color. The code would look something like:

def ConnectNodes(numItems, capacity, sizes, values, nodeColor):   # if no more items left to connect or capacity is full   if (numItems == 0 or capacity == 0):     return 0    # if can't fit item into knapsack, try the next item   if (sizes[numItems-1] > capacity):     ConnectNodes(numItems-1, capacity, sizes, values, nodeColor)    # find the max of connecting or not connecting node   return max(     RulesForProfit(numItems-1, nodeColor) + ConnectNodes(numItems-1,capacity - weights[numitems-1], sizes, values, nodeColor),     ConnectNodes(numItems-1, capacity, sizes, values, nodeColor))