TY - GEN

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

AU - Hon, Wing Kai

AU - Tsai, Meng Tsung

AU - Wang, Hung Lung

N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - Given three n by n integer matrices A, B, and P, determining whether the product AB equals P can be done in randomized O(n2) time by Freivalds’ algorithm. In this paper, we consider some generalized Boolean matrix multiplication AB= Pf, which is defined to be setting the entry pij of Pf 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(n2) time to verify whether the generalized product Pf 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(n2) 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 Ω (n3 - ε) time for any constant ε> 0, assuming the hardness of triangle detecting.Detect any designated 4-node induced subgraph in randomized O(n2) time for n-node triangle-free graphs. In contrast, the known best algorithm for this problem on general graphs needs triangle time.

AB - Given three n by n integer matrices A, B, and P, determining whether the product AB equals P can be done in randomized O(n2) time by Freivalds’ algorithm. In this paper, we consider some generalized Boolean matrix multiplication AB= Pf, which is defined to be setting the entry pij of Pf 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(n2) time to verify whether the generalized product Pf 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(n2) 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 Ω (n3 - ε) time for any constant ε> 0, assuming the hardness of triangle detecting.Detect any designated 4-node induced subgraph in randomized O(n2) time for n-node triangle-free graphs. In contrast, the known best algorithm for this problem on general graphs needs triangle time.

KW - Colored 4-cycles

KW - Ramsey-type Theorems

KW - Small Induced Subgraphs

UR - http://www.scopus.com/inward/record.url?scp=85172720581&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172720581&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_33

DO - 10.1007/978-3-031-38906-1_33

M3 - Conference contribution

AN - SCOPUS:85172720581

SN - 9783031389054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 507

EP - 520

BT - Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

Y2 - 31 July 2023 through 2 August 2023

ER -