[Solved]: How to enumerate minimal covers of a set

Problem Detail: 

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.

Asked By : Authary

Answered By : DCTLib

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35475

 Ask a Question

 Download Related Notes/Documents