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.
$\begingroup$
$\endgroup$
7
-
7$\begingroup$ 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. $\endgroup$– Suresh VenkatOct 30, 2012 at 21:01
-
$\begingroup$ 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. $\endgroup$– lbedogniOct 31, 2012 at 6:04
-
$\begingroup$ 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. $\endgroup$– lbedogniOct 31, 2012 at 10:14
-
$\begingroup$ 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? $\endgroup$– JoeOct 31, 2012 at 17:40
-
1$\begingroup$ 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.) $\endgroup$– JeffεNov 11, 2012 at 4:40
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Nov 10, 2012 at 20:24
-
$\begingroup$ It is similar to Steiner's problem, but I have a limited number of edges. Thanks for your pointer anyway. $\endgroup$– lbedogniNov 13, 2012 at 11:32
-
1$\begingroup$ It seems like I understood your problem correctly, here is a paper studying the same problem as yours: pasteur.fr/recherche/unites/Biolsys/benno/downloads/… $\endgroup$ Nov 13, 2012 at 16:03
-
1$\begingroup$ This thesis explains it better, see page 60 for a definition of your problem. 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. $\endgroup$ Nov 13, 2012 at 16:24