Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees

Abstract We propose a method for cutting down a random recursive tree that focuses on its higher-degree vertices. Enumerate the vertices of a random recursive tree of size n according to the decreasing order of their degrees; namely, let (v^ (i) ) ₈=₁^n be such that (v^ (1) ) (v^ (n) ). The targeted vertex-cutting process is performed by sequentially removing vertices v^ (1), v^ (2), , v^ (n) and keeping only the subtree containing the root after each removal. The algorithm ends when the root is picked to be removed. The total number of steps for this procedure, Kₙ, is upper bounded by Z ₃, which denotes the number of vertices that have degree at least as large as the degree of the root. We prove that Z ₃ grows as n asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the k th moment of Z ₃ is proportional to (\! n) ᵏ. As a consequence, we obtain that the first-order growth of Kₙ is upper bounded by n^1- 2, which is substantially smaller than the required number of removals if, instead, the vertices were selected uniformly at random.