CS614. Advanced Algorithms. L18 Quiz.

CS614. Advanced Algorithms.

L18 Quiz

Back to the course page

Problem 1. 3-Hitting Set

Obtain an algorithm for 3-Hitting Set running in time \(2.4656^k n^{\mathcal{O}(1)}\) using iterative compression.

Problem 2. d-Hitting Set

Generalize the algorithm from the previous problem to obtain an algorithm for \(d\)-Hitting Set running in time \(((d-1)+0.4656)^k n^{\mathcal{O}(1)}\).