{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:57Z","timestamp":1771036377861,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T00:00:00Z","timestamp":1710460800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T00:00:00Z","timestamp":1710460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We initiate the study of the<jats:sc>Diverse Pair of (Maximum\/ Perfect) Matchings<\/jats:sc>problems which given a graph<jats:italic>G<\/jats:italic>and an integer<jats:italic>k<\/jats:italic>, ask whether<jats:italic>G<\/jats:italic>has two (maximum\/perfect) matchings whose symmetric difference is at least<jats:italic>k<\/jats:italic>.<jats:sc>Diverse Pair of Matchings<\/jats:sc>(asking for two not necessarily maximum or perfect matchings) is<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>NP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete on general graphs if<jats:italic>k<\/jats:italic>is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that<jats:sc>Diverse Pair of Maximum Matchings<\/jats:sc>is<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{FPT}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>FPT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>parameterized by<jats:italic>k<\/jats:italic>. We round off the work by showing that<jats:sc>Diverse Pair of Matchings<\/jats:sc>has a kernel on<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {O}}(k^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>k<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>vertices.<\/jats:p>","DOI":"10.1007\/s00453-024-01214-7","type":"journal-article","created":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T08:02:23Z","timestamp":1710489743000},"page":"2026-2040","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Diverse Pairs of Matchings"],"prefix":"10.1007","volume":"86","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danil","family":"Sagunov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,3,15]]},"reference":[{"issue":"4","key":"1214_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"1214_CR2","doi-asserted-by":"crossref","unstructured":"Baste, J., Fellows, M.R., Jaffke, L., Masa\u0159\u00edk, T., de\u00a0Oliveira\u00a0Oliveira, M., Philip, G., Rosamond, F.A.: Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory. In: IJCAI 2020, pp. 1119\u20131125 (2020)","DOI":"10.24963\/ijcai.2020\/156"},{"issue":"12","key":"1214_CR3","doi-asserted-by":"publisher","first-page":"254","DOI":"10.3390\/a12120254","volume":"12","author":"J Baste","year":"2019","unstructured":"Baste, J., Jaffke, L., Masa\u0159\u00edk, T., Philip, G., Rote, G.: FPT algorithms for diverse collections of hitting sets. Algorithms 12(12), 254 (2019)","journal-title":"Algorithms"},{"key":"1214_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984","volume-title":"Handbook of Computational Social Choice","author":"F Brandt","year":"2016","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D.: Handbook of Computational Social Choice. Cambridge University Press, Cambridge (2016)"},{"key":"1214_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"1214_CR6","volume-title":"Graph Theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2005)"},{"key":"1214_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"issue":"3","key":"1214_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17(3), 449\u2013467 (1965)","journal-title":"Can. J. Math."},{"key":"1214_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U., Ofek, E., Wieder, U.: Approximating maximum edge coloring in multigraphs. In: APPROX 2002, pp. 108\u2013121. Springer, Berlin (2002)","DOI":"10.1007\/3-540-45753-4_11"},{"key":"1214_CR10","unstructured":"Fellows, M.R..: The Diverse X paradigm. Manuscript (2018)"},{"key":"1214_CR11","unstructured":"Fomin, F.V., Golovach, P.A., Panolan, F., Philip, G., Saurabh, S.: Diverse collections in matroids and graphs. In: Bl\u00e4ser, M., Monmege, B. (eds.) STACS 2021, vol. 187 of LIPIcs, pp. 31:1\u201331:14. Schloss Dagstuhl (2021)"},{"key":"1214_CR12","volume-title":"Theory of Parameterized Preprocessing","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Theory of Parameterized Preprocessing. Cambridge University Press, Kernelization (2018)"},{"issue":"4","key":"1214_CR13","doi-asserted-by":"publisher","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":"1214_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1112\/jlms\/s1-10.37.26","volume":"10","author":"P Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 10, 26\u201330 (1935)","journal-title":"J. Lond. Math. Soc."},{"key":"1214_CR15","doi-asserted-by":"crossref","unstructured":"Hanaka, T., Kobayashi, Y., Kurita, K., Otachi, Y.: Finding diverse trees, paths, and more. In: AAAI 2021, pp 3778\u20133786. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i5.16495"},{"issue":"4","key":"1214_CR16","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981)","journal-title":"SIAM J. Comput."},{"key":"1214_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An $$n^{5\/2}$$ algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2, 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1214_CR18","doi-asserted-by":"publisher","first-page":"1334","DOI":"10.1137\/120899765","volume":"28","author":"M Jakub Kami\u0144ski","year":"2014","unstructured":"Jakub Kami\u0144ski, M., Kowalik, L.: Beyond the Vizing\u2019s bound for at most seven colors. SIAM J. Discrete Math. 28(3), 1334\u20131362 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"1214_CR19","first-page":"49","volume":"215","author":"AV Karzanov","year":"1974","unstructured":"Karzanov, A.V.: The problem of finding the maximal flow in a network by the method of preflows. Dokl. Akad. Nauk SSSR 215, 49\u201352 (1974)","journal-title":"Dokl. Akad. Nauk SSSR"},{"issue":"4","key":"1214_CR20","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/BF01456961","volume":"77","author":"D K\u0151nig","year":"1916","unstructured":"K\u0151nig, D.: \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77(4), 453\u2013465 (1916)","journal-title":"Math. Ann."},{"key":"1214_CR21","unstructured":"Lov\u00e1sz, L.: On determinants, matchings, and random algorithms. In: Fundamentals of Computation Theory. Akademie Verlag, pp. 565\u2013574 (1979)"},{"key":"1214_CR22","volume-title":"Matching Theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. AMS, Providence (2009)"},{"key":"1214_CR23","doi-asserted-by":"crossref","unstructured":"M\u0105dry, A.: Navigating central path with electrical flows: From flows to matchings, and back. In: FOCS 2013, pp. 253\u2013262. IEEE Computer Society (2013)","DOI":"10.1109\/FOCS.2013.35"},{"key":"1214_CR24","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: FOCS 2004, pp. 248\u2013255. IEEE Computer Society (2004)","DOI":"10.1007\/978-3-540-30140-0_48"},{"key":"1214_CR25","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: FOCS pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"2","key":"1214_CR26","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1145\/3363825","volume":"63","author":"T Olsson","year":"2020","unstructured":"Olsson, T., Huhtam\u00e4ki, J., K\u00e4rkk\u00e4inen, H.: Directions for professional social matching systems. Commun. ACM 63(2), 60\u201369 (2020)","journal-title":"Commun. ACM"},{"key":"1214_CR27","unstructured":"O\u2019Malley, G.: Algorithmic Aspects of Stable Matching Problems. PhD thesis, University of Glasgow (2007)"},{"issue":"4","key":"1214_CR28","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"MO Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. J. Algorithms 10(4), 557\u2013567 (1989)","journal-title":"J. Algorithms"},{"key":"1214_CR29","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency, vol. A. Springer, Berlin (2003)"},{"key":"1214_CR30","unstructured":"Suomela, J.: Complexity of two perfect matchings with minimum shared edges? Theoretical Computer Science Stack Exchange (2010) https:\/\/cstheory.stackexchange.com\/q\/1291 (version: 2010-09-14)"},{"key":"1214_CR31","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6, 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"1214_CR32","unstructured":"Vazirani, V.V.: A Proof of the MV Matching Algorithm (2014)"},{"key":"1214_CR33","first-page":"25","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Discrete Anal. 3, 25\u201330 (1964)","journal-title":"Discrete Anal."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01214-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01214-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01214-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,14]],"date-time":"2024-11-14T10:23:06Z","timestamp":1731579786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01214-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,15]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1214"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01214-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,15]]},"assertion":[{"value":"19 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}