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 and acknowledge you have read our privacy policy.

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