Is it known whether hypergraph minimal covers are P-enumerable? Is it known or unknown whether hypergraph minimal covers are P-enumerable? I would be most happy with lower bounds. I'd also like to hear about conditional results, which assume some conjecture is true. Of course, I'd also want to know about closely related problems (such as independent sets and cliques).

Motivation. I have a problem to which enumeration of minimal covers in hypergraphs can be reduced, and an algorithm that is exponential in the worst case and works OKish in practice.  I wonder whether doing much better is possible; or are there good reasons I haven't found something better? (The problem arises in the context of static analysis of programs.)

Background. A hypergraph is a pair $(V, E)$ of vertices $V$ and edges $E:(V\to2)\to2$, the latter being subsets of vertices. A cover $U$ is a subset of vertices that intersects all edges: $\forall e:E\;\exists u:U\;(u:e)$. A cover is minimal when no strict subset of it is a cover.

Judging from the results of googling &lsquo;P-enumerable&rsquo;, the term is not too popular. I'm referring to the definition given by Valiant [1]:


  A relation $R$ is P-enumerable iff there is a polynomial $p$ such
  that for all $x$ the set $\{y:R(x,y)\}$ can be enumerated in time
  $|\{y:R(x,y)\}|\times p(|x|)$.


Related. According to Johnson et al. [2], in 1988 it was unknown whether minimal covers of hypergraphs are P-enumerable.  The equivalent problem for graphs, when $\forall e:E\;(|e|=2)$, is known to be P-enumerable, since 1977 [3]. But, [2] explains why the method of [3] cannot be generalized to hypergraphs. The related decision problem of finding one minimal cover is clearly in P. The related counting problem is #P-complete for graphs [1]. 

I also found some sources [4, 5] which I find hard to read: one uses many concepts I'm not familiar with, and the other is long.  For example, Theorem 1.1 in [4] seems to imply that there exists a quasi-polynomial algorithm; but, [5] has an extra condition (1.2, submodularity) that wouldn't hold for the covers problem. Moreover, [5] mentions an obstruction (Proposition 5.2) similar to the one alluded to by [2] (&lsquo;exercise for the reader&rsquo;) for the methods of [3]. So, it seems to me that it was still unknown in 2002 whether hypergraph minimal covers are P-enumerable, although I'm not completely sure I interpret [4 and 5] correctly.



[1] Valiant, The Complexity of Enumeration and Reliability Problems, 1979.

[2] Johnson, Yannakakis, Papadimitriou, On Generating All Maximal Independent Sets, 1988.

[3] Tsukiyama, Ide, Ariyoshi, Shirakawa, A New Algorithm for Generating All Maximal Independent Sets, 1977

[4] Boros, Elbassioni, Gurvich, Khachiyan, Makino, Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities, 2002

[5] Elbassioni, Incremental Algorithms for Enumerating Extremal Solutions of Monotone Systems of Submodular Inequalities and Their Applications, 2002
You are looking for an output-polynomial algorithm for enumerating minimal transversals of hypergraphs (or hitting sets for set systems). According to Golovach et al. (ICALP 2013),


  The question whether the minimal transversals
  of a hypergraph can be enumerated in output polynomial time is a fundamental and
  challenging question; it has been open for several decades and has triggered extensive
  research. [...]
  
  Whether or not all minimal transversals of a
  hypergraph can be listed in output polynomial time has been identied as a fundamental
  challenge in a long list of seminal papers, e.g., [10, 11, 12, 13, 14, 19, 30], and it remains
  unresolved despite continuous attempts since the 1980's.