On Finding Acyclic Subhypergraphs

摘要

In this paper, we investigate the problem of finding acyclic subhypergraphs in a hypergraph. First we show that the problem of determining whether or not a hypergraph has a spanning connected acyclic subhypergraph is NP-complete. Also we show that, for a given K > 0, the problem of determining whether or not a hypergraph has an acyclic subhypergraph containing at least K hyperedges is NP-complete. Next, we introduce a maximal acyclic subhypergraph, which is an acyclic subhypergraph that is cyclic if we add any hyperedge of the original hypergraph to it. Then, we design the linear-time algorithm mas to find it, which is based on the acyclicity test algorithm designed by Tarjan and Yannakakis (1984).