Heavy path decomposition

In combinatorial mathematics and theoretical computer science, heavy path decomposition (also called heavy-light decomposition) is a technique for decomposing a rooted tree into a set of paths. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants (breaking ties arbitrarily). The selected edges form the paths of the decomposition.

Decomposition into paths

If the edges of a tree T are partitioned into a set of heavy edges and light edges, with one heavy edge from each non-leaf node to one of its children, then the subgraph formed by the heavy edges consists of a set of paths, with each non-leaf vertex belonging to exactly one path, the one containing its heavy edge. Leaf nodes of the tree that are not the endpoint of a heavy edge may be considered as forming paths of length zero. In this way, each vertex belongs to exactly one of the paths. Each path has a head vertex, its topmost vertex.

Alternatively, the paths of heavy edges may be extended by including one light edge, the one from the head of the path to its parent.^[1] In this variation of the decomposition, some vertices belong to multiple paths, but every edge of T belongs to exactly one path.

The path tree

The paths of the decomposition may themselves be organized into a tree called the "path tree", "heavy path tree", or "compressed tree". Each node of the path tree corresponds to a path of the heavy path decomposition. If p is a path of the heavy path decomposition, then the parent of p in the path tree is the path containing the parent of the head of p. The root of the path tree is the path containing the root of the original tree. Alternatively, the path tree may be formed from the original tree by edge contraction of all the heavy edges.

A "light" edge of a given tree is an edge that was not selected as part of the heavy path decomposition. If a light edge connects two tree nodes x and y, with x the parent of y, then x must have at least twice as many descendants as y. Therefore, on any root-to-leaf path of a tree with n nodes, there can be at most log₂ n light edges. Equivalently, the path tree has height at most log₂ n.

Applications

Heavy path decomposition was introduced by Sleator & Tarjan (1983) as part of the amortized analysis of their link/cut tree structure,^[2] and by Harel & Tarjan (1984) as part of their data structure for lowest common ancestors,^[3] The link/cut tree data structure uses a partition of a dynamic tree into paths that is not necessarily the heavy path decomposition; its analysis uses a potential function measuring its distance from the heavy path decomposition, and the small height of the path tree implies that each data structure operation performs only a small number of steps that cannot be charged against improvements to this function.^[2] In the lowest common ancestor data structure, the decomposition is used to embed the input tree into a complete binary tree of logarithmic depth, allowing each query to be solved by constant-time bitwise operations.^[3]

Subsequent applications of heavy path decomposition have included solving the level ancestor problem,^[4] computing the edit distance between trees,^[5][6] graph drawing and greedy embedding,^[7][8][9] finding a path near all nodes of a given graph,^[10] fault diagnosis in fiber-optic communication networks,^[1] and decoding grammar-based codes,^[11] among others.

References

1. Harvey, Nicholas J. A.; Pătraşcu, Mihai; Wen, Yonggang; Yekhanin, Sergey; Chan, Vincent W. S. (2007), "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs", 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 697–705, doi:10.1109/INFCOM.2007.87.
2. Sleator, Daniel D.; Tarjan, Robert Endre (1983), "A data structure for dynamic trees", Journal of Computer and System Sciences 26 (3): 362–391, doi:10.1016/0022-0000(83)90006-5, MR 710253.
3. Harel, Dov; Tarjan, Robert E. (1984), "Fast algorithms for finding nearest common ancestors", SIAM Journal on Computing 13 (2): 338–355, doi:10.1137/0213024.
4. Dietz, Paul F. (1991), "Finding level-ancestors in dynamic trees", Algorithms and data structures (Ottawa, ON, 1991), Lecture Notes in Computer Science 519, Berlin: Springer, pp. 32–40, doi:10.1007/BFb0028247, MR 1146687.
5. Klein, Philip N. (1998), "Computing the edit-distance between unrooted ordered trees", Algorithms—ESA '98 (Venice), Lecture Notes in Computer Science 1461, Berlin: Springer, pp. 91–102, doi:10.1007/3-540-68530-8_8, MR 1683332.
6. Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010), "An optimal decomposition algorithm for tree edit distance", ACM Transactions on Algorithms 6 (1): A2, doi:10.1007/978-3-540-73420-8_15, MR 2654906.
7. Buchsbaum, Adam L.; Westbrook, Jeffery R. (2000), "Maintaining hierarchical graph views", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), New York: ACM, pp. 566–575, MR 1755515.
8. Eppstein, David; Goodrich, Michael T. (2011), "Succinct greedy geometric routing using hyperbolic geometry", IEEE Transactions on Computers 60 (11): 1571–1580, doi:10.1109/TC.2010.257, MR 2830035.
9. Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2013), "Drawing trees with perfect angular resolution and polynomial area", Discrete and Computational Geometry 49 (2): 157–182, doi:10.1007/s00454-012-9472-y, MR 3017904.
10. Alstrup, Stephen; Lauridsen, Peter W; Sommerlund, Peer; Thorup, Mikkel (1997), "Finding cores of limited length", Algorithms and Data Structures, Lecture Notes in Computer Science Volume 1272, Springer, pp. 45–54, doi:10.1007/3-540-63307-3_47.
11. Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren (2011), "Random access to grammar-compressed strings", Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 373–389, MR 2857133.