Abstract
A matching M in a graph G is an induced matching if the subgraph of G induced by M is the same as the subgraph of G induced by \(S = \{v \in V(G)\mid v\) is incident on an edge of \(M\}\). Given a graph G and a positive integer k, Induced Matching asks whether G has an induced matching of cardinality at least k. An induced matching M is maximal if it is not properly contained in any other induced matching of G. Given a graph G, Min-Max-Ind-Matching is the problem of finding a maximal induced matching M in G of minimum cardinality. Given a bipartite graph \(G=(X\uplus Y,E(G))\), Saturated Induced Matching asks whether there exists an induced matching in G that saturates every vertex in Y. In this paper, we study Min-Max-Ind-Matching and Saturated Induced Matching. First, we strengthen the hardness result of Min-Max-Ind-Matching by showing that its decision version remains \({\textsf{NP}}\)-complete for perfect elimination bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. Then, we show the hardness difference between Induced Matching and Min-Max-Ind-Matching. Finally, we propose a linear-time algorithm to solve Saturated Induced Matching.
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
Brandstädt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.: Dually chordal graphs. SIAM J. Discrete Math. 11(3), 437–455 (1998)
Bao, F.S., Zhang, Y.: A review of tree convex sets test. Comput. Intell. 28, 358–372 (2012)
Cameron, K.: Induced matchings. Discrete Appl. Math. 24(1–3), 97–102 (1989)
Chaudhary, J., Mishra, S., Panda, B. S.: On the complexity of minimum maximal acyclic matching. In: Zhang, Y., Miao, D., Möhring, R. (eds.) Computing and Combinatorics. COCOON 2022. LNCS, vol. 13595, pp. 106–117. Springer, cham (2022). https://doi.org/10.1007/978-3-031-22105-7_10
Chaudhary, J., Panda, B.S.: On the complexity of minimum maximal uniquely restricted matching. Theor. Comput. Sci. 882, 15–28 (2021)
Clark, L.: The strong matching number of a random graph. Australas. J. Comb. 24, 47–58 (2001)
Duckworth, W., Manlove, D.F., Zito, M.: On the approximability of the maximum induced matching problem. J. Discrete Algorithms 3(1), 79–91 (2005)
Goddard, W., Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R.: Generalized subgraph-restricted matchings in graphs. Discrete Math. 293(1–3), 129–138 (2005)
Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2(2), 155–163 (1978)
Gotthilf, Z., Lewenstein, M.: Tighter approximations for maximum induced matchings in regular graphs. In: Erlebach, T., Persinao, G. (eds.) WAOA 2005. LNCS, vol. 3879, pp. 270–281. Springer, Heidelberg (2006). https://doi.org/10.1007/11671411_21
Lepin, V.V.: A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree. Electron. Notes in Discrete Math. 24, 111–116 (2006)
Panda, B.S., Pandey, A.: On the complexity of minimum cardinality maximal uniquely restricted matching in graphs. In: Arumugam, S., Bagga, J., Beineke, L.W., Panda, B.S. (eds.) ICTCSDM 2016. LNCS, vol. 10398, pp. 218–227. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-64419-6_29
Panda, B.S., Pandey, A., Chaudhary, J., Dane, P., Kashyap, M.: Maximum weight induced matching in some subclasses of bipartite graphs. J. Comb. Optim. 40, 1–20 (2020)
Pandey, A., Panda, B.S.: Domination in some subclasses of bipartite graphs. Discrete Appl. Math. 252, 51–66 (2019)
Orlovich, Y.L., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discrete Optim. 5(3), 584–593 (2008)
Orlovich, Y.L., Zverovich, I.E.: Maximal induced matchings of minimum/maximum size. Technical report, DIMACS TR 2004-26 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Chaudhary, J., Panda, B.S. (2022). On Two Variants of Induced Matchings. In: Hsieh, SY., Hung, LJ., Klasing, R., Lee, CW., Peng, SL. (eds) New Trends in Computer Technologies and Applications. ICS 2022. Communications in Computer and Information Science, vol 1723. Springer, Singapore. https://doi.org/10.1007/978-981-19-9582-8_4
Download citation
DOI: https://doi.org/10.1007/978-981-19-9582-8_4
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-19-9581-1
Online ISBN: 978-981-19-9582-8
eBook Packages: Computer ScienceComputer Science (R0)