Finding four-node subgraphs in triangle time

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle). The best known algorithms for triangle finding in an n-node graph take O (n^ω) time, where ^ω< 2.373 is the matrix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in O (n^ω) time with high probability. The algorithm can be derandomized in some cases: we show how todetect a diamond (or its complement) in deterministic O (n^ω) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C₄ detection ran in O (n^3.3) time, and for diamond detection in O (n³) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O (m^{2ω/ ( ω+1)}) ≤ O (m^1.14) time. We give a randomized O (m^{2ω/ ( ω+1)}) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C₄, K₄ and their complements. In the case of diamond detection, we also design a deterministic O (m^{2ω/ ( ω+1)}) time algorithm. For C₄ or its complement, we give randomized O (m^{(4ω-1)/ (2ω+1)})≥O (^m1.48)tjme findjng algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in 0 (m^1.5) time.