# Specialized Algorithm for Set-Cover with $k=3$

I know that the Set-cover problem with $$n$$ elements and a universe of size $$N$$ is NP complete. Also, the problem is has parameterized complexity regarding the number of sets $$k$$ that should cover the whole universe: There are only $${n \choose k}=\mathcal{O}(n^k)$$ different combinations of $$k$$ subsets.

My specific problem is easily reducible to the set-cover problem with $$k=3$$. My approach that iterates over all $${n \choose k}=\mathcal{O}(n^3)$$ subsets does not perform well enough.

Is there any specialized algorithm for the 3-set-cover problem? Ideally, I would like some parameterized algorithm or some potent preprocessing techniques that exploit $$k=3$$.

• You might be able to go down to $O(n^2)$ using a meet-in-the-middle approach, but it seems hard to go beyond that. – Yuval Filmus Oct 19 '18 at 15:52
• An algorithm running in time $n^k$ is not FPT for the parameter $k$, it is only an XP-algorithm. You need a running time of the form $f(k) n^{O(1)}$. – Juho Oct 19 '18 at 17:34
• @juho true, I remembered incorrectly – Samuel Pilz Oct 20 '18 at 7:04
• @YuvalFilmus I would be very interested in a $\mathcal{O}(n^2)$ algorithm. I will try some meet-in-the-middle approach. Do you have a $\mathcal{O}(n^2)$ solution? – Samuel Pilz Oct 20 '18 at 7:09
• I don’t have such a solution in mind. – Yuval Filmus Oct 20 '18 at 8:57