Chapter XV Hitting Set

Hit them all

Vertex cover is hitting set on edges (size-2 sets). Hitting set is just vertex cover with arbitrary set sizes.

A hitting set for a family F is a set that intersects every member:

H \subseteq U such that H \cap S \neq = \emptyset for every S \in F . (1)

Minimum hitting set is NP-hard (Karp). The bounded-width special case — every set in F has size at most d — is fixed-parameter tractable in the answer size k, with running time

O (d^{k} \cdot n) . (2)

The runtime (2) is fast when both d (the set width) and k (the cover size) are small.

The reduction between hitting set and set cover is so direct that the two problems are essentially the same, framed from opposite sides: in set cover the elements are passive and you pick sets; in hitting set the sets are passive and you pick elements.

Figures, in plain terms

(1)

H ⊆ U picks a subset of the universe — the elements we choose to be our "hitters."

The condition uses the same intersection notation as vertex cover: H ∩ S is the elements common to H and S, and ≠ ∅ says that intersection is non-empty.

So the condition reads: H and S share at least one element.

for every S ∈ F demands this holds for every set in the family. No set is allowed to escape with zero elements in H.

Compared to vertex cover (chapter 5), each "edge" was a pair {u, v} — a 2-element set. Hitting set just lets each "edge" be a set of any size. That's why d-hitting-set, where each set has size at most d, generalizes vertex cover at d = 2.

(2)

O(d^k · n) is exponential in two parameters: d (the maximum set size in the family) and k (the answer size).

If d and k are both small constants, the runtime is just O(n) — linear in the input size.

For 4-hitting-set with answer size at most 10: 4^10 = ~1 million. Multiply by n and you have a fast algorithm even for very large families.