# Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

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?

## 1 Answer

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

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