How to choose the maximum number of nodes (with constraints) from a graph Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. 

A positive integer $x$ is given and you want to choose at most $x$ nodes so that


There is a path connecting all the nodes you choose that doesn't visit any node you haven't chosen.  A path can backtrack. This is to say the set of vertices you choose induces a connected subgraph in $G$.
Each node you choose has weight at least as great as all nodes you haven't chosen. 


The goal is to maximize the number of nodes you choose.

Is there  a fast algorithm for this problem?
Assume the set of nodes have weights $v_1 &lt; v_2 &lt; \dots &lt; v_n$.

Two observations that follow immediately from your restrictions:


Your selection has to be a set of the form $v_i, v_{i+1}, \dots, v_n$.
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' &gt; 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):


Sort the nodes by weight.
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$).
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.