Moderately exponential time algorithms for the maximum induced matching problem

详细信息    查看全文

• 作者：Maw-Shang Chang ; Li-Hsuan Chen ; Ling-Ju Hung
• 关键词：Induced matching ; Branch and reduce ; Measure and conquer ; Approximation algorithm
• 刊名：Optimization Letters
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：9
• 期：5
• 页码：981-998
• 全文大小：606 KB
• 参考文献：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鈥?079 (2004)
  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^n\) -barrier for irredundance: two lines of attack. J. Discret. Algorithms 9, 214鈥?30 (2011)View Article MATH MathSciNet
  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鈥?970 (2011)MATH MathSciNet
  4.Cardoso, D.M., Kaminski, M., Lozin, V.: Maximum \(k\) -regular induced subgraphs, Rutcor Research Report (RRR) 3 (2006)
  5.Cameron, K.: Induced matching. Discret. Appl. Math. 24, 97鈥?02 (1989)View Article MATH
  6.Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discret. Math. 266, 133鈥?42 (2003)View Article MATH MathSciNet
  7.Cameron, K.: Induced matchings in intersection graphs. Discret. Math. 278, 1鈥? (2004)View Article MATH
  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鈥?79
  9.Chang, J.-M.: Induced matching in asteroidal triple-free graphs. Discret. Appl. Math. 132, 67鈥?8 (2004)View Article
  10.Chang, M.-S., Hung, L.-J., Miau, C.-A.: An \(O^{\ast }(1.4786^n)\) -time algorithm for the maximum induced matching problem. In: Chang, R.S., Jain, L.C., Peng, S.-L. (eds.) Proceedings of ICS 2012: algorithms and bioinformatics workshop, advances in intelligent systems and application, SIST 20, pp. 49鈥?8. Springer, Berlin (2013)
  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鈥?397 (2013)View Article MathSciNet
  12.Cygan, M., Pilipczuk, M., Wojtaszczyk, JO.: Irredundant set faster than \(O(2^n)\) . In: Proceedings of CIAC 2010, LNCS 6078, pp. 288鈥?98 (2010)
  13.Dabrowski, K., Demange, M., Lozin, V.V.: New results on maximum induced matchings in bipartite graphs and beyond. Theor. Comput. Sci. 478, 33鈥?0 (2013)View Article MATH MathSciNet
  14.Duckworth, W., Manlove, D.F., Zito, M.: On the approximability of the maximum induced matching problem. J. Discret. Algorithms 3, 79鈥?1 (2005)View Article MATH MathSciNet
  15.Erman, R., Kowalik, 艁., Krnc, M., Wale艅, T.: Improved induced matching in sparse graphs. Discret. Appl. Math. 158, 1994鈥?003 (2010)View Article MATH
  16.Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Berlin (2010)View Article MATH
  17.Fricke, G., Laskar, R.: String matching in trees. Congr. Numer. 89, 239鈥?43 (1992)MathSciNet
  18.Gupta, S., Raman, V., Saurabh, S.: Maximum \(r\) -regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discret. Math. 26, 1758鈥?780 (2012)View Article MATH MathSciNet
  19.Hosono, K.: Induced forests in trees and outerplanar graphs. Proc. Fac. Sci. Tokai Univ. 25, 27鈥?9 (1990)MATH MathSciNet
  20.Kang, R.J., Mnich, M., M眉ller, T.: Induced matchings in subcubic planar graphs. SIAM J. Discret. Math. 26, 1383鈥?411 (2012)View Article MATH
  21.Kanj, I., Pelsmajer, M.J., Schaefer, M., Xia, G.: On the induced matching problem. J. Comput. Syst. Sci. 77, 1058鈥?070 (2011)View Article MATH MathSciNet
  22.Ko, C.W., Shepherd, F.B.: Bipartite domination and simultaneous matroid cover. SIAM J. Discret. Math. 16, 327鈥?46 (2003)View Article MathSciNet
  23.Kobler, D., Rotics, U.: Finding maximum induced matching 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鈥?46 (2003)View Article MATH MathSciNet
  24.Krishnamurthy, C.M., Sritharan, R.: Maximum induced matching problem on hhd-free graphs. Discret. Appl. Math. 160, 224鈥?30 (2012)View Article MATH MathSciNet
  25.Lozin, V.V.: On maximum induced matchings in bipartite graphs. Inf. Process. Lett. 81, 7鈥?1 (2002)View Article MATH MathSciNet
  26.Lozin, V.V., Mosca, R.: Maximum regular induced subgraphs in \(2P_3\) -free graphs. Theor. Comput. Sci. 460, 26鈥?3 (2012)View Article MATH MathSciNet
  27.Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem in planar graphs. Discret. Appl. Math. 157, 715鈥?27 (2009)View Article MATH MathSciNet
  28.Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discret. Algorithms 7, 181鈥?90 (2009)View Article MATH MathSciNet
  29.Orlovich, Y., Finke, G., Gordon, V., Zverovich, I.: Approximability results for the maximum and minimum maximal induced matching problems. Discret. Optim. 5, 584鈥?93 (2008)View Article MATH MathSciNet
  30.Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425鈥?40 (1986)View Article MATH MathSciNet
  31.Stockmeyer, L.J., Vazirani, V.V.: NP-completeness of some generalizations of the maximum matching problem. Inf. Process. Lett. 15, 14鈥?9 (1982)View Article MATH MathSciNet
  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鈥?1) (2011)
  33.Zito, M.: Linear time maximum induced matching algorithm for trees. Nord. J. Comput. 7, 58鈥?3 (2000)MATH MathSciNet
  
• 作者单位：Maw-Shang Chang (1)
  Li-Hsuan Chen (2)
  Ling-Ju Hung (1)
  
  1. Department of Computer Science and Information Engineering, HungKuang University, 43302, Sha Lu, Taichung, Taiwan
  2. Department of Computer Science and Information Engineering, National Chung Cheng University, 62102, Min-Hsiung, Chiayi, Taiwan
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

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^{*}(1.4658^n)\) which is faster than previously known algorithms. By adding two branching rules in the simple exact algorithm, we obtain an \(O^{*}(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^{*}(1.3348^n)\).