Bipartite bihypergraphs: A survey and new results

Let H0H0 and H1H1 be hypergraphs with the same vertex-set VV. The ordered pair H=(H0,H1)H=(H0,H1) is called a bihypergraph  . A set S⊆VS⊆V is stable   in HiHi if S   contains no hyperedges of HiHi, i=0,1i=0,1. A bihypergraph H=(H0,H1)H=(H0,H1) is called bipartite   if there exists an ordered partition S0∪S1=V(H)S0∪S1=V(H) such that the set SiSi is stable in HiHi for i=0,1i=0,1.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 H=(H0,H1)H=(H0,H1) is called k-complete  , k⩾0k⩾0, if each k  -subset of V(H)V(H) contains a hyperedge of H  , i.e., a hyperedge of H0H0 or H1H1. Moreover, we can construct all bipartitions of a k-complete bihypergraph, if any, in polynomial time.A bihypergraph H=(H0,H1)H=(H0,H1) is called strongly bipartite   if each maximal stable set of H0H0 is a transversal of H1H1. We show that recognizing strongly bipartite bihypergraphs (H0,H1)(H0,H1) is a co-NP-complete problem even in the case where H0H0 is a graph and H1H1 has exactly one hyperedge. Some examples of strongly bipartite bihypergraphs are given.