DIMACS TR: 2004-03

Recognizing $k$-complete bipartite bihypergraphs



Authors: I. E. Zverovich and I. I. Zverovich

ABSTRACT

Let $H^0$ and $H^1$ be hypergraphs with the same vertex-set $V$. The ordered pair $H = (H^0, H^1)$ is called a {\em bihypergraph}. A set $S \subseteq V(H)$ is {\em stable} in $H^i$ if $S$ contains no hyperedges of $H^i$, $i = 0, 1$. A bihypergraph $H = (H^0, H^1)$ is called {\em bipartite} if there exists an ordered partition $S^0 \cup S^1 = V(H)$ such that the set $S^i$ is stable in $H^i$ for $i = 0, 1$.

In Section 1, we give a survey numerous applications of bipartite bihypergraphs.

In Section 2, we show that recognizing bipartite bihypergraphs within classes of $k$-complete bihypergraphs can be done in polynomial time. A bihypergraph $H = (H^0, H^1)$ is called {\em $k$-complete}, $k \ge 0$, if each $k$-subset of $V(H)$ contains a hyperedge of $H$, i.e., a hyperedge of $H^0$ or $H^1$. Moreover, we can construct all bipartitions of a $k$-complete bihypergraph, if any, in polynomial time.

A bihypergraph $H = (H^0, H^1)$ is called {\em strongly bipartite} if each maximal stable set of $H^0$ is a transversal of $H^1$. We show that recognizing strongly bipartite bihypergraphs $(H^0, H^1)$ is a co-NP-complete problem even in the case where $H^0$ is a graph and $H^1$ has exactly one hyperedge. Some examples of strongly bipartite bihypergraphs are given.

AMS Subject Classification: 05C65, 03E20, 05C75, 05B35.

Keywords: Bipartite bihypergraphs, bipartite hypergraphs, $k$-complete bihypergraphs, satisfiability problem.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-03.ps.gz

DIMACS Home Page