<p>I am not sure I understand the problem correctly, but let me try a definition:
Given a graph and an integer k.
Find the subset $S$ of $k+1$ vertices with max sum of weights such that $S$ induces a connected graph (i.e. there is a tree with k edges spanning $S$).</p>

<p>This sounds to me like the Steiner tree problem
<a href="http://en.wikipedia.org/wiki/Steiner_tree_problem" rel="nofollow">http://en.wikipedia.org/wiki/Steiner_tree_problem</a></p>

<p>The steiner tree problem gives as input a graph, a set of terminals and asks for a set of edges from the graph (i.e. a tree) that connects all terminals.
The goal is to minimize the sum of the edge weights.</p>

<p>Gary and Johnson showed this NP-complete, I believe even for all edge weights 1.</p>

<p>Give the terminals a high weight such that any solution would need to take all terminals.
The rest of the vertices gets weight 1. Since a tree always has 1 edge less than number of nodes the question is find a set of nodes such that all terminals will be connected.</p>

<p>Hence your problem is NP-complete.
Much work has been done on approximation, there has been comparison of different implementations. I seem to remember there was a DIMACS challenge on the Steiner tree problem.</p>

CC BY-SA 3.0
2012-11-13T11:32:09.240Z
It is similar to Steiner's problem, but I have a limited number of edges. Thanks for your pointer anyway.
lbedogni
CC BY-SA 3.0
2012-11-13T16:03:49.180Z
It seems like I understood your problem correctly, here is a paper studying the same problem as yours:
http://www.pasteur.fr/recherche/unites/Biolsys/benno/downloads/IdekerOSS02Preprint.pdf
Martin Vatshelle
CC BY-SA 3.0
2012-11-13T16:24:45.337Z
This thesis explains it better, see page 60 for a definition of your problem.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.3694
If you ask about the parameterized complexity of this problem, i.e. can the problem be solved in $f(k) \cdot poly(n)$ or does it need $n^k$ then the thesis states it as an open problem.

It makes a huge difference whether you allow negative weights or not.
Martin Vatshelle
CC BY-SA 3.0
2012-11-10T20:24:08.277Z
2012-11-10T22:41:19.823Z
2012-11-10T22:41:19.823Z
Martin Vatshelle
<p>I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best graph connecting the vertices, defining best as the maximum value achievable by summing node fitness. I already have an algorithm for that, I'm only asking if this is a well-known problem or a more efficient algorithm than NP-hard does exist.</p>

CC BY-SA 3.0
2012-10-30T21:01:03.910Z
your question is missing some information. If all nodes have to be connected, and fitness is defined solely in terms of node weights, then there is nothing to maximize. Presumably your *edge* choices matter, but then you haven't told us how to assign a cost to edges.
Suresh Venkat
CC BY-SA 3.0
2012-10-31T06:04:36.807Z
Nodes doesn't need to be all connected. Edges have the same cost, I'm interested in knowing which is the best connection if i use one edge, which is the best if i use two of them and so on.
lbedogni
CC BY-SA 3.0
2012-10-31T10:14:59.263Z
I'll elaborate a bit more. It's like trying to find the minimum spanning tree but with a limited number of edges you can choose. Basically one could think that every edge has a cost on it, representing the average fitnes of the two nodes it connects. Then the question is to find the "best" spanning tree with a limited number of edges.
lbedogni
CC BY-SA 3.0
2012-10-31T17:40:49.840Z
I still don't know what "best" means here. Do the edges have to span or not? Are you just maximizing average fitness from selected edges?
Joe
CC BY-SA 3.0
2012-11-01T06:15:30.697Z
The "best" is the subgraph with the maximum fitness. You have a limited number of edges, so you want to find the subgraph, given a number of edges, which is the maximum.
lbedogni
CC BY-SA 3.0
2012-11-11T04:40:08.830Z
So is the problem trivial if all the vertices have positive fitness?  (Proposed solution: Choose _all_ the vertices; add the required number of edges anywhere you like.)
Jeffε
CC BY-SA 3.0
2012-11-12T16:34:51.803Z
no the problem is not trivial, since you can be limited on the total number of edges you can add.
lbedogni
CC BY-SA 4.0
2024-01-30T21:46:04.697Z
Perhaps OP intends the following problem?  *Given a vertex-weighted graph and an integer $k$, choose $k$ edges to maximize the sum of the weights of the vertices touched by those edges (counting each vertex just once, even if is touched by multiple edges).*  Perhaps (?) there is an additional constraint that the chosen edges should connect all the touched vertices.
Neal Young
<ds.algorithms><graph-theory><co.combinatorics><graph-algorithms><partition-problem>
Graph building with weighted nodes
lbedogni
# Graph building with weighted nodes

(Asked by: username_0 on 2012-10-30)

I have a set of nodes which can be connected together through arcs. Every node has an associated value, reflecting the "fitness" that this particular node has in the graph. I have to find the best graph connecting the vertices, defining best as the maximum value achievable by summing node fitness. I already have an algorithm for that, I'm only asking if this is a well-known problem or a more efficient algorithm than NP-hard does exist.

**Tags:** ds.algorithms, graph-theory, co.combinatorics, graph-algorithms, partition-problem
> **Comments:**
> **username_1**: your question is missing some information. If all nodes have to be connected, and fitness is defined solely in terms of node weights, then there is nothing to maximize. Presumably your *edge* choices matter, but then you haven't told us how to assign a cost to edges.  
> **username_0**: Nodes doesn't need to be all connected. Edges have the same cost, I'm interested in knowing which is the best connection if i use one edge, which is the best if i use two of them and so on.  
> **username_0**: I'll elaborate a bit more. It's like trying to find the minimum spanning tree but with a limited number of edges you can choose. Basically one could think that every edge has a cost on it, representing the average fitnes of the two nodes it connects. Then the question is to find the "best" spanning tree with a limited number of edges.  
> **username_2**: I still don't know what "best" means here. Do the edges have to span or not? Are you just maximizing average fitness from selected edges?  
> **username_0**: The "best" is the subgraph with the maximum fitness. You have a limited number of edges, so you want to find the subgraph, given a number of edges, which is the maximum.  
> **username_3**: So is the problem trivial if all the vertices have positive fitness?  (Proposed solution: Choose _all_ the vertices; add the required number of edges anywhere you like.)  
> **username_0**: no the problem is not trivial, since you can be limited on the total number of edges you can add.  
> **username_4**: Perhaps OP intends the following problem?  *Given a vertex-weighted graph and an integer $k$, choose $k$ edges to maximize the sum of the weights of the vertices touched by those edges (counting each vertex just once, even if is touched by multiple edges).*  Perhaps (?) there is an additional constraint that the chosen edges should connect all the touched vertices.  

---

## 1 answers

### Answer by username_5 on 2012-11-10. Score: 2

I am not sure I understand the problem correctly, but let me try a definition:
Given a graph and an integer k.
Find the subset $S$ of $k+1$ vertices with max sum of weights such that $S$ induces a connected graph (i.e. there is a tree with k edges spanning $S$).

This sounds to me like the Steiner tree problem
<http://en.wikipedia.org/wiki/Steiner_tree_problem>

The steiner tree problem gives as input a graph, a set of terminals and asks for a set of edges from the graph (i.e. a tree) that connects all terminals.
The goal is to minimize the sum of the edge weights.

Gary and Johnson showed this NP-complete, I believe even for all edge weights 1.

Give the terminals a high weight such that any solution would need to take all terminals.
The rest of the vertices gets weight 1. Since a tree always has 1 edge less than number of nodes the question is find a set of nodes such that all terminals will be connected.

Hence your problem is NP-complete.
Much work has been done on approximation, there has been comparison of different implementations. I seem to remember there was a DIMACS challenge on the Steiner tree problem.

> **Comments:**
> **username_0**: It is similar to Steiner's problem, but I have a limited number of edges. Thanks for your pointer anyway.  
> **username_5**: It seems like I understood your problem correctly, here is a paper studying the same problem as yours: http://www.pasteur.fr/recherche/unites/Biolsys/benno/downloads/IdekerOSS02Preprint.pdf  
> **username_5**: This thesis explains it better, see page 60 for a definition of your problem. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.3694 If you ask about the parameterized complexity of this problem, i.e. can the problem be solved in $f(k) \cdot poly(n)$ or does it need $n^k$ then the thesis states it as an open problem.  It makes a huge difference whether you allow negative weights or not.  

---

