โ† Wiki Index / Computation & Algorithms / Centroid Decomposition
๐Ÿ’ป Computation & Algorithms

Centroid Decomposition

Centroid decomposition is a divide-and-conquer tree algorithm that recursively splits a tree at its centroid vertex into subtrees of at most half size, yielding a centroid tree of O(log n) height for path queries.

Centroid decomposition is a fundamental divide-and-conquer technique on unrooted trees T = (V, E) that recursively partitions a tree by removing its centroidโ€”a vertex whose deletion splits the remaining forest into connected components each containing at most โŒŠ|V| / 2โŒ‹ vertices. By repeating this splitting process recursively on every resulting connected component and linking each component's centroid to the parent centroid that created it, the algorithm constructs an auxiliary centroid tree TC over the same vertex set V whose total height is guaranteed to be at most โŒˆlog2 |V|โŒ‰.

Because any path between two vertices u and v in the original tree T passes through their lowest common ancestor c = LCAC(u, v) in the centroid tree TC, centroid decomposition breaks every path in T into two shorter radial paths (u โ†’ c and c โ†’ v) while keeping every vertex's ancestor chain bounded by O(log n). This property enables fast static and dynamic distance queries, path counting, and parallel tree contraction.

Finding a Tree Centroid and Construction Complexity

By Jordan's theorem on trees (1869), every finite tree has either one unique centroid or two adjacent centroids connected by an edge. A centroid can be found in O(m) time for a component of size m:

  1. Run a depth-first search (DFS) from an arbitrary root r to compute the subtree size *sz*[v] of every vertex v in the component.
  2. Start at r. If r has a child u with *sz*[u] > m / 2, step to u and repeat; otherwise, r is a centroid.

Because each step moves strictly into the unique child subtree exceeding half the component size, the walk terminates without cycles at a vertex where every adjacent component (all children plus the remaining m โˆ’ *sz*[r] parent side) has size โ‰ค โŒŠm / 2โŒ‹. Across all levels of recursion, component sizes halve at every step, so each vertex appears in at most โŒˆlog2 nโŒ‰ levels; consequently, building the entire centroid tree takes O(n log n) total time and O(n) (or O(n log n) with precomputed distances) space.

Tree TechniqueDecomposition HeightPrimary Query CapabilityStatic Build TimeDynamic Updates Supported?
Centroid Decompositionโ‰ค โŒˆlog2 nโŒ‰Unordered path-sum / nearest-marked-node queriesO(n log n)Yes (mark/unmark nodes in O(log n) or O(log2 n))
Heavyโ€“Light Decomposition (HLD)O(log n) chainsPath range updates & queries (with segment tree)O(n)Yes (along paths via segment tree)
Euler Tour + RMQO(1) LCASubtree updates & static path sumsO(n log n)Subtree updates only

Path Counting and Dynamic Nearest-Marked-Vertex Queries

Centroid decomposition excels at two broad families of tree problems:

  1. Offline path counting (divide-and-conquer on trees): To count all pairs (u, v) whose path in T satisfies a condition (such as exact length k or weight โ‰ค W), process each centroid c, collect path lengths from c into each child component sequentially, and match pairs across different child components (avoiding self-component double counting) before deleting c and recursing. Total time is O(n log n) (or O(n log2 n) with FFT/sorting).
  2. Online "Paint / Query Nearest Red Node": Each vertex u has at most O(log n) ancestors in the centroid tree TC. When a vertex u is marked red, update the minimum recorded distance *best*[c] = min(*best*[c], distT(u, c)) for all O(log n) ancestors c of u in TC. To query the shortest distance from any vertex v to the nearest red node, walk up v's O(log n) centroid ancestors and take min(distT(v, c) + *best*[c]). Because the true shortest path from v to any red node u passes through their centroid-tree LCA c, the minimum over v's centroid ancestors is guaranteed to recover the exact optimal path in O(log n) (or O(log2 n) with online LCA).

Frequently Asked Questions

What is the difference between a tree center and a tree centroid? A tree center minimizes the maximum distance (eccentricity) to any other vertex, whereas a tree centroid minimizes the maximum subtree size (number of vertices) in any remaining component after its removal.

Why does a centroid tree always have O(log n) height? Because removing a centroid splits a component of size m into subtrees each of size at most m/2, the component size halves at every recursion depth, guaranteeing at most log2 n levels.

Can a tree have more than one centroid? Yes. A tree with an even number of vertices can have at most two centroids, which must be directly connected by an edge splitting the tree into two equal halves of size n/2.

References

  1. Cole, R., & Vishkin, U. (1988). The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time. Algorithmica. https://doi.org/10.1007/bf01762121
  2. Berry, A., et al. (2014). Organizing the atoms of the clique separator decomposition into an atom tree. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2014.05.030
  3. (2022). Resource Cooperative Integrated Scheduling Algorithm Based on Sub-tree Cycle Decomposition of Process Tree. Journal of Mechanical Engineering. https://doi.org/10.3901/jme.2022.13.228
๐Ÿงฌ Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
๐Ÿ’ก Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision