×

Induced matching in some subclasses of bipartite graphs. (English) Zbl 1485.68196

Gaur, Daya (ed.) et al., Algorithms and discrete applied mathematics. Third international conference, CALDAM 2017, Sancoale, Goa, India, February 16–18, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10156, 308-319 (2017).
Summary: For a graph \(G=(V,E)\), a set \(M\subseteq E\) is called a matching in \(G\) if no two edges in \(M\) share a common vertex. A matching \(M\) in \(G\) is called an induced matching in \(G\) if \(G[M]\), the subgraph of \(G\) induced by \(M\), is same as \(G[S]\), the subgraph of \(G\) induced by \(S=\{v \in V \mid v \text{ is incident on an edge of } M\}\). The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. Given a graph \(G\) and a positive integer \(k\), the Induced Matching Decision problem is to decide whether \(G\) has an induced matching of cardinality at least \(k\). The Induced Matching Decision problem is NP-complete on bipartite graphs, but polynomial time solvable for convex bipartite graphs. In this paper, we show that the Induced Matching Decision problem is NP-complete for star-convex bipartite graphs and perfect elimination bipartite graphs. On the positive side, we propose polynomial time algorithms to solve the Maximum Induced Matching problem in circular-convex bipartite graphs and triad-convex bipartite graphs by making polynomial reductions from the Maximum Induced Matching problem in these graph classes to the Maximum Induced Matching problem in convex bipartite graphs.
For the entire collection see [Zbl 1355.68015].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W05 Nonnumerical algorithms
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15, 14–19 (1982) · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1
[2] Cameron, K.: Induced matchings. Discret. Appl. Math. 24, 97–102 (1989) · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F
[3] Kobler, D., Rotics, U.: Finding maximum induced matchings in subclasses of claw-free and \[ {P}_5 \] -free graphs, and in graphs with matching and induced matching of equal maximum size. Algorithmica 37, 327–346 (2003) · Zbl 1082.68592 · doi:10.1007/s00453-003-1035-4
[4] Zito, M.: Induced matchings in regular graphs and trees. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol. 1665, pp. 89–101. Springer, Heidelberg (1999). doi: 10.1007/3-540-46784-X_10 · Zbl 0941.05052 · doi:10.1007/3-540-46784-X_10
[5] Duckworth, W., Manlove, D.F., Zito, M.: On the approximability of the maximum induced matching problem. J. Discret. Algorithms 3, 79–91 (2005) · Zbl 1075.68063 · doi:10.1016/j.jda.2004.05.001
[6] Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inf. Process. Lett. 81, 7–11 (2002) · Zbl 1046.68081 · doi:10.1016/S0020-0190(01)00185-5
[7] Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discret. Math. 266, 133–142 (2003) · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8
[8] Golumbic, M., Lewenstein, M.: New results on induced matchings. Discret. Appl. Math. 101, 157–165 (2000) · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8
[9] Liang, Y.D., Blum, N.: Circular convex bipartite graphs: maximum matching and hamiltonial circuits. Inf. Process. Lett. 56, 215–219 (1995) · Zbl 0875.68698 · doi:10.1016/0020-0190(95)00145-3
[10] Liu, T.: Restricted bipartite graphs: comparison and hardness results. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 241–252. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-07956-1_22 · Zbl 1445.05073 · doi:10.1007/978-3-319-07956-1_22
[11] Liu, T., Lu, M., Lu, Z., Xu, K.: Circular convex bipartite graphs: feedback vertex sets. Theoret. Comput. Sci. (2014). doi: 10.1016/j.tcs.2014.05.001 · Zbl 1339.05398 · doi:10.1016/j.tcs.2014.05.001
[12] 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). doi: 10.1007/978-3-642-38768-5_65 · Zbl 1382.68118 · doi:10.1007/978-3-642-38768-5_65
[13] Pandey, A., Panda, B.S.: Domination in some subclasses of bipartite graphs. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 169–180. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-14974-5_17 · Zbl 1432.68366 · doi:10.1007/978-3-319-14974-5_17
[14] Chen, H., Lei, Z., Liu, T., Tang, Z., Wang, C., Xu, K.: Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs. J. Comb. Optim. 32, 95–110 (2016) · Zbl 1348.05150 · doi:10.1007/s10878-015-9917-3
[15] Liu, W.J.T., Wang, C., Xu, K.: Feedback vertex sets on restricted bipartite graphs. Theoret. Comput. Sci. 507, 41–51 (2013) · Zbl 1302.05191 · doi:10.1016/j.tcs.2012.12.021
[16] Song, Y., Liu, T., Xu, K.: Independent domination on tree convex bipartite graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM/FAW -2012. LNCS, vol. 7285, pp. 129–138. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29700-7_12 · Zbl 1304.68064 · doi:10.1007/978-3-642-29700-7_12
[17] Brandstädt, A., Eschen, E.M., Sritharan, R.: The induced matching and chain subgraph cover problems for convex bipartite graphs. Inf. Process. Lett. 381, 260–265 (2007) · Zbl 1188.68209
[18] Zhang, Y., Bao, F.: A review of tree convex sets test. Comput. Intell. 28, 358–372 (2012) · Zbl 06221847 · doi:10.1111/j.1467-8640.2012.00428.x
[19] Golumbic, M.C., Goss, C.F.: Perfect elimination and chordal bipartite graphs. J. Graph Theory 2, 155–163 (1978) · Zbl 0411.05060 · doi:10.1002/jgt.3190020209
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.