\documentclass{ctwart}

% % More symbols and math environments
\usepackage{amsmath}
% \usepackage{amsthm}
\usepackage{amssymb}

\newcommand{\neigh}[1]{\ensuremath{\Gamma\left({#1}\right)}}
\newcommand{\degree}[1]{\ensuremath{\delta\left({#1}\right)}}
\newcommand{\bigO}[1]{\ensuremath{O\left({#1}\right)}}
\newcommand{\distributed}{\ensuremath{\sim}}
\newcommand{\Bin}[2]{\ensuremath{\operatorname{Bin}\left({#1},{#2}\right)}}
\newcommand{\Expect}[1]{\ensuremath{{\mathbb E}\left[{#1}\right]}}
\newcommand{\Prob}[1]{\ensuremath{{\mathbb P}\left[{#1}\right]}}
\newcommand{\Exp}[1]{\ensuremath{e^{#1}}}

\newcommand{\elli}[1]{\ensuremath{\ell_{#1}}}

\newcommand{\M}{\ensuremath{M}}
\newcommand{\Melem}[2]{\ensuremath{\M_{{#1},{#2}}}}
\newcommand{\Q}{\ensuremath{Q}}
\newcommand{\Qelem}[2]{\ensuremath{\Q_{{#1},{#2}}}}

\begin{document}
\setcounter{page}{29}
\begin{frontmatter}


\title{Bisimplicial Edges in Bipartite Graphs\thanksref{label1}}
\thanks[label1]{This work was supported by the Dutch Innovation Oriented Research Program ``Integral Product Creation and Realisation (IOP-IPCR)'' of the Dutch Ministry of Economic Affairs.}

\author{Matthijs Bomhoff\corauthref{cor1}}
\ead{m.j.bomhoff@utwente.nl}
\corauth[cor1]{Corresponding Author}
\author{Bodo Manthey}
\ead{b.manthey@utwente.nl}

\address{Faculty of Electrical Engineering, Mathematics and Computer Science \\ University of Twente, P.O.\ Box 217, 7500 AE Enschede, The Netherlands}

\begin{abstract}
	Bisimplicial edges in bipartite graphs are closely related to pivots in Gaussian elimination that avoid turning zeroes into non-zeroes. We present a new deterministic algorithm to find such edges in bipartite graphs. The expected time complexity of our new algorithm is $\bigO{n^2 \log n}$ on random bipartite graphs in which each edge is present with a fixed probability $p$, a polynomial improvement over the fastest algorithm found in the existing literature.
\end{abstract}

\begin{keyword}
bipartite graphs \sep random graphs \sep algorithms \sep Gaussian elimination
\end{keyword}

\end{frontmatter}

\section{Introduction}

When applying Gaussian elimination to a square $n \times n$ matrix $\M$ containing some elements with value zero, the choice of pivots can often determine the amount of zeroes turned into non-zeroes during the process, the so called \emph{fill-in}. Some matrices even allow Gaussian elimination without any fill-in. Avoiding fill-in has the nice property of bounding the required space for intermediate results of the Gaussian elimination to the space required for storing the input matrix $\M$. This can be important for processing very large sparse matrices. Even when fill-in cannot be completely avoided, it may still be worthwhile to avoid it for several iterations, motivating the search for pivots that avoid fill-in.

If we assume subtracting a multiple of one row of $\M$ from another turns at most one non-zero into a zero, we may restrict ourselves to considering only $\{0, 1\}$ matrices. Given such a square matrix $\M$, we can construct the bipartite graph $G[\M]$ with vertices corresponding to the rows and columns in $\M$, where vertices $i$ and $j$ are adjacent if and only
if $\Melem{i}{j}$ is nonzero. The $\{0, 1\}$ matrices that allow Gaussian elimination without fill-in correspond to the class of \emph{perfect elimination bipartite} graphs~\cite{PerfectEliminationAndChordalBipartiteGraphs}. Central to the recognition of this class of graphs is the notion of a
\emph{bisimplicial} edge that corresponds to an element of $\M$ that can be used as a pivot without causing fill-in. The fastest algorithm for finding bisimplicial edges in the existing literature has a time complexity equal to that of matrix
multiplication~\cite{RecognitionOfPerfectEliminationBipartiteGraphs,RecognizingQuasiTriangulatedGraphs}, i.e., $\bigO{n^{2.376}}$~\cite{MatrixMultiplicationViaArithmeticProgressions}. We present a new deterministic algorithm for finding a bisimplicial edge in a bipartite graph, if one exists, and show that its expected time complexity on random bipartite graphs where each edge is present with some fixed probability $p$ is $\bigO{n^2 \log n}$.

\section{Bisimplicial Edges}

We denote by $\neigh{u}$ the neighbors of a vertex $u$.

\begin{defn}
	\label{def:bisimplicial}
	An edge $uv$ of a bipartite graph $G = (U, V, E)$ is called \emph{bisimplicial},
	if the induced subgraph $G[\neigh{u} \cup \neigh{v}]$ is a complete bipartite graph.
\end{defn}

Clearly, for a given edge $uv$ we can determine in $\bigO{|E|}$ time if it is a bisimplicial edge by simply checking all edges adjacent to it. So a simple algorithm to find a bisimplicial edge in a bipartite graph $G$, if one exists, takes $\bigO{|E|^2}$ time.

Goh and Rotem~\cite{RecognitionOfPerfectEliminationBipartiteGraphs} present a faster algorithm based on the following:
A row $\Melem{a}{*}$ is said to \emph{majorize} a row $\Melem{b}{*}$ if for each $1 \le j \le n$ we have $\Melem{a}{j} \ge \Melem{b}{j}$. According to this definition, every row majorizes itself.

\begin{thm}[Goh and Rotem~\cite{RecognitionOfPerfectEliminationBipartiteGraphs}]
	\label{thm-goh-rotem}
	Let $\M$ be an $n \times n$ $\{0,1\}$ matrix representing a bipartite graph $G = (U, V, E)$. Let $\elli{i}$ be the number of rows in $\M$ that majorize row $i$ and let $s_j$ be the sum of the entries in column $j$ of $\M$. Then $\Melem{i}{j} = 1$ and $\elli{i} = s_j$ if
	and only if the edge $u_i v_j$ is a bisimplicial edge of~$G$.
\end{thm}

Let $\Q = \M \M^T$, this implies $\elli{i}$ is equal to the number of elements in the row $\Qelem{i}{*}$ that are equal to $\Qelem{i}{i}$ (including $\Qelem{i}{i}$ itself). Clearly, the time complexity of finding a bisimplicial edge in $G[\M]$ is bounded by the time complexity of the matrix multiplication. The fastest currently known algorithm for this has a time complexity of
$\bigO{n^{2.376}}$~\cite{MatrixMultiplicationViaArithmeticProgressions}.

To improve on this, our new approach first selects a set of candidate edges. If a bisimplicial edge exists, then one of our candidates is bisimplicial. Thus we can restrict ourselves to checking the candidate edges for bisimpliciality. By bounding the number of candidates we achieve an improved expected time complexity. The following observation is the basis of our candidate selection procedure.

\begin{lem}
	\label{lem:bisimplicial_min_degrees}
	If an edge $uv$ of a bipartite graph $G = (U, V, E)$ is bisimplicial, we must have $\degree{u} = \min_{u' \in \neigh{v}}\degree{u'}$ and $\degree{v} = \min_{v' \in \neigh{u}}\degree{v'}$.
\end{lem}

Translated to the matrix $\M$, this means that if $\Melem{i}{j} = 1$, it can only correspond to a bisimplicial edge if row $i$ has a minimal number of ones over all the rows that have a $1$ in column $j$ and column $j$ has a minimal number of ones over all the columns having a $1$ in row $i$. In what follows, we will call the row (column) in $\M$ with the minimal number of ones over all the rows (columns) in $\M$ the \emph{smallest} row (column). Using this observation, we construct an algorithm to pick candidate edges that may be bisimplicial:

\begin{alg}
	\label{alg:candidates}
	\begin{enumerate}
		\item Determine the row and column sums ($a_i$ and $b_j$) for each row and column of $\M$.
		\item Determine for each row $i$ the index $c_i$ of the smallest column with $\Melem{i}{c_i} = 1$ (breaking ties by favoring the lowest index); or $c_i = 0$ if row $i$ has no one.
		\item Determine for each column $j$ the index $r_j$ of the smallest row with $\Melem{r_j}{j} = 1$ (breaking ties by favoring the lowest index); or $r_j = 0$ if column $j$ has no one.
		\item Mark $\Melem{i}{j}$ as a candidate edge if $c_i = j$ and $r_j = i$.
	\end{enumerate}
\end{alg}

Clearly, all steps in the algorithm can be performed in $\bigO{n^2}$ time. Furthermore, the last step will mark at most $n$ candidate edges (and at least $1$).

\begin{thm}
	If $G = (U, V, E)$ contains a bisimplicial edge, at least one of the candidates marked by the algorithm will be bisimplicial.
\end{thm}

As each of the candidates can subsequently be checked for bisimpliciality in $\bigO{n^2}$, we obtain a $\bigO{n^3}$ algorithm that finds a single bisimplicial edge in a bipartite graph $G$, if one exists, without using matrix multiplication. By itself, this is not really interesting, as the worst case time complexity is not an improvement over previously known algorithms. However, for random bipartite graphs, our new algorithm performs significantly better.

\section{Asymptotic Expected Behavior on Random Graphs}

For a fixed value of $p \in ( 0,1 )$, we consider random bipartite graphs from the $G_{n,n,p}$ model: i.e., we have $n$ vertices in each vertex class, and each edge is present with probability $p$. Such a random graph corresponds to a stochastic $n \times n$ $\{0,1\}$ matrix $\M$ with $\Prob{\Melem{i}{j} = 1} = p$. We denote by random variable $X_i$ the $\{0,1\}$ vector that forms row $i$ of $\M$ and use $|X_i|$ to denote the sum of its elements. If we order the $X_i$ vectors according to the number of ones they contain (breaking ties by favoring lower values of $i$), we denote by $X_{(1)}$ the row with the least number of ones, by $X_{(2)}$ the row with the second-to-least number etc.

\begin{lem}
	\label{lem:pprime}
	For any $\varepsilon > 0$ and sufficiently large $n$, we have
	\begin{align*}
		\Prob{ |X_{(1)}| < (1 - \varepsilon) p n } \le \frac{1}{n}.
	\end{align*}
\end{lem}

\begin{lem}
	\label{lem:bound}
	For any $p', k$ with $0 < p' < p$ and $k \ge 1$ and sufficiently large $n$, we have
	\begin{align*}
		\Prob{ \text{Algorithm \ref{alg:candidates} selects more than $k$ candidates}} \le n (1 - p')^k + \frac{1}{n}.
	\end{align*}
\end{lem}

From this, we immediately get a bound on the expected number of candidates that our algorithm selects.

\begin{thm}
	\label{thm:bound}
	For any $p'$ with $0 < p' < p$ and sufficiently large $n$, we have
	\begin{align*}
		\Expect{ \text{number of candidates selected by Algorithm \ref{alg:candidates}} } \le 2 + 2 \log_{(1 - p')} \frac{1}{n}.
	\end{align*}
\end{thm}

\begin{cor}
	For any fixed $p$, the expected time complexity of finding a bisimplicial edge or deciding there is none using Algorithm \ref{alg:candidates} is $\bigO{n^2 \log n}$.
\end{cor}

\begin{thebibliography}{00}

\bibitem{PerfectEliminationAndChordalBipartiteGraphs}
Martin~Charles Golumbic and Clinton~F. Goss.
\newblock Perfect elimination and chordal bipartite graphs.
\newblock {\em J. Graph Theory}, 2(2):155--163, 1978.

\bibitem{RecognitionOfPerfectEliminationBipartiteGraphs}
L.~Goh and D.~Rotem.
\newblock Recognition of perfect elimination bipartite graphs.
\newblock {\em Inform. Process. Lett.}, 15(4):179--182, 1982.

\bibitem{RecognizingQuasiTriangulatedGraphs}
Jeremy~P. Spinrad.
\newblock Recognizing quasi-triangulated graphs.
\newblock {\em Discrete Appl. Math.}, 138(1-2):203--213, 2004.

\bibitem{MatrixMultiplicationViaArithmeticProgressions}
Don Coppersmith and Shmuel Winograd.
\newblock Matrix multiplication via arithmetic progressions.
\newblock {\em J. Symbolic Comput.}, 9(3):251--280, 1990.

\end{thebibliography}

\end{document}

