Julien Baste, Lars Jaffke, Tomáš Masařík, Geevarghese Philip, and Günter Rote:

FPT algorithms for diverse collections of hitting sets

Abstract

We study the 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]. 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. This could be of independent interest.

Errata

1. In the "folklore" Lemma 1 at the bottom of p. 10 (of the journal version), the polynomial part of the running time must somehow involve the size of the input, i.e., the total size of the sets in the family S, and this is not captured by the term |U|². A correct replacement for the term |U|² is in fact the total size of the sets in S, or in other words, the number of edges of the bipartite incidence graph that represents the input.
2. The analysis at the bottom of p. 12 (of the journal version), showing that the depth of the branching process in Lemma 2 is at most 2k, is incomplete (but the claim is valid). Consider the third case, where we have a path vpw of three vertices in C and both v and w have a neighbor in B. Then one of the 8 branching possibilities assigns v and w to A and p to B. This may increase cc(B) by 1, but it simultaneously increases |A| by 2. Thus, also in this case, the conclusion that |A|−cc(B) increases by at least 1 remains valid.