Open Access
- 15 March 2024
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 86 (6) , 2026-2040
Abstract
We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ -complete on general graphs ifkis 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 thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ vertices.
Keywords
All Related Versions
Funding Information
- University of Bergen
This publication has 23 references indexed in Scilit:
- Handbook of Computational Social Choice2016
- Parameterized Algorithms2015
- Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back2013
- Maximum Matchings in Planar Graphs via Gaussian Elimination2004
- Approximating Maximum Edge Coloring in Multigraphs2002
- Parameterized Complexity1999
- Maximum matchings in general graphs through randomizationJournal of Algorithms, 1989
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973
- On Representatives of SubsetsJournal of the London Mathematical Society, 1935
- Über Graphen und ihre Anwendung auf Determinantentheorie und MengenlehreMathematische Annalen, 1916