Hypergraph dualization

Suppose a selection must include something from each of two groups: {a,b} and {b,c}. Choosing {b} meets both requirements; choosing {a,c} does too. Each is minimal: remove any chosen item and a requirement fails. These are all the minimal choices in this example, even though they have different sizes. A hitting set meets every required group. Hypergraph dualization asks whether a fixed procedure without random choices can efficiently check that a proposed list contains exactly all the minimal hitting sets for any finite list of groups.[1]

When requirements each allow several items, how can we know that every irredundant way of satisfying them has been listed? A hypergraph $H$ consists of a finite vertex set and explicitly listed subsets called hyperedges. A hitting set, also called a transversal, intersects every hyperedge. It is inclusion-minimal when none of its proper subsets is still a hitting set. For $H=\{\{a,b\},\{b,c\}\}$, these sets are $\{b\}$ and $\{a,c\}$. The set $\{a,b\}$ hits both hyperedges but is not minimal, since removing a leaves the hitting set {b}. Given another explicit family $G$ on the same vertices, the decision target is $$G=\operatorname{Tr}(H),$$ where $\operatorname{Tr}(H)$ denotes all inclusion-minimal transversals. The required algorithm runs in deterministic polynomial time in the combined encoding length of $H$ and $G$. Checking that each proposed set is a minimal hitting set does not check completeness: $G=\{\{b\}\}$ passes those individual checks but omits $\{a,c\}$.[1]

The unknown is a test whose work is always bounded by one fixed power of the two lists’ combined length. A square or cube would qualify, but no particular power is prescribed. This is the polynomial-time target.[1]

The general fixed-power time bound remains unknown. Known general algorithms have quasipolynomial guarantees, whose exponent can grow with input size rather than stay fixed. The cited January 2026 revision obtains polynomial guarantees for restricted families, including bounded VC-dimension, which limits how freely their groups can realize subset patterns. Those restrictions do not cover arbitrary explicitly listed hypergraphs.[1]

One successful choice does not reveal every alternative. In the example, listing only {b} hides the equally minimal option {a,c}; that option matters if b is unavailable. A completeness test helps distinguish a finished menu of irredundant choices from a list that merely contains some valid answers.[1]

There can be exponentially many minimal hitting sets compared with the requirement list, so writing every answer cannot always take time polynomial in that list alone. A polynomial completeness test is instead connected to incremental enumeration: producing further minimal sets in time polynomial in the original input and the number already produced. The target therefore addresses a real obstacle in describing all alternatives without charging an algorithm for output it has not yet generated.[1]