Hydras: Directed Hypergraphs and Horn Formulas

Robert H. Sloan, Despina Stasi, Gyorgy Turan

We introduce a new graph parameter, the hydra number, arising from the minimization problem for Horn formulas in propositional logic. The hydra number of a graph $G=(V,E)$ is the m…