@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{kuznetsov2004icd,
  author = {Kuznetsov, S.O.},
  interhash = {25e972f2dc80f7362dae4fd68c4e7f47},
  intrahash = {7d4e785ce77ab0df94fd2786c2ea0a7a},
  journal = {Journal of Universal Computer Science},
  number = 8,
  pages = {927--933},
  title = {{On the intractability of computing the Duquenne-Guigues base}},
  volume = 10,
  year = 2004
}

@article{keyhere,
  abstract = {Implications of a formal context (G,M,I) have a minimal implication basis, called Duquenne-Guigues basis or stem base. It is shown that the problem of deciding whether
a set of attributes is a premise of the stem base is in coNP and determining the size of the stem base is polynomially Turingequivalent to a #P-complete problem.},
  author = {Kuznetsov, Sergei and Obiedkov, Sergei},
  interhash = {621d51fff81b1ed566607b7e18480dbc},
  intrahash = {de0a8419ab5d374012b9d05498f840b0},
  journal = {Formal Concept Analysis},
  pages = {306--308},
  title = {Counting Pseudo-intents and #P-completeness},
  url = {http://dx.doi.org/10.1007/11671404_21},
  year = 2006
}

@article{1393768,
  abstract = {Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.},
  address = {Amsterdam, The Netherlands, The Netherlands},
  author = {Kuznetsov, Sergei O. and Obiedkov, Sergei},
  doi = {http://dx.doi.org/10.1016/j.dam.2007.04.014},
  interhash = {984c199174cd75cfb8e315494a1a1477},
  intrahash = {5cc734b8c96126d43e9b6c1fc91933d9},
  issn = {0166-218X},
  journal = {Discrete Appl. Math.},
  number = 11,
  pages = {1994--2003},
  publisher = {Elsevier Science Publishers B. V.},
  title = {Some decision and counting problems of the Duquenne-Guigues basis of implications},
  url = {http://portal.acm.org/citation.cfm?id=1393768},
  volume = 156,
  year = 2008
}

@article{46243,
  address = {Amsterdam, The Netherlands, The Netherlands},
  author = {Johnson, David S. and Papadimitriou, Christos H.},
  doi = {http://dx.doi.org/10.1016/0020-0190(88)90065-8},
  interhash = {9c96c160fa3a6124d40e1e8a1b9e1f7f},
  intrahash = {3766db2fcdce6f15149ddbd4829ac380},
  issn = {0020-0190},
  journal = {Inf. Process. Lett.},
  number = 3,
  pages = {119--123},
  publisher = {Elsevier North-Holland, Inc.},
  title = {On generating all maximal independent sets},
  url = {http://portal.acm.org/citation.cfm?id=46241.46243},
  volume = 27,
  year = 1988
}

@misc{Brandes2006,
  abstract = {Several algorithms have been proposed to compute partitions of networks
	into communities that score high on a graph clustering index called
	modularity. While publications on these algorithms typically contain
	experimental evaluations to emphasize the plausibility of results,
	none of these algorithms has been shown to actually compute optimal
	partitions. We here settle the unknown complexity status of modularity
	maximization by showing that the corresponding decision version is
	NP-complete in the strong sense. As a consequence, any efficient,
	i.e. polynomial-time, algorithm is only heuristic and yields suboptimal
	partitions on many instances.},
  author = {Brandes, U. and Delling, D. and Gaertler, M. and Goerke, R. and Hoefer, M. and Nikoloski, Z. and Wagner, D.},
  interhash = {3e2bf460cff3138de1e855a7cf5d659d},
  intrahash = {b5185cbb85b90294fa15dd2e8ea53f5e},
  note = {cite arxiv:physics/0608255 Comment: 10 pages, 1 figure},
  title = {Maximizing Modularity is hard},
  url = {http://arxiv.org/abs/physics/0608255},
  year = 2006
}