|
I am trying to solve a graph theory problem. I have an undirected graph where the nodes have node weights n and edges have edge weights g. I want to be able to select the subgraph such that the total weight of nodes+edges is maximized. Each node doesn’t count equally though, as each node has a nonuniform weight w. I think this is also equivalent to the 0/1 knapsack problem except that there are additional benefits to each pair of items put into the knapsack, in addition to their singular benefit. What is the name of such a graph theory problem? Thanks Ralph |
|
Assuming that the only restrictions are (a) the capacity limit on nodes selected and (b) that you get the benefit of an edge only if both endpoints are selected, it sounds like a quadratic knapsack problem to me. The value of the nodes selected is a linear term in the objective function, and the value of the edges selected is a quadratic term. |
|
Sorry I mistyped. I am constrained in the number of nodes I can select to make the maximal subgraph. But instead of saying "I can pick N nodes," I have a constraint saying "I can pick up to X worth of nodes" - but each node may contribute 1 toward X, or 2 toward X, like in a knapsack problem. It is still a bit unclear to me. Would it be possible to add a mathematical formulation of the problem?
(12 Apr '16, 02:50)
Renaud
|
|
OK, I thought it was equivalent to the quadratic knapsack problem but I wasn't sure. In any case, in the particular application I'm using for, I ended up coding a pure integer program in R to solve the QKP because my nXn profit matrix was not positive semidefinite and thus I couldn't use quadprog(). Is there a name for this problem in graph theory terms? |
Are the weights nonnegative? If so, I think something is missing from the problem description, else selecting the entire graph would automatically be optimal.