% Template article for preprint document class `elsart'
% SP 2001/01/05

% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/

\documentclass{ctwart}

% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{algorithm}
\usepackage{algorithmic}


\begin{document}

\begin{frontmatter}

% Title, authors and addresses

% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}

\title{On Enumerating All Maximal Bicliques of Bipartite Graphs}

% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}

\author{Enver Kayaaslan}

\address{enver@cs.bilkent.edu.tr}

\begin{keyword}
bipartite graph \sep biclique \sep maximal biclique
% keywords here, in the form: keyword \sep keyword
\end{keyword}

\end{frontmatter}

% main text

\input{macros}

\section{Introduction}

Enumerating all maximal bicliques of a bipartite graph has two main contributions to literature:
First, we can use all maximal bicliques to find minimum number of bicliques 
covering a subset of edges or vertices for given bipartite graph. This problem is referred
as Minimum Biclique Cover (MBC) Problem and dates back to the study of Orlin~\cite{orlin77}. 
A recent work by Cornaz and Fonlupt deals with MBC problem for general graphs and useful
references can be found therein~\cite{cornaz06}. Secondly, Agarwal et al. show that extracting all maximal bicliques
can be used for compression~\cite{agarwal94}. 

In this work, we focus on finding all maximal bicliques in general bipartite graphs.
In this point of view,  this work can be considered as the specified version of study by Alexe et. al.~\cite{alexe04}
where the authors try to solve maximal biclique generation problem (MBGP) which is the problem of
enumerating all maximal bicliques in simple graphs. 
Here, we present some theoretical results including a sufficient and necessary 
condition for a maximal biclique in a bipartite graph as well as a practical 
algorithm for generating all maximal bicliques of a given bipartite graph.

\section{Theoritical Results}

A bipartite graph $\B = (X,Y,\E)$ is a graph,
where the vertices can be divided into two disjoint sets $X$ and $Y$ 
such that every edge $e_{ij} \in \E$ connectes a vertex in $X$ to one in $Y$.
A biclique $(S_x, S_y)$ of a bipartite graph $\B$ is a complete bipartite subgraph
of $\B$ induced by vertex set $S_x \cup S_y$.
% pair of sets $S_x \subseteq X$
% and $S_y \subseteq Y$ such that for all the pairs $(x_i\in S_x, y_j\in S_y)$ there is an edge $e_{ij}$ of $\B$, i.e.,
% $S_x \times S_y \subseteq \E$.
The neighbor set $N_y(x_i)$ of a vertex $x_i \in X$ is defined as the set of vertices $y_j$ such that
there is an edge $e_{ij} \in \E$, i.e., $N_y(x_i) = \{y_j \in Y: (x_i, y_j) \in \E \}$. Similarly,
$N_x(y_j) = \{x_i \in X: (x_i, y_j) \in \E \}$. The empty biclique $(\emptyset, \emptyset)$ is simply denoted
as $\emptyset$.

\begin{defin}[Maximal Biclique]
Given a bipartite graph $\B = (X, Y, \E)$, a biclique $(S_x, S_y)$
is a maximal biclique of $\B$ if no proper superset of $(S_x, S_y)$ is a biclique, i.e.,
there exists no biclique $(S'_x, S'_y) \neq (S_x, S_y)$ such that $S_x \subseteq S'_x$ and $S_y \subseteq S'_y$.
\end{defin}

\noindent For the sake of simplicity, pair of sets $(S_x, \{y_j\})$ and $(\{x_i\}, S_y)$ 
are denoted as $(S_x, y_j)$ and $(x_i, S_y)$, respectively.

% As to note that we take $(\emptyset, \emptyset)$ as a maximal biclique for the sake of completeness of 
% theoritical results presented in this section.

\begin{defin}[Consensus Set]
Given a bipartite graph $\B = (X, Y, \E)$, for a subset $S_x \subseteq X$ ($S_y \subseteq Y$)
the consensus set $P_y(S_x)$ ($P_x(S_y)$) is defined as the intersection of neighbor set of each 
vertex $x_i\in S_x$ ($y_j \in S_y$),i.e,
\begin{equation}
P_y(S_x) = \bigcap_{x_i \in S_x}N_y(x_i)
\end{equation}
By definition, $P_x(\emptyset) = P_y(\emptyset) = \emptyset$.
\end{defin}

\noindent Note that this is equaivalent to $P_y(S_x) = \{ y_j \in Y: (S_x, y_j) \mbox{ is biclique} \}$ 
and similarly $P_x(S_y) = \{ x_i \in X: (x_i, S_y)$ is biclique $\}$.

\begin{theom}
\label{thm-maximal}
%Given a bipartite graph $\B = (X, Y, \E)$; 
$(S_x,S_y) \neq \emptyset$ is a maximal biclique $\Leftrightarrow$ $S_y=P_y(S_x)$ and  $S_x=P_x(S_y)$.
\end{theom}
\noindent {\it Proof:} Let $(S_x, S_y) \neq \emptyset$ be a biclique and so $S_x \subseteq P_x(S_y)$ and
$S_y \subseteq P_y(S_x)$.
By defintion of maximality, $S_x, S_y$ is a maximal biclique if and only if there exists
no $y_j \in Y / S_y$ such that $(S_x, y_j)$ is a biclique and similarly there exists
no $x_i \in X / S_x$ such that $(x_i, S_y)$ is biclique. This is equivalent to that
there exists no $y_j \in Y / S_y$ such that $y_j \in P_y(S_x)$ and 
there exists no $x_i \in X / S_x$ such that $x_i \in P_x(S_y)$. 
Equivalently $S_y = P_y(S_x)$ and $S_x = P_x(S_y)$. $\qed$.

\begin{lemma}
For any $S_y \subseteq Y$, $S_y \subseteq P_y(P_x(S_y))$. Similarly, for any 
$S_x \subseteq X$, $S_x \subseteq P_x(P_y(S_x))$.
\end{lemma}
\noindent {\it Proof:} 
Consider a vertex $y_j \in S_y$. Since $(P_x(S_y), S_y)$ is biclique, $(P_x(S_y), y_j)$ is also biclique.
Thus, $y_j \in P_y(P_x(S_y))$ which concludes that $S_y \subseteq P_y(P_x(S_y))$. Similar proof
can be conducted for $S_x \subseteq P_x(P_y(S_x))$. $\qed$

\begin{theom}
%Given a bipartite graph $\B = (X, Y, \E)$; 
For any $S_y \subseteq Y$ such that $P_x(S_y) \neq \emptyset$, $(P_x(S_y),P_y(P_x(S_y)))$ is a maximal biclique.
Similarly, for any $S_x \subseteq X$ such that $P_y(S_x) \neq \emptyset$, $(P_x(P_y(S_x)), P_y(S_x))$ is a maximal biclique.
\end{theom}
\noindent {\it Proof:} 
Let $S_y$ be a subset of $Y$ such that $P_x(S_y)$ and let $\tilde{S}_y$ denote $P_y(P_x(S_y))$.
Consider a vertex $x_i \in P_x(\tilde{S}_y)$. Then, $(x_i, \tilde{S}_y)$ is biclique.
Since \mbox{$S_y \subseteq \tilde{S}_y$}, $(x_i, S_y)$ is also biclique. Thus 
$x_i \in P_x(S_y)$ which concludes that $P_x(S_y) \supseteq P_x(\tilde{S}_y)$.
Since $P_x(S_y) \subseteq P_x(\tilde{S}_y)$, $P_x(S_y) = P_x(\tilde{S}_y)$.
Since both $P_y(P_x(S_y)) = \tilde{S}_y$ and $P_x(S_y) = P_x(\tilde{S}_y)$,
$(P_x(S_y),\tilde{S}_y)$ is a maximal biclique. Similar proof can be conducted for 
maximality of biclique $(P_x(P_y(S_x)), P_y(S_x))$. $\qed$


\section{Algorithm}


Theoretical results suggest that it is sufficient
to enumerate on the consensus sets, in order to find all maximal bicliques.
Therefore we find all consensus $X$ subsets of bipartite graph $\B = (X, Y, \E)$.
The algorithm requires only the bipartite graph $\B$.
Then we initialize a set of consensus $X$ subsets $\Ss$ with neighbor sets
of every vertex $y_j \in Y$. Concurrently, we hold a priority queue $Q$
which works in a FIFO manner, and it is also initialized by the same set of consensus $X$ subsets.
We iteratively grow the set $\Ss$ as follows. At each iteration, we select
an unselected consensus set $S_x$ from queue $Q$.
For each vertex $y_j \in Y$ which is not in the consensus set of $S_x$,
we construct a set $S_{new}$ by the intersection of $S_x$ and neighbor set $N(y_j)$.
$S_{new}$ corresponds to the consensus set of $P_y(S_x) \cup \{y_j\}$.
We do not consider a vertex in $P_y(S_x)$, because for such a vertex,
the intersection will result again $S_x$ which wouldn't be a new consensus set in $\Ss$.
If $S_{new}$ is a new consensus set in $\Ss$, we insert $S_{new}$ to $\Ss$.
We also enqueue it to priority queue $Q$ in order to expand new consensus sets based on $S_{new}$.
The iterations terminate whenever there remains no consensus set to generate new ones.
By the termination, we compute the maximal bicliques by taking pairs $(S_x, P_y(S_x))$ for each
subset $S_x \in \Ss$.


\begin{algorithm}
\caption{FIND-ALL-MAXIMAL Algorithm}
\label{alg-mxs}
\begin{algorithmic}
\REQUIRE {Bipartite graph $\B = (X, Y, \E)$ }
\STATE $\Ss \leftarrow \{N_x(y_j): y_j \in Y \}$
\STATE $Q \leftarrow \Ss$
\WHILE{$Q \neq \emptyset$}
	\STATE $S_x \leftarrow$ DEQUEUE($Q$) 
	\FOR{{\bf each} $y_j \in Y / P_y(S_x)$}
		\STATE $S_{new} \leftarrow S_x \cap N(y_j)$
		\IF{$S_{new} \not \in \Ss$}
			\STATE $\Ss \leftarrow \Ss \cup \{ S_{new} \}$
			\STATE ENQUEUE($Q, S_{new}$)
		\ENDIF
	\ENDFOR
\ENDWHILE
\STATE $\C_{max} = \{(S_x, P_y(S_x)): S_x \in \Ss \}$
\STATE {\bf return} $\C_{max}$
\end{algorithmic}
\end{algorithm} 

For each maximal biclique we check for at most $|Y|$ new bicliques. 
With a naive implementation, the checking procedure
can be done in polynomial time on number of total maximal bicliques and number of vertices.
Thus, the whole procedure runs in polynomial-time in total of input and output size with a naive implementation 
which conludes that FIND-ALL-MAXIMAL is a {\it total polynomial} algorithm~\cite{johnson88} 
for the problem of enumerating all maximal bicliques of a bipartite graph.

\section{Conclusion}

In this work, we study the problem of enumerating all maximal bicliques in a given
bipartite graphs. We devised a necessary and sufficient condition for a maximal biclique
in bipartite graph which happened to be useful for enumeration. 
As well as, we constructed an algorithm for generating all maximal bicliques of a bipartite graph
which runs in {\it total polynomial} time.


\bibliographystyle{siam}
\begin{thebibliography}{1}

\bibitem{agarwal94}
{\sc P.~K. Agarwal, N.~Alon, B.~Aranov, and S.~Suri}, {\em Can visibility
  graphs be represented compactly?}, Discrete and Computational Geometry, 12
  (1994), pp.~347 -- 365.

\bibitem{alexe04}
{\sc G.~Alexe, S.~Alexe, Y.~Crama, S.~Foldes, P.~L. Hammer, and B.~Simeone},
  {\em Consensus algorithms for the generation of all maximal bicliques},
  Discrete Applied Mathematics, 145 (2004), pp.~11 -- 21.
\newblock Graph Optimization IV.

\bibitem{cornaz06}
{\sc D.~Cornaz and J.~Fonlupt}, {\em Chromatic characterization of biclique
  covers}, Discrete Mathematics, 306 (2006), pp.~495 -- 507.

\bibitem{johnson88}
{\sc D.~S. Johnson, M.~Yannakakis, and C.~H. Papadimitriou}, {\em On generating
  all maximal independent sets}, Information Processing Letters, 27 (1988),
  pp.~119 -- 123.

\bibitem{orlin77}
{\sc J.~Orlin}, {\em Contentment in graph theory: Covering graphs with
  cliques}, Proceedings of the Koninklijke Nederlandse,  (1977), pp.~406--424.

\end{thebibliography}


\end{document}

