Bipartite bihypergraphs: A survey and new results Original Research Article

Let image and image be hypergraphs with the same vertex-set image. The ordered pair image is called a bihypergraph. A set image is stable in image if S contains no hyperedges of image, image. A bihypergraph image is called bipartite if there exists an ordered partition image such that the set image is stable in image for image. In Section 1, we survey numerous applications of bipartite bihypergraphs. In Section 3, we show that recognizing bipartite bihypergraphs within classes of k-complete bihypergraphs can be done in polynomial time. A bihypergraph image is called k-complete, image, if each k-subset of image contains a hyperedge of H, i.e., a hyperedge of image or image. Moreover, we can construct all bipartitions of a k-complete bihypergraph, if any, in polynomial time. A bihypergraph image is called strongly bipartite if each maximal stable set of image is a transversal of image. We show that recognizing strongly bipartite bihypergraphs image is a co-NP-complete problem even in the case where image is a graph and image has exactly one hyperedge. Some examples of strongly bipartite bihypergraphs are given.