Divide and Conquer on Trees – Centroid Decomposition

I am currently working on a research project which involves modeling Database Join Queries as special graphs(trees, cliques, etc.) and improving worst case bounds for them. While working on trees, I came across this approach.

Separator Decomposition(also known as Centroid Decomposition) is based on a 1869 result by Jordan:

Given a tree on n vertices, there exists a vertex whose removal partitions the tree into components, each with at most n/2 vertices.

Proof – We can pick any arbitrary vertex v from the tree. Now assuming v is deleted, check the sizes of the connected components the tree will be split into. If all the connected components have a size <= n/2, then we are done. Else, select the component that contains more than n/2 vertices and choose w(an adjacent vertex of v) in it. Continue the same process till we get the vertex that partitions the tree into components, each with at most n/2 vertices. The tree has a finite number of vertices and each vertex is processed at most once. Hence, this method will terminate for sure.

We will be calling that vertex a centroid hereon.

Given a tree T, we can build a centroid tree using this approach –

1. Find the centroid C of T and make it the root of the centroid tree that we are building.

2. Recursively find the centroids of the connected components(think of them as new trees) and add them to the centroid tree.

3. As we are limiting the component size as half of the total nodes, its easy to see that the centroid tree will have depth O(log n). Finding the centroid takes at most O(n) time and hence, this tree can be constructed in O(nlogn) time.

Let’s see how to implement this –

Step 0 : Root the tree arbitrarily.

Step 1 : Calculate the size of each subtree(excluding the vertex rooted at it).

http://pastebin.com/H8dtk34p

Step 2 : Finding the center of the tree.

http://pastebin.com/E2rdgC4j

Step 3 : The Divide and Conquer function.

http://pastebin.com/SWn8b5QX

Shortcomings – 

This technique cannot be as widely applied as Heavy-Light-Decomposition(http://blog.anudeep2011.com/heavy-light-decomposition/) especially when “Query on a Path” is asked for. It is due to the fact the centroids of x and y need not belong to the path from x to y.

Problems to Try – 

1. http://ioi2011.contest.atcoder.jp/tasks/ioi2011_1_2 – Direct application of this idea. For each center, just figure out what to do and then you’re done.

2. http://www.codechef.com/problems/PRIMEDST – Basic idea is Divide and Conquer on Trees but FFTs make it harder.

 

 

 

 

Advertisements

2 thoughts on “Divide and Conquer on Trees – Centroid Decomposition

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s