Obtain an algorithm for 3-Hitting Set running in time 2.4656^k n^{\mathcal{O}(1)} using iterative compression.
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)}.
© 2022 • Neeldhara Misra • Credits •
Corrections? Please leave a comment here or a PR in this repository, thanks!
I’d rather be a failure at something I love than a success at something I hate.
George Burns
You live and you learn — at any rate, you live.
Douglas Adams
A problem worthy of attack proves its worth by fighting back.
Paul Erdos