Tutorial + Video: Centroid Decomposition

Revision en1, by Algorithms_with_Shayan, 2023-12-16 01:24:11

Centroid

If you have ever read about graph theory or participated in a Codeforces contest, you've likely heard about trees. In this tutorial, I'll be talking about centroid, an important vertex that helps you to solve many problems.

To comprehend what centroid is, you need to first be familiar with trees, and also know a little bit about divide and conquer.

The following tutorial is accompanied by the following two videos I prepared to explain centroid:

Centroid #1 | Full Explanation and Implementation

Centroid #2 | Bonus and Interesting facts

Some sample problems

Centroid #1 0:41

The following problems can be solved using centroid:

Ciel the Commander (I solve this problem for you in my first video)

Distance in Tree (Can also be solved without centroid, but it is a good training for implementing centroid)

Xenia and Tree

Kirito in Memeland (Also needs segment tree)

Close Vertices (Also needs segment tree)

Feel free to suggest additional problems.

Definition

Centroid #1 1:44

A centroid is a vertex that, if you remove it from the tree, all connected components afterward have at most n/2 vertices.

You might have these questions now:

  1. Why should such a vertex exist?
  2. How can we find it?
  3. How this vertex can help us solve problems?

Proof of existence and the algorithm to find it

Centroid #1 3:19

We address both questions simultaneously. In other words, we prove the existence of a centroid by discovering it. Once found, its existence is validated.

We root the tree arbitrarily (let's say at vertex 1) and determine the subtree size for each vertex.

Initially, we start from vertex 1. In each step, if the current vertex has a child with a subtree size exceeding n/2, we move to that vertex. Eventually, we will stop moving. We argue that the vertex we are in is our centroid. (Detailed proof in the video)

How centroid helps us

If you are familiar with divide and conquer, "n/2" likely strikes a chord!

As the number of vertices is halved at each step, removing the centroid, selecting one of the resulting connected components, and repeating this process over and over again, each time reduces the tree's size by half. Hence, how many times we repeat our process? Yes, at most log(n). :) (each time, the number of vertices is halved, we start from n vertices, so we have at most lg(n) steps)

Solving a problem using centroid

Centroid #1 9:09

In the video, I solve 'Ciel and Commander'. Make sure to watch it to comprehend how centroid can aids to solve a problem.

How many centroids?

Centroid #2 00:45

In the video, I prove that there are two cases: 1. We have only one centroid. 2. We have two centroid, and there are adjacent.

Most of the time, the first case happens.

An alternative definition for centroid + Proof

Centroid #2 5:14

There is also another definition for centroid.

If we define S(v), as the sum of the distances of all the vertices in the tree from vertex v (unweighted distance), then vertex c is a centroid if and only if S(c) is minimal. I prove this in detail in the video.

The rest of the topic is covered in my second video about centroid.

The second proof

Centroid #2 13:15

Now that we know a vertex with the minimal value of S is a centroid, it's clear we have one because there's a vertex with a minimal S value. :)

In order to find the centroid, you can calculate the value S for all the vertices (using dynamic programming) and report the minimal one as your centroid.

The third proof (and the most incredible one)

Centroid #2 15:17

For each edge, see how many vertices are on each side of this edge. Direct the edge toward the side with more vertices (if equal, direct it randomly).

With n vertices and n-1 edges, there will be a vertex with zero outgoing edges. (Otherwise, we needed to have at least n edges) That vertex is a centroid. (Why?)

I hope this tutorial helps you. I'm trying to help everyone get familiar with algorithms and competitive programming easily. Your feedback is very important to me. Please share your comments and suggestions. If these tutorials aid, I will dedicate myself to releasing at least one every Friday. If you want to support this initiative, liking the videos and subscribing to the channel can be very helpful.

Thank you,

Shayan

Tags graphs, trees, centroid, centroid decomposition

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Algorithms_with_Shayan 2023-12-16 02:00:49 99 Tiny change: ' original post [here](ht' -> ' original codeforces blog [here](ht'
en1 English Algorithms_with_Shayan 2023-12-16 01:24:11 5556 Initial revision (published)