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's gravatar image

kmwest
5316
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 ♦♦

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.

link

answered 12 Apr '16, 11:41

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

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.

link

answered 11 Apr '16, 19:37

kmwest's gravatar image

kmwest
5316
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

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?

link

answered 12 Apr '16, 11:50

kmwest's gravatar image

kmwest
5316
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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

Asked: 11 Apr '16, 19:14

Seen: 985 times

Last updated: 12 Apr '16, 11:50

OR-Exchange! Your site for questions, answers, and announcements about operations research.