Hitting Set Iterative Compression

In $$d$$ -Hitting Set, we are given a universe $$S$$ , a family $$C$$ of subsets of size at most $$d$$ , and a budget $$k$$ . The task is to decide whether there is a hitting set $H \subseteq S$ with $|H| \le k$ . These questions explore iterative compression assuming a solver for $$(d-1)$$ -Hitting Set.

Part A

Let $S = \{1,2,3,4,5,6,7,8,9\}$ be a set of elements, and let $$C$$ be the collection of subsets:

C = \{ \{1,2,3\}, \{2,3,4\}, \{3,4,5\}, \{1,4,5\}, \{2,6,7\}, \{1,7,8\}, \{3,8,9\}, \{2,5,9\}, \{1,6,9\}, \{3,6,8\}, \{2,4,8\}, \{1,5,7\} \}

Now, suppose we are given

X = \{1,2,3,7\}

as a Hitting Set of size

$4$

and we want to know if there is a hitting set

$Y$

of size

$3$

. Let us assume that

Y \cap X = \{1,2\}

. Then we can throw away the sets that contain

$1$

$2$

from

$C$

. What is the collection that remains?

Part B

Continuing from the example in the previous question, recall that we have $Y \cap X = \{1,2\}$ . Now, we want to know if there is a hitting set $$Y$$ of size $$3$$ overall. This will be the case if and only if:

Part C

Based on your answer to the previous question, simplify the leftover family from the first question to observe that solving the remaining problem is now equivalent to:

Part D

For the example in the first question, we can extend the solution $\{1,2\}$ to a complete solution of size at most three if and only if:

Part E

If we know how to solve $$(d-1)$$ -Hitting Set in time $O(c^k \cdot \text{poly}(n))$ , then we can solve $$d$$ -Hitting Set in time: