Hydras: directed hypergraphs and Horn formulas

DOI10.1007/978-3-642-34611-8_25zbMATH Open1341.05181arXiv1504.07753OpenAlexW2103113565MaRDI QIDQ5200511FDOQ5200511

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)

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.

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

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

zbMATH Keywords

hydra numbercomplete binary trees

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

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)