Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

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

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

    
What are your thoughts on the matter? We can't help you without any indication where your problem is. –  Raphael Mar 5 '13 at 7:06
    
@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. –  Paresh Mar 5 '13 at 7:32
    
@Paresh, You are right, my mistake. –  user742 Mar 5 '13 at 7:33

3 Answers 3

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

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
Thanks a lot. Djikstra will find me the shortest paths. I need to split this tree down the middle some how, any idea? –  user2102697 Mar 1 '13 at 17:17
    
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? –  user2102697 Mar 2 '13 at 12:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.