Hydras: Directed hypergraphs and Horn formulas

详细信息    查看全文

• 作者：Robert H. Sloan^a ; ^{sloan@uic.edu} ; Despina Stasi^b ; ^{stasdes@iit.edu} ; Gyö ; rgy Tur&aacute ; n^a ; ^c ; ^gyt@uic.edu
• 关键词：Directed hypergraphs ; Horn formulas ; Horn minimization ; Hydra ; Hydra number
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PB
• 页码：417-428
• 全文大小：513 K
• 卷排序：658

文摘

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)G=(V,E) is the minimal number of hyperarcs of the form u,v→wu,v→w required in a directed hypergraph H=(V,F)H=(V,F), such that for every pair (u,v)(u,v), the set of vertices reachable in H   from {u,v}{u,v} is the entire vertex set V   if (u,v)∈E(u,v)∈E, and it is {u,v}{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.