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


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\}$).

  • $\begingroup$ Thanks, I now understand. $\endgroup$
    – Domination
    Sep 3 '19 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.