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 Õ ( n ω ) time with high probability. The algorithm can be derandomized in some cases: we show how to detect a diamond (or its complement) in deterministic Õ ( n ω ) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C 4 detection ran in O ( n 3. 3 ) time, and for diamond detection in O ( n 3 ) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O ( m 2 ω / ( ω +1) ) ≤ O ( m 1. 41 ) time. We give a randomized Õ ( m 2 ω /( ω +1) ) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C 4, K 4 and their complements. In the case of diamond detection, we also design a deterministic Õ ( m 2 ω /( ω +1) ) time algorithm. For C 4 or its complement, we give randomized Õ ( m (4 ω– 1)/(2 ω +1) ) ≤ O ( m 1. 48 ) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O ( m 1. 5 ) time.

Authors

• Virginia Vassilevska Williams
• Joshua R. Wang
• R. Ryan Williams
• Huacheng Yu

Keywords

No keywords are indexed for this paper.