On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2021

On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters

Abstract

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.

Dates and versions

lirmm-03867040 , version 1 (23-11-2022)

Identifiers

Cite

Svein Høgemo, Benjamin Bergougnoux, Ulrik Brandes, Christophe Paul, Jan Arne Telle. On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters. FCT 2021 - 23rd International Symposium on Fundamentals of Computation Theory, Sep 2021, Athens, Greece. pp.287-300, ⟨10.1007/978-3-030-86593-1_20⟩. ⟨lirmm-03867040⟩
39 View
0 Download

Altmetric

Share

More