Hydra Number of Graphs

In this talk we define and discuss the hydra number, a graph parameter 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) is an edge in E, and it is only the vertices themselves otherwise. Here reachability is defined by the standard forward chaining or marking algorithm.

We give various bounds for the hydra number and discuss its connection to the path cover number of the line graph L(G), and to the total interval number of a graph. We will define the relevant notions of Horn formulas, directed hypergraphs, and graph theoretical notions that we use.

This talk is based on joint work with Gyorgy Turan and Robert H. Sloan.

Event Topic

Discrete Applied Math Seminar