# 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 ‘P-enumerable’, 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] (‘exercise for the reader’) 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

• note hypergraph traversals also go by the name "hitting sets" which may be helpful on literature search. my understanding is that this problem is also equivalent to dualization of monotone boolean formulas for which there are some papers. this problem seems to have been approached independently from many angles, all increasingly converging.
– vzn
Jul 2 '13 at 15:14