# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 1 Introduction  
Network-based analysis offers a powerful approach for modeling elements and their interactions in complex systems. In particular, network models make it possible to take advantage of graph algorithms for mining massive datasets. For example, in protein-protein interaction networks, proteins are represented as vertices and interaction between pairs of proteins are represented by edges [1; 2; 3]. In genome research, the relationship between genes and diseases can be modeled using graphs in which vertices represent genes and diseases and edges represent a meaningful or hypothetical relationship between a gene and a disease [4; 5]. The World Wide Web can be represented using a graph in which vertices are documents and edges are the hyperlinks between documents [6; 7]. Network models provide a valuable description of such systems and allow us to apply advanced techniques for identification of some of the global structural properties of the system and prediction of their future behavior. Biclique community detection has been studied extensively in recent years due to its various applications in automata and language theory, biology and genome research, clustering and data mining, artificial intelligence and graph compression [4; 8; 9; 10; 11; 12; 13; 14]. Several different variants of the biclique community detection problems have been introduced and studied in the literature in this context. Next, we provide formal definitions and briefly review related literature. Let \(G=(V,E)\) be a simple, undirected graph, where \(V=\{1,\ldots,n\}\) is the vertex set, and \(E\subseteq\{\{i,j\}:i,j\in V,i\
eq j\}\) is the edge set. Let \(N_{G}(i)=\{j\in V:\{i,j\}\in E\}\) denote the _neighborhood_ of a vertex \(i\) in \(G\), and let \(N_{G}[i]=N_{G}(i)\cup\{i\}\) be the _closed neighborhood_ of \(i\). For \(C\subseteq V\), let \(G[C]=(C,E(C))\), where \(E(C)=\{\{i,j\}\in E:i,j\in C,i\
eq j\}\), denote the subgraph induced by \(C\) in \(G\). The set \(C\) iscalled an _independent set_ if \(G[C]\) is edgeless, and \(C\) is a _clique_ if \(G[C]\) is a complete graph (i.e., has all possible edges). Let \(\alpha(G)\) be the independence number of \(G\), which is the cardinality of a maximum independent set in \(G\). A graph is called bipartite if its set of vertices can be partitioned into two non-overlapping independent sets, referred to as parts. Definition 1: A set \(C\subseteq V\) is called a _biclique_ if \(G[C]\) is a complete bipartite graph, which is a bipartite graph with all possible edges between the parts. A biclique is called _maximal_ if it is not a subset of a larger biclique and, _maximum_ if there is no larger biclique in \(G\). Note that according to Definition 1, an independent set is a biclique with one of the parts being an empty set. However, from a practical perspective, one is not interested in independent set solutions when searching for large bicliques in a graph. This observation is reflected in the definitions of the corresponding optimization problems given next. Definition 2: Given a simple, undirected graph \(G=(V,E)\), the maximum biclique (MB) problem is to find a maximum cardinality biclique in \(G\) that is not an independent set. Definition 3: Given a simple, undirected graph \(G=(V,E)\), the maximum edge biclique (MEB) problem is to find a biclique with the maximum number of edges in \(G\). Different algorithms have been proposed for biclique community detection ranging from enumeration of all maximal (non-induced) bicliques of a graph [13; 15; 16; 17; 18], finding a maximum edge cardinality biclique [5] and maximum balanced bicliques [19] to exact, exponential-time methods [20], approximation algorithms [21] and mining quasi-bicliques [22; 23]. In particular, the MB problem has been proved to be NP-hard in general graphs, but polynomial-time solvable in bipartite graphs [21]. The maximum edge biclique (MEB) problem has been successfully used for biclustering and formal concept analysis [4; 5; 24].