My research problem involves solving a special instance of the 3-Hitting Set problem, and I was wondering whether my result is actually significant (i.e. if it is better than the best known result for 3-Hitting Set).

I'm specifically interested in the case where the parameter is the optimal hitting set size.

I know the paper by Niedermeier and Rossmanith that presents an algorithm of run-time $O(2.27^k + n)$, but that paper is pretty old.


1 Answer 1


According to the Parameterized Complexity Wiki, the currently best known FPT algorithm for 3-Hitting-Set has a complexity of $2.076^k \cdot n^{O(1)}$, the algorithm is from the PhD thesis of Magnus Wahlström.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.