# maximal subset - include nonuniform node weights and node values

 0 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 asked 11 Apr '16, 19:14 kmwest 53●1●7 accept rate: 0% Are the weights nonnegative? If so, I think something is missing from the problem description, else selecting the entire graph would automatically be optimal. (11 Apr '16, 19:34) Paul Rubin ♦♦

 1 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. answered 12 Apr '16, 11:41 Paul Rubin ♦♦ 14.6k●5●13 accept rate: 19%
 0 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. answered 11 Apr '16, 19:37 kmwest 53●1●7 accept rate: 0% 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
 0 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? answered 12 Apr '16, 11:50 kmwest 53●1●7 accept rate: 0%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×17
×13