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 -