Diverse Pairs of Matchings Article Swipe
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1007/s00453-024-01214-7
· OA: W3084126163
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 $$\textsf{NP}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>NP</mml:mi></mml:math> -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 $$\textsf{FPT}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>FPT</mml:mi></mml:math> parameterized by k . We round off the work by showing that Diverse Pair of Matchings has a kernel on $${\mathcal {O}}(k^2)$$ <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> vertices.
