  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 minimal number of hyperarcs of the form
$u,v\rightarrow w$ required in a directed hypergraph $H=(V,F)$, such that for
every pair $(u, v)$, the set of vertices reachable in $H$ from $\{u, v\}$ is
the entire vertex set $V$ if $(u, v) \in E$, and it is $\{u, v\}$ otherwise.
Here reachability is defined by forward chaining, a standard marking algorithm.
  Various bounds are given for the hydra number. We show that the hydra number
of a graph can be upper bounded by the number of edges plus the path cover
number of the line graph of a spanning subgraph, which is a sharp bound in
several cases. On the other hand, we construct single-headed graphs for which
that bound is off by a constant factor. Furthermore, we characterize trees with
low hydra number, and give a lower bound for the hydra number of trees based on
the number of vertices that are leaves in the tree obtained from $T$ by
deleting its leaves. This bound is sharp for some families of trees. We give
bounds for the hydra number of complete binary trees and also discuss a related
minimization problem.
