Abstract
In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem introduced by Corneil et al. in 2010 asks for search orderings ending in a special vertex. On the other hand, the problem of finding orderings that induce a given search tree was introduced already in the 1980s s by Hagerup and received new attention most recently by Beisegel et al. Here, we introduce a generalization of some of these problems by studying the question whether there is a search ordering that is a linear extension of a given partial order on a graph’s vertex set. We show that this problem can be solved in polynomial time on chordal bipartite graphs for LBFS, which also implies the first polynomial-time algorithms for the end-vertex problem and two search tree problems for this combination of graph class and search. Furthermore, we present polynomial-time algorithms for LBFS and MCS on split graphs, which generalize known results for the end-vertex and search tree problems.
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
Beisegel, J., et al.: Recognizing graph search trees. Preprint on arXiv (2018). https://doi.org/10.48550/arXiv.1811.09249
Beisegel, J., et al.: On the End-Vertex Problem of Graph Searches. Discrete Math. Theor. Comput. Sci. 21(1) (2019). https://doi.org/10.23638/DMTCS-21-1-13
Beisegel, J., et al.: Recognizing graph search trees. In: Proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium. ENTCS, vol. 346, pp. 99–110. Elsevier (2019). https://doi.org/10.1016/j.entcs.2019.08.010
Beisegel, J., et al.: The recognition problem of graph search trees. SIAM J. Discrete Math. 35(2), 1418–1446 (2021). https://doi.org/10.1137/20M1313301
Berry, A., Blair, J.R., Heggernes, P., Peyton, B.W.: Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica 39(4), 287–298 (2004). https://doi.org/10.1007/s00453-004-1084-3
Bretscher, A., Corneil, D., Habib, M., Paul, C.: A simple linear time LexBFS cograph recognition algorithm. SIAM J. Discrete Math. 22(4), 1277–1296 (2008). https://doi.org/10.1137/060664690
Charbit, P., Habib, M., Mamcarz, A.: Influence of the tie-break rule on the end-vertex problem. Discrete Math. Theor. Comput. Sci. 16(2), 57 (2014). https://doi.org/10.46298/dmtcs.2081
Chu, F.P.M.: A simple linear time certifying LBFS-based algorithm for recognizing trivially perfect graphs and their complements. Inf. Process. Lett. 107(1), 7–12 (2008). https://doi.org/10.1016/j.ipl.2007.12.009
Corneil, D.G., Dusart, J., Habib, M., Mamcarz, A., De Montgolfier, F.: A tie-break model for graph search. Discrete Appl. Math. 199, 89–100 (2016). https://doi.org/10.1016/j.dam.2015.06.011
Corneil, D.G., Köhler, E., Lanlignel, J.M.: On end-vertices of lexicographic breadth first searches. Discrete Appl. Math. 158(5), 434–443 (2010). https://doi.org/10.1016/j.dam.2009.10.001
Corneil, D.G., Krueger, R.M.: A unified view of graph searching. SIAM J. Discrete Math. 22(4), 1259–1276 (2008). https://doi.org/10.1137/050623498
Corneil, D.G., Olariu, S., Stewart, L.: The LBFS structure and recognition of interval graphs. SIAM J. Discrete Math. 23(4), 1905–1953 (2009). https://doi.org/10.1137/S0895480100373455
Dusart, J., Habib, M.: A new LBFS-based algorithm for cocomparability graph recognition. Discrete Appl. Math. 216, 149–161 (2017). https://doi.org/10.1016/j.dam.2015.07.016
Gorzny, J., Huang, J.: End-vertices of LBFS of (AT-free) bigraphs. Discrete Appl. Math. 225, 87–94 (2017). https://doi.org/10.1016/j.dam.2017.02.027
Hagerup, T.: Biconnected graph assembly and recognition of DFS trees. Technical report A 85/03, Universität des Saarlandes (1985). https://doi.org/10.22028/D291-26437
Hagerup, T., Nowak, M.: Recognition of spanning trees defined by graph searches. Technical report A 85/08, Universität des Saarlandes (1985)
Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974). https://doi.org/10.1145/321850.321852
Krueger, R., Simonet, G., Berry, A.: A general label search to investigate classical graph search algorithms. Discrete Appl. Math. 159(2–3), 128–142 (2011). https://doi.org/10.1016/j.dam.2010.02.011
Kumar, P.S., Madhavan, C.E.V.: Minimal vertex separators of chordal graphs. Discrete Appl. Math. 89(1), 155–168 (1998). https://doi.org/10.1016/S0166-218X(98)00123-1
Rong, G., Cao, Y., Wang, J., Wang, Z.: Graph searches and their end vertices. Algorithmica (2022). https://doi.org/10.1007/s00453-022-00981-5
Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5(2), 266–283 (1976). https://doi.org/10.1137/0205021
Scheffler, R.: Linearizing partial search orders. Preprint on arXiv (2022). https://doi.org/10.48550/arXiv.2206.14556
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13(3), 566–579 (1984). https://doi.org/10.1137/0213035
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Scheffler, R. (2022). Linearizing Partial Search Orders. In: Bekos, M.A., Kaufmann, M. (eds) Graph-Theoretic Concepts in Computer Science. WG 2022. Lecture Notes in Computer Science, vol 13453. Springer, Cham. https://doi.org/10.1007/978-3-031-15914-5_31
Download citation
DOI: https://doi.org/10.1007/978-3-031-15914-5_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-15913-8
Online ISBN: 978-3-031-15914-5
eBook Packages: Computer ScienceComputer Science (R0)