2
$\begingroup$

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$.

What is the best algorithm for enumerating all the inclusion-minimal covers of $S$ contained in a set $P$ and what is its running time?

Additional information : The algorithm must work in the general case. $|S|$ and $n$ can be anything. I need to enumerate the exact set of all the inclusion-minimal covers of $S$ contained in $P$. Obviously, it is possible to find the first one in polynomial time by just removing elements of $P$. The second one could be found easily by using the same method starting with the different $P\setminus \{P_{i}\}$ with $P_{i}$ an element of the first cover.

I don't really hope for a polynomial delay algorithm but I would be really happy with an incremental polynomial delay, if such a thing exists.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ There could be exponentially many such covers, is that a problem? $\endgroup$ – Yuval Filmus Dec 18 '14 at 16:41
  • $\begingroup$ In practice ? Yes. But unfortunately I need them all anyway. $\endgroup$ – Authary Dec 18 '14 at 18:01
  • $\begingroup$ 1. What are the parameter sizes in your setting? In other words, what's the size of $S$ and a typical range of sizes for each $P_i$? What's a typical value for $n$? About how many inclusion-minimal subsets do you expect there to exist, typically? These parameter settings will inform the choice of an algorithm and approach to your problem, so I suggest you edit your question to include that in the question. 2. Asking for a "best" algorithm is not well-defined, since you haven't described what metric you will use to evaluate the algorithm. Can you be more specific? $\endgroup$ – D.W.♦ Dec 18 '14 at 23:41
1
$\begingroup$

The problem is equivalent to translating a monotone conjunctive normal form Boolean formula to a monotone disjunctive normal form Boolean formula (also called "monotone dualization" in the literature).

Let us for example take $P = \{\{x,z\}, \{x,a\}, \{y,z \}, \{y,c\}\}$. We can translate $P$ to the following boolean formula: $ \psi = (x \vee z) \wedge (x \vee a) \wedge (y \vee z) \wedge (y \vee c)$ and ask for a valuation of the variables that makes the formula valid, but has as few as possible variables set to true as possible.

If we translate $\psi$ to disjunctive normal form, we obtain: $$\psi' = (x \wedge y) \vee (x \wedge z \wedge c) \wedge (z \wedge a \wedge c)$$ It is now easy to list all ''minimal'' solutions to $\psi \equiv \psi'$.

The paper "Computational aspects of monotone dualization: A brief survey" by Thomas Eitera, Kazuhisa Makinob, and Georg Gottlob contains a nice survey on existing literature to the topic, including algorithms and complexity results.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, so if I understand the paper correctly (my boolean logic is a bit rusty) the disjunctive normal form (and thus my minimal covers) can be computed in quasi-polynomial time. The enumeration part of it is a little bit fuzzy but that's probably me. Thank you. $\endgroup$ – Authary Dec 19 '14 at 15:51
0
$\begingroup$

You should not expect an asymptotically efficient solution to your problem, for two reasons:

  1. As Yuval mentions, there can be exponentially many covers. Therefore, merely printing out the answer can take exponential time in the worst case.

  2. Your problem is NP-hard. Finding the smallest such cover is the NP-hard set cover problem, and your problem is at least as hard as that.

Consequently, you should not expect an asymptotically efficient algorithm that is general (works correctly for all inputs).

So, you have several options: accept exponential-time algorithms; try to find some special structure in your problem instance, and look for an algorithm that exploits that structure; seek an approximation algorithm; look for a heuristic that might not give an optimal answer. The next step will depend on your problem domain, and is up to you. See, e.g., NP-complete decision problems - how close can we come to a solution?.

Note that there is a natural way to express your problem as an instance of SAT, so you could express it as SAT instance (a boolean formula $\varphi$) and then use a SAT solver to find all satisfying assignments to that formula. See, e.g., Set cover problem and the existence of such cover and Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers and Maximum minimal set coverage.

| cite | improve this answer | |
$\endgroup$

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.