×

Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs. (English) Zbl 1535.68213

Summary: A bipartite graph \(G=(U,V,E)\) is convex if the vertices in \(V\) can be linearly ordered such that for each vertex \(u\in U\), the neighbors of \(u\) are consecutive in the ordering of \(V\). An induced matching \(H\) of \(G\) is a matching for which no edge of \(E\) connects endpoints of two different edges of \(H\). We show that in a convex bipartite graph with \(n\) vertices and \(m\) weighted edges, an induced matching of maximum total weight can be computed in \(O(n+m)\) time. An unweighted convex bipartite graph has a representation of size \(O(n)\) that records for each vertex \(u\in U\) the first and last neighbor in the ordering of \(V\). Given such a compact representation, we compute an induced matching of maximum cardinality in \(O(n)\) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in \(O(n)\) time. If no compact representation is given, the cover can be computed in \(O(n+m)\) time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of \(O(n^2)\) [A. Brandstädt et al., Theor. Comput. Sci. 381, No. 1–3, 260–265 (2007; Zbl 1188.68209)]. The weighted case has not been considered before.

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)
68W40 Analysis of algorithms

Citations:

Zbl 1188.68209

References:

[1] Asdre, K.; Nikolopoulos, SD, NP-completeness results for some problems on subclasses of bipartite and chordal graphs, Theor. Comput. Sci., 381, 1, 248-259 (2007) · Zbl 1188.68208 · doi:10.1016/j.tcs.2007.05.012
[2] Booth, KS; Lueker, GS, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Syst. Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034 · doi:10.1016/S0022-0000(76)80045-1
[3] Brandstädt, A.; Eschen, EM; Sritharan, R., The induced matching and chain subgraph cover problems for convex bipartite graphs, Theor. Comput. Sci., 381, 1-3, 260-265 (2007) · Zbl 1188.68209 · doi:10.1016/j.tcs.2007.04.006
[4] Brandstädt, A.; Hoàng, CT, Maximum induced matchings for chordal graphs in linear time, Algorithmica, 52, 4, 440-447 (2008) · Zbl 1171.68595 · doi:10.1007/s00453-007-9045-2
[5] Cameron, K., Induced matchings, Discrete Appl. Math., 24, 1-3, 97-102 (1989) · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F
[6] Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Math., 266, 1-3, 133-142 (2003) · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8
[7] Chang, JM, Induced matchings in asteroidal triple-free graphs, Discrete Appl. Math., 132, 1-3, 67-78 (2003) · Zbl 1029.05120 · doi:10.1016/S0166-218X(03)00390-1
[8] Ding, G., Covering the edges with consecutive sets, J. Graph Theory, 15, 5, 559-562 (1991) · Zbl 0763.05079 · doi:10.1002/jgt.3190150508
[9] Duckworth, W.; Manlove, D.; Zito, M., On the approximability of the maximum induced matching problem, J. Discrete Algorithms, 3, 1, 79-91 (2005) · Zbl 1075.68063 · doi:10.1016/j.jda.2004.05.001
[10] Gallo, G., An \(O(n \log n)\) algorithm for the convex bipartite matching problem, Oper. Res. Lett., 3, 1, 31-34 (1984) · Zbl 0537.90091 · doi:10.1016/0167-6377(84)90068-3
[11] Glover, F., Maximum matching in a convex bipartite graph, Nav. Res. Logist. Q., 14, 3, 313-316 (1967) · Zbl 0183.24501 · doi:10.1002/nav.3800140304
[12] Golumbic, MC; Lewenstein, M., New results on induced matchings, Discrete Appl. Math., 101, 1-3, 157-165 (2000) · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8
[13] Hammer, PL; Peled, UN; Sun, X., Difference graphs, Discrete Appl. Math., 28, 1, 35-44 (1990) · Zbl 0716.05032 · doi:10.1016/0166-218X(90)90092-Q
[14] Hung, R., Linear-time algorithm for the paired-domination problem in convex bipartite graphs, Theory Comput. Syst., 50, 4, 721-738 (2012) · Zbl 1253.68175 · doi:10.1007/s00224-011-9378-8
[15] Katriel, I., Matchings in node-weighted convex bipartite graphs, INFORMS J. Comput., 20, 2, 205-211 (2008) · Zbl 1243.05200 · doi:10.1287/ijoc.1070.0232
[16] 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, 4, 327-346 (2003) · Zbl 1082.68592 · doi:10.1007/s00453-003-1035-4
[17] Lozin, VV, On maximum induced matchings in bipartite graphs, Inf. Process. Lett., 81, 1, 7-11 (2002) · Zbl 1046.68081 · doi:10.1016/S0020-0190(01)00185-5
[18] McConnell, RM; Mehlhorn, K.; Näher, S.; Schweitzer, P., Certifying algorithms, Comput. Sci. Rev., 5, 2, 119-161 (2011) · Zbl 1298.68289 · doi:10.1016/j.cosrev.2010.09.009
[19] Müller, H., Hamiltonian circuits in chordal bipartite graphs, Discrete Math., 156, 1-3, 291-298 (1996) · Zbl 0856.68113 · doi:10.1016/0012-365X(95)00057-4
[20] Panda, BS; Pandey, A.; Chaudhary, J.; Dane, P.; Kashyap, M., Maximum weight induced matching in some subclasses of bipartite graphs, J. Combin. Optim., 40, 713-732 (2020) · Zbl 1466.90091 · doi:10.1007/s10878-020-00611-2
[21] Pandey, A., Panda, B.S., Dane, P., Kashyap, M.: Induced matching in some subclasses of bipartite graphs. In: Gaur, D.R., Narayanaswamy, N.S. (eds.) Algorithms and Discrete Applied Mathematics-Third International Conference, CALDAM 2017, Sancoale, Goa, India, February 16-18, 2017, Proceedings, Lecture Notes in Computer Science, vol. 10156, pp. 308-319. Springer (2017). doi:10.1007/978-3-319-53007-9_27 · Zbl 1485.68196
[22] Schrijver, A.: Combinatorial Optimization—Polyhedra and Efficiency, Vol. B, Algorithms and Combinatorics, vol. 24. Springer (2003) · Zbl 1041.90001
[23] Soares, J.; Stefanes, MA, Algorithms for maximum independent set in convex bipartite graphs, Algorithmica, 53, 1, 35-49 (2009) · Zbl 1171.68648 · doi:10.1007/s00453-007-9006-9
[24] Spinrad, JP, Efficient Graph Representations (2003), Providence: American Mathematical Society, Providence · Zbl 1033.05001 · doi:10.1090/fim/019
[25] Steiner, G.; Yeomans, J., A linear time algorithm for maximum matchings in convex, bipartite graphs, Comput. Math. Appl., 31, 12, 91-96 (1996) · Zbl 0851.68090 · doi:10.1016/0898-1221(96)00079-X
[26] Stockmeyer, LJ; Vazirani, VV, NP-completeness of some generalizations of the maximum matching problem, Inf. Process. Lett., 15, 1, 14-19 (1982) · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1
[27] Yu, CW; Chen, GH; Ma, TH, On the complexity of the \(k\)-chain subgraph cover problem, Theor. Comput. Sci., 205, 1-2, 85-98 (1998) · Zbl 0913.68004 · doi:10.1016/S0304-3975(97)00036-4
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.