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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abboud, A., Cohen-Addad, V., Klein, P.N.: New hardness results for planar graph problems in p and an algorithm for sparsest cut. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 996–1009. ACM (2020). https://doi.org/10.1145/3357713.3384310
Berendsohn, B.A., Kozma, L.: Splay trees on trees. CoRR, abs/2010.00931 (2020). arXiv:2010.00931
Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discret. Math. 11(1), 168–181 (1998). https://doi.org/10.1137/S0895480195282550
Charikar, M., Chatziafratis, V.: Approximate hierarchical clustering via sparsest cut and spreading metrics. In: Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841–854 (2017)
Charikar, M., Chatziafratis, V., Niazadeh, R.: Hierarchical clustering better than average-linkage. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2291–2304 (2019)
Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: On the complexity of searching in trees and partially ordered structures. Theoret. Comput. Sci. 412(50), 6879–6896 (2011)
Cicalese, F., Jacobs, T., Laber, E., Molinaro, M.: Improved approximation algorithms for the average-case tree searching problem. Algorithmica 68(4), 1045–1074 (2014)
Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F., Mathieu, C.: Hierarchical clustering: objective functions and algorithms. J. ACM 66(4), 26:1–26-42 (2019)
Dasgupta, S.: A cost function for similarity-based hierarchical clustering. In: Annual ACM symposium on Theory of Computing (STOC), pp. 118–127 (2016)
de la Torre, P., Greenlaw, R., Schäffer, A.A.: Optimal edge ranking of trees in polynomial time. Algorithmica 13(6), 592–618 (1995)
Deogun, J.S., Kloks, T., Kratsch, D., Müller, H.: On vertex ranking for permutation and other graphs. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol. 775, pp. 747–758. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-57785-8_187
Deogun, J.S., Kloks, T., Kratsch, D., Müller, H.: On the vertex ranking problem for trapezoid, circular-arc and other graphs. Discret. Appl. Math. 98(1), 39–63 (1999). https://doi.org/10.1016/S0166-218X(99)00179-1
Diestel, R.: Graph Theory, 5th edn. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-53622-3
Dong, S., Wang, H., Mostafavi, A., Gao, J.: Robust component: a robustness measure that incorporates access to critical facilities under disruptions. J. R. Soc. Interface 16(157), 20190149 (2019)
Høgemo, S., Paul, C., Telle, J.A.: Hierarchical clusterings of unweighted graphs. In: International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), vol. 170, pp. 47:1–47:13 (2020). https://doi.org/10.4230/LIPIcs.MFCS.2020.47
Høgemo, S., Bergougnoux, B., Brandes, U., Paul, C., Telle, J.A.: On dasgupta’s hierarchical clustering objective and its relation to other graph parameters. arXiv preprint arXiv:2105.12093 (2021)
Iyer, A.V., Ratliff, H.D., Vijayan, G.: Optimal node ranking of trees. Inf. Process. Lett. 28(5), 225–229 (1988). https://doi.org/10.1016/0020-0190(88)90194-9
Iyer, A.V., Ratliff, H.D., Vijayan, G.: On an edge ranking problem of trees and graphs. Discret. Appl. Math. 30(1), 43–52 (1991). https://doi.org/10.1016/0166-218X(91)90012-L
Jing-Ho, Y., Jer-Jeong, C., Chang, G.J.: Quasi-threshold graphs. Discret. Appl. Math. 69(3), 247–255 (1996). https://doi.org/10.1016/0166-218X(96)00094-7
Lam, T.W., Yue, F.L.: Edge ranking of graphs is hard. Discret. Appl. Math. 85(1), 71–86 (1998). https://doi.org/10.1016/S0166-218X(98)00029-8
Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. Algorithmica 30(1), 12–33 (2001)
Nastos, J., Gao, Y.: Familial groups in social networks. Soc. Netw. 35(3), 439–450 (2013). https://doi.org/10.1016/j.socnet.2013.05.001
Nešetřil, J., Ossona de Mendez, P.: On low tree-depth decompositions. Graph. Combin. 31(6), 1941–1963 (2015)
Nešetřil, J., Ossona de Mendez, P.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Combin. 27(6), 1022–1041 (2006). https://doi.org/10.1016/j.ejc.2005.01.010
Pothen, A.: The complexity of optimal elimination trees. Technical report (1988)
Roy, A., Pokutta, S.: Hierarchical clustering via spreading metrics. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS 2016, pp. 2324–2332 (2016)
Schäffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91–96 (1989). https://doi.org/10.1016/0020-0190(89)90161-0
Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM J. Algebraic Discret. Methods 2, 77–79 (1981)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Høgemo, S., Bergougnoux, B., Brandes, U., Paul, C., Telle, J.A. (2021). On Dasgupta’s Hierarchical Clustering Objective and Its Relation to Other Graph Parameters. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)