Hydras: Directed hypergraphs and Horn formulas

Autor: Robert H. Sloan, Despina Stasi, György Turán
Rok vydání: 2017
Předmět:
Zdroj: Theoretical Computer Science. 658:417-428
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2016.05.036
Popis: 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 → 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 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.
Databáze: OpenAIRE
Externí odkaz: