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

• 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):

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

StackExchange Computer Science Q#35335, answer score: 6