Hydras: Directed Hypergraphs and Horn Formulas

We consider a graph parameter, the

hydra number

, arising from an optimization 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

 → 

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

) ∈ 

E

, and it is {

u

,

v

} otherwise. Here reachability is defined by the standard forward chaining or 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 its line graph, and this is a sharp bound for some graphs. On the other hand, we construct graphs with hydra number equal to the number of edges, but having arbitrarily large path cover number. Furthermore we characterize trees with low hydra number, give bounds for the hydra number of complete binary trees, discuss a related optimization problem and formulate several open problems.