Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
The Complexity of Acyclic Subhypergraph Problems
verfasst von : David Duris, Yann Strozecki
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate the computational complexity of two decision problems concerning the existence of certain acyclic subhypergraphs of a given hypergraph, namely the
Spanning Acyclic Subhypergraph
problem and the
Maximum Acyclic Subhypergraph
problem. The former is about the existence of an acyclic subhypergraph such that each vertex of the input hypergraph is contained in at least one hyperedge of the subhypergraph. The latter is about the existence of an acyclic subhypergraph with
k
hyperedges where
k
is part of the input. For each of these problems, we consider different notions of acyclicity of hypergraphs: Berge-acyclicity,
γ
-acyclicity,
β
-acyclicity and
α
-acyclicity. We are also concerned with the size of the hyperedges of the input hypergraph. Depending on these two parameters (notion of acyclicity and size of the hyperedges), we try to determine which instances of the two problems are in
P
∩
RNC
and which are
NP
-complete.