Header menu link for other important links
X
Diverse collections in matroids and graphs
F.V. Fomin, P.A. Golovach, , G. Philip, S. Saurabh
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2021
Volume: 187
   
Abstract
We investigate the parameterized complexity of finding diverse sets of solutions to three fundamental combinatorial problems, two from the theory of matroids and the third from graph theory. The input to the Weighted Diverse Bases problem consists of a matroid M, a weight function ω: E(M) → N, and integers k ≥ 1, d ≥ 0. The task is to decide if there is a collection of k bases B1,..., Bk of M such that the weight of the symmetric difference of any pair of these bases is at least d. This is a diverse variant of the classical matroid base packing problem. 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 ≥ 0. The task is to decide if there is a collection of k common independent sets I1,..., Ik of M1 and M2 such that the weight of the symmetric difference of any pair of these sets is at least d. This is motivated by the classical weighted matroid intersection problem. The input to the Diverse Perfect Matchings problem consists of a graph G and integers k ≥ 1, d ≥ 0. The task is to decide if G contains k perfect matchings M1,..., Mk such that the symmetric difference of any two of these matchings is at least d. The underlying problem of finding one solution (basis, common independent set, or perfect matching) is known to be doable in polynomial time for each of these problems, and Diverse Perfect Matchings is known to be NP-hard for k = 2. We show that Weighted Diverse Bases and Weighted Diverse Common Independent Sets are both NP-hard. We show also that Diverse Perfect Matchings cannot be solved in polynomial time (unless P = NP) even for the case d = 1. We derive fixed-parameter tractable (FPT) algorithms for all three problems with (k, d) as the parameter. The above results on matroids are derived under the assumption that the input matroids are given as independence oracles. For Weighted Diverse Bases we present a polynomial-time algorithm that takes a representation of the input matroid over a finite field and computes a poly(k, d)-sized kernel for the problem. © Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh; licensed under Creative Commons License CC-BY 4.0.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969