Complexity limits for finding key sets in special hypergraphs
Lower Bounds for Minimal-Transversal Enumeration of Bounded-Dimension Hypergraphs and the maximum Minimal Hitting Set Problem
Computational Complexity
Summary
Some mathematical problems involve finding small sets that intersect certain groups, which mathematicians call minimal hitting sets or transversals in hypergraphs. This paper shows that even for hypergraphs with limited group sizes, it is very hard to decide or list these special sets quickly. The authors build on earlier research to prove that there are fundamental time limits for solving these problems efficiently, assuming widely believed computational assumptions. Their results suggest that no fast, general algorithm exists for these tasks in many cases.
What this means in practice
- •For algorithm designers: Rule out the possibility of fast algorithms for enumerating minimal transversals in bounded-dimension hypergraphs under established complexity assumptions.
- •For database system engineers: Understand inherent computational limits when trying to efficiently list minimal keys or covers, particularly in hypergraph-inspired data models of low dimension.
A theory result. No direct application yet.
Authors
Arnaud Mary
Abstract
We present lower bounds for the maximum minimal hitting set problem and for the problem of enumeration of minimal transversals in bounded-dimension hypergraphs. Our starting point is the recent reduction of Kobayashi, Kurita, and Wasa (2026), developed to establish ETH-based hardness of hypergraph dualization. Adapting their construction, we show that, under ETH, deciding whether a hypergraph $\mathcal{G}$ with $n$ vertices and $m$ hyperedges has a minimal transversal of size at least $k$ cannot be done in time $n^{f(k)}m^{o(k)}$, for an arbitrary computable $f$. We transfer this bound to the following decision problem: given a dimension-at-most-$r$ hypergraph and a family of $s$ of its minimal transversals, decide whether another exists. Under ETH, this problem admits no uniform algorithm with running time $n^{f(r)}(s+1)^{o(r)}$. Under SETH, for every fixed $t \geq 2$, it admits no algorithm with running time $\poly(|\mathcal{G}|)(s+1)^c$ for dimension at most $2t$ and any $c<t$. As corollaries, the same exponent obstructions hold for the total time of any output-polynomial enumeration algorithm, with $s$ replaced by the total number of minimal transversals. In particular, polynomial delay is excluded under SETH already for dimension at most four.