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


asked 11 Apr '16, 19:14

kmwest's gravatar image

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.


answered 12 Apr '16, 11:41

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
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.


answered 11 Apr '16, 19:37

kmwest's gravatar image

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?


answered 12 Apr '16, 11:50

kmwest's gravatar image

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



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



Asked: 11 Apr '16, 19:14

Seen: 1,086 times

Last updated: 12 Apr '16, 11:50

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