Algorithms for recognizing bipartite‐Helly and bipartite‐conformal hypergraphs

A hypergraph is Helly if every family of hyperedges of it, formed by pairwise intersecting hyperedges, has a common vertex. We consider the concepts of bipartite‐conformal and (colored) bipartite‐Helly hypergraphs. In the same way as conformal hypergraphs and Helly hypergraphs are dual concepts, bipartite‐conformal and bipartite‐Helly hypergraphs are also dual. They are useful for characterizing biclique matrices and biclique graphs, that is, the incident biclique‐vertex incidence matrix and the intersection graphs of the maximal bicliques of a graph, respectively. These concepts play a similar role for the bicliques of a graph, as do clique matrices and clique graphs, for the cliques of the graph. We describe polynomial time algorithms for recognizing bipartite‐conformal and bipartite‐Helly hypergraphs as well as biclique matrices.