## 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