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.
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.