Click here to flash read.
Given a hypergraph $\mathcal{H}$, the dual hypergraph of $\mathcal{H}$ is the
hypergraph of all minimal transversals of $\mathcal{H}$. The dual hypergraph is
always Sperner, that is, no hyperedge contains another. A special case of
Sperner hypergraphs are the conformal Sperner hypergraphs, which correspond to
the families of maximal cliques of graphs. All these notions play an important
role in many fields of mathematics and computer science, including
combinatorics, algebra, database theory, etc. In this paper we study
conformality of dual hypergraphs. While we do not settle the computational
complexity status of recognizing this property, we show that the problem is in
co-NP and can be solved in polynomial time for hypergraphs of bounded
dimension. In the special case of dimension $3$, we reduce the problem to
$2$-Satisfiability. Our approach has an implication in algorithmic graph
theory: we obtain a polynomial-time algorithm for recognizing graphs in which
all minimal transversals of maximal cliques have size at most $k$, for any
fixed $k$.
No creative common's license