Algorithms and Complexity – DP Hitting set

Given:

that all contain elements from means subset of ,
Subset is a hitting set if it contains an element from all
Size

Solve:

Branching-HS(A, (B1, …,Bm), k)
if k = o: 		//base case
	if Bi = original Bi for some i:
		return “no HS”
	else return empty set
else:
	choose some Bi
	for u ∈ Bi
		Brahching-HS(A-u, {Bi-u | i=1, …, m}, k-1)
	if all recursive
		return “no HS”, then return “no HS”
	else:
            choose some u where u ∈ Bi worked,
            add u to the result from that, call and return.

Running Time:

• {Bi-u | i=1 to m} takes
• 
• there are amout of in , so this runs in times
• Subset has elements, have elements, so

Rerolling above gives overall running time .