Acyclic Hypergraph Projections

Hypergraphs can be partitioned into two classes: tree (acyclic) hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. HypergraphHis an Xring if the hyperedges ofHcan be circularly ordered so that for every vertex, all hyperedges containing the vertex are consecutive; in addition, the vertices of no hyperedge may be a subset of the vertices of another hyperedge, and no vertex may appear in exactly one hyperedge. LetH₁andH₂be two hypergraphs. A tree projection ofH₁with respect toH₂is an acyclic hypergraphH₃such that the vertices of each hyperedge inH₁appear among the vertices of some hyperedge ofH₃and the vertices of each hyperedge inH₃appear among the vertices of some hyperedge ofH₂. A polynomial time algorithm is presented for deciding, given XringH₁and arbitrary hypergraphH₂, whether there exists a tree projection ofH₂with respect toH₁. It is shown that hypergraphHis an Xring iff a modified adjacency graph ofHis a circular-arc graph. A linear time Xring recognition algorithm, for GYO reduced hypergraphs as inputs, is presented.