Link-Cut Trees

Core Idea

Link-cut trees, introduced by Sleator and Tarjan (1983), maintain a forest of rooted trees under link (add an edge), cut (remove an edge), and path queries (find minimum/aggregate on root-to-node path), all in O(log n) amortized time. The data structure represents each tree as a collection of preferred paths (heavy paths chosen dynamically based on access patterns), each stored as a splay tree keyed by depth. The access operation splays a node to the root of its auxiliary tree and restructures preferred paths, making it the foundation for all other operations. Link-cut trees achieve O(m log n) total time for max-flow algorithms (by maintaining the residual tree structure) and are essential for dynamic graph algorithms, making them one of the most powerful data structures in advanced algorithm design.

Explainer

Link-cut trees solve the dynamic trees problem: maintain a forest of rooted trees under edge insertions (link), edge deletions (cut), and path queries (find the minimum or sum along the path from a node to its tree's root), all in O(log n) amortized time per operation. Sleator and Tarjan introduced them in 1983, building on their earlier invention of splay trees. The data structure is subtle but powerful, and its applications to network flow, dynamic connectivity, and dynamic graph algorithms make it one of the most important advanced data structures.

The key idea is path decomposition. Each tree in the represented forest is decomposed into preferred paths — vertex-disjoint paths covering all vertices, where each node has at most one preferred child. The preferred child of a node v is the child most recently accessed (in the subtree rooted at v). This means that after accessing a node, the entire root-to-node path becomes preferred, concentrating the data structure's representation on the most relevant path. Each preferred path is stored in an auxiliary splay tree, keyed by depth: an in-order traversal of the splay tree visits the nodes from shallowest (closest to root) to deepest. Non-preferred edges between paths are represented by path-parent pointers connecting the top of one auxiliary tree to its parent in the represented tree.

The access(v) operation is the core of the data structure. It makes v the root of its auxiliary splay tree and restructures preferred paths so that the entire root-to-v path becomes a single preferred path. This involves: (1) splaying v within its current auxiliary tree, (2) cutting the preferred path below v (detaching the right subtree in the auxiliary tree), (3) following the path-parent pointer to the parent auxiliary tree, splaying the relevant node there, and joining v's tree as the right child. This repeats until v's path reaches the root of the represented tree. Each step changes an O(1) number of preferred-child designations and performs a splay. The amortized cost of access is O(log n), proved using the same potential function as splay tree analysis: Phi = sum of log(subtree sizes) across all auxiliary trees.

All other operations reduce to access. Link(u, v) accesses u (making it the root of its auxiliary tree), then sets u's path-parent to v. Cut(v) accesses v, then detaches the left subtree in v's auxiliary tree (which contains the path from v's parent to the root). Find-root(v) accesses v, then walks to the leftmost node in the auxiliary tree (the shallowest, which is the root). Path queries (minimum, sum, update) are handled by augmenting the splay trees with subtree aggregates, identical to augmented BSTs.

The application to maximum flow is where link-cut trees have their greatest algorithmic impact. In Dinic's algorithm, each blocking flow phase pushes flow along paths from source to sink in a layered graph. Maintaining the current augmenting tree as a link-cut tree reduces per-path cost from O(n) to O(log n): find the bottleneck via path-minimum, update capacities via path-update, remove saturated edges via cut, and add new tree edges via link. This improvement, from O(mn) to O(m log n) per blocking flow phase, is significant for dense graphs and has theoretical implications for the best known max-flow running times. Beyond flow, link-cut trees are essential for dynamic connectivity, dynamic minimum spanning trees, and any problem where a forest evolves over time and path queries must be answered efficiently.