2026-07-25T03:07:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13370 2024-03-06T10:51:48Z ddc:004 open_access

Diverse Pairs of Matchings Fomin, Fedor V. Golovach, Petr A. Jaffke, Lars Philip, Geevarghese Sagunov, Danil Matching Solution Diversity Fixed-Parameter Tractability We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k 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 Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Lars Jaffke and Geevarghese Philip and Danil Sagunov 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.26 urn:nbn:de:0030-drops-133706 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode