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 $Psetminus {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
