# Maximum weight tree with weights on vertices

Problem Statement

Let, $G(V,E)$ be a graph with a weight function $w(v)$ defined for all vertices. We need to find a tree $T(V',E')$ such that the resulting tree have maximum sum of weights of vertices, where $V' \in V$ and $E' \in E$. In short, we need to remove some vertices(along with all their edges) from $G(V,E)$ such that the resulting graph is a tree and have maximum weight among all such trees. $T(V'.E')$ should be an induced subgraph of $G(V,E)$.

My Attempt

First, sort the vertices in descending order. Then, pick the vertices in that order ensuring that adding a vertex won't create cycles. If it creates cycles, don't consider that vertex. To check if adding a particular vertex adds cycles, I thought of assigning each component a uniaue number. Hence, if adding a vertex results in joining that vertex to two vertices of the same component, we don't add that vertex. But, I couldn't find an efficient way on how should we keep track of which vertex belongs of which component. Can DSU help me with this approach?

• Does the tree need to be an induced subgraph? In other words, are you also allowed to remove edges, or just vertices (along with edges incident to them)? – Yuval Filmus Jun 8 '17 at 22:32
• Yes, the tree must be an induced subgraph. I have updated the problem statement. – bro-mo Jun 8 '17 at 22:38

When introducing each node $u$ with highest weight not in the tree, get all the nodes $u$ is connected to, call that neighbor set $C$. Iterate over all pairs $\{v, v'\}$ in $C$, $v \neq v'$, and check to see wether the disjoint-set trees of $v$ and $v'$ are same; if yes, adding $u$ will introduce a cycle. Finally, if adding that node $u$ restoring all the induced edges is possible without introducing a cycle, make sure that you add that $u$ to the same Disjoint-Set "tree" that contains all the prior nodes.