Header menu link for other important links
X

Diverse collections in matroids and graphs

Fomin F.V., Golovach P.A., , Philip G., Saurabh S.
Published in Springer Science and Business Media Deutschland GmbH
2023
Abstract
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 M, a weight function ω: E(M) → N, and integers k≥ 1 , d≥ 1. The task is to decide if there is a collection of kbasesB1, ⋯ , Bk of M such that the weight of the symmetric difference of any pair of these bases is at least d. The input to the Weighted Diverse Common Independent Sets problem consists of two matroids M1, M2 defined on the same ground set E, a weight function ω: E→ N, and integers k≥ 1 , d≥ 1. The task is to decide if there is a collection of kcommon independent setsI1, ⋯ , Ik of M1 and M2 such that the weight of the symmetric difference of any pair of these sets is at least d. The input to the Diverse Perfect Matchings problem consists of a graph G and integers k≥ 1 , d≥ 1. The task is to decide if G contains kperfect matchingsM1, ⋯ , Mk such that the symmetric difference of any two of these matchings is at least d. We show that none of these problems can be solved in polynomial time unless P=NP. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k, d) as the parameter, and present a poly(k, d) -sized kernel for Weighted Diverse Bases. © 2023, The Author(s).
About the journal
JournalMathematical Programming
PublisherSpringer Science and Business Media Deutschland GmbH
ISSN00255610
Open AccessNo