For hypergraph Horn functions, enumerating all coatoms (equivalently minimal stopping sets) is not output-polynomial unless P=NP when hyperedge size and element frequency are both at least three, and becomes output-linear when either is at most two.
Algorithms for𝑘-meet-semidistributive lattices.Theoretical Computer Science, 658:391–398, 2017
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2026 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Coatom Enumeration in Hypergraph Horn Functions: Rank-Three Representations of Horn Model Posets
For hypergraph Horn functions, enumerating all coatoms (equivalently minimal stopping sets) is not output-polynomial unless P=NP when hyperedge size and element frequency are both at least three, and becomes output-linear when either is at most two.