Julien Baste, Lars Jaffke, Tomáš Masařík,
Geevarghese Philip, and Günter Rote:
FPT algorithms for diverse collections of hitting sets
-
Algorithms
12 (2019), Article 254, 18 pages. doi:10.3390/a12120254, arXiv:1911.05032 [cs.DS].
→BibTeX
- Reprinted in New Frontiers in Parameterized Complexity and Algorithms.
Editors: Frances Rosamond, Neeldhara Misra, and Meirav
Zehavi. MDPI, 2024, pp. 122–139. doi:10.3390/books978-3-7258-1302-5. →BibTeX
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
-
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|2.
A correct replacement for the term |U|2 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.
-
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.
Last update: August 19, 2024.