×

On some hard and some tractable cases of the maximum acyclic matching problem. (English) Zbl 1431.05121

Summary: Three well-studied types of subgraph-restricted matchings are induced matchings, uniquely restricted matchings, and acyclic matchings. While it is hard to determine the maximum size of a matching of each of these types, whether some given graph has a maximum matching that is induced or has a maximum matching that is uniquely restricted, can both be decided efficiently. In contrast to that we show that deciding whether a given bipartite graph of maximum degree at most four has a maximum matching that is acyclic is NP-complete. Furthermore, we show that maximum weight acyclic matchings can be determined efficiently for \(P_4\)-free graphs and \(2P_3\)-free graphs, and we characterize the graphs for which every maximum matching is acyclic.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Agrawal, A., Gupta, S., Saurabh, S., & Sharma, R. (2017). Improved algorithms and combinatorial bounds for independent feedback vertex set. Leibniz International Proceedings in Informatics, 63, 2:1-2:14. · Zbl 1398.68203
[2] Baste, J., & Rautenbach, D. (2018). Degenerate matchings and edge colorings. Discrete Applied Mathematics, 239, 38-44. · Zbl 1382.05057 · doi:10.1016/j.dam.2018.01.002
[3] Bonamy, M. Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2017). Independent feedback vertex set for \[P_5\] P5-free graphs. arXiv:1707.09402. · Zbl 1422.68105
[4] Brandstädt, A., & Mosca, R. (2011). On distance-\[33\] matchings and induced matchings. Discrete Applied Mathematics, 159, 509-520. · Zbl 1210.05105 · doi:10.1016/j.dam.2010.05.022
[5] Cameron, K. (1989). Induced matchings. Discrete Applied Mathematics, 24, 97-102. · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F
[6] Cameron, K. (2004). Induced matchings in intersection graphs. Discrete Mathematics, 278, 1-9. · Zbl 1033.05080 · doi:10.1016/j.disc.2003.05.001
[7] Cameron, K., & Walker, T. (2005). The graphs with maximum induced matching and maximum matching the same size. Discrete Mathematics, 299, 49-55. · Zbl 1073.05054 · doi:10.1016/j.disc.2004.07.022
[8] Dabrowski, K. K., Demange, M., & Lozin, V. V. (2013). New results on maximum induced matchings in bipartite graphs and beyond. Theoretical Computer Science, 478, 33-40. · Zbl 1267.68118 · doi:10.1016/j.tcs.2013.01.027
[9] Duarte, M., Joos, F., Penso, L. D., Rautenbach, D., & Souza, U. (2015). Maximum induced matchings close to maximum matchings. Theoretical Computer Science, 588, 131-137. · Zbl 1326.05120 · doi:10.1016/j.tcs.2015.04.001
[10] Duckworth, W., Manlove, D. F., & Zito, M. (2005). On the approximability of the maximum induced matching problem. Journal of Discrete Algorithms, 3, 79-91. · Zbl 1075.68063 · doi:10.1016/j.jda.2004.05.001
[11] Francis, M. C., Jacob, D., & Jana, S. (2016). Uniquely restricted matchings in interval graphs. arXiv:1604.07016. · Zbl 1378.05137
[12] Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness (p. x+338). San Francisco: W.H. Freeman and Co. · Zbl 0411.68039
[13] Goddard, W., Hedetniemi, S. M., Hedetniemi, S. T., & Laskar, R. (2005). Generalized subgraph-restricted matchings in graphs. Discrete Mathematics, 293, 129-138. · Zbl 1063.05108 · doi:10.1016/j.disc.2004.08.027
[14] Golumbic, M. C., Hirst, T., & Lewenstein, M. (2001). Uniquely restricted matchings. Algorithmica, 31, 139-154. · Zbl 0980.68084 · doi:10.1007/s00453-001-0004-z
[15] Joos, F., & Rautenbach, D. (2015). Equality of distance packing numbers. Discrete Mathematics, 338, 2374-2377. · Zbl 1318.05059 · doi:10.1016/j.disc.2015.06.003
[16] Kobler, D., & Rotics, U. (2003). Finding maximum induced matchings in subclasses of claw-free and \[P_5\] P5-free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica, 37, 327-346. · Zbl 1082.68592 · doi:10.1007/s00453-003-1035-4
[17] Lokshantov, D., Vatshelle, M., & Villanger, Y. (2014). Independent set in \[P_5\] P5-free graphs in polynomial time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms (SODA ’14), pp. 570-581. · Zbl 1422.68126
[18] Lozin, V. (2002). On maximum induced matchings in bipartite graphs. Information Processessing Letters, 81, 7-11. · Zbl 1046.68081 · doi:10.1016/S0020-0190(01)00185-5
[19] Lozin, V., & Mosca, R. (2012). Maximum regular induced subgraphs in \[2P_32\] P3-free graphs. Theoretical Computer Science, 460, 26-33. · Zbl 1252.68155 · doi:10.1016/j.tcs.2012.06.014
[20] Lovász, L., & Plummer, M. D. (1986). Matching theory. In Annals of discrete mathematics, Vol. 29. Amsterdam: North-Holland Publishing Co. · Zbl 0618.05001
[21] Mishra, S. (2011). On the maximum uniquely restricted matching for bipartite graphs. Electronic Notes in Discrete Mathematics, 37, 345-350. · Zbl 1268.68135 · doi:10.1016/j.endm.2011.05.059
[22] Misra, N., Philip, G., Raman, V., & Saurabh, S. (2012). On parameterized independent feedback vertex set. Theoretical Computer Science, 461, 65-75. · Zbl 1253.68181 · doi:10.1016/j.tcs.2012.02.012
[23] Panda, B. S., & Pradhan, D. (2012). Acyclic matchings in subclasses of bipartite graphs. Discrete Mathematics Algorithms and Applications, 4, 1250050. · Zbl 1257.05132 · doi:10.1142/S1793830912500504
[24] Penso, L. D., Rautenbach, D., & Souza, U. (2015). Graphs in which some and every maximum matching is uniquely restricted. arXiv:1504.02250. · Zbl 1401.05239
[25] Stockmeyer, L. J., & Vazirani, V. V. (1982). NP-completeness of some generalizations of the maximum matching problem. Information Processing Letters, 15, 14-19. · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1
[26] Tamura, Y., Ito, T., & Zhou, X. (2015). Algorithms for the independent feedback vertex set problem. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 98, 1179-1188. · doi:10.1587/transfun.E98.A.1179
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.