An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Leonid Khachiyan, Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Research output: Contribution to journalArticlepeer-review

43 Scopus citations

Abstract

Given a finite set V, and a hypergraph H ⊆ 2V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time. More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.

Original languageBritish English
Pages (from-to)2350-2372
Number of pages23
JournalDiscrete Applied Mathematics
Volume154
Issue number16
DOIs
StatePublished - 1 Nov 2006

Keywords

  • Dualization
  • Empty boxes
  • Frequent sets
  • Generation algorithms
  • Hypergraph transversals
  • Monotone properties

Fingerprint

Dive into the research topics of 'An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation'. Together they form a unique fingerprint.

Cite this