7
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jul 2, 2013 at 15:14

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jul 2, 2013 at 15:12
  • $\begingroup$ 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. $\endgroup$
    – Serge Gaspers
    Jul 2, 2013 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.