patternMinor
Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"
Viewed 0 times
hittinginclusionwithbooktheoryparameterizedrespectcomplexityminimalfrom
Problem
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
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
Solution
It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of minimum cardinality, not a minimal set.
A set $S$ is called minimal with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.
On the other hand, a set $S$ is said to have minimum size or cardinality with respect to some property if there exists no set $T$ of strictly smaller size (i.e. $|T|< |S|$) that also satisfies this property.
A minimum size set must be minimal (why?), but a minimal set need not be of minimum size (why?).
In the example in the book, the set $\{b,c,d\}$ is not a minimal hitting set, because its strict subset $\{c,d\}$ is also a hitting set. The subset $\{b,d,f\}$ is a minimal hitting set, because it has no strict subset that is a hitting set. It is not a minimum hitting set, because there is a hitting set of size $2$ ($\{c,d\}$).
A set $S$ is called minimal with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.
On the other hand, a set $S$ is said to have minimum size or cardinality with respect to some property if there exists no set $T$ of strictly smaller size (i.e. $|T|< |S|$) that also satisfies this property.
A minimum size set must be minimal (why?), but a minimal set need not be of minimum size (why?).
In the example in the book, the set $\{b,c,d\}$ is not a minimal hitting set, because its strict subset $\{c,d\}$ is also a hitting set. The subset $\{b,d,f\}$ is a minimal hitting set, because it has no strict subset that is a hitting set. It is not a minimum hitting set, because there is a hitting set of size $2$ ($\{c,d\}$).
Context
StackExchange Computer Science Q#113283, answer score: 3
Revisions (0)
No revisions yet.