How to choose the maximum number of nodes (with constraints) from a graph

Assume the set of nodes have weights $v_1 < v_2 < \dots < v_n$.

Two observations that follow immediately from your restrictions:

1. Your selection has to be a set of the form $v_i, v_{i+1}, \dots, v_n$.
2. Every chosen node is neighbour of another chosen node.

That is, we want to find

$\qquad\displaystyle \min \{ i \mid \forall j \geq i\ \exists j' > j\,.\ j \in N(j')\} $

where $N(i)$ denotes the neighbourhood of nodes with (weight-)index $i$.

Therefore, the following algorithm solves the problem in time $O(n \log n)$ (assuming an adjacency matrix):

1. Sort the nodes by weight.
2. Choose nodes greedily from the back of the list as long as the new node is neighbour of one of its predecessors (and you have chosen less than $x$).
3. Output the result.

I'll leave the proofs of correctness and runtime to you.

Now, if weights can be equal we may be able to take some more nodes; if $v_i$ is the first weight we don't pick according to the above algorithm, we have to check all $k$ nodes of weight $v_i$ we have not checked yet, picking as many as we can. This adds a fix-point iteration with at most $k$ iterations running in time $O(k)$ each.

An alternative is to sort the weights in to buckets and pick reachable nodes from the next smallest buckets. Details again left to the reader.

For general graphs, determining if there exists a solution of exact $x$ nodes is NP-complete, and therefore the problem is also NP-complete for general graphs. The proof reduces the Set-Cover (SC) problem to this problem. An instance of SC includes a collection $C$ of subsets $S_j$ of a universal set $U=\{u_i\mid 1\leq i\leq N\}$, and we want to determine if there exist $k$ subsets in $C$ such that their union is $U$. For each $S_j$ and each $u_i$ we construct a node. The weight of each $S_j$ is one and each $u_i$ has weight two. Connect all $u_i$ into a clique and all $S_j$ form an independent set. An edge $(u_i,S_j)$ exists iff $u_i\in S_j$. Now we can easily show that there is a $k$-subset SC iff there is a solution of $x=N+k$ nodes for this problem since such a solution must include all $u_j$, according to the weight constraint.

For your problem, the input is a tree (connected undirected acyclic graph), and we can solve it in polynomial time as follows. First we show how to determine a solution with smallest weight $w$. Find the subgraph $H(w)$ induced by nodes of weight at least $w$. If $H(w)$ is disconnected, then no solutions. If it is connected and the number of nodes is smaller than or equal to $x$, then return yes. If it has too many nodes, repeatedly delete a leaf of weight $w$. In the deletion process, if no leaves of weight $w$, then return no solutions. Using a binary search on $w$, the problem can be solved in $O(n\log n)$.

mentioned this following idea in chat w/you, expanding into answer. dont know why the following wont work. its $O(n^2)$. (other solutions may be faster but on the other hand not all the other answers calculate their complexity.) this does succeed in the criteria of "fast" in the sense of efficient/ PTime.

consider that greedy algorithms sometimes give the optimum with trees eg as with the minimum spanning tree algorithm where this problem has similarities.

imagine an MST-like algorithm but using node weights instead of edge weights. nodes have an analogous adjacency to a tree just as edges do. so start at each initial node, and generate sequentially an MST-like tree expanding outward, and stop only when condition (2) in your requirements kicks in. each of the $n$ nodes could lead to up to $n$ steps hence the quadratic complexity.

furthermore if you start in order of the largest weights 1st, the 1st solution found would be correct.

this solution seems to be similar to R's but is maybe not identical. (R made a comment in chat that might be interpreted as stating his algorithm is not correct based on new edits to your problem.)