@article{219403,
  abstract = {The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied computer science. Hypergraph saturation (i.e., given a hypergraph $\cal H$, decide if every subset of vertices is contained in or contains some edge of $\cal H$) is shown to be co-NP-complete. A certain subproblem of hypergraph saturation, the saturation of simple hypergraphs (i.e., Sperner families), is shown to be under polynomial transformation equivalent to transversal hypergraph recognition; i.e., given two hypergraphs ${\cal H}_{1}, {\cal H}_{2}$, decide if the sets in ${\cal H}_{2}$ are all the minimal transversals of ${\cal H}_{1}$. The complexity of the search problem related to the recognition of the transversal hypergraph, the computation of the transversal hypergraph, is an open problem. This task needs time exponential in the input size; it is unknown whether an output-polynomial algorithm exists. For several important subcases, for instance if an upper or lower bound is imposed on the edge size or for acyclic hypergraphs, output-polynomial algorithms are presented. Computing or recognizing the minimal transversals of a hypergraph is a frequent problem in practice, which is pointed out by identifying important applications in database theory, Boolean switching theory, logic, and artificial intelligence (AI), particularly in model-based diagnosis.},
  address = {Philadelphia, PA, USA},
  author = {Eiter, Thomas and Gottlob, Georg},
  doi = {http://dx.doi.org/10.1137/S0097539793250299},
  interhash = {76c12a1c1a65d5f3bd9e1682db7ab11c},
  intrahash = {cd05f6dae9a4feed33fa7df223ab89ec},
  issn = {0097-5397},
  journal = {SIAM J. Comput.},
  number = 6,
  pages = {1278--1304},
  publisher = {Society for Industrial and Applied Mathematics},
  title = {Identifying the Minimal Transversals of a Hypergraph and Related Problems},
  url = {http://portal.acm.org/citation.cfm?id=219403},
  volume = 24,
  year = 1995
}

@article{papa2007hpa,
  author = {Papa, D.A. and Markov, I.L.},
  interhash = {68b9025134cf6e3a4fb2fe8c3194e2b4},
  intrahash = {1c9083525938ab35d2a35df850612cb1},
  journal = {Handbook of Approximation Algorithms and Metaheuristics},
  publisher = {Chapman \& Hall/CRC},
  title = {{Hypergraph partitioning and clustering}},
  year = 2007
}

@article{karypis1997mhp,
  author = {Karypis, G. and Aggarwal, R. and Kumar, V. and Shekhar, S.},
  booktitle = {Proceedings of the 34th annual conference on Design automation},
  interhash = {77aa28416ddb1c22834224cf0b09c74e},
  intrahash = {bdfb6003e7a8786b0a5649bb250c0a77},
  organization = {ACM New York, NY, USA},
  pages = {526--529},
  title = {{Multilevel hypergraph partitioning: Application in VLSI domain}},
  year = 1997
}

@inproceedings{Karypis98multilevelk-way,
  abstract = {In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K  -  1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR. 1 Introduction  Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design [10], efficient storage of large databases on disks [14], and data mining [13]. The problem is to partition the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized. A commonly used obje...},
  author = {Karypis, George and Kumar, Vipin},
  booktitle = {In Proceedings of the Design and Automation Conference},
  interhash = {413d89f472133bf5ff0671cccc818f55},
  intrahash = {d63a73732f65ce10595e210cedda3bd1},
  pages = {343--348},
  title = {Multilevel k-way Hypergraph Partitioning},
  year = 1998
}