Abstract
The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is \(\mathcal {NP}\)-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular class of graphs received significant attention, mainly due to potential applications. These include purely combinatorial applications like searching in tree-like partial orders (which generalizes binary search in sorted data), or practical ones in parallel processing.
Work partially supported under Ministry of Science and Higher Education (Poland) subsidy for Gdańsk University of Technology. Moreover, D. Dereniowski and D. Osula have been partially supported by National Science Centre (Poland) grant number 2018/31/B/ST6/00820.
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
Ben-Asher, Y., Farchi, E., Newman, I.: Optimal search in trees. SIAM J. Comput. 28(6), 2090–2102 (1999)
Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discrete Math. 11(1), 168–181 (1998)
Carmo, R., Donadelli, J., Kohayakawa, Y., Laber, E.S.: Searching in random partially ordered sets. Theor. Comput. Sci. 321(1), 41–57 (2004)
Cicalese, F., Jacobs, T., Laber, E.S., Valentim, C.D.: The binary identification problem for weighted trees. Theor. Comput. Sci. 459, 100–112 (2012)
Cicalese, F., Keszegh, B., Lidický, B., Pálvölgyi, D., Valla, T.: On the tree search problem with non-uniform costs. Theor. Comput. Sci. 647, 22–32 (2016)
Dereniowski, D.: Edge ranking of weighted trees. Discret. Appl. Math. 154(8), 1198–1209 (2006)
Dereniowski, D.: Edge ranking and searching in partial orders. Discret. Appl. Math. 156(13), 2493–2500 (2008)
Dereniowski, D., Kosowski, A., Uznański, P., Zou, M.: Approximation strategies for generalized binary search in weighted trees. In: ICALP 2017, pp. 84:1–84:14 (2017)
Dereniowski, D., Nadolski, A.: Vertex rankings of chordal graphs and weighted trees. Inf. Process. Lett. 98(3), 96–100 (2006)
Emamjomeh-Zadeh, E., Kempe, D.: A general framework for robust interactive learning. In: NIPS 2017, pp. 7082–7091 (2017)
Giannopoulou, A.C., Hunter, P., Thilikos, D.M.: LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth. Discret. Appl. Math. 160(15), 2089–2097 (2012)
Iyer, A.V., Ratliff, H.D., Vijayan, G.: Optimal node ranking of trees. Inf. Process. Lett. 28(5), 225–229 (1988)
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
Laber, E.S., Milidiú, R.L., Pessoa, A.A.: On binary searching with nonuniform costs. SIAM J. Comput. 31(4), 1022–1047 (2002)
Lam, T.W., Yue, F.L.: Edge ranking of graphs is hard. Discret. Appl. Math. 85(1), 71–86 (1998)
Lam, T.W., Yue, F.L.: Optimal edge ranking of trees in linear time. Algorithmica 30(1), 12–33 (2001)
Liu, J.W.: The role of elimination trees in sparse factorization. SIAM J. Matrix Anal. Appl. 11(1), 134–172 (1990)
Liu, J.: Equivalent sparse matrix reorderings by elimination tree rotations. SIAM J. Sci. Stat. Comput. 9(3), 424–444 (1988)
Makino, K., Uno, Y., Ibaraki, T.: On minimum edge ranking spanning trees. J. Algorithms 38(2), 411–437 (2001)
Mozes, S., Onak, K., Weimann, O.: Finding an optimal tree searching strategy in linear time. In: SODA 2008, pp. 1096–1105 (2008)
Nešetřil, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27(6), 1022–1041 (2006)
Onak, K., Parys, P.: Generalization of binary search: searching in trees and forest-like partial orders. In: FOCS 2006, pp. 379–388 (2006)
Schäffer, A.A.: Optimal node ranking of trees in linear time. Inf. Process. Lett. 33(2), 91–96 (1989)
de la Torre, P., Greenlaw, R., Schäffer, A.A.: Optimal edge ranking of trees in polynomial time. Algorithmica 13(6), 592–618 (1995)
Zhou, X., Kashem, M.A., Nishizeki, T.: Generalized edge-rankings of trees (extended abstract). In: d’Amore, F., Franciosa, P.G., Marchetti-Spaccamela, A. (eds.) WG 1996. LNCS, vol. 1197, pp. 390–404. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62559-3_31
Zhou, X., Nishizeki, T.: An efficient algorithm for edge-ranking trees. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 118–129. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0049402
Zhou, X., Nishizeki, T.: Finding optimal edge-rankings of trees. In: SODA 1995, pp. 122–131
Zwaan, R.: Vertex ranking with capacity. In: van Leeuwen, J., Muscholl, A., Peleg, D., Pokorný, J., Rumpe, B. (eds.) SOFSEM 2010. LNCS, vol. 5901, pp. 767–778. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11266-9_64
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
Borowiecki, P., Dereniowski, D., Osula, D. (2021). The Complexity of Bicriteria Tree-Depth. 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_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_7
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)