Maximum induced matchings for chordal graphs in linear time. (English) Zbl 1171.68595
Summary: The Maximum Induced Matching (MIM) Problem asks for a largest set of pairwise vertex-disjoint edges in a graph which are pairwise of distance at least two. It is well-known that the MIM problem is NP-complete even on particular bipartite graphs and on line graphs. On the other hand, it is solvable in polynomial time for various classes of graphs (such as chordal, weakly chordal, interval, circular-arc graphs and others) since the MIM problem on graph \(G\) corresponds to the Maximum Independent Set problem on the square \(G^{*}=L(G)^{2}\) of the line graph \(L(G)\) of \(G\), and in some cases, \(G^{*}\) is in the same graph class; for example, for chordal graphs \(G,G^{*}\) is chordal. The construction of \(G^{*}\), however, requires \({\mathcal{O}}(m^{2})\) time, where \(m\) is the number of edges in \(G\). Is has been an open problem whether there is a linear-time algorithm for the MIM problem on chordal graphs. We give such an algorithm which is based on perfect elimination order and LexBFS.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
maximum induced matchings; chordal graphs; perfect elimination order; lexicographic breadth-first search; linear time algorithmReferences:
| [1] | Brandstädt, A., Dragan, F.F., Nicolai, F.: LexBFS-orderings and powers of chordal graphs. Discrete Math. 171, 27–42 (1997) · Zbl 0880.05074 · doi:10.1016/S0012-365X(96)00070-2 |
| [2] | Cameron, K.: Induced matchings. Discrete Appl. Math. 24, 97–102 (1989) · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F |
| [3] | Cameron, K.: Induced matchings in intersection graphs (extended abstract). Electron. Notes Discrete Math. 5 (2000) · Zbl 1412.05158 |
| [4] | Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math. 266, 133–142 (2003) · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8 |
| [5] | Chang, J.-M.: Induced matchings in asteroidal-triple-free graphs. Discrete Appl. Math. 132, 67–78 (2004) · Zbl 1029.05120 · doi:10.1016/S0166-218X(03)00390-1 |
| [6] | Fricke, G., Laskar, R.: Strong matchings on trees. Congr. Numer. 89, 239–243 (1992) · Zbl 0786.05065 |
| [7] | Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic, San Diego (1980) · Zbl 0541.05054 |
| [8] | Golumbic, M.C., Laskar, R.C.: Irredundancy in circular-arc graphs. Discrete Appl. Math. 44, 79–89 (1993) · Zbl 0783.05059 · doi:10.1016/0166-218X(93)90223-B |
| [9] | Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Appl. Math. 101, 157–165 (2000) · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8 |
| [10] | Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid covers. SIAM J. Discrete Math. 16, 517–523 (2003) · Zbl 1029.05097 · doi:10.1137/S089548019828371X |
| [11] | 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 |
| [12] | Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266–283 (1976) · Zbl 0353.65019 · doi:10.1137/0205021 |
| [13] | Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inform. Process. Lett. 15, 14–19 (1982) · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1 |
| [14] | Zito, M.: Linear time maximum induced matching algorithm for trees. Nord. J. Comput. 7, 58–63 (2000) · Zbl 0957.68095 |
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.
