Hydras: directed hypergraphs and Horn formulas

DOI10.1007/978-3-642-34611-8_25MaRDI QIDQ5200511zbMATH OpenOpenAlexFDO

Authors Despina Stasi, Gy. Turán, R. H. Sloan

Publication date 6 November 2012

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07753

zbMATH Keywords

hydra numbercomplete binary trees

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

Abstract: 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,vightarroww$ 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)inE$, 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.

Recommendations

• Hydras: directed hypergraphs and Horn formulas
• On the hydra number of disconnected graphs
• Hydras: complexity on general graphs and a subclass of trees
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• Directed hypergraphs and applications

Cited in

(5)

• On the hydra number of disconnected graphs
• Directed hypergraphs and Horn minimization
• Hydras: complexity on general graphs and a subclass of trees
• Hydras: directed hypergraphs and Horn formulas
• Strongly connected multivariate digraphs

This page was built for publication: Hydras: directed hypergraphs and Horn formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5200511)