TY - GEN

T1 - Finding four-node subgraphs in triangle time

AU - Williams, Virginia Vassilevska

AU - Wang, Joshua R.

AU - Williams, Ryan

AU - Yu, Huacheng

N1 - Publisher Copyright:
Copyright © 2015 by the Society for Industrial and Applied Mathmatics.

PY - 2015

Y1 - 2015

N2 - 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 C4 detection ran in O (n3.3) time, and for diamond detection in O (n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O (m2ω/ ( ω+1)) ≤ O (m1.14) time. We give a randomized O (m2ω/ ( ω+1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic O (m2ω/ ( ω+1)) time algorithm. For C4 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 (m1.5) time.

AB - 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 C4 detection ran in O (n3.3) time, and for diamond detection in O (n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O (m2ω/ ( ω+1)) ≤ O (m1.14) time. We give a randomized O (m2ω/ ( ω+1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic O (m2ω/ ( ω+1)) time algorithm. For C4 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 (m1.5) time.

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

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

U2 - 10.1137/1.9781611973730.111

DO - 10.1137/1.9781611973730.111

M3 - Conference contribution

AN - SCOPUS:84938228047

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1671

EP - 1680

BT - Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

PB - Association for Computing Machinery

T2 - 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015

Y2 - 4 January 2015 through 6 January 2015

ER -