Abstract
Convex bipartite graphs are a subclass of circular convex bipartite graphs and chordal bipartite graphs. Chordal bipartite graphs are a subclass of perfect elimination bipartite graphs and tree convex bipartite graphs. No other inclusion among them is known. In this paper, we make a thorough comparison on them by showing the nonemptyness of each region in their Venn diagram. Thus no further inclusion among them is possible, and the known complexity results on them are incomparable. We also show the \(\mathcal{NP}\)-completeness of treewidth and feedback vertex set for perfect elimination bipartite graphs.
Partially supported by National 973 Program of China (Grant No. 2010CB328103) and Natural Science Foundation of China (Grant Nos. 61370052 and 61370156).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discrete Methods 8, 277–284 (1987)
Brandstad, A., Le, V.B., Spinrad, J.P.: Graph Classes - A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)
Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2, 155–163 (1978)
Grover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14, 313–316 (1967)
Jiang, W., Liu, T., Ren, T., Xu, K.: Two hardness results on feedback vertex sets. In: Atallah, M., Li, X.-Y., Zhu, B. (eds.) FAW-AAIM 2011. LNCS, vol. 6681, pp. 233–243. Springer, Heidelberg (2011)
Jiang, W., Liu, T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theor. Comput. Sci. 507, 41–51 (2013)
Jiang, W., Liu, T., Xu, K.: Tractable feedback vertex sets in restricted bipartite graphs. In: Wang, W., Zhu, X., Du, D.-Z. (eds.) COCOA 2011. LNCS, vol. 6831, pp. 424–434. Springer, Heidelberg (2011)
Karp, R.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Kloks, T.: Treewidth: Computations and Approximations. Springer (1994)
Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs. J. Algorithms 19, 266–281 (1995)
Kloks, T., Liu, C.H., Pon, S.H.: Feedback vertex set on chordal bipartite graphs. arXiv:1104.3915 (2011)
Kloks, T., Wang, Y.L.: Advances in Graph Algorithms (2013) (manuscript)
Liang, Y.D., Blum, N.: Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits. Inf. Process. Lett. 56, 215–219 (1995)
Liu, T., Lu, Z., Xu, K.: Tractable connected domination for restricted bipartite graphs. J. Comb. Optim. (2014), , doi 10.1007/s10878-014-9729-x
Lu, M., Liu, T., Xu, K.: Independent domination: Reductions from circular- and triad-convex bipartite graphs to convex bipartite graphs. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol. 7924, pp. 142–152. Springer, Heidelberg (2013)
Lu, M., Liu, T., Tong, W., Lin, G., Xu, K.: Set cover, set packing and hitting set for tree convex and tree-like set systems. In: Gopal, T.V., Agrawal, M., Li, A., Cooper, S.B. (eds.) TAMC 2014. LNCS, vol. 8402, pp. 248–258. Springer, Heidelberg (2014)
Lu, Z., Liu, T., Xu, K.: Tractable connected domination for restricted bipartite graphs (extended abstract). In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 721–728. Springer, Heidelberg (2013)
Lu, Z., Lu, M., Liu, T., Xu, K.: Circular convex bipartite graphs: Feedback vertex set. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 272–283. Springer, Heidelberg (2013)
Song, Y., Liu, T., Xu, K.: Independent domination on tree convex bipartite graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 129–138. Springer, Heidelberg (2012)
Tucker, A.: A structure theorem for the consecutive 1’s property. Journal of Combinatorial Theory 12(B), 153–162 (1972)
Wang, C., Chen, H., Lei, Z., Tang, Z., Liu, T., Xu, K.: Tree convex bipartite graphs: \(\mathcal{NP}\)-complete domination, hamiltonicity and treewidth. In: Proc. of FAW (2014)
Wang, C., Liu, T., Jiang, W., Xu, K.: Feedback vertex sets on tree convex bipartite graphs. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 95–102. Springer, Heidelberg (2012)
Yannakakis, M.: Node-deletion problem on bipartite graphs. SIAM J. Comput. 10, 310–327 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, T. (2014). Restricted Bipartite Graphs: Comparison and Hardness Results. In: Gu, Q., Hell, P., Yang, B. (eds) Algorithmic Aspects in Information and Management. AAIM 2014. Lecture Notes in Computer Science, vol 8546. Springer, Cham. https://doi.org/10.1007/978-3-319-07956-1_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-07956-1_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-07955-4
Online ISBN: 978-3-319-07956-1
eBook Packages: Computer ScienceComputer Science (R0)