Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”
-
05-11-2019 - |
문제
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
올바른 솔루션이 없습니다
제휴하지 않습니다 cs.stackexchange