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?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ What are your thoughts on the matter? We can't help you without any indication where your problem is. $\endgroup$– Raphael ♦Mar 5, 2013 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$– PareshMar 5, 2013 at 7:32
-
$\begingroup$ @Paresh, You are right, my mistake. $\endgroup$– user742Mar 5, 2013 at 7:33
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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|$.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
-
$\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$– user2102697Mar 1, 2013 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$– user2102697Mar 2, 2013 at 12:39