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.

  • 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 Venkat Oct 30 '12 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$ – lbedogni Oct 31 '12 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$ – lbedogni Oct 31 '12 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$ – Joe Oct 31 '12 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 '12 at 4:40

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.

  • $\begingroup$ It is similar to Steiner's problem, but I have a limited number of edges. Thanks for your pointer anyway. $\endgroup$ – lbedogni Nov 13 '12 at 11:32
  • $\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$ – Martin Vatshelle Nov 13 '12 at 16:03
  • $\begingroup$ This thesis explains it better, see page 60 for a definition of your problem. citeseerx.ist.psu.edu/viewdoc/summary?doi= 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$ – Martin Vatshelle Nov 13 '12 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.