<p>You are looking for an <em>output-polynomial</em> algorithm for enumerating <em>minimal transversals</em> of hypergraphs (or <em>hitting sets</em> for set systems). According to <a href="http://www.ii.uib.no/~pinar/Enumeration-line.pdf">Golovach et al. (ICALP 2013)</a>,</p>

<blockquote>
  <p>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. [...]</p>
  
  <p>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.</p>
</blockquote>

CC BY-SA 3.0
2013-07-02T15:12:43.833Z
it would be helpful to sketch out or cite how output polynomial time and P-enumerable are equivalent. the former seems to be a more recent formulation than the latter.
vzn
CC BY-SA 3.0
2013-07-02T15:50:12.670Z
An algorithm is output-polynomial if its running time is upper bounded by a function that is polynomial in the size of the input plus the size of the output. P-enumerable applies to relations / computational problems, whereas output-polynomial applies to algorithms. Also, it seems to me that the term output-polynomial is used more often in recent years.
Serge Gaspers
CC BY-SA 3.0
2013-07-01T13:21:26.993Z
2013-07-01T13:21:26.993Z
Serge Gaspers
<p>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).</p>

<p><strong>Motivation.</strong> 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.)</p>

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

<p>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]:</p>

<blockquote>
  <p>A relation $R$ is <em>P-enumerable</em> 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|)$.</p>
</blockquote>

<p><strong>Related.</strong> 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]. </p>

<p>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 <em>long</em>.  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.</p>

<hr>

<p>[1] Valiant, <em>The Complexity of Enumeration and Reliability Problems</em>, 1979.</p>

<p>[2] Johnson, Yannakakis, Papadimitriou, <em>On Generating All Maximal Independent Sets</em>, 1988.</p>

<p>[3] Tsukiyama, Ide, Ariyoshi, Shirakawa, <em>A New Algorithm for Generating All Maximal Independent Sets</em>, 1977</p>

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

<p>[5] Elbassioni, <em>Incremental Algorithms for Enumerating Extremal Solutions of Monotone Systems of Submodular Inequalities and Their Applications</em>, 2002</p>

CC BY-SA 3.0
2013-07-02T15:14:26.120Z
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
<cc.complexity-theory><reference-request><lower-bounds>
Is it known whether hypergraph minimal covers are P-enumerable?
Radu GRIGore
# Is it known whether hypergraph minimal covers are P-enumerable?

(Asked by: username_0 on 2013-06-29)

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

**Tags:** cc.complexity-theory, reference-request, lower-bounds

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-07-01. Score: 6 | Accepted answer

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)](http://www.ii.uib.no/~pinar/Enumeration-line.pdf),

> 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.

> **Comments:**
> **username_1**: it would be helpful to sketch out or cite how output polynomial time and P-enumerable are equivalent. the former seems to be a more recent formulation than the latter.  
> **username_2**: An algorithm is output-polynomial if its running time is upper bounded by a function that is polynomial in the size of the input plus the size of the output. P-enumerable applies to relations / computational problems, whereas output-polynomial applies to algorithms. Also, it seems to me that the term output-polynomial is used more often in recent years.  

---

