# FPT Algorithms for Diverse Collections of Hitting Sets

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2019.

## 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)
- [Diversity in Kemeny Rank Aggregation: A Parameterized Approach](https://mlsanity.com/paper/2105.09413/) (2021)
- [Heuristic for Diverse Kemeny Rank Aggregation based on Quantum Annealing](https://mlsanity.com/paper/2301.05146/) (2023)

## Abstract (arXiv)

In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity [Baste et al., 2019]. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process which models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are FPT in k + r for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of `base' solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.