Skip to Main content Skip to Navigation
Conference papers

Hierarchical Clusterings of Unweighted Graphs

Svein Hogemo 1 Christophe Paul 2 Jan Arne Telle 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We study the complexity of finding an optimal hierarchical clustering of an unweighted similarity graph under the recently introduced Dasgupta objective function. We introduce a proof technique, called the normalization procedure, that takes any such clustering of a graph G and iteratively improves it until a desired target clustering of G is reached. We use this technique to show both a negative and a positive complexity result. Firstly, we show that in general the problem is NP-complete. Secondly, we consider min-well-behaved graphs, which are graphs H having the property that for any k the graph H^{(k)} being the join of k copies of H has an optimal hierarchical clustering that splits each copy of H in the same optimal way. To optimally cluster such a graph H^{(k)} we thus only need to optimally cluster the smaller graph H. Co-bipartite graphs are min-well-behaved, but otherwise they seem to be scarce. We use the normalization procedure to show that also the cycle on 6 vertices is min-well-behaved.
Complete list of metadata
Contributor : Christophe Paul <>
Submitted on : Friday, November 27, 2020 - 10:59:46 AM
Last modification on : Saturday, November 28, 2020 - 3:21:18 AM
Long-term archiving on: : Sunday, February 28, 2021 - 6:59:14 PM


Distributed under a Creative Commons Attribution 4.0 International License




Svein Hogemo, Christophe Paul, Jan Arne Telle. Hierarchical Clusterings of Unweighted Graphs. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2020, Prague, Czech Republic. pp.47:1-47:13, ⟨10.4230/LIPIcs.MFCS.2020.47⟩. ⟨lirmm-03027532⟩



Record views


Files downloads