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$.

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 19, 2018 at 15:52
  • $\begingroup$ 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)}$. $\endgroup$
    – Juho
    Oct 19, 2018 at 17:34
  • $\begingroup$ @juho true, I remembered incorrectly $\endgroup$ Oct 20, 2018 at 7:04
  • $\begingroup$ @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? $\endgroup$ Oct 20, 2018 at 7:09
  • $\begingroup$ I don’t have such a solution in mind. $\endgroup$ Oct 20, 2018 at 8:57


Your Answer

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

Browse other questions tagged or ask your own question.