Verifying the Product of Generalized Boolean Matrix Multiplication and Its Applications to Detect Small Subgraphs

Given three n by n integer matrices A, B, and P, determining whether the product AB equals P can be done in randomized O(n²) time by Freivalds’ algorithm. In this paper, we consider some generalized Boolean matrix multiplication AB= P_f, which is defined to be setting the entry p_ij of P_f for i, j∈ [ n] as the value of a given function f of the entries on the ith row of A and jth column of B. We show that, for a family of functions f, it takes deterministic O(n²) time to verify whether the generalized product P_f contains only False entries. Then, we present how to apply such a result to detect small subgraphs efficiently, including: Detect any designated colored 4-cycle in randomized O(n²) time for n-node k-edge-colored (for k= O(1 ) ) complete graphs with maximum color degree at most 2 (including 1-edge-colored general graphs), which unifies several independently discovered algorithms each corresponding to a customized Ramsey-type theorem. As a complementary result, we show that if the maximum color degree is at least 3, any combinatorial algorithm that solves this problem requires Ω (n^{3 - ε}) time for any constant ε> 0, assuming the hardness of triangle detecting.Detect any designated 4-node induced subgraph in randomized O(n²) time for n-node triangle-free graphs. In contrast, the known best algorithm for this problem on general graphs needs triangle time.