×

Moderately exponential time algorithms for the maximum induced matching problem. (English) Zbl 1327.90350

Summary: An induced matching \(M\subseteq E\) in a graph \(G=(V, E)\) is a matching such that no two edges in \(M\) are joined by any third edge of the graph. The Maximum Induced Matching problem is to find an induced matching of maximum cardinality. It is NP-hard. Branch-and-reduce algorithms proposed in the previous results for the Maximum Induced Matching problem use a standard branching rule: for a vertex \(v\), it branches into \(\deg(v)+1\) subproblems that either \(v\) is not an endvertex of any edge in \(M\) or \(v\) and one of its neighbor are endvertices of an edge in \(M\). In this paper, we give a simple branch-and-reduce algorithm consisting of a boundary condition, a reduction rule, and a branching rule. Especially, the branching rule only branches the original problem into two subproblems. When the algorithm meets the input instance satisfying the boundary condition, we reduce the Maximum Induced Matching problem to the Maximum Independent Set problem. By using the measure-and-conquer approach to analyze the running time of the algorithm, we show that this algorithm runs in time \(O^\ast(1.4658^n)\) which is faster than previously known algorithms. By adding two branching rules in the simple exact algorithm, we obtain an \(O^\ast(1.4321^n)\)-time algorithm for the Maximum Induced Matching problem. Moreover, we give a moderately exponential time \(\rho\)-approximation algorithm, \(0 < \rho < 1\), for the Maximum Induced Matching problem. For \(\rho =0.5\), the algorithm runs in time \(O^\ast(1.3348^n)\).

MSC:

90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balakrishnan, H., Barrett, C.L., Anil Kumar, V.S., Marathe, M.V., Thite., S.: The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks. IEEE J. Select. Areas Commun. 22 (6), 1069-1079 (2004) · Zbl 0957.68095
[2] Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the \[2^n2\] n-barrier for irredundance: two lines of attack. J. Discret. Algorithms 9, 214-230 (2011) · Zbl 1225.05227 · doi:10.1016/j.jda.2011.03.002
[3] Bourgeois, N., Escoffier, B., Paschos, VTh: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159, 1954-1970 (2011) · Zbl 1237.05146
[4] Cardoso, D.M., Kaminski, M., Lozin, V.: Maximum \[k\] k-regular induced subgraphs, Rutcor Research Report (RRR) 3 (2006) · Zbl 1149.90169
[5] Cameron, K.: Induced matching. Discret. Appl. Math. 24, 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. Discret. Math. 266, 133-142 (2003) · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8
[7] Cameron, K.: Induced matchings in intersection graphs. Discret. Math. 278, 1-9 (2004) · Zbl 1033.05080 · doi:10.1016/j.disc.2003.05.001
[8] Chalermsook, P., Laekhanukit, B., Nanongkai, D.: Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In Proceedings of FOCS 2013, pp. 370-379 · Zbl 1082.68592
[9] Chang, J.-M.: Induced matching in asteroidal triple-free graphs. Discret. Appl. Math. 132, 67-78 (2004) · Zbl 1029.05120 · doi:10.1016/S0166-218X(03)00390-1
[10] Chang, M-S; Hung, L-J; Miau, C-A; Chang, RS (ed.); Jain, LC (ed.); Peng, S-L (ed.), An \[O^{\ast }(1.4786^n)O\]*(1.4786n)-time algorithm for the maximum induced matching problem, 49-58 (2013), Berlin
[11] Christou, I.T., Vassilaras, S.: A parallel hybrid greedy branch and bound scheme for the maximum distace-2 matching problem. Comput. Operat. Res. 40, 2387-2397 (2013) · Zbl 1348.90592 · doi:10.1016/j.cor.2013.04.009
[12] Cygan, M., Pilipczuk, M., Wojtaszczyk, JO.: Irredundant set faster than \[O(2^n)O\](2n). In: Proceedings of CIAC 2010, LNCS 6078, pp. 288-298 (2010) · Zbl 1284.05279
[13] Dabrowski, K., Demange, M., Lozin, V.V.: New results on maximum induced matchings in bipartite graphs and beyond. Theor. Comput. Sci. 478, 33-40 (2013) · Zbl 1267.68118 · doi:10.1016/j.tcs.2013.01.027
[14] 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
[15] Erman, R., Kowalik, Ł., Krnc, M., Waleń, T.: Improved induced matching in sparse graphs. Discret. Appl. Math. 158, 1994-2003 (2010) · Zbl 1215.05129 · doi:10.1016/j.dam.2010.08.026
[16] Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010) · Zbl 1370.68002 · doi:10.1007/978-3-642-16533-7
[17] Fricke, G., Laskar, R.: String matching in trees. Congr. Numer. 89, 239-243 (1992) · Zbl 0786.05065
[18] Gupta, S., Raman, V., Saurabh, S.: Maximum \[r\] r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discret. Math. 26, 1758-1780 (2012) · Zbl 1261.05066 · doi:10.1137/09077850X
[19] Hosono, K.: Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25, 27-29 (1990) · Zbl 0735.05027
[20] Kang, R.J., Mnich, M., Müller, T.: Induced matchings in subcubic planar graphs. SIAM J. Discret. Math. 26, 1383-1411 (2012) · Zbl 1256.05191 · doi:10.1137/100808824
[21] Kanj, I., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. J. Comput. Syst. Sci. 77, 1058-1070 (2011) · Zbl 1235.05114 · doi:10.1016/j.jcss.2010.09.001
[22] Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid cover. SIAM J. Discret. Math. 16, 327-346 (2003) · Zbl 1029.05097 · doi:10.1137/S089548019828371X
[23] Kobler, D., Rotics, U.: Finding maximum induced matching 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 (2003) · Zbl 1082.68592 · doi:10.1007/s00453-003-1035-4
[24] Krishnamurthy, C.M., Sritharan, R.: Maximum induced matching problem on hhd-free graphs. Discret. Appl. Math. 160, 224-230 (2012) · Zbl 1237.05166 · doi:10.1016/j.dam.2011.08.027
[25] 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
[26] Lozin, V.V., Mosca, R.: Maximum regular induced subgraphs in \[2P_32\] P3-free graphs. Theor. Comput. Sci. 460, 26-33 (2012) · Zbl 1252.68155 · doi:10.1016/j.tcs.2012.06.014
[27] Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem in planar graphs. Discret. Appl. Math. 157, 715-727 (2009) · Zbl 1172.05350 · doi:10.1016/j.dam.2008.07.011
[28] Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7, 181-190 (2009) · Zbl 1187.68351 · doi:10.1016/j.jda.2008.09.005
[29] Orlovich, Y., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5, 584-593 (2008) · Zbl 1140.90479 · doi:10.1016/j.disopt.2007.11.010
[30] Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425-440 (1986) · Zbl 0637.68080 · doi:10.1016/0196-6774(86)90032-5
[31] 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
[32] Vassilaras, S., Christou, I.T.: On the optimal MAC layer capacity of delay tolerant mobile Ad Hoc networks with a finite number of nodes, In: 22nd annual IEEE international symposium on personal, indoor and mobile radio communication (PIMRC’11) (2011) · Zbl 0957.68095
[33] 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.