1
$\begingroup$

I am given a set $U = \{1, \cdots, n\}$ and a set of subsets $C_1, \cdots, C_k$ of $U$; here the sets are all the same size.

The minimum set-cover problem of course is to find the minimum number of the $C_i$ such that their union is $U$.

I'm looking at the "opposite" problem: I want to find the minimum-size subset $K$ of $U$ such that every $k \in K$ has that $k \in C_i$ for some $i$.

Edit: I researched more and this is the Minimum Satisfiability problem. One can formulate the problem as a CNF SAT formula: the formula is the conjunction of $(c_{i,1} \vee \cdots \vee c_{i,m} )$ where the $c_{i,j} \in C_i$ for all $i$.

The MinSat problem is NP-complete in the general case, but here all of the literals are positive. Are there faster algorithms for this case?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I don't think you are expressing your problem correctly. The $K$ set can be a single element, and you are saying you just need the element of $k$ to exist in some $C_i$. I think you mean that every $C_i$ has some $k$ in $K$. If I understand your problem correctly, this is equivalent to HITTING SET, which has quite a lot of practical algorithms for... including approximation algorithms or quite fast FPT exact algorithms. $\endgroup$ – JimN Dec 14 '17 at 3:52
  • $\begingroup$ @JimN Looks like it, thank you! The name sure escaped me... $\endgroup$ – Ryan Dec 14 '17 at 3: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.