2
$\begingroup$

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

  • A set of colored nodes is given.

  • 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 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.

$\endgroup$
1
$\begingroup$

Let your vertex set be $\{v_1, \dots, v_n\}$. If $n\leq5$, just add all possible edges. Otherwise, create a new graph with vertices $\big\{v_{i,j}\mid i\in\{1, \dots, n\},\ j\in\{1, 2, 3, 4\}\big\}$, and edge set $\{v_{i,j}v_{k,\ell}\mid i\neq k\}$. You're looking for a minimum-weight perfect matching in that graph. (Which is the same thing as a maximum-weight matching in the graph where you multiply all the costs by $-1$). This can be done in polynomial time, even though the graph isn't bipartite.

$\endgroup$
  • $\begingroup$ Thanks. I am reading about minimum-weight perfect matching. I will get back. $\endgroup$ – Suresh Apr 24 '17 at 11:15

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