Diverse Pairs of Matchings
Journal article, Peer reviewed
Published version
![Thumbnail](/bora-xmlui/bitstream/handle/11250/2755713/LIPIcs-ISAAC-2020-26.pdf.jpg?sequence=6&isAllowed=y)
View/ Open
Date
2020Metadata
Show full item recordCollections
- Department of Informatics [978]
- Registrations from Cristin [10237]
Original version
Leibniz International Proceedings in Informatics. 2020, 181, 26:1-26:12 10.4230/LIPIcs.ISAAC.2020.26Abstract
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.