3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Yuval Filmus Jun 8 '17 at 22:32
  • $\begingroup$ Yes, the tree must be an induced subgraph. I have updated the problem statement. $\endgroup$ – bro-mo Jun 8 '17 at 22:38
1
$\begingroup$

It would seem that you need a Disjoint-set data structure.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.