4
$\begingroup$

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the complexity?

Can I please have a hint?

$\endgroup$

migrated from stackoverflow.com Mar 4 '13 at 15:00

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ What are your thoughts on the matter? We can't help you without any indication where your problem is. $\endgroup$ – Raphael Mar 5 '13 at 7:06
  • $\begingroup$ @SaeedAmiri From what I understand from the question, the number of connected components does not have to be 2, and the size of each components has to be at most $\lceil |V|/2 \rceil$. So, removing the center in the star graph is a valid solution. $\endgroup$ – Paresh Mar 5 '13 at 7:32
  • $\begingroup$ @Paresh, You are right, my mistake. $\endgroup$ – user742 Mar 5 '13 at 7:33
4
$\begingroup$

Use dynamic programming to find division number of each node, For leaf nodes set it to $0$ Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number: $$\text{division}(v) = \Sigma (\text{division}(\text{child}_i)+1)$$ Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.

This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v_i) = 2|E| = 2|V-1|$.

$\endgroup$
2
$\begingroup$

You might want to first compute the number of vertices in each sub-tree. Now you start at the root: if the number of vertices in both sub-trees is at most $|V|/2$ you remove the root and you are done. Otherwise, you choose the root of the sub-tree whose number of elements is $\gt |V|/2$ and try again. this has complexity linear in $|V|$. This works for binary trees only but you can binarize any tree I believe.

$\endgroup$
2
$\begingroup$

You problem is solved trivially in order statistic trees, where each node has an additional size attribute, and many answers have already mentioned this situation.

So what to do first is to calculate and memorize size for each node ($O(|V|)$), and then do a BST search to find the node with rank $|V|/2$, which is $O(\log(|V|))$ for balanced trees.

This works in binary trees only, but can be easily generalized to any trees.

$\endgroup$
1
$\begingroup$

Your graph is a tree - so removing any node will resolve in having two connected components (unless the node was a leaf, than you will still have only one component).

If you graph is a balanced tree, then you should remove the root.

If it is a generic graph than maybe finding the Jordan center of the graph and removing that one would help. You will have to pass by Djikstra over all nodes or Floyd-Warshall.

Take a look at this one

$\endgroup$
  • $\begingroup$ Thanks a lot. Djikstra will find me the shortest paths. I need to split this tree down the middle some how, any idea? $\endgroup$ – user2102697 Mar 1 '13 at 17:17
  • $\begingroup$ Ok, so I did the following: I would first use BFS algorithm (it has to be run for each verticle) for computing shortest distances between all pairs of verticles. Then for each verticle V find Vm - the largest distance to any other verticles among the data returned form BFS. Then, the verticles with the smallest Vm are the one in the graph center. It comes down to O(V^2), any thing better then that? $\endgroup$ – user2102697 Mar 2 '13 at 12:39

Your Answer

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