# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 1 Introduction
It has been proved to be NP-hard in general and hard to approximate even for bipartite graphs [25; 26], but polynomial time solvable in convex bipartite and biconvex graphs [5] (A bipartite graph \(G=(V_{1},V_{2},E)\) is called convex on \(V_{2}\) if there exists an ordering of the vertices of \(V_{2}\) such that for any \(v\in V_{1}\), \(N_{G}(v)\) consists of vertices that are consecutive in \(V_{2}\). The graph \(G\) is biconvex if it is convex on both \(V_{1}\) and \(V_{2}\)). The _maximum edge weight biclique problem_, an edge-weighted generalization of MEB, has also been considered in the literature [11; 27]. It should be noted that the NP-hardness of the MB problem in some of the previous publications [21; 25] has been claimed based on a more general result by [PERSON] [28], as discussed next. A graph property \(\Pi\) is said to be _hereditary on induced subgraphs_ if for a graph \(G\) with property \(\Pi\), the deletion of any subset of vertices does not produce a graph violating \(\Pi\). A property \(\Pi\) is said to be _nontrivial_ if it is true for a single-vertex graph and is not satisfied by every graph. Also a property is said to be _interesting_ if there are arbitrarily large graphs satisfying \(\Pi\). The _maximum_\(\Pi\) problem is to find the largest order induced subgraph that does not violate property \(\Pi\). [PERSON] [28] proved that the maximum \(\Pi\) problem for nontrivial, interesting graph properties that are hereditary on induced subgraphs is NP-hard. If an independent set is accepted as a feasible solution for the MB problem, then clearly the property \"a graph whose set of vertices is a biclique\" is nontrivial, interesting and hereditary on induced subgraphs, which proves that this version of the MB problem (that accepts independent set solutions) is NP-hard. However, requiring bicliques to have two nonempty parts (as in this paper and in [21]) violates the heredity property, since removing the central vertex of a star graph gives an independent set, which is infeasible under this requirement. Thus, the result of Yannakakis is not applicable for this, more practically reasonable version of the MB problem. Nonetheless, the reduction from the independent set problem used in [21] does prove that the non-hereditary version of the MB problem is indeed NP-hard. On a practical note, the lack of heredity implies that the general-purpose combinatorial branch-and bound framework known as Russian Doll Search (RDS) [29; 30] is not directly applicable to the problems considered in this paper. The focus of this paper is on developing effective scale reduction techniques for the MB and MEB problems that can be used in combination with an exact algorithm in order to solve this problem to optimality on large, sparse networks. Simple scale reduction techniques have been successfully applied to other important combinatorial optimization problems, including the maximum clique and minimum vertex coloring problems [31; 32], the maximum independent set problem [33], and the minimum vertex cover problem [34] among others. The ideas behind these methods are similar to some of those used to develop parameterized algorithms for hard optimization problems [35]. In parameterized approaches, one considers a parameter \(k\) (e.g., the target size of a solution) along with the usual input size \(n\)[36]. A parameterized problem is called fixed-parameter tractable if there exists an algorithm (called an fpt-algorithm) solving this problem in \(f(k)\cdot n^{O(1)}\) time, where \(f\) is a computable function depending only on \(k\) (typically exponentially). The first result on parameterized complexity of a problem dealing with finding bicliques has only been established recently, after numerous previous attempts. More specifically, [PERSON] [37] has proved that the problem of deciding whether a given graph \(G\) contains a complete bipartite subgraph \(K_{k,k}\) is W[1]-hard, meaning that an fpt-algorithm is unlikely to exist. In another recent paper, [PERSON] et al.