TY - JOUR

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

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

N1 - Funding Information:
This research was supported by the National Science Foundation (Grant IIS-0118635). The authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.

PY - 2006/11/1

Y1 - 2006/11/1

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

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

KW - Dualization

KW - Empty boxes

KW - Frequent sets

KW - Generation algorithms

KW - Hypergraph transversals

KW - Monotone properties

UR - http://www.scopus.com/inward/record.url?scp=33747864496&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2006.04.012

DO - 10.1016/j.dam.2006.04.012

M3 - Article

AN - SCOPUS:33747864496

SN - 0166-218X

VL - 154

SP - 2350

EP - 2372

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 16

ER -