The parameterized complexity of the induced matching problem. (English) Zbl 1172.05350
Summary: Given a graph \(G\) and an integer \(k\geq 0\), the NP-complete Induced Matching problem asks whether there exists an edge subset \(M\) of size at least \(k\) such that \(M\) is a matching and no two edges of \(M\) are joined by an edge of \(G\). The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is \(W\)[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
induced matching; parameterized complexity; planar graph; kernelization; tree decompositionReferences:
| [1] | Alber, J.; Bodlaender, H. L.; Fernau, H.; Kloks, T.; Niedermeier, R., Fixed parameter algorithms for dominating set and related problems on planar graphs, Algorithmica, 33, 4, 461-493 (2002) · Zbl 1016.68055 |
| [2] | Alber, J.; Dorn, B.; Niedermeier, R., A general data reduction scheme for domination in graphs, (Proceedings of SOFSEM’06. Proceedings of SOFSEM’06, LNCS, vol. 3831 (2006), Springer), 137-147 · Zbl 1175.68193 |
| [3] | Alber, J.; Fellows, M. R.; Niedermeier, R., Polynomial-time data reduction for dominating set, Journal of the ACM, 51, 3, 363-384 (2004) · Zbl 1192.68337 |
| [4] | Alber, J.; Niedermeier, R., Improved tree decomposition based algorithms for domination-like problems, (Proceedings of LATIN’02. Proceedings of LATIN’02, LNCS, vol. 2286 (2002), Springer), 613-628 · Zbl 1059.68598 |
| [5] | Bodlaender, H. L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, 25, 6, 1305-1317 (1996) · Zbl 0864.68074 |
| [6] | Bodlaender, H. L., Treewidth: Algorithmic techniques and results, (Proceedings of MFCS’97. Proceedings of MFCS’97, LNCS, vol. 1295 (1997), Springer), 19-36 · Zbl 0941.05057 |
| [7] | Bodlaender, H. L., Treewidth: Characterizations, applications, and computations, (Proceedings of WG’06. Proceedings of WG’06, LNCS, vol. 4271 (2006), Springer), 1-14 · Zbl 1167.68404 |
| [8] | Cameron, K., Induced matchings, Discrete Applied Mathematics, 24, 97-102 (1989) · Zbl 0687.05033 |
| [9] | Cameron, K., Induced matchings in intersection graphs, Discrete Mathematics, 278, 1-3, 1-9 (2004) · Zbl 1033.05080 |
| [10] | Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Mathematics, 266, 1-3, 133-142 (2003) · Zbl 1022.05064 |
| [11] | Chen, J.; Fernau, H.; Kanj, I. A.; Xia, G., Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, SIAM Journal on Computing, 37, 4, 1077-1106 (2007) · Zbl 1141.05075 |
| [12] | Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems, (Proceedings of ESA’04. Proceedings of ESA’04, LNCS, vol. 3221 (2004), Springer), 192-203 · Zbl 1111.68782 |
| [13] | Courcelle, B., The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, 85, 1, 12-75 (1990) · Zbl 0722.03008 |
| [14] | Downey, R.; Fellows, M. R.; Raman, V., The complexity of irredundant sets parameterized by size, Discrete Applied Mathematics, 100, 3, 155-167 (2000) · Zbl 0948.68133 |
| [15] | Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076 |
| [16] | Duckworth, W.; Manlove, D.; Zito, M., On the approximability of the maximum induced matching problem, Journal of Discrete Algorithms, 3, 1, 79-91 (2005) · Zbl 1075.68063 |
| [17] | Faudree, R. J.; Flandrin, E.; Ryjácek, Z., Claw-free graphs—A survey, Discrete Mathematics, 164, 1-3, 87-147 (1997) · Zbl 0879.05043 |
| [18] | Fellows, M. R., The lost continent of polynomial time: Preprocessing and kernelization, (Proceedings of IWPEC’06. Proceedings of IWPEC’06, LNCS, vol. 4169 (2006), Springer), 276-277 · Zbl 1154.68560 |
| [19] | Flum, J.; Grohe, M., Parameterized Complexity Theory (2006), Springer · Zbl 1143.68016 |
| [20] | Fomin, F. V.; Thilikos, D. M., Fast parameterized algorithms for graphs on surfaces: Linear kernel and exponential speed-up, (Proceedings of ICALP’04. Proceedings of ICALP’04, LNCS, vol. 3142 (2004), Springer), 581-592 · Zbl 1099.68077 |
| [21] | Fricke, G.; Laskar, R., String matching in trees, Congressum Numerantium, 89, 239-243 (1992) · Zbl 0786.05065 |
| [22] | Golumbic, M. C.; Laskar, R., Irredundancy in circular arc graphs, Discrete Applied Mathematics, 44, 1-3, 79-89 (1993) · Zbl 0783.05059 |
| [23] | Golumbic, M. C.; Lewenstein, M., New results on induced matchings, Discrete Applied Mathematics, 101, 1-3, 157-165 (2000) · Zbl 0951.68104 |
| [24] | Gotthilf, Z.; Lewenstein, M., Tighter approximations for maximum induced matchings in regular graphs, (Proceedings of WAOA’05. Proceedings of WAOA’05, LNCS, vol. 3879 (2005), Springer), 270-281 · Zbl 1177.68256 |
| [25] | Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, ACM SIGACT News, 38, 1, 31-45 (2007) |
| [26] | Guo, J.; Niedermeier, R., Linear problem kernels for NP-hard problems on planar graphs, (Proceedings of ICALP’07. Proceedings of ICALP’07, LNCS, vol. 4596 (2007), Springer), 375-386 · Zbl 1171.68488 |
| [27] | Guo, J.; Niedermeier, R.; Wernicke, S., Fixed-parameter tractability results for full-degree spanning tree and its dual, (Proceedings of IWPEC’06. Proceedings of IWPEC’06, LNCS, vol. 4169 (2006), Springer), 203-214 · Zbl 1154.68425 |
| [28] | I.A. Kanj, M.J. Pelsmajer, G. Xia, M. Schaefer, On the induced matching problem, in: Proceedings of STACS’08, Internationales Begegnungs- und Forschungszentrum für Informatik, IBFI, Schloss Dagstuhl, Germany, 2008, pp. 397-408; I.A. Kanj, M.J. Pelsmajer, G. Xia, M. Schaefer, On the induced matching problem, in: Proceedings of STACS’08, Internationales Begegnungs- und Forschungszentrum für Informatik, IBFI, Schloss Dagstuhl, Germany, 2008, pp. 397-408 · Zbl 1259.68095 |
| [29] | Kloks, T., (Treewidth, Computations and Approximations. Treewidth, Computations and Approximations, LNCS, vol. 842 (1994), Springer) · Zbl 0825.68144 |
| [30] | Kneis, J.; Mölle, D.; Richter, S.; Rossmanith, P., Divide-and-color, (Proceedings of WG’06. Proceedings of WG’06, LNCS, vol. 4271 (2006), Springer), 58-67 · Zbl 1167.68411 |
| [31] | Ko, C. W.; Shepherd, F. B., Bipartite domination and simultaneous matroid covers, SIAM Journal on Discrete Mathematics, 16, 4, 517-523 (2003) · Zbl 1029.05097 |
| [32] | 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 |
| [33] | Lozin, V. V., On maximum induced matchings in bipartite graphs, Information Processing Letters, 81, 1, 7-11 (2002) · Zbl 1046.68081 |
| [34] | Lozin, V. V.; Rautenbach, D., Some results on graphs without long induced paths, Information Processing Letters, 88, 4, 167-171 (2003) · Zbl 1178.68285 |
| [35] | Moser, H.; Thilikos, D. M., Parameterized complexity of finding regular induced subgraphs, (Proceedings of ACiD’06. Proceedings of ACiD’06, Texts in Algorithmics, vol. 7 (2006), College Publications), 107-118 |
| [36] | Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [37] | Orlovich, Y.; Finke, G.; Gordon, V.; Zverovich, I., Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optimization, 5, 584-593 (2008) · Zbl 1140.90479 |
| [38] | Raman, V.; Saurabh, S., Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, Algorithmica, 52, 2, 203-225 (2008) · Zbl 1170.68019 |
| [39] | Roussopoulos, N. D., A \(\max \{m, n \}\) algorithm for determining the graph \(H\) from its line graph \(G\), Information Processing Letters, 2, 4, 108-112 (1973) · Zbl 0274.05116 |
| [40] | Stockmeyer, L. J.; Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Information Processing Letters, 15, 1, 14-19 (1982) · Zbl 0493.68039 |
| [41] | H. Fernau, D. Raible, A parameterized perspective on packing paths of length two, in: Proceedings of COCOA’08, in: LNCS, vol. 5165, Springer, 2008, pp. 54-63. (doi:10.1007/978-3-540-85097-7_6; H. Fernau, D. Raible, A parameterized perspective on packing paths of length two, in: Proceedings of COCOA’08, in: LNCS, vol. 5165, Springer, 2008, pp. 54-63. (doi:10.1007/978-3-540-85097-7_6 · Zbl 1168.05358 |
| [42] | Zito, M., Induced matchings in regular graphs and trees, (Proceedings of WG’99. Proceedings of WG’99, LNCS, vol. 1665 (1999), Springer), 89-100 · Zbl 0941.05052 |
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.
