Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices

We study the problem of finding a given [Formula: see text] matrix as a submatrix of a given Boolean matrix. Three variants are considered: search for a matching submatrix of any area, of minimum area, or of maximum area. The problem relates to 2D pattern matching, and to fields such as data mining, where the search for submatrices plays an important role. Besides these connections, the problem itself is very natural and its investigation helps to demonstrate differences between search tasks in one-dimensional and multidimensional topologies. Our results reveal that the problem variants are of different complexities. First, we show that given an [Formula: see text] Boolean matrix, the any variant can be solved in [Formula: see text] time for any given [Formula: see text] matrix, but requires various strategies for different [Formula: see text] matrices. This contrasts with the complexity of the task over matrices with entries from the set [Formula: see text], where the problem is Triangle Finding-hard and hence no algorithm with similar running time is known for it. Then, we show that the minimization variant in the case of Boolean matrices can also be solved in [Formula: see text] time. Finally, in contrast, we prove Triangle Finding-hardness for the maximization variant and show that there is a rectangular matrix multiplication-based algorithm solving it in [Formula: see text] time.