In combinatorial mathematics and

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

, heavy path decomposition (also called heavy-light decomposition) is a technique for decomposing a

rooted tree In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''a ...

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. 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 as part of the amortized analysis of their link/cut tree structure, and by as part of their

data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...

for lowest common ancestors, 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. In the lowest common ancestor data structure, the decomposition is used to embed the input tree into a

complete binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary tr ...

of logarithmic depth, allowing each query to be solved by constant-time

bitwise operation In computer programming, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits. It is a fast and simple action, basic to the higher-level arithmetic operati ...

s. Subsequent applications of heavy path decomposition have included solving the level ancestor problem, computing the edit distance between trees,

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

and greedy embedding, finding a path near all nodes of a given graph, fault diagnosis in

fiber-optic communication Fiber-optic communication is a method of transmitting information from one place to another by sending pulses of infrared light through an optical fiber. The light is a form of carrier wave that is modulated to carry information. Fiber is pref ...

networks, and decoding

grammar-based code Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms. To compres ...

s, among others.

References

{{reflist, 30em, refs= {{citation , last1 = Alstrup , first1 = Stephen , last2 = Lauridsen , first2 = Peter W , last3 = Sommerlund , first3 = Peer , last4 = Thorup , first4 = Mikkel , contribution = Finding cores of limited length , doi = 10.1007/3-540-63307-3_47 , pages = 45–54 , publisher = Springer , series = Lecture Notes in Computer Science Volume , title = Algorithms and Data Structures , volume = 1272 , year = 1997 {{citation , last1 = Bille , first1 = Philip , last2 = Landau , first2 = Gad M. , last3 = Raman , first3 = Rajeev , last4 = Sadakane , first4 = Kunihiko , last5 = Satti , first5 = Srinivasa Rao , last6 = Weimann , first6 = Oren , contribution = Random access to grammar-compressed strings , location = Philadelphia, PA , mr = 2857133 , pages = 373–389 , publisher = SIAM , title = Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , year = 2011 {{citation , last1 = Buchsbaum , first1 = Adam L. , last2 = Westbrook , first2 = Jeffery R. , author2-link = Jeff Westbrook , contribution = Maintaining hierarchical graph views , location = New York , mr = 1755515 , pages = 566–575 , publisher = ACM , title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000) , year = 2000 {{citation , last1 = Demaine , first1 = Erik D. , author1-link = Erik Demaine , last2 = Mozes , first2 = Shay , last3 = Rossman , first3 = Benjamin , last4 = Weimann , first4 = Oren , doi = 10.1007/978-3-540-73420-8_15 , issue = 1 , journal = ACM Transactions on Algorithms , mr = 2654906 , page = A2 , title = An optimal decomposition algorithm for tree edit distance , volume = 6 , year = 2010 {{citation , last = Dietz , first = Paul F. , contribution = Finding level-ancestors in dynamic trees , doi = 10.1007/BFb0028247 , location = Berlin , mr = 1146687 , pages = 32–40 , publisher = Springer , series = Lecture Notes in Computer Science , title = Algorithms and data structures (Ottawa, ON, 1991) , volume = 519 , year = 1991 {{citation , last1 = Duncan , first1 = Christian A. , last2 = Eppstein , first2 = David , author2-link = David Eppstein , last3 = Goodrich , first3 = Michael T. , author3-link = Michael T. Goodrich , last4 = Kobourov , first4 = Stephen G. , last5 = Nöllenburg , first5 = Martin , doi = 10.1007/s00454-012-9472-y , issue = 2 , journal = Discrete and Computational Geometry , mr = 3017904 , pages = 157–182 , title = Drawing trees with perfect angular resolution and polynomial area , volume = 49 , year = 2013, arxiv = 1009.0581 {{citation , last1 = Eppstein , first1 = David , author1-link = David Eppstein , last2 = Goodrich , first2 = Michael T. , author2-link = Michael T. Goodrich , doi = 10.1109/TC.2010.257 , issue = 11 , journal =

IEEE Transactions on Computers ''IEEE Transactions on Computers'' is a monthly peer-reviewed scientific journal covering all aspects of computer design. It was established in 1952 and is published by the IEEE Computer Society. The editor-in-chief is Ahmed Louri, David and Marily ...

, mr = 2830035 , pages = 1571–1580 , title = Succinct greedy geometric routing using hyperbolic geometry , volume = 60 , year = 2011 {{citation , last1 = Harel , first1 = Dov , last2 = Tarjan , first2 = Robert E. , author2-link = Robert Tarjan , title = Fast algorithms for finding nearest common ancestors , journal = SIAM Journal on Computing , volume = 13 , issue = 2 , pages = 338–355 , year = 1984 , doi = 10.1137/0213024 {{citation , last1 = Harvey , first1 = Nicholas J. A. , last2 = Pătraşcu , first2 = Mihai , author2-link = Mihai Pătrașcu (computer scientist) , last3 = Wen , first3 = Yonggang , last4 = Yekhanin , first4 = Sergey , last5 = Chan , first5 = Vincent W. S. , contribution = Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs , doi = 10.1109/INFCOM.2007.87 , pages = 697–705 , title = 26th IEEE International Conference on Computer Communications (INFOCOM 2007) , year = 2007 {{citation , last = Klein , first = Philip N. , contribution = Computing the edit-distance between unrooted ordered trees , doi = 10.1007/3-540-68530-8_8 , location = Berlin , mr = 1683332 , pages = 91–102 , publisher = Springer , series = Lecture Notes in Computer Science , title = Algorithms—ESA '98 (Venice) , volume = 1461 , year = 1998 {{citation , last1 = Sleator , first1 = Daniel D. , author1-link = Daniel Sleator , last2 = Tarjan , first2 = Robert Endre , author2-link = Robert Tarjan , doi = 10.1016/0022-0000(83)90006-5 , issue = 3 , journal =

Journal of Computer and System Sciences The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been publishe ...

, mr = 710253 , pages = 362–391 , title = A data structure for dynamic trees , volume = 26 , year = 1983 Trees (graph theory)