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

Did you think maybe about greedy approach ? For all colors and corresponding colorA->colorB values, if for each colored edge you will do

edge_color  :  sort_in_descending_order(edge_color_To_color_Prices)
example:
    red: red->black  30
         red->white  20
         red->yellow 10
    black: black->green 15
           black->grey 10

iterate until there is room for new edge (4 per node) and take biggest possible edge value(mark it as visited as well it will help you latter) (I assume you can link nodeA with nodeB only once). We can assume that edge is not directed from what you have said. In each node you have to store those chosen values, so when you are iterating over next edge that you already used you have to be aware of the chosen edges (black node has to be aware of red->black 30 chosen by red)

red: 1st edge: red->black 30 -> stores that in black node list as 
[red,30]
     2nd edge: ...........20 ->...
     3rd edge: ...........10
     4th edge: ...........5
     ---------------------------
     5th edge: ...........4   (after update from black it will be 4th 
edge)
black: 1st edge: black->white   50  > [red,30] 
       2nd edge: .............. 40
       3rd edge: .............. 35
       4th edge: .............. 34
       ---------------------------
       5th edge  .............. 30 (this is our red->black edge)

replace by (black->white 50) and go to red node to update it with the next max (because we just removed red->black 30 by black->white 50 - we will replace it only if we reached the limit of edges in Black node following the min value criteria - we are removing/replacing lowest priced edge from Black node)

That should work

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

Answer 3

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 4

Here is linear programming formulation for this problem: assign a variable for each color pair present in "profit" table (up to c*(c+1)/2 variables needed, where c is the number of colors), use c constraints determined by "4 edges per node" limitation and one constraint for each variable to limit the number of possible edges (except when there are at least 4 nodes for each of edge's color or 5 nodes for single-color edges), and maximize the sum of variable*profit terms.

LP solver might find all-integer variables for this problem (if we are lucky). Or there may be solutions with fractional variables, see counterexample below.

When we get an LP solution (where each variable represents number of edges for some color combination), we should actually add edges to the graph. Use some strategy to avoid loops and duplicate edges (like "choose least connected node" from nodes of same color).

---

Counterexample: 5 red, 4 green, several blue nodes, profit 100 for red-green edges, 10 for red-red, 1 for red-blue. LP solution gives 20 red-green edges (correct), 2.5 red-red edges (should be 2), and zero red-blue edges (should be 1).

Fix: Integer linear programming is a correct approach to this problem. For up to 50 colors we'll need up to 1275 variables. This should be relatively simple task for a decent ILP solver.

Answer 5

Just an idea, didn't have much time to verify it.
How about starting with a weighted graph G=(V,E) where V is your set of nodes and the weight E is the profit from your table. Let O be a empty set that will be our output.

Then use a matching algorithm(Blossom algorithm) on G. Add these edges to O.

Repeat the algorithm with input G'=(V,E\O). Again add these edges to O.

Repeat another two times. Return O.

Running time:
Blossom algorithm's running time is O(E*V^(1/2)) according to wikipedia. Since the algorithm is used 4 times the overall running time would also be O(E*V^(1/2)).