{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T17:25:16Z","timestamp":1784568316634,"version":"3.55.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/P020372\/1"],"award-info":[{"award-number":["EP\/P020372\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/16"],"award-info":[{"award-number":["NI 369\/16"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["NI 369\/16"],"award-info":[{"award-number":["NI 369\/16"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For <jats:italic>m<\/jats:italic>-edge and <jats:italic>n<\/jats:italic>-vertex graphs, it is well-known to be solvable in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(m\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mrow>\n<mml:mi>O<\/mml:mi>\n<mml:mo>(<\/mml:mo>\n<mml:mi>m<\/mml:mi>\n<mml:msqrt>\n<mml:mi>n<\/mml:mi>\n<\/mml:msqrt>\n<mml:mo>)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on <jats:italic>linear-time kernelization<\/jats:italic>. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.<\/jats:p>","DOI":"10.1007\/s00453-020-00736-0","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T07:02:25Z","timestamp":1594018945000},"page":"3521-3565","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The Power of Linear-Time Data Reduction for Maximum Matching"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7182-585X","authenticated-orcid":false,"given":"George B.","family":"Mertzios","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7451-9401","authenticated-orcid":false,"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"issue":"4","key":"736_CR1","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1137\/S0097539796305109","volume":"27","author":"R Bar-Yehuda","year":"1998","unstructured":"Bar-Yehuda, R., Geiger, D., Naor, J., Roth, R.M.: Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM J. Comput. 27(4), 942\u2013959 (1998)","journal-title":"SIAM J. Comput."},{"key":"736_CR2","doi-asserted-by":"crossref","unstructured":"Bartha, M., Kresz, M.: A depth-first algorithm to reduce graphs in linear time. In: Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC\u2019 09). IEEE, pp. 273\u2013281 (2009)","DOI":"10.1109\/SYNASC.2009.48"},{"key":"736_CR3","doi-asserted-by":"crossref","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP \u201990). Vol. 443. LNCS. Springer, pp. 586\u2013597 (1990)","DOI":"10.1007\/BFb0032060"},{"key":"736_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey, vol. 3. SIAM, SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"1","key":"736_CR5","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Appl. Math. 127(1), 415\u2013429 (2003)","journal-title":"Discrete Appl. Math."},{"key":"736_CR6","doi-asserted-by":"crossref","unstructured":"Chang, M.: Algorithms for maximum matching and minimum fill-in on Chordal bipartite graphs. In: Proceedings of the 7th International Symposium on Algorithms and Computation (ISAAC \u201996). Vol. 1178. LNCS. Springer, pp. 146\u2013155 (1996)","DOI":"10.1007\/BFb0009490"},{"issue":"1\u20133","key":"736_CR7","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0166-218X(98)00006-7","volume":"84","author":"E Dahlhaus","year":"1998","unstructured":"Dahlhaus, E., Karpinski, M.: Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Appl. Math. 84(1\u20133), 79\u201391 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"736_CR8","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2529989","volume":"61","author":"R Duan","year":"2014","unstructured":"Duan, R., Pettie, S.: Linear-time approximation for maximum weight matching. J. ACM 61(1), 1:1\u20131:23 (2014)","journal-title":"J. ACM"},{"issue":"3","key":"736_CR9","doi-asserted-by":"crossref","first-page":"34:1","DOI":"10.1145\/3186898","volume":"14","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Pilipczuk, M., Saurabh, S., Wrochna, M.: Fully polynomial-time parameterized computations for graphs and matrices of low Treewidth. ACM Trans. Algorithms 14(3), 34:1\u201334:45 (2018)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"736_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"HN Gabow","year":"1985","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209\u2013221 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"736_CR11","doi-asserted-by":"crossref","first-page":"815","DOI":"10.1145\/115234.115366","volume":"38","author":"HN Gabow","year":"1991","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph-matching problems. J. ACM 38(4), 815\u2013853 (1991)","journal-title":"J. ACM"},{"key":"736_CR12","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.tcs.2017.05.017","volume":"689","author":"AC Giannopoulou","year":"2017","unstructured":"Giannopoulou, A.C., Mertzios, G.B., Niedermeier, R.: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs. Theor. Comput. Sci. 689, 67\u201395 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"736_CR13","doi-asserted-by":"crossref","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC \u201904). Vol. 3162. LNCS. Springer, pp. 162\u2013173 (2004)","DOI":"10.1007\/978-3-540-28639-4_15"},{"key":"736_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully Dynamic (1+ e)-Approximate Matchings. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201913). IEEE, pp. 548\u2013557 (2013)","DOI":"10.1109\/FOCS.2013.65"},{"issue":"4","key":"736_CR15","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$\\text{ n }^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"736_CR16","unstructured":"Iwata, Y., Ogasawara, T., Ohsaka, N.: On the power of tree-depth for fully polynomial FPT algorithms. In: 35th Symposium on Theoretical Aspects of Computer Science (STACS \u201918). Vol. 96. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 41:1-41:14 (2018)"},{"key":"736_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R. M., Sipser, M.: Maximum matchings in sparse random graphs. In: Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201981). IEEE, pp. 364\u2013375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"key":"736_CR18","unstructured":"Korenwein, V., Nichterlein, A., Niedermeier, R., Zschoche, P.: Data reduction for maximum matching on real-world graphs: theory and experiments. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018). Vol. 112. LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 53:1-53:13 (2018)"},{"key":"736_CR19","unstructured":"Kratsch, S., Nelles, F.: Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018). Vol. 112. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 55:1-55:15 (2018)"},{"issue":"4","key":"736_CR20","doi-asserted-by":"crossref","first-page":"2820","DOI":"10.1137\/17M1120920","volume":"32","author":"GB Mertzios","year":"2018","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: Linear-time algorithm for maximum-cardinality matching on cocomparability graphs. SIAM J. Discrete Math. 32(4), 2820\u20132835 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"736_CR21","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V. V.: An $$O(\\sqrt{|V|} |E|)$$ algorithm for finding maximum matching in general graphs. In: Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201980). IEEE, pp. 17\u201327 (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"736_CR22","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS \u201904). IEEE, pp. 248\u2013255 (2004)"},{"key":"736_CR23","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Sparsity\u2014Graphs, Structures, and Algorithms, vol. 28. Springer, Algorithms and Combinatorics (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"736_CR24","volume-title":"The Algorithm Design Manual","author":"SS Skiena","year":"2010","unstructured":"Skiena, S.S.: The Algorithm Design Manual. Springer, Berlin (2010)"},{"key":"736_CR25","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G Steiner","year":"1996","unstructured":"Steiner, G., Yeomans, J.S.: A linear time algorithm for maximum matchings in convex bipartite graphs. Comput. Math. Appl. 31, 91\u201396 (1996)","journal-title":"Comput. Math. Appl."},{"issue":"1","key":"736_CR26","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00453-012-9625-7","volume":"66","author":"R Yuster","year":"2013","unstructured":"Yuster, R.: Maximum matching in regular and almost regular graphs. Algorithmica 66(1), 87\u201392 (2013)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00736-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00736-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00736-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,5]],"date-time":"2021-07-05T23:41:38Z","timestamp":1625528498000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00736-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":26,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["736"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00736-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"18 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}