2021/05/25 by Svein Høgemo, Benjamin Bergougnoux, Høgemo, Svein +7 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Topological and Geometric Data Analysis #cs.DS
paper · pdf · doi:10.48550/arxiv.2105.12093
Full version, 19 pages
arxiv created 2021/05/25 · openalex publication_date 2021/05/25 · arxiv updated 2021/05/26 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The minimum height of vertex and edge partition trees are well-studied graph parameters known as, for instance, vertex and edge ranking number. While they are NP-hard to determine in general, linear-time algorithms exist for trees. Motivated by a correspondence with Dasgupta's objective for hierarchical clustering we consider the total rather than maximum depth of vertices as an alternative objective for minimization. For vertex partition trees this leads to a new parameter with a natural interpretation as a measure of robustness against vertex removal. As tools for the study of this family of parameters we show that they have similar recursive expressions and prove a binary tree rotation lemma. The new parameter is related to trivially perfect graph completion and therefore intractable like the other three are known to be. We give polynomial-time algorithms for both total-depth variants on caterpillars and on trees with a bounded number of leaf neighbors. For general trees, we obtain a 2-approximation algorithm.