We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems. The input to the Weighted Diverse Bases problem consists of a matroid , a weight function , and integers . The task is to decide if there is a collection of bases of such that the weight of the symmetric difference of any pair of these bases is at least . The input to the Weighted Diverse Common Independent Sets problem consists of two matroids defined on the same ground set , a weight function , and integers . The task is to decide if there is a collection of common independent sets of and such that the weight of the symmetric difference of any pair of these sets is at least . The input to the Diverse Perfect Matchings problem consists of a graph and integers . The task is to decide if contains perfect matchings such that the symmetric difference of any two of these matchings is at least . We show that none of these problems can be solved in polynomial time unless . We derive fixed-parameter tractable () algorithms for all three problems with as the parameter, and present a -sized kernel for Weighted Diverse Bases.
Keywords: Diversity of solutions; Graphs; Matroids; Parameterized complexity.
© The Author(s) 2023.