Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”
-
05-11-2019 - |
Question
In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality.
In Fig. 1.3, the author says a black colored leaf is the minimal with respect to set inclusion and a hitting set consists of the vertices labeling the edges on the path from the root to the leaf. However, both grey and black colored hitting set consists of 3 vertices. Why grey colored leaf is not minimal in this case?
Related question: Given a set of sets, find the smallest set(s) containing at least one element from each set
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange