# Diverse Pairs of Matchings

arXiv: https://arxiv.org/abs/2009.04567 · HTML: https://mlsanity.com/paper/2009.04567/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2020.

## Built on by (most cited first, 4 of 4)

- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study](https://mlsanity.com/paper/2112.05403/) (2021)
- [Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing](https://mlsanity.com/paper/2301.05146/) (2023)
- [Representative Sets in Propositional Abduction](https://mlsanity.com/paper/2607.21183/) (2026)

## Abstract (arXiv)

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 O(k2) vertices.